Rosio Pavoris

I mentioned Diffie-Hellman key exchange in the context of asymmetric cryptography. I think it’s time to look at the algorithm a bit more closely.

As usual, Alice and Bob are trying to securely exchange some information, and they’re trying to agree on a key they can use for a symmetric algorithm. Perhaps they don’t know about asymmetric encryption, or they’re trying to exchange too much data for it to be feasible, or they need a stream cipher. Either way, they want to use symmetric encryption.
They have no secure way to exchange keys, because Eve is listening. After all, this is why they want to use the symmetric cipher as well. This is a very common situation on the internets.

The first thing they do is agree on a large prime number p, and any natural number, g, over the insecure channel. Let’s say they pick 37 for p, and 2 for g.
37 isn’t a big number by any standard, and in practice, p will generally be 512 or 1024 bits (or even larger). g, however, doesn’t have to be large at all, and in practice is indeed often 2 or 5 or something similar.
Note that Eve knows both p and g.

Next, Alice chooses a secret integer a, which she doesn’t share with anyone. She then calculates and sends Bob the result.¹
Let’s say she picked 7 for a. A would then be 17. Note that since A was sent over the insecure channel, Eve also has it.

Bob then does the same thing. He picks a secret integer b and calculates , which he sends to Alice.
Let’s say he picked 10, making B 25. Again, Eve also has this number.

Now for the magic bit: Alice raises B to the power of her secret integer a and applies the modulo operation with respect to p again:

And Bob does the same with A and his own integer:

Gasp!
Does this surprise you? Perhaps it shouldn’t. Let’s look at what they’re actually computing.
This is Alice’s equation:

And this is Bob’s:

They arrive at the same number because .

“But Carin,” you ask, “So what? Eve has access to g, p, A, and B. Surely she can derive S herself!”
And you’re right, she could. She would, however, have to solve the Diffie-Hellman problem, the basic form of which is:

Given an element g and the values of g^x and g^y, what is the value of g^xy?

This problem is assumed² to be hard.
In fact, for large enough g, a, and b, it quickly becomes impossible for Eve to figure out S in practice, even with a few hundred Storms.

As such, Alice and Bob now have a key they can use for their symmetric algorithm, and Eve is thwarted.

RSA is essentially a more general application of this algorithm. In assymetric cryptography terms, g and p together form the public key, while a and b form the private keys.
As with RSA, it’s important that the public and private keys are chosen well. It’s slightly less tricky than for RSA itself, but an unfortunate choice of keys will, of course, render S worthless.

Also note that while this algorithm is safe against eavesdroppers, it doesn’t protect from man-in-the-middle attacks. One way to protect against those would be to get digital signatures involved, but that requires an existing public key infrastructure. And if you have that you could just pick an S and encrypt it asymmetrically anyway, without this hassle.

¹ “mod” is the modulo operation. x mod y equals the remainder of dividing x by y, in integer division.

² Not proven, except in some limited sense, though it has survived over three decades of scrutiny. The most efficient known way to solve it is to solve the discrete logarithm problem, which Wikipedia will be happy to tell you all about.
For the purposes of this post, suffice it to say no known algorithm for it runs in polynomial time.