INNOVATE
The Diffie-Hellman(-Merkle) Key Exchange
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!
If you want to learn more about the history of cryptography pioneers — check out talks by Diffie and Hellman (here and here), their articles (here and here) that reflect on the history and impact of their most influential article, or a book on relationships and marriage by Hellman and his wife, which includes many stories accumulated during his career.
This article was written by Tamara Finogina (PhD), Cryptography Researcher at Scytl.
¹An entirely new idea even for classified researchers at GCHQ — UK’s intelligence agency — who years later claimed to work on public key exchange or non-secret encryption as they called it.
LINK: https://cryptocellar.org/cesg/ellis.pdf
²As Diffie remarked: “we took what Merkle had done, and produced a solution to it in a different way”[1]. In the fall of 1974, a UC Berkeley undergrad, Ralph Merkle, started investigating ways to establish secure communications over insecure channels[3]. His research finally[2] resulted in a publication in 1978, which became known as Merkle’s Puzzles[4].
[1] https://www.youtube.com/watch?v=1BJuuUxCaaY
[2] https://www.ralphmerkle.com/1974/
[3] https://people.scs.carleton.ca/~paulv/papers/society-impact-of-pkc-v4.pdf
[4] https://www.ralphmerkle.com/1974/PuzzlesAsPublished.pdf
³Not every number can be a generator. Only numbers called primitive roots modulo p can be generators for the group Zˣ_p. However, this is where the definition gets recursive — primitive root modulo p is defined as a number that … generates the group Zˣ_p. There is no simple formula to find it — the problem is still unsolved[1]. So, in cryptography, we prefer using a subgroup of Zˣ_p. In particular, we select p = 2q + 1, where both p and q are primes. Then, use only elements x from Zˣ_p such that x 𐞥 mod p = 1 (aka group membership test). Each number that passed the test belongs to our subgroup (usually called G_q). We can guarantee there will be only q such numbers. However, the best part is that every number from our subgroup is a generator, so the problem is avoided!
[1] https://cosec.bit.uni-bonn.de/fileadmin/user_upload/publications/pubs/gatshp98a-www.pdf
⁴Names obligatory for any cryptographic protocol explanation https://en.wikipedia.org/wiki/Alice_and_Bob#cite_note-rfc4949-1
⁵We can also re-word the DL problem and say that we need to find x such that gˣ = a for some integer a. If DL problem is hard, then finding x is hard.
⁶The assumption is formally stated as follows: For a cyclic group G of order q, given tuple (g, gᵃ, gᵇ) for a randomly chosen generator g and random a, b ∈ {0, …, q — 1}, it is computationally intractable to compute the value gᵃᵇ.
⁷The assumption is formally stated as follows: For a cyclic group G of order q, the value gᵃᵇ for a randomly chosen generator g and random a, b ∈ {0, …, q — 1} “looks random”, which means the tuple (g, gᵃ, gᵇ,gᵃᵇ), it is indistinguishable from (g, gᵃ, gᵇ,gᶜ) for a randomly chosen value c.
