DI Management Home > Cryptography > Public key cryptography using discrete logarithms > Part 1: Diffie-Hellman key exchange

Public key cryptography using discrete logarithms.
Part 1: Diffie-Hellman key exchange


In the introduction to the basic Diffie-Hellman key exchange method we noted that it is possible to fool users into using a generator $g$ which only generates a small subgroup of $\mathbb{Z}_p^*$. This page describes the standard solution.

<< previous: Introduction next: MQV Key Agreement >>

Diffie-Hellman with a large cyclical subgroup

The usual solution to prevent the "small-group" problem is to make sure that the order of the group, $p-1$, has a large prime divisor $q$. This means there is a unique cyclic subgroup of order $q$ mod $p$, and we make sure that $g$ is a generator of this subgroup. In practice $q$ should be a prime at least 160 bits long, preferably 256 bits. This is too large for a feasible brute-force search or any of the other techniques available. The modulus $p$ should be at least 1024 bits.

The public domain parameters are now $(p,q,g)$, and parties Alice and Bob must select private keys in the range $[2,q-2]$ (see note **). A user being given new parameters generated by others can carry out basic checks to make sure they are not being fooled into using a small subgroup.

This method is described in ANSI X9.42 [X9-42] and RFC 2631 [RFC2631]. The technique of using a prime order $q$ subgroup was first identified by Claus-Peter Schnorr [SCH91].


Algorithm: Generate Domain Parameters.
INPUT: Required bit lengths for modulus $p$ and prime divisor $q$.
OUTPUT: Parameters $(p,q,g)$.
  1. Generate a random prime $q$ of the required bit length.
  2. Choose an even random number $j$ of bit length equal to bitlen($p$) $-$ bitlen($q$)
  3. Compute $p = jq+1$. If $p$ is not prime, then go to step 2.
  4. Choose a random number $h$ in the range $1 \lt h \lt p-1$.
  5. Compute $g=h^j\mod p$. If $g = 1$ then go to step 4.
  6. Return $(p,q,g)$.


Algorithm: Verify Domain Parameters.
INPUT: Parameters $(p,q,g)$.
OUTPUT: "Accept parameters" or "Reject parameters".
  1. Check that $1 \lt g \lt p-1$. If not, then return "Reject parameters" and stop
  2. Test $q$ for primality. If $q$ is not prime then return "Reject parameters" and stop
  3. Test $p$ for primality. If $p$ is not prime then return "Reject parameters" and stop
  4. Compute $(p-1) \mod q$. If this is not equal to 0 then return "Reject parameters" and stop
  5. Compute $g^q \mod p$. If this is not equal to 1 then return "Reject parameters" and stop
  6. Return "Accept parameters".

▷ Why does this work?

The group $\mathbb{Z}_p^*$ has order $p-1$. Any subgroup of $\mathbb{Z}_p^*$ will have order equal to a divisor of $p-1$ (by Lagrange's theorem). The divisors of $p-1$ are $q$ and $j$: $q$ is large and prime but $j$ is small and composite. We want to ensure that our generator $g$ does not have order equal to $j$ or one of its divisors. In fact, the method always gives a generator of order $q$ as we show below.

If, for any $h \in [2,p-2]$, we have $h^j = 1$ then $h$ has order $j$ or less, so we reject it. Otherwise $g=h^j \gt 1$ has the property that $g^q = \left(h^{(p-1)/q}\right)^q = h^{p-1} = 1$ (by Fermat's little theorem) and so $\text{order}(g)\leq q$. Since $q$ is prime and therefore has no proper divisors then the order of $g$ cannot be less than $q$, so $\text{order}(g)\geq q$. It follows that $g$ has order exactly $q$. You usually find a suitable $g$ on the first go.

Example of parameter generation

This is an illustrative example with trivially small numbers.

To verify these, we carry out the following checks:

  1. $1 \lt g=60 \lt p-1 = 282$, so OK.
  2. $q=47$ is prime, so OK.
  3. $p=283$ is prime, so OK.
  4. $(p-1)\mod q = (283-1)\mod 47 = 0$, so OK.
  5. $g^q\mod p = 60^{47}\mod 283 = 1$, so OK.
  6. All OK, so "Accept parameters".

Algorithm: Key Pair Generation.
INPUT: Parameters $(p,q,g)$.
OUTPUT: Party A's private/public key pair $(a, A)$.
  1. Party A chooses a number $a$ in the range $[2,q-2]$.
  2. Compute $A = g^a \mod p$.
  3. Return $(a, A)$. Keep $a$ secret.

Think of $g^a\mod p$ as the action of "throwing" the secret key $a$ somewhere in the large range $[1,p-1]$. Because it is done modulo $p$ there is no efficient way to go backwards and find $a$ for a large enough $p$.

Example of key pair generation


Algorithm: Computation of shared secret by Party A.
INPUT: Parameters $(p,q,g)$, $B$, $a$.
OUTPUT: Shared secret $Z$.
  1. Check that $1 \lt B \lt p$ and that $B^q\mod p = 1$. If not then return "Failure" and stop.
  2. Compute $Z = B^a \mod p$.
  3. Return $Z$.

▷ Why do we do the checks in step 1?

The public keys $B=0$ and $B=1$ give no security at all, so we make sure $B\gt 1$. You have the same effect if you can trick someone into using $B=kp$ or $B=1+kp$, so we limit $B\lt p$.

The check $B^q\mod p = 1$ only holds if $g^q\mod p = 1$, which ensures that $g$ is a generator for the subgroup of order $q\mod p$. We have $B^q\equiv \left(g^b\right)^q \equiv \left(g^q\right)^b\equiv 1^b\equiv 1\pmod{p}$.

Example of computation of shared secret

Remarks

Notes

** Selecting private keys in the range $[2,q-2]$, or is it $[1,q-1]$?
Depending on which references you read, some will say select the private key $a$ in the range $[1,q-1]$ and others will say use $[2,q-2]$. In practice, we are looking at picking a random number in a range of billions, so it is extremely unlikely we'll end up with a value at the limits. However, in the pedantically unlikely event we do generate a private key $a=1$, we will get a public key $A=g^1$ which equals, er, $g$ and may give a clue to an adversary as to the value of your private key. Similarly if we generate $a=q-1$ we also get $A=g^{q-1}=1$ by Fermat's Little Theorem. So why take the risk?

References

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 25 August 2013. Last updated 1 October 2016.