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 Z_{p}^{*}
Blake now computes k = h^{b}, 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 Z_{p}^{*}; 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 x^{q} (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 2^{256}, 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 g^{q} (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 = g^{a} (mod p) and sends x to Blake
Blake picks a secret random number b in the range 1 < b < q−1
Blake computes y = g^{b} (mod p) and sends y to Alex
Alex makes sure 1 < y < p and y^{q} (mod p) = 1
Alex computes k = y^{a} (mod p) = g^{ba} (mod p)
Blake makes sure 1 < x < p and x^{q} (mod p) = 1
Blake computes k = x^{b} (mod p) = g^{ab} (mod p)
Alex and Blake derive the secure channel session key from k
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 Z_{p}^{*}
Public parameters (same as Diffie-Hellman)
p = Z_{p}^{*} modulus — 2048-bit prime
Subgroup order q — 256-bit prime
g = Generator for an order-q subgroup of Z_{p}^{*}
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 = g^{b} (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 = g^{a} (mod p)
(This is Alex's half of a Diffie-Hellman key exchange)
Alex computes k = (g^{b})^{a} (mod p) from Blake's public key
Alex computes masked message c = km (mod p)
Alex sends ciphertext = (ephemeral key, masked message) = (g^{a}, c) to Blake
Note that ciphertext size = 2 × plaintext size
Blake decrypting a ciphertext (g^{a}, c)
Blake computes k = (g^{a})^{b} (mod p) — modular exponentiation
Blake computes k^{−1} (mod p) — modular inversion
Blake computes m = k^{−1}c (mod p) — modular product