Exploring Diffie-Hellman Encryption

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.