# Exploring Diffie-Hellman Encryption

## Security

by Jack Dennon

Communicating "in the clear", Alice and Bob select two numbers, q and n. Alice then selects the secret number xa. Bob selects the secret number xb. From the two public numbers, q and n, and her secret number xa, Alice calculates ya and sends the number to Bob. Using the same two public numbers, q and n, and his secret number xb, Bob calculates yb and sends the number to Alice. Alice and Bob have completed step one of the Diffie-Hellman process.

The program crypto.bc shows how Alice calculates ya using the formula

ya = (n ^ xa) % q

This says, multiply n by itself xa times, then divide the product by q and save only the remainder.

Alice sends the number ya to Bob. In the meantime, Bob applies the same formula to the numbers n, xb and q to calculate the number yb:

yb = (n ^ xb) % q

Bob sends the number yb to Alice. They are ready for step two.

Using the number yb received from Bob, Alice calculates

ka = (yb ^ xa) % q

Again, this means multiply yb by itself xa times, and then save the remainder after dividing the product by q. When Bob receives Alice's number ya he calculates:

kb = (ya ^ xb) % q

Alice and Bob have completed the Diffie-Hellman encryption process.

Magic

Alice applied her secret number xa to Bob's value yb and calculated ka. Bob applied his secret number xb to Alice's value ya and calculated kb. Presto: it turns out that ka = kb, a number now known to Alice and Bob, but to no one else. Even though Eve, the eavesdropper, may have been monitoring their communications studiously, Eve cannot discover the number ka easily.

Diffie-Hellman Algorithm

The following program, written for the bc compiler, was adapted from Simson Garfinkel's book on Phil Zimmerman's Pretty Good Privacy. Where large numbers would be used in practice, we use small numbers for clarity. The operation x % y returns x modulo y, that is, the remainder obtained when x is divided by y. The operation n ^ xa multiplies the number n times itself xa times. In programs designed to handle really large numbers, we can speed up the calculation of (n ^ xa) % q by applying the modulo operation after each multiply. While using relatively small numbers, illustration is made simpler with the naïve literal method used below:

```/* crypto.bc - From Simson Garfinkel: PGP, appendix F
* the mathematics of Diffie-Hellman encryption.
*/
q = 563         /* Alice and Bob select a large prime */
a = 5           /* ...and another random number       */
xa = 9          /* Alice picks the random number 9 */
xb = 14         /* Bob picks the random number 14 */

ya = a ^ xa     /* Alice */
ya = ya % q
print "_nAlice sends ya = ", ya," to Bob_n";

yb = a ^ xb     /* Bob */
yb = yb % q
print "Bob sends yb = ", yb," to Alice_n";

ka = yb ^ xa
print "_n   from yb^xa = ";ka;
ka = ka % q
print "         Alice calculates ka = ",ka,"_n"

kb = ya ^ xb
print "   from ya^xb = "; kb;
kb = kb % q
print "         Bob calculates kb = ",kb,"_n";
print "_nThey can now use ",kb," to encrypt messages._n";
quit
```

When executed with the command bc crypto.bc, this program writes the following output to stdout:

```        Alice sends ya = 78 to Bob
Bob sends yb = 534 to Alice
from yb^xa = 3530785328217308860798464
Alice calculates ka = 117
from ya^xb = 308549209196654470906527744
Bob calculates kb = 117
They can now use 117 to encrypt messages.
```
Passing a Secret in Public

Operating entirely in the clear, Alice and Bob have passed the number 117 between them without disclosing it to anyone else. Eve, who may have been monitoring their communications or recording them for analysis, may have difficulty discovering the number ka = 117.

Eve knows the numbers n, q, ya and yb, so she could write the equation

ya = ( n ^ xa) % q

and try all possible values of xa until she finds one that generates the known value of ya. Using that value of xa in the equation

ka = (yb ^ xa) % q

Eve could calculate the value of ka. This "brute force" method of attack, however, is practical only if Alice and Bob use small numbers. By using large numbers, preferably large prime numbers, Alice and Bob can make Eve's brute force attack impractical.

Prime Numbers

If the only two numbers that can be multiplied together to form the number n are the number 1 and the number n itself, then n is said to be prime. Any number can be formed as the product of some two numbers. For example, the number 21 can be formed as the product of 3 and 7, the number 221 can be formed as the product of 13 and 17 and so on. To continue, the number 221 is said to have the "factors" 13 and 17, but a prime number has only the factors 1 and itself.

We need prime numbers for the Diffie-Hellman process, so let's write a bc program to find them. Call your favorite text editor with a command such as able testprime.bc, and type in the following:

