Diffie Hellman Key Exchange

September 12, 2013

[ I apologize for not posting an exercise on Tuesday. I have had intermittent internet access at home since last week that has prevented me from working on the blog. And now I published it immediately instead of scheduling it for Friday morning. Oh my! ]

Diffie-Hellman key exchange is a method for two people, traditionally named Alice and Bob, to agree on a secret key known only to the two of them using an insecure communications channel; Wikipedia gives an explanation, complete with a cheesy diagram.

The key exchange begins when Alice and Bob agree on parameters p, which should be at least a few hundred decimal digits in a real-life application, and g, which is typically small, say 2 or 3 or 5; we will follow Wikipedia’s illustration and choose p = 23 and g = 5. Then Alice chooses a secret number a, computes ga (mod p), and sends it to Bob; in a real application, a will be of similar magnitude to p, but for illustration we choose a = 6, so Alice sends the number 56 (mod 23) = 8 to Bob. Bob follows the same procedure, choosing b, computing gb (mod p), and sending it to Alice; in a real application, b will be of similar magnitude to p, but for illustration we choose b = 15, so Bob sends the number 515 (mod 23) = 19 to Alice. All of these exchanges can be conducted over an insecure channel, as long as Alice keeps a secret and Bob keeps b secret.

Once those exchanges have been made, Alice and Bob can both compute the same secret key s; Alice computes s = 196 (mod 23) = 2, using Bob’s public number 19 and her secret number a = 6, and Bob computes s = 815 (mod 23) = 2, using Alice’s public number 8 and his secret number b = 15. At this point, both a and b can be discarded. Using the shared secret number s = 2 as a key, Alice and Bob can encrypt and decrypt messages using any symmetric cipher, such as DES or AES, and send encrypted messages over insecure channels, confident that no one else knows their secret key. In practice, p is generally taken to be 2q+1, where q is a Sophie Germain prime of at least 512 bits, and g is generally taken to be a primitive root modulo p; these rules guarantee some desirable properties of the security of the secret key. The only way for someone with knowledge of g, p, ga (mod p) and gb (mod p) to determine the secret key s is to solve for a and b, but that involves computing the discreet logarithm and is intractable with current algorithms.

Your task is to write programs that perform Diffie-Hellman key exchange as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

3 Responses to “Diffie Hellman Key Exchange”

  1. Valentin said

    Typo: … choosing b, computing gb (mod p), and sending it to Alice; in a real application, a will be…
    The last “a” should be a “b”.

  2. programmingpraxis said

    Fixed. Thanks.

  3. JP said

    Here’s mine in Racket: jverkamp.com: Diffie-Hellman Key Exchange

    I half used it as an excuse to learn about how Racket’s TCP connections work. The key exchange takes a client/server model and once the secret is established it’s used to seed the RNG for an xor encryption cipher. Works rather well and was fun to write. Racket’s math/number-theory library helped somewhat. :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: