The Diffie-Hellman(-Merkle) Key Exchange
Scytl medium.com
Learn more about the beginnings of the cryptographic concept of public key encryption and the even more revolutionary idea of digital signatures.
https://miro.medium.com/v2/5d8de952517e8160e40ef9841c781cdc14a5db313057fa3c3de41c6f5b494b19
Medium
INNOVATE

If one has to select the most impactful cryptographic paper ever, it would arguably be “New Directions in Cryptography,” published by Whitfield Diffie and Martin Hellman in 1976. The paper started with: “We stand today on the brink of a revolution in cryptography, “ and (despite sounding fairly theatrical) it was every bit true! They proposed the concept of public key encryption and the even more revolutionary idea¹ of digital signatures. Concepts that are so fundamental for cryptography that it’s hard to believe they didn’t exist forever.

Among other contributions, Diffie and Hellman published the first-ever practical algorithm for establishing a shared secret between two participants over an untrusted channel, which came to be known as the Diffie–Hellman key exchange, forever changing how communications are secured! Later, Hellman suggested calling it the Diffie-Hellman-Merkle key exchange to recognize Ralph Merkle’s essential contribution upon which everything was built².

At first glance, “Establishing a shared secret” might not sound so exciting. However, imagine that you start talking with someone you just met in English (or any other language), and after a few phrases, you both switch to a new language that only you two understand. You can share any secret, and no one will be able to understand it! Even if they were standing right in front of you two the whole time and could hear everything. It sounds like magic, but this is precisely what the Diffie-Hellman protocol does!

The math is not so complex. We need a multiplicative group of integers modulo prime p, which is a mathematician’s way of saying we need numbers {0,1,2,3 … p — 1}. Say p = 11, then our multiplicative group modulo 11 is {1,2,3,4,5,6,7,8,9,10}. Usually, we use:

to refer to such a group, where * means that the zero is excluded. So, for our example, it would be:

The beauty of this group is that it is cyclic, which means we can generate all elements from just one — called a group generator. No need to keep all the numbers! To generate all integers from the group, we need to exponentiate our generator to number 1 … 10 and then apply modulo p. For our example, the generator³ is equal to 2:

2¹ mod 11 = 2,

2² mod 11 = 4,

2³ mod 11 = 8,

2⁴ mod 11 = 16 mod 11 = 5 (take a look here for an explanation on modular arithmetic).

2⁵ mod 11 = 10,

2⁶ mod 11 = 9,

2⁷ mod 11 = 7,

2⁸ mod 11 = 3,

2⁹ mod 11 = 6,

2¹⁰ mod 11 = 1,

The order is different, but we got all the elements! Even more curious is if we continue…. we start circling (precisely why the group is called cyclic).

2¹¹ mod 11 = 2,

2¹² mod 11 = 4,

2¹³ mod 11 = 8,

…

No matter how far we go, we will keep cycling between numbers of the group!

Finally, we are ready to show how the Diffie-Hellman protocol works. For simplicity, let’s focus on our example. Suppose Alice and Bob⁴ agreed on the prime p = 11 and the generator g = 2. Then Alice selects her secret (any number from 1 to 10), suppose it’s a = 3, and computes:

Bob does the same: selects his secret, say b = 9, and computes:

Then, Alice sends her gᵃ = 8 to Bob, and Bob sends his gᵇ = 8 to Alice. Now, Alice can compute:

Interestingly, by computing:

Bob also obtains the same lucky number 7. This value is called a shared secret. Now, Bob and Alice can use it to derive symmetric keys, seed a pseudorandom number generator, etc.

Of course, our toy example is totally insecure — the numbers are so small that we can easily “crack” the secrets (get a and b from gᵃ and gᵇ). However, if we keep increasing prime p, the “cracking” of gˣ will become more and more difficult, while calculating gˣ will remain easy. The value x from gˣ is called a discrete logarithm. It is not ALWAYS hard to find x (there are special cases and groups where it’s not such a problem), but no efficient method is known for computing them in a cyclic group in general. So, in cryptography, we often rely on the assumption that computing a discrete logarithm is hard and call it a discrete logarithm problem⁵, or DL for short. It is such a basic assumption that it’s hard to believe it was not in cryptography forever, and Diffie and Hellman were the first to rely on it.

Unfortunately, assuming that a DL is hard is not enough for the Diffie-Hellman protocol to be secure. Breaking a DL to get a and b is just one way to get the same secret as Alice and Bob. Another one is to compute gᵃᵇ from gᵃ and gᵇ. If someone can do it, then there is no need to break the DL — anyone can get the same secret as Alice and Bob from the publicly sent gᵃ and gᵇ. However, in their paper, Diffie and Hellman assumed that this problem is also hard. This assumption is known as the computational Diffie–Hellman (CDH)⁶ assumption. Turns out, indeed, it holds for many groups.

Yet, again, CDH is not enough. Sure, we cannot compute gᵃᵇ, but what if we can learn something about it or predict the value with some probability? To avoid it, Diffie and Hellman made another assumption — that gᵃᵇ looks exactly like a random element from our group. Not surprisingly, this assumption is named after them too and called the decisional Diffie–Hellman (DDH)⁷ assumption.

All assumptions we discussed are related and can be ranked. Informally, we say DDH is the strongest, while DL is the weakest: DL < CDH < DDH. The strongest here merely means “a bigger number of restrictions we put on a cyclic group”. Because, if one can break DL — it will ruin them all!

Diffie and Hellman’s paper was truly revolutionary. It made them cryptography pioneers. “New Directions in Cryptography” was cited more than 23,524 times! And nearly 40 years after publishing it, Diffie and Hellman were awarded the ACM Turing Award, also known as the “Nobel Prize of Computing,” for critical contributions to modern cryptography. But most importantly, it gave such a boost to the cryptographic field that papers, proposals, and cryptosystems sprang up like mushrooms: Rivest, Shamir, and Adleman presented the RSA cryptosystem in 1977, Ralph Merkle published Merkel Puzzles in 1978, Loren Kohnfelder invented public key infrastructure (PKI) in 1978, Taher ElGamal presented ElGamal public key encryption in 1984, and finally, in 1985 elliptic curves appeared, and elliptic curve cryptography began its reign. Hopefully, we will touch on the victorious history of ECC next time!