Introduction

Every cipher we have worked with up to this point has been what is called a symmetric key cipher, in that the key with which you encipher a plaintext message is the same as the key with which you decipher a ciphertext message. As we have discussed from time to time, this leads to several problems. One of these is that, somehow, two people who want to use such a system must privately and secretly agree on a secret key. This is quite difficult if they are a long distance apart (it requires either a trusted courier or an expensive trip), and is wholly impractical if there is a whole network of people (for example, an army) who need to communicate. Even the sophisticated Enigma machine required secret keys. In fact, it was exactly the key distribution problem that led to the initial successful attacks on the Enigma machine.

However, in the late 1970's, several people came up with a remarkable new way to solve the key-distribution problem. This allows two people to publicly exchange information that leads to a shared secret without anyone else being able to figure out the secret. The Diffie-Hellman key exchange is based on some math that you may not have seen before. Thus, before we get to the code, we discuss the necessary mathematical background.

Prime Numbers and Modular Arithmetic

Recall that a prime number is an integer (a whole number) that has as its only factors 1 and itself (for example, 2, 17, 23, and 127 are prime). We'll be working a lot with prime numbers, since they have some special properties associated with them.

Modular arithmetic is basically doing addition (and other operations) not on a line, as you usually do, but on a circle -- the values "wrap around", always staying less than a fixed number called the modulus.

To find, for example, 39 modulo 7, you simply calculate 39/7 (= 5 4/7) and take the remainder. In this case, 7 divides into 39 with a remainder of 4. Thus, 39 modulo 7 = 4. Note that the remainder (when dividing by 7) is always less than 7. Thus, the values "wrap around," as you can see below:

To do modular addition, you first add the two numbers normally, then divide by the modulus and take the remainder. Thus, (17+20) mod 7 = (37) mod 7 = 2.

Modular arithmetic is not unfamiliar to you; you've used it before when you want to calculate, for example, when you would have to get up in the morning if you want to get a certain number of hours of sleep. Say you're planning to go to bed at 10 PM and want to get 8 hours of sleep. To figure out when to set your alarm for, you count, starting at 10, the hours until midnight (in this case, two). At midnight (12), you reset to zero (you "wrap around" to 0) and keep counting until your total is 8. The result is 6 AM. What you just did is to solve (10+8) mod 12. As long as you don't want to sleep for more than 12 hours, you'll get the right answer using this technique. What happens if you slept more than 12 hours?

Examples

1. 12+18(mod 9) Answer
   
   
2. 3*7(mod 11) Answer
   
   
3. (103 (mod 17))*(42 (mod 17)) (mod 17) Answer
   
   
4. 103*42 (mod 17) Answer
   
   
5. 7² (mod 13) Answer
   
   
6. 7³ (mod 13) Answer
   
   
7. 7⁴ (mod 13) Answer
   
   
8. 7⁵ (mod 13) Answer
   
   
9. 7⁶ (mod 13) Answer
   
   

Did you notice something funny about the last 5 exercises? While, usually, when we take powers of numbers, the answer gets systematically bigger and bigger, using modular arithmetic has the effect of scrambling the answers. This is, as you may guess, useful for cryptography!

Diffie-Hellman Key Exchange

The premise of the Diffie-Hellman key exchange is that two people, Alice and Bob, want to come up with a shared secret number. However, they're limited to using an insecure telephone line that their adversary, Eve (an eavesdropper), is sure to be listening to. Alice and Bob may use this secret number as their key to a Vigenere cipher, or as their key to some other cipher. If Eve gets the key, then she'll be able to read all of Alice and Bob's correspondence effortlessly. So, what are Alice and Bob to do? The amazing thing is that, using prime numbers and modular arithmetic, Alice and Bob can share their secret, right under Eve's nose! Here's how the key exchange works.

1. Alice and Bob agree, publicly, on a prime number P, and a base number N. Eve will know these two numbers, and it won't matter!
   
   
2. Alice chooses a number A, which we'll call her "secret exponent." She keeps A secret from everyone, including Bob. Bob, likewise, chooses his "secret exponent" B, which he keeps secret from everyone, including Alice (for subtle reasons, both A and B should be relatively prime to N; that is, A should have no common factors with N, and neither should B).
   
   
3. Then, Alice computes the number

   J = N^A (mod P)

   and sends J to Bob. Similarly, Bob computes the number

   K = N^B (mod P)

   and sends K to Alice. Note that Eve now has both J and K in her possession.

