Exploring Diffie-Hellman Encryption
The GNU bc threaded code compiler, included with most Linux distributions, provides arbitrary precision arithmetic that can handle the large numbers used in modern cryptography. Here we use the bc compiler to explore Diffie-Hellman public key 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.