Math Behind Public Encryption

Since there seemed to be some interest in the math underneath public key encryption, based on the humming, I thought I would get my math-geek on and share a simple example and explanation that captures most of Diffie’s intuition. A more technical and rigorous discussion can be found here.

Public key encryption allows two people to basically “create” a shared secret through public communication by cleverly exploiting a one-way function. A one-way function is an operation in which one direction can be computed easily and mechanically, but the inverse of the function is hard to compute analytically, and requires reliance on essentially guess-and-check methods.

The simplest example of one-way functions are exponents and their inverse, logarithms, in modular arithmetic. You can think of modular arithmetic as translating all integers into their “remainders” when divided by a given base. So let’s say we are in a base 7 world—the “mod 7 world.” In this system, 23 is equivalent to 2; this means that when divided by 7, 23 yields 2 as its remainder (23 = 21+2 = 7*3+2). 18 would be equivalent to 4, as 18 yields a remainder of 4 when divided by 7 (18 = 14+4 = 7*2+4). These relations are written: 23 = 2 (mod 7); 18 = 4 (mod 7).

A few more examples are: 14 = 0 (mod 7); 3 = 3 (mod 7); 8 = 1 (mod 7). Note that in this mod 7 world there are only really 7 elements or numbers {0,1,2,3,4,5,6}. Every integer will equivalent to one of these elements mod 7, as these are the only possible remainders when a number is divided by 7.

Raising a number to a power is easy in modular arithmetic. You just do the multiplication, and then the divide by the base to get the remainder. For example, to compute 3³ (mod 7), you just multiply 3*3*3 = 27, then divide 27 by 7, and you get 3³ = 27 = 7*3+6. Thus 3³ = 6 (mod 7). This is mechanical and a computer can do it very quickly even if the numbers are large. But taking logarithms in the mod 7 world is hard. Imagine you have this problem 3^x = 6 (mod 7). The question you’re faced with is: what power must 3 be raised to yield 6 (mod 7)? There’s no good way to do this other than guess-and-check (i.e., try 6², then 6³, etc., until you get a winner). This is our one-way function.

Now let’s generate our shared secret. I’ll go through the process in the abstract and then do a small number example. By tradition, imagine two people, Alice and Bob, want to share generate a secret key between them. But they can’t confer in secret ahead of time, and our eavesdropper Eve will be listening in to all their communications. Here’s how they get around this limitation:

• First, Alice and Bob (with Eve listening, of course) agree on what mod world and what base they will use. Let’s have them choose the base g and the mod p world. (Technically, we have to require here that p be a prime and g be a generator of the group mod p, hence the letters).
• Second, Alice and Bob each choose some random number for their private key, which they keep to themselves. Let Alice choose a and Bob choose b.
• Third, Alice sends to Bob g^a (mod p), and Bob sends g^b (mod p) to Alice. Eve now knows g^a, g^b, and g, but she can’t easily figure out either a or b, because of the one-way function problem. This is the rub for Eve.
• Lastly, Alice takes what she was sent, g^b, and raises it to her private key, yielding (g^b)^a = g^ab(mod p). Bob does the analogous thing and raises what Alice sent to his private key, yielding (g^a)^b = g^ab (mod p).
• At the end both Alice and Bob know g^ab, but Eve does not. This is their shared secret, though it was created completely publicly. They can exploit this fact by, for example, using g^ab as an old-fashioned WWII-style key.

Using real numbers, let’s say Alice and Bob choose the mod 5 world and the base 3 (g=3 and p=5). Then they each choose a private key; let Alice choose a=2 and Bob choose b=3. Now:

• Alice computes 3² = 4 (mod 5), and sends 4 to Bob. Bob computes 3³ = 2 (mod 5) and sends 2 to Alice.
• Alice then takes what Bob sent and raises it to her private key; she computes 2² = 4 (mod 5). Bob does likewise, computing 4³ = 64 = 4 (mod 5). Now they both know 4 = g^ab; the number 4 is their shared secret.
• Let’s put ourselves in Eve’s shoes. At the end of the exchange, Eve knows that p=5, and g=3. She saw that 4 was sent from Alice to Bob, and that 2 was sent from Bob to Alice. So Eve knows that 3^a = 4 and 3^b = 2. But can’t figure out a and b (and thus g^ab) without guess-and-check. Here, there are only 4 possibilities, but in practice we want p to be very large so guess-and-check is computationally difficult.

That, essentially, is the magic.