```/* testprime2.bc: test for prime numbers
The exhaustive search method used here
works ok for numbers up to about 12 digits.
*/
define qprime(value) {
auto d, rem

small_factor = 2
rem = value % 2
if ( rem == 0 ) return(rem) # it is even
small_factor = 3
if ( value == 9) return(0)  # skip it so we can start at 3

for (d = 3; d^2 <= value; d += 2) {
rem = value % d
/*      print "d = ",d
print "rem = ",rem
print "_n"
*/
if ( rem == 0 ) break
}
small_factor = d
return(rem)
}
scale = 0
print "enter a starting value, then increments (or 0 to quit):_n"
testvalue = read();     /* get the starting value */
while ( 1 ) {
a = qprime(testvalue)
print testvalue
if ( a == 0 && testvalue != 2 ) {
print " is not prime, smallest factor is ",small_factor
}
if ( a != 0 ) {
print " is a prime number"
}
if ( testvalue == 2 ) {
print " is a special case, Ducky"
}
print "_n"
if (increment == 0) { break }
testvalue += increment
}
halt
```

Save the text file and then call the program with the command bc testprime.bc.

The program first asks for a starting value. It tests the number entered, then loops repeatedly asking for an increment, advancing the test value by that amount and then testing again. Here is an example interaction:

```        enter a starting value, then increments (or 0 to quit):
123487 is not prime, smallest factor is 7
2
123489 is not prime, smallest factor is 3
2
123491 is a prime number
0
```

We need two prime numbers, so call the program again:

```        bc testprime.bc

enter a starting value, then increments (or 0 to quit):
394323 is not prime, smallest factor is 3
2
394325 is not prime, smallest factor is 5
2
394327 is a prime number
0
```

Now we need bc programs to evaluate the Diffie-Hellman equations for Alice and for Bob. Call your text editor with a command such as able alice.bc, and key in the following text:

```/* alice.bc: Diffie-Hellman encryption demo
*/
# this modexp() bc routine is a transliteration
# of the C routine found in Bruce Schneier's
# "Applied Cryptography" Wiley, New York. 1994.
# ISBN 0-471-59756-2
# modexp: from page 200
define modexp(a, x, n) { # return a ^ x mod n
auto r

r = 1
while ( x > 0 ) {
if ( (x % 2) == 1 ) {
r = (r * a) % n
}

a = ( a * a ) % n
x /= 2
}
return(r)
}
print "Alice:_n"
print "Enter public value q: "; q = read()
print "Enter public value n: "; n = read()
ya = modexp(n,xa,q)
print "_nAlice, here is the number to send to Bob, ya: "; ya
print "_nEnter the number you received from Bob, yb: "; yb = read()

ka = modexp(yb,xa,q)
print "Result: "; ka
print "_n_n"
halt
```

Make a copy of Alice's program with the command cp alice.bc bob.bc. Then call your text editor with a command such as able bob.bc, and modify the program to look like this for Bob:

```/* bob.bc: Diffie-Hellman encryption demo for Bob
*/
# this modexp() bc routine is a transliteration
# of the C routine found in Bruce Schneier's
# "Applied Cryptography" Wiley, New York. 1994.
# ISBN 0-471-59756-2
# modexp: from page 200
define modexp(a, x, n) { # return a ^ x mod n
auto r

r = 1
while ( x > 0 ) {
if ( (x % 2) == 1 ) {
r = (r * a) % n
}

a = ( a * a ) % n
x /= 2
}
return(r)
}
print "Bob:_n"
print "Enter public value q: "; q = read()
print "Enter public value n: "; n = read()
yb = modexp(n,xb,q)
print "_nBob, here is the number to send to Alice, yb: "; yb
print "_nEnter the number received from Alice, ya: "; ya = read()

kb = modexp(ya,xb,q)
print "_nResult: "; kb
print "_n_n"
halt
```
Trying It Out

When Alice selects a secret number, such as 76697, and calls her program with the command bc alice.bc, her interactive session looks like this:

```
Alice:
Enter public value q: 394327
Enter public value n: 123493
Enter your secret number xa: 76697
Alice, here is the number to send to Bob, ya: 323823
```

Hold down Alt and press F2, for example, to switch your console to a different virtual terminal (or if using a graphical user interface, open a new xterm), and then call Bob's program with the command bc bob.bc. Bob selects the secret number 69623. His interactive session looks like this:

```        Bob:
Enter public value q: 394327
Enter public value n: 123493
Enter your secret number xb: 69623
Bob, here is the number to send to Alice, yb: 32675
Enter the number received from Alice, ya: 323823
Result: 74297
```

Bob has completed his side of the Diffie-Hellman process.

Switch back to Alice's virtual terminal, or window. When Alice receives the number yb from Bob, she cam complete the process on her side:

```        Enter the number you received from Bob, yb: 32675
Result: 74297
```

Alice and Bob each have slipped the number 74297 past Eve, and they now can use that number to generate a key for encrypting messages.

Eve Strikes

Eve, of course, has been watching all this and has written a program of her own. Here is Eve's program:

```/* eve.bc: Brute force attack on Diffie-Hellman encryption
*/
define modexp(a, x, n) { # return a ^ x mod n
auto r

r = 1
while ( x > 0 ) {
if ( (x % 2) == 1 ) {
r = (r * a) % n
}

a = ( a * a ) % n
x /= 2
}
return(r)
}
print "Eve:_n"
print "enter public value q: "; q = read()
print "enter public value n: "; n = read()
print "_nenter observed public number ya: "; ya = read()
print "_nenter observed public number yb: "; yb = read()
print "_nenter a starting value for xa: "; xa = read()
while ( 1 ) {
tya = modexp(n,xa,q)
if (tya == ya) { break }
xa += 1
print "trying ", xa, "_r"
}

print "_nfound xa = "; xa
ka = modexp(yb,xa,q)
print "_nResult: "; ka
quit
```

When Eve calls her program with the command bc eve.bc, her interactive session looks like this:

```        Eve:
enter public value q: 394327
enter public value n: 123493
enter observed public number ya: 323823
enter observed public number yb: 32675
enter a starting value for xa: 2
trying 3
trying 4
trying 5
trying 6
trying 7
<snip>
trying 76693
trying 76694
trying 76695
trying 76696
trying 76697
found xa = 76697
Result: 74297
```

Depending on the speed of Eve's computer, this may take several minutes.

Patch the Compiler

If the output routine used by your bc compiler, like the one used above, refuses to recognize that the program statement

print "trying ", xa, "_r"

is expected to repeatedly use the same display line, as in C, you may need to post the following little patch to your bc system. The patch adds a few lines of code at the beginning of the routine out_schar(). Source for this routine is in util.c, located in the directory bc_1.06/bc.

```        341a342,347
>   if (ch == '_r')
>     {
>       out_col = 0;
>       putchar('_r');
>       return;
>     }
```
How to Select q and n

When selecting two prime numbers for the Diffie-Hellman process, use the larger number for q and the smaller number for n. To discover why, try swapping the two numbers around. With the values of q and n swapped, that is, with n larger than q, while Alice and Bob may see nothing out of the ordinary, Eve's cryptanalysis becomes much easier.

And there is more. In addition to q being a prime number, the value (q-1)/2 should also be a prime number. So let's write a modified version of testprime.bc that will test for that condition. Make a copy of testprime.bc with the command cp testprime.bc testqm1.bc, and then call your editor with a command such as able testqm1.bc. Modify the program to look like this:

```/* testqm1.bc: find prime number q and test (q-1)/2 also.
The exhaustive search method used here
works ok for numbers up to about 12 digits.
*/
define qprime(value) {
auto d, rem

small_factor = 2
rem = value % 2
if ( rem == 0 ) return(rem) # it is even
small_factor = 3
if ( value == 9) return(0)  # skip it so we can start at 3

for (d = 3; d^2 <= value; d += 2) {
rem = value % d
if ( rem == 0 ) break
}
small_factor = d
return(rem)
}
scale = 0
print "enter a starting value, then state how many primes to find:_n"
testvalue = read()      /* get the starting value */
find = read()           /* get the count of primes to find */
i = 0; increment = 2
while ( i < find ) {
a = qprime(testvalue)
if ( a != 0 ) {
savetest = testvalue
t = (testvalue - 1)/2
aa = qprime(t)
if ( aa != 0 ) {
print "q = ", testvalue
print " is prime and (q-1)/2 = ", t
print " is ALSO prime_n"
i += 1
}
}
if ( testvalue == 2 ) {
print testvalue
print " is a special case, Ducky_n"
testvalue += 1
}
testvalue += increment
}
halt
```

When called with the command bc testqm1.bc, an example session looks like:

```enter a starting value, then state how many primes to find:
2426697105
3
q = 2426697107 is prime and (q-1)/2 = 1213348553 is ALSO prime
q = 2426697359 is prime and (q-1)/2 = 1213348679 is ALSO prime
q = 2426698727 is prime and (q-1)/2 = 1213349363 is ALSO prime
```
Try Larger Primes

