#
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)$.

- Generate a random prime $q$ of the required bit length.
- Choose an even random number $j$ of bit length equal to bitlen($p$) $-$ bitlen($q$)
- Compute $p = jq+1$. If $p$ is not prime, then go to step 2.
- Choose a random number $h$ in the range $1 \lt h \lt p-1$.
- Compute $g=h^j\mod p$. If $g = 1$ then go to step 4.
- Return $(p,q,g)$.

**Algorithm:**Verify Domain Parameters.

INPUT: Parameters $(p,q,g)$.

OUTPUT: "Accept parameters" or "Reject parameters".

- Check that $1 \lt g \lt p-1$. If not, then return "Reject parameters" and stop
- Test $q$ for primality. If $q$ is not prime then return "Reject parameters" and stop
- Test $p$ for primality. If $p$ is not prime then return "Reject parameters" and stop
- Compute $(p-1) \mod q$. If this is not equal to 0 then return "Reject parameters" and stop
- Compute $g^q \mod p$. If this is not equal to 1 then return "Reject parameters" and stop
- 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.

- 1. "Generate" random prime $q=47$.
- 2a. Try $j=2$:
- 3a. Compute $p = jq + 1 = 2\cdot 47 + 1 = 95$, which is
*not*prime, so go to step 2. - 2b. Try $j=6$:
- 3b. Compute $p = jq + 1 = 6\cdot 47 + 1 = 283$, which is prime, so continue.
- 4. Try $h=5$:
- 5. Compute $g = h^j\mod p = 5^6 \mod 283 = 60 \neq 1$, so continue.
- 6. Publish $(p,q,g) = (283,47,60)$.

To verify these, we carry out the following checks:

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

**Algorithm:**Key Pair Generation.

INPUT: Parameters $(p,q,g)$.

OUTPUT: Party A's private/public key pair $(a, A)$.

- Party A chooses a number $a$ in the range $[2,q-2]$.
- Compute $A = g^a \mod p$.
- 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

- A.1. Alice chooses $a=24$ and keeps it secret.
- A.2. Compute $A = g^a\mod p = 60^{24}\mod 283 = 158$.
- A.3. Alice sends $A=158$ to Bob.
- B.1. Bob chooses $b=7$ and keeps it secret.
- B.2. Compute $B = g^b\mod p = 60^7\mod 283 = 216$.
- B.3. Bob sends $B=216$ to Alice.

**Algorithm:**Computation of shared secret by Party A.

INPUT: Parameters $(p,q,g)$, $B$, $a$.

OUTPUT: Shared secret $Z$.

- Check that $1 \lt B \lt p$ and that $B^q\mod p = 1$. If not then return "Failure" and stop.
- Compute $Z = B^a \mod p$.
- 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

- COMMON INPUT: $(p=283, q=47, g=60)$
- INPUT FOR Alice: $B=216$, $a=24$.
- A.1. Check: $1 \lt B = 216 \lt p = 283$ and $B^q\mod p = 216^{47} \mod 283 = 1$ $\Rightarrow$ OK.
- A.2. Compute $Z = B^a\mod p = 216^{24}\mod 283 = 181$.
- INPUT FOR Bob: $A=158$, $b=7$.
- B.1. Check: $1 \lt A = 158 \lt p = 283$ and $A^q\mod p= 158^{47} \mod 283 = 1$ $\Rightarrow$ OK.
- B.2. Compute $Z = A^b\mod p = 158^{7}\mod 283 = 181$.

## Remarks

- In practice $q$ is at least 160 bits and $p$ at least 1024 bits. A real example with numbers in decimal is
q = 983633858469108611936846792207646525014934079943 j = 19648785705229832512739279235719869326994578857372093636756123297040568424679124 64540061234193169057945703804694798339619887840647564390726543645590797170304574 76946989704881415213211796495985450103517961540422421579976333688259982527955809 16414671992092563312 p = 19327210897467885519624495407304217845488409100133554803661172025039322784872775 17278952189544417869074042858818503169545381538675666261955584944665679490522111 57880020162452917682834724804605237775109730850324717111878065901859872191793450 22033106753600355795626394426859896564719805266547324204357196851217 g = 20088512678116493013820556973260022253215016292246160430979593078444726373397837 79480891271906681929732776937543331689329117914118665148580824850572191418544875 10980215434186216265442406596314406393660737560679656370638936273176777219436857 6684632589065496658911743756860379357301492526015846031839304359976 a = 443154410456340133792289316319263982636340525614 A = 19214527844626903057876819500198193169641589347178408096123216510760347079712191 31303229964898309632972369585510990825414095578611652854141854136282707158639017 76349124806492330431394779299032591894335300024413826806576151022179543880341303 35905388651243538583579147122642435281102052849841738314682543989601 b = 708552627548105121354432083524985769585714694203 B = 39370801881546774932592357170039231704520402513227223839981915392904026892875070 04151691833350902076026964761378570941292367186512432962797136953267476511207359 49561972379770636776112864650706982533730860846695796684838147638233797651141503 6913259368572438791510731359101113653373912723872286563003569148155 Z = 3319378743040852066281248525554807677790302702508026945509475209822628115979919 7208611387091356050777485694513339213618300369077644017879638157922142896658726 2535373398289694901821015274930091093239014497316409413910122183039716148353078 3129064601312291695971038344663201164529792929266992327467270782207

- The ordinary Diffie-Hellman method above is still susceptible to a man-in-the-middle attack because the key exchange messages cannot be authenticated.
- The parameter generation method described in X9.42 and RFC 2631 [X9-42, RFC2631] uses a random `seed` and `counter` to derive $p$ and $q$ using the SHA-1 hash algorithm. These extra two parameters are supplied along with $(p,q,g)$ and a recipient can use them to check that the parameters were indeed generated correctly from a random seed and are therefore unlikely to be vulnerable to a small subgroup attack or other trickery.
- The shared secret $Z$ is usually hashed along with mutually agreed salting material and a counter to generate a session key to be used
to encrypt material to be passed between the parties.
Session Key K_1 = Hash(Z || salt || 0001) Session Key K_2 = Hash(Z || salt || 0002) ...etc...

where the hashes are either concatenated or truncated to form a symmetrical encryption key of the required length (e.g. 128 bits for AES-128). Incidentally, the X9.42 test vectors are wrong.

## 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

**[RFC2631]**RFC 2631 Diffie-Hellman Key Agreement Method, E. Rescoria, June 1999. <http://www.ietf.org/rfc/rfc2631.txt>**[SCH91]**Schnorr, C. P. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161-174, 1991. <pdf-link>**[X9-42]**ANSI X9.42-2003 Agreement of Symmetric Keys Using Discrete Logarithm Cryptography, American National Standards Institute, November 2003.

## 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.*