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.

We use JavaScript to display the mathematics on this page. Please enable JavaScript in your browser for it to work.

<< 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\bmod 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) \bmod q$. If this is not equal to 0 then return "Reject parameters" and stop
Compute $g^q \bmod 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\bmod p = 5^6 \bmod 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)\bmod q = (283-1)\bmod 47 = 0$, so OK.
$g^q\bmod p = 60^{47}\bmod 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 \bmod p$.
Return $(a, A)$. Keep $a$ secret.

Think of $g^a\bmod 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\bmod p = 60^{24}\bmod 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\bmod p = 60^7\bmod 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\bmod p = 1$. If not then return "Failure" and stop.
Compute $Z = B^a \bmod 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\bmod p = 1$ only holds if $g^q\bmod p = 1$, which ensures that $g$ is a generator for the subgroup of order $q\bmod 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\bmod p = 216^{47} \bmod 283 = 1$ $\Rightarrow$ OK.
A.2. Compute $Z = B^a\bmod p = 216^{24}\bmod 283 = 181$.
INPUT FOR Bob: $A=158$, $b=7$.
B.1. Check: $1 \lt A = 158 \lt p = 283$ and $A^q\bmod p= 158^{47} \bmod 283 = 1$ $\Rightarrow$ OK.
B.2. Compute $Z = A^b\bmod p = 158^{7}\bmod 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. <https://tools.ietf.org/html/rfc2631>
[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.