Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 8. Public-Key Cryptosystems Based on the DLP Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### More Number Theory

• The multiplicative group modulo p: Zp*
• Where p is a prime number
• Set of group elements = {1, 2, . . . , p−1}
• Group operation is multiplication (mod p)
• The group is closed under the group operation
• The product (mod p) of any two elements in the set is also in the set
• The group operation is associative
• a(bc) ≡ (ab)c (mod p) for any elements a, b, and c
• There is an identity element such that:
• For every element x, applying the group operation to x and the identity element yields x
• The Zp* identity element is 1
• For every element x there is an inverse y, such that:
• Applying the group operation to x and its inverse yields the identity element
• The Zp* inverse of x is x−1 (mod p)
• That is, x ⋅ x−1 ≡ 1 (mod p)
• In addition, Zp* is an Abelian group; the group operation is commutative; ab ≡ ba (mod p) for any elements a and b

• A generator of the multiplicative group modulo p:
• A number g such that the set {g0 (mod p), g1 (mod p), g2 (mod p), . . . , gp−2 (mod p)} is the same set as Zp*
• After that, it starts repeating: gp−1 (mod p) = g0 (mod p) = 1, gp (mod p) = g1 (mod p) = g, etc.
• Because gp−1 (mod p) = 1 — that is, because the size of the set generated by g is p−1 — we say that the order of g is p−1

• Example:
• p = 23 is prime
• Z23* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}
• g = 5 is a generator for Z23*
• The powers of 5 (mod 23), in order, are {1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14}
• 522 (mod 23) = 1

• An order-q subgroup of the multiplicative group modulo p:
• A q-element subset of {1, 2, . . . , p−1} such that the subset is itself a group with the group operation being multiplication modulo p

• A generator of an order-q subgroup of the multiplicative group modulo p:
• A number g such that the set {g0 (mod p), g1 (mod p), g2 (mod p), . . . , gq−1 (mod p)} is an order-q subgroup of Zp*
• After that, it starts repeating: gq (mod p) = g0 (mod p) = 1, gq+1 (mod p) = g1 (mod p) = g, etc.
• Because gq (mod p) = 1 — that is, because the size of the set generated by g is q — we say that the order of g is q

• Fact: The orders of the subgroups of Zp* are equal to the factors of p−1
• There is always an order-(p−1) subgroup, namely the full group
• There is always an order-1 subgroup, namely {1}, and its generator is 1
• If p is prime, then there is always an order-2 subgroup, and its generator is p−1
• If p is prime, then there is always an order-((p−1)/2) subgroup
• There may also be subgroups of other orders

• Example:
• p = 23
• The factors of p−1 = 22 are 22, 11, 2, and 1
• g = 5 is a generator for an order-22 subgroup of Z23*, namely the full group
• g = 2 is a generator for an order-11 subgroup of Z23*
• The powers of 2 (mod 23), in order, are {1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12}
• 211 (mod 23) = 1
• g = 22 is a generator for an order-2 subgroup of Z23*
• The powers of 22 (mod 23), in order, are {1, 22}
• 222 (mod 23) = 1
• g = 1 is a generator for an order-1 subgroup of Z23*, namely {1}

### Diffie-Hellman Key Exchange

• The Problem
• Alex and Blake need a unique, secret session key for a secure channel
• Each new secure channel needs a new session key, so Alex and Blake can't use a fixed value chosen ahead of time
• Alex and Blake are the only ones in the whole world allowed to know the session key — Harry the Hacker can't know the session key
• But without a session key, Alex and Blake can't communicate securely, and Harry can eavesdrop
• Alex and Blake need a secure channel so they can establish a secret session key so they can establish a secure channel . . .

• W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, November 1976.

• Diffie-Hellman Key Exchange, Version 1
• Pick a random large prime number, p
• Bare minimum: 2048 bits
• If at all possible: 4096 bits (say Ferguson & Schneier)
• Let g be a generator for the full group Zp*
• Alex, Blake, and Harry all know p and g
• Alex picks a secret random number a in the range 1 < a < p−1
• Alex computes x = ga (mod p) and sends x to Blake
• Blake picks a secret random number b in the range 1 < b < p−1
• Blake computes y = gb (mod p) and sends y to Alex
• Alex computes k = ya (mod p) = gba (mod p)
• Blake computes k = xb (mod p) = gab (mod p)
• Harry cannot compute gab (mod p) knowing only ga (mod p) and gb (mod p)
• The "Diffie-Hellman Problem"
• A variant of the "Discrete Logarithm Problem"
• No efficient discrete logarithm algorithm is known for large p
• So Alex and Blake can exchange x and y over a public (non-confidential) channel
• Alex and Blake derive the secure channel session key from k