4. The final mathematical trick is that Alice now takes K, the number she got from Bob, and computes
   K^A(mod P).

   Bob does the same step in his own way, computing

   J^B (mod P).

   The number they get is the same! Why is this so? Well, remember that K = N^B (mod P) and Alice computed K^A (mod P) = (N^B)^A (mod P) = N^BA (mod P). Also, Bob used J = N^A (mod P), and computed J^B (mod P) = (N^A)^B (mod P) = N^AB (mod P).

   Thus, without ever knowing Bob's secret exponent, B, Alice was able to compute N^AB (mod P). With this number as a key, Alice and Bob can now start communicating privately using some other cipher.

   Why Diffie-Hellman Works

   At this point, you may be asking, "Why can't Eve break this?" This is indeed, a good question. Eve knows N, P, J, and K. Why can't she find A, B, or, most importantly, N^AB(mod P)? Isn't there some sort of inverse process by which Eve can recover A from N^A(mod P)?

   Well, the thing Eve would most like to do, that is, take the logarithm (base N) of J, to get A, is confounded by the fact that Alice and Bob have done all of their math modulo P. The problem of finding A, given N, P, and N^A (mod P) is called the discrete logarithm problem. As of now, there is no fast way known to do this, especially as P gets really large. One way for Eve to solve this is to make a table of all of the powers of N modulo P. However, Eve's table will have (P-1) entries in it. Thus, if P is enormous (say 100 digits long), the table Eve would have to make would have more entries in it than the number of atoms in the universe! Simply storing that table would be impossible, not to mention searching through it to find a particular number. Thus, if P is sufficiently large, Eve doesn't have a good way to recover Alice and Bob's secret.

   "That's fine," you counter, "but if P is so huge, how in the world are Alice and Bob going to compute powers of numbers that big?" This is, again, a valid question. Certainly, raising a 100-digit-long number to the power 138239, for example, will produce a ridiculously large number. This is true, but since Alice and Bob are working modulo P, there is a shortcut called the repeated squaring method.

   To illustrate the method, we'll use small numbers (it works the same for larger numbers, but it requires more paper to print!). Say we want to compute 7²⁹ (mod 17). It's actually possible to do this on a simple four-function calculator. Certainly, 7²⁹ is too large for the calculator to handle by itself, so we need to break the problem down into more manageable chunks. First, break the exponent (29) into a sum of powers of two. That is,

   29 = 16 + 8 + 4 + 1 = 2⁴ + 2³ + 2² + 2⁰

   (all we're doing here is writing 29 in binary: 11101). Now, make a list of the repeated squares of the base (7) modulo 17:

   7¹ (mod 17) = 7
   7² (mod 17) = 49 (mod 17) = 15
   7⁴ (mod 17) = 7² * 7² (mod 17) = 15 * 15 (mod 17) = 4
   7⁸ (mod 17) = 7⁴ * 7⁴ (mod 17) = 4*4 (mod 17) = 16
   7¹⁶ (mod 17) = 7⁸ * 7⁸ (mod 17) = 16*16 (mod 17) = 1

   Then, 7²⁹ (mod 17) = 7¹⁶ * 7⁸ * 7⁴ * 7¹ (mod 17) = 1 * 16 * 4 * 7 (mod 17) = 448 (mod 17) = 6.

   The neat thing is that the numbers in this whole process never got bigger than 16² = 256 (except for the last step; if those numbers get too big, you can reduce mod 17 again before multiplying). Thus, even though P may be huge, Alice's and Bob's computers don't need to deal with numbers bigger than (P-1)² at any point.

   Key Exchange Worksheet

   Here's a worksheet to try this whole process out on. It may help to work with a few friends!

   Questions to Consider

   1. Will this method work if Alice and Bob don't know each other? What could Eve do if she were impersonating one of them? What if she were "in the middle", that is, what if Bob thought Eve was Alice and Alice thought Eve was Bob?
      
      

      Answer

   2. How can Alice and Bob know that Eve hasn't jumped "in the middle"? That is, how can Alice really know that Bob is Bob? (This is called authentication.) Is there any way for Alice to know with absolute certainty?

   Other Links*

   • More on modular arithmetic
   • Overview of Diffie-Hellman

   * These links are for informational purposes only and are from sources outside MEC and Cornell University