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.

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.

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.

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.

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"
        increment = read()
        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()
        print "_nEnter your secret number xa: "; xa = 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()
        print "_nEnter your secret number xb: "; xb = 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

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, 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 your secret number x: "; xa = 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.

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;
        >     }

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

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

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.

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.

Sources for all the programs in this article are in the compressed project file dhcrypt.tgz that can be downloaded from www.seasurf.com/~jdennon

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.