• Key derivation
• Master key = Session key = k (from Diffie-Hellman key exchange)
• Alex-to-Blake encryption key = Hash(k||0)
• Alex-to-Blake authentication key = Hash(k||1)
• Blake-to-Alex encryption key = Hash(k||2)
• Blake-to-Alex authentication key = Hash(k||3)

• Problem 1: Trivial subgroup attack
• Harry is in the middle between Alex and Blake
• When Alex sends x, Harry intercepts it and sends 1 to Blake
• When Blake sends y, Harry intercepts it and sends 1 to Alex
• Alex and Blake now compute k = 1, and of course Harry knows k
• Solution: Blake must make sure x ≠ 1, Alex must make sure y ≠ 1

• Problem 2: Small subgroup attack
• Harry is in the middle between Alex and Blake
• When Alex sends x, Harry intercepts it and sends h to Blake, where h is a generator for a small subgroup of Zp*
• Blake now computes k = hb, which is a member of a small set
• Harry can now do an exhaustive search to find Blake's k
• Harry does the same to Alex
• Solution: Make sure g is a generator for a large subgroup of Zp*; Blake and Alex must make sure x and y are members of this subgroup

• To make sure g is a generator for a large subgroup:
• Use a safe prime p = 2q + 1, where q is a large prime
• Then the only subgroup orders are the factors of p−1 = 2q, namely p−1, q, 2, and 1
• We want to use the order-q subgroup
• To find a safe prime:
• Pick a large random number q
• Test whether q is prime
• Test whether p = 2q + 1 is prime
• Repeat until both p and q are prime
• To find a generator for the order-q subgroup:
• Pick a random number α in the range 2 .. p−2
• Set g = α2 (mod p)
• If g = 1, then g is a generator for the order-1 subgroup {1}, so try again with another random α
• If g = p−1, then g is a generator for the order-2 subgroup {1, p−1}, so try again with another random α
• Otherwise, g is a generator for the order-q subgroup {α0, α2, α4, . . .} (the odd powers of α are missing), so go with it

• To make sure x (and y) are members of the subgroup generated by g:
• Make sure that x ≠ 1 and xq (mod p) = 1

• Problem 3: The above choice of subgroup leads to computations that take too long
• E.g., if p is a 2048-bit number, then q is a 2047-bit number, the exponents in Alex's and Blake's calculations can be as many as 2047 bits long, and the modular exponentiations can take as many as 2047 squarings and multiplications
• Solution: Use a smaller (but still large enough) subgroup
• E.g., let q be a 256-bit prime, then the subgroup order is about 2256, too large for Harry to do an exhaustive search

• Diffie-Hellman parameter generation
• Repeat:
• Pick a random 256-bit odd number q
• Pick a random 1792-bit even number N
• Until q is prime and p = Nq + 1 is prime (p is a 2048-bit number)
• Repeat:
• Pick a random α in the range 1 .. p−1
• Set g = αN (mod p)
• Until g ≠ 1 and gq (mod p) = 1
• Publish (p, q, g) as the Diffie-Hellman parameters — modulus, subgroup order, generator for order-q subgroup

• Diffie-Hellman Key Exchange, Version 2
• Alex picks a secret random number a in the range 1 < a < q−1
• Alex computes x = ga (mod p) and sends x to Blake
• Blake picks a secret random number b in the range 1 < b < q−1
• Blake computes y = gb (mod p) and sends y to Alex
• Alex makes sure 1 < y < p and yq (mod p) = 1
• Alex computes k = ya (mod p) = gba (mod p)
• Blake makes sure 1 < x < p and xq (mod p) = 1
• Blake computes k = xb (mod p) = gab (mod p)
• Alex and Blake derive the secure channel session key from k

• Diffie-Hellman Key Exchange Example