Knowing all of this, Alice selects 2426697107 for q and calls the testqm1 program again to find a smaller prime to use for n:

```enter a starting value, then state how many primes to find:
17123201
2
q = 17123207 is prime and (q-1)/2 = 8561603 is ALSO prime
q = 17124539 is prime and (q-1)/2 = 8562269 is ALSO prime
```

Alice selects 17123207 for n. With these numbers, and selecting the arbitrary number 31925631 for xa, Alice's interactive session looks like:

```
Alice:
Enter public value q: 2426697107
Enter public value n: 17123207
Enter your secret number xa: 31925631
Alice, here is the number to send to Bob, ya: 919478360
```

Alice sends the numbers q, n and ya to Bob. Using his selected secret number 19758139, Bob's interactive session looks like:

```        Bob:
Enter public value q: 2426697107
Enter public value n: 17123207
Enter your secret number xb: 19758139
Bob, here is the number to send to Alice, yb: 1724324231
Enter the number received from Alice, ya: 919478360
Result: 1490225501
```

When Alice receives Bob's number yb, she completes her calculation:

```        Enter the number you received from Bob, yb: 1724324231
Result: 1490225501
```
Eve Strikes Again

Eve calls her program with the command time bc eve.bc. The time utility will print the elapsed time when the process is complete. Her interactive session looks like:

```        Eve:
enter public value q: 2426697107
enter public value n: 17123207
enter observed public number ya: 919478360
enter observed public number yb: 1724324231
enter a starting value for xa: 2
trying 3
trying 4
trying 5
trying 6
trying 7
...
<snip>

```

Eve's program found xa = 31925631 and the result = 1490225501. On a Slackware Linux 2.4 system with a 451 MHz K6 processor reporting 897.84 BogoMIPS, the search took a little over 19 hours. Eve's program tried each of about 31.9 million possible values of xa before it got a hit. On this system it appears that brute force discovery of xa takes about one half hour per one million trial values of xa.

If Eve is on a network where she has access to, say, 30 other similar systems, she could run 30 copies of her program simultaneously; starting the first program near 0, the second at 1000000, the third at 2000000 and so on. One of the computers should find the solution within about 30 minutes. That being the case, perhaps Alice and Bob should use numbers even larger.

Larger Yet

Alice and Bob used a 10-digit value for q and an 8-digit value for n. Alice selected an 8-digit value for her secret number xa and Bob selected an 8-digit value for his secret number xb. Because it is xa or xb that Eve will be trying to find, we should investigate the result of Alice and Bob each selecting a 9-digit value for their secret numbers. From the previous experiment it would appear that even Eve's network scheme would need four or five hours to find the solution. On a single computer, Eve's program evidently would need about a week to find the solution.

Selecting Secret Numbers

Because it is xa that Eve's program must find, it might appear that simply selecting a very large value for xa would defeat Eve's brute force attack. The reality, though, is exactly the opposite. For the values

```        q = 394327
n = 123493
xa = 76697
xb = 59232
```

Alice and Bob found result 365557. Eve's program found the same xa = 77797 and result = 365557 in about three minutes. For the same values of q and n with the larger values

```        xa = 766973423
xb = 592329871
```

Alice and Bob obtained the result = 32000. In only eight seconds, Eve's program found this same result at a test value of xa = 9353. So it seems that if xa has more digits than q, then Eve's program doesn't even need to discover Alice's secret number xa at all. Instead it can find a solution at the much smaller trial value of xa. Modulo arithmetic is like a football--it's hard to guess which way it will bounce.

Resources

On that site you can also check out my pretty good editor for GNU/Linux, described in the book Build Your Own LINUX C Toolbox.

An interactive calculator for finding large prime numbers is available at wims.unice.fr.

GNU Privacy Guard, a free replacement for PGP, can be downloaded from www.gnupg.org.

Also available from the Free Software Foundation is the GNU bc compiler written by Philip A. Nelson. The entire bc package, including sources, can be downloaded from www.gnu.org/directory/bc.html.

An introduction to Pretty Good Privacy, including a blow-by-blow account of Phil Zimmerman's many battles, can be found in the book PGP: Pretty Good Privacy, by Simson Garfinkel, published in 1995 by O'Reilly. ISBN 1-56592-098-8.

For additional background on PGP, see Phil Zimmerman's own book, The Official PGP User's Guide, published in 1995 by The MIT Press.

For background on cryptography in practice that is written by a professional in the field, with details on Diffie-Hellman, RSA and many other algorithms, find a copy of Bruce Schneier's Applied Cryptography, published by Wiley. The second edition is available on Amazon.