4003-482-01/4005-705-01 Cryptography
Chapter 8. Public-Key Cryptosystems Based on the DLP
Lecture Notes

More Number Theory

• The multiplicative group modulo p: Z_p^*
  • 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, 1, such that for any element x, x*1 (mod p) = 1*x (mod p) = x
  • For every element x there is an inverse y, such that xy (mod p) = 1
  • In addition, Z_p^* 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 {g⁰ (mod p), g¹ (mod p), g² (mod p), . . . , g^p−2 (mod p)} is the same set as Z_p^*
  • After that, it starts repeating: g^p−1 (mod p) = g⁰ (mod p) = 1, g^p (mod p) = g¹ (mod p) = g, etc.
  • Because g^p−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
  • Z₂₃^* = {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 Z₂₃^*
  • 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}
  • 5²² (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 {g⁰ (mod p), g¹ (mod p), g² (mod p), . . . , g^q−1 (mod p)} is an order-q subgroup of Z_p^*
  • After that, it starts repeating: g^q (mod p) = g⁰ (mod p) = 1, g^q+1 (mod p) = g¹ (mod p) = g, etc.
  • Because g^q (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 Z_p^* 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 Z₂₃^*, namely the full group
  • g = 2 is a generator for an order-11 subgroup of Z₂₃^*
    • The powers of 2 (mod 23), in order, are {1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12}
    • 2¹¹ (mod 23) = 1
  • g = 22 is a generator for an order-2 subgroup of Z₂₃^*
    • The powers of 22 (mod 23), in order, are {1, 22}
    • 22² (mod 23) = 1
  • g = 1 is a generator for an order-1 subgroup of Z₂₃^*, namely {1}

Diffie-Hellman Key Exchange

• The Problem
  • Alice and Bob need a unique, secret session key for a secure channel
  • Each new secure channel needs a new session key, so Alice and Bob can't use a fixed value chosen ahead of time
  • Alice and Bob 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, Alice and Bob can't communicate securely, and Harry can eavesdrop
  • Alice and Bob 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 Z_p^*
  • Alice, Bob, and Harry all know p and g
  • Alice picks a secret random number a in the range 1 < a < p−1
  • Alice computes x = g^a (mod p) and sends x to Bob
  • Bob picks a secret random number b in the range 1 < b < p−1
  • Bob computes y = g^b (mod p) and sends y to Alice
  • Alice computes k = y^a (mod p) = g^ba (mod p)
  • Bob computes k = x^b (mod p) = g^ab (mod p)
  • Harry cannot compute g^ab (mod p) knowing only g^a (mod p) and g^b (mod p)
    • The "Diffie-Hellman Problem"
    • A variant of the "Discrete Logarithm Problem"
    • No efficient discrete logarithm algorithm is known for large p
  • So Alice and Bob can exchange x and y over a public (non-confidential) channel
  • Alice and Bob derive the secure channel session key from k

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

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

• Problem 2: Small subgroup attack
  • Harry is in the middle between Alice and Bob
  • When Alice sends x, Harry intercepts it and sends h to Bob, where h is a generator for a small subgroup of Z_p^*
  • Bob now computes k = h^b, which is a member of a small set
  • Harry can now do an exhaustive search to find Bob's k
  • Harry does the same to Alice
  • Solution: Make sure g is a generator for a large subgroup of Z_p^*; Bob and Alice 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 = α² (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 {α⁰, α², α⁴, . . .} (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 Alice's and Bob'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²⁵⁶, 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
  • Alice picks a secret random number a in the range 1 < a < q−1
  • Alice computes x = g^a (mod p) and sends x to Bob
  • Bob picks a secret random number b in the range 1 < b < q−1
  • Bob computes y = g^b (mod p) and sends y to Alice
  • Alice makes sure 1 < y < p and y^q (mod p) = 1
  • Alice computes k = y^a (mod p) = g^ba (mod p)
  • Bob makes sure 1 < x < p and x^q (mod p) = 1
  • Bob computes k = x^b (mod p) = g^ab (mod p)
  • Alice and Bob 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 Alice
  • Harry carries out a legitimate Diffie-Hellman key exchange and establishes another session key with Bob
  • Harry intercepts Alice's messages, decrypts them with the one session key, re-encrypts them with the other session key, and sends them on to Bob
  • Vice versa for Bob's messages to Alice
  • 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 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^*

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

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

• Bob decrypting a ciphertext (g^a, c)
  • Bob computes k = (g^a)^b (mod p) -- modular exponentiation
  • Bob computes k⁻¹ (mod p) -- modular inversion
  • Bob computes m = k⁻¹c (mod p) -- modular product

• Alternative decryption formula
  • By Fermat's Little Theorem, x^p−1 = 1 (mod p)
  • Therefore, k⁻¹ = ((g^a)^b)⁻¹ = (g^a)^−b = (g^a)^−b (g^a)^p−1 = (g^a)^p−b−1 (mod p)
  • So Bob can compute m = (g^a)^p−b−1c (mod p) and avoid the modular inversion

• Security of El Gamal
  • Harry cannot discover k by observing g^b and g^a (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 = g^x

• 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 Z_p^*: |G| ≥ 2⁸⁰

• 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 Z_p^*: |G| ≥ 2¹⁶⁰

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

• 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 Z_p^*:
    • 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 ≥ 2¹⁶⁰
    • We ensure this by choosing q itself to be a prime ≥ 2¹⁶⁰
    • 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 Z_p^*

• Index calculus method
  • Specifically for solving the DLP in Z_p^*
  • Subexponential running time
  • For 80-bit security in Z_p^*: p ≥ 2¹⁰²⁴

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

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 28-Jan-2013. Please send comments to ark­@­cs.rit.edu.