• Problem 4: Man-in-the-middle attack
• Harry carries out a legitimate Diffie-Hellman key exchange and establishes one session key with Alex
• Harry carries out a legitimate Diffie-Hellman key exchange and establishes another session key with Blake
• Harry intercepts Alex's messages, decrypts them with the one session key, re-encrypts them with the other session key, and sends them on to Blake
• Vice versa for Blake's messages to Alex
• Solution: Authenticate the key exchange messages
• But now we need an authentication method that does not require a pre-established secret authentication key:
• Digital signature

• Diffie-Hellman key exchange and digital signatures are used in the Internet Key Exchange protocol
• Wikipedia article
• RFC 2407: The Internet IP Security Domain of Interpretation for ISAKMP, November 1998
• RFC 2408: Internet Security Association and Key Management Protocol (ISAKMP), November 1998
• RFC 2409: The Internet Key Exchange (IKE), November 1998
• RFC 5996: Internet Key Exchange Protocol Version 2 (IKEv2), September 2010

### El Gamal Encryption

• T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469-472, July 1985.

• Based on the difficulty of the Discrete Logarithm Problem in Zp*

• Public parameters (same as Diffie-Hellman)
• p = Zp* modulus — 2048-bit prime
• Subgroup order q — 256-bit prime
• g = Generator for an order-q subgroup of Zp*

• Blake's key generation
• Blake picks a random number b in the range 1 < b < q−1
• Blake's private key = b
• Blake's public key = gb (mod p)
• (This is Blake's half of a Diffie-Hellman key exchange)

• Alex encrypting a message m for Blake
• m is an encoded message, using a padding function similar to OAEP
• Alex picks a random number a in the range 1 < a < q−1
• Alex computes ephemeral key = ga (mod p)
• (This is Alex's half of a Diffie-Hellman key exchange)
• Alex computes k = (gb)a (mod p) from Blake's public key
• Alex computes masked message c = km (mod p)
• Alex sends ciphertext = (ephemeral key, masked message) = (ga, c) to Blake
• Note that ciphertext size = 2 × plaintext size

• Blake decrypting a ciphertext (ga, c)
• Blake computes k = (ga)b (mod p) — modular exponentiation
• Blake computes k−1 (mod p) — modular inversion
• Blake computes m = k−1c (mod p) — modular product

• Alternative decryption formula
• By Fermat's Little Theorem, xp−1 = 1 (mod p)
• Therefore, k−1 = ((ga)b)−1 = (ga)−b = (ga)−b (ga)p−1 = (ga)p−b−1 (mod p)
• So Blake can compute m = (ga)p−b−1c (mod p) and avoid the modular inversion

• Security of El Gamal
• Harry cannot discover k by observing gb and ga (same as Diffie-Hellman)
• Without k, Harry cannot compute m from c

### Discrete Logarithm Algorithms

• The Discrete Logarithm Problem (DLP)
• Given a cyclic (sub)group, generator g, and group element y:
• Find x such that y = gx

• If we can solve the DLP efficiently, we can break D-H key exchange and El Gamal encryption

• Let G be the subgroup and |G| be the order of the subgroup

• Brute force search
• Try all values of x until we find the right one
• For 80-bit security in Zp*: |G| ≥ 280

• Shanks's baby-step giant-step algorithm
• Precomputation step: O(|G|1/2) time, O(|G|1/2) memory to store a hash table
• Solution step: O(|G|1/2) time, assuming constant-time hash table lookups
• For 80-bit security in Zp*: |G| ≥ 2160

• Pollard's rho method
• No precomputation and negligible memory
• O(|G|1/2) time
• For 80-bit security in Zp*: |G| ≥ 2160

• Pohlig-Hellman algorithm
• Find the prime factors of |G|
• Use baby-step giant-step or Pollard's rho to solve the DLP in the subgroups of G, whose orders are the prime factors of |G|
• Combine the results using the Chinese Remainder Theorem
• For 80-bit security in Zp*:
• The subgroup orders are the factors of p−1
• Suppose G is an order-q subgroup, |G| = q
• We make sure the largest prime factor of q is ≥ 2160
• We ensure this by choosing q itself to be a prime ≥ 2160
• Then we choose a prime p such that q is a factor of p−1; that is; p = nq + 1 for some n
• Then we choose a generator g for an order-q subgroup of Zp*

• Index calculus method
• Specifically for solving the DLP in Zp*
• Subexponential running time
• For 80-bit security in Zp*: p ≥ 21024

• Bottom line, for 80-bit security in Zp*:
• p is a 1024-bit prime
• Subgroup order |G| is a 160-bit prime

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005