One of the great things about working in maths or computer science is that if you’re the inventor or discoverer of a really nice piece of mathematical theory, it will often be named after you. Sometimes the things that get named after you end up overshadowing all your other work – John Conway, for instance, quickly got pretty sick of answering questions about Conway’s Game of Life, when it was only one of many things he’s worked on in his extensive mathematical career.

Whitfield Diffie and Martin Hellman, both winners of the ACM Turing Award (among many other prestigious honours) are both past visitors to the Heidelberg Laureate Forum, and valued contributors to the programme. Their names are well-known in cryptography classrooms the world over, because of their eponymous encryption system. But what is Diffie-Hellman Key Exchange?

Sending Secret Messages

In any communication system, it’s safe to assume that a malicious third party is capable of tapping your communications and reading the messages you’re sending back and forth. This means if you were to send your message in a readable form, they’d be able to intercept and read it. This means it’s necessary to encrypt your message.

There are plenty of simple ways to encrypt data – some of which are so simple, a child could use them (and I often did). For example, the Caesar (Shift) cipher is a simple form of encryption where you substitute each letter for one three along in the alphabet – A goes to D, B goes to E and so on. Suhwwb vlpsoh, kxk? It’s easy enough to apply the code to your message, but this kind of code is easily broken by a mildly intelligent interceptor.

A more secure method would be to use a key to encrypt the message. A Vigenère cipher uses a keyword applied to a Caesar cipher – so instead of shifting the alphabet along by three for every letter, it’ll shift it by a different amount for each letter in the message, according to a pre-agreed keyword. For example, if I used the keyword HEIDELBERG, I would shift the first letter in the message along by H (8) spaces, then the second letter by E (5) spaces, then I (9) and so on. The keyword is repeated as many times as needed along the length of the message.

While such a code can still be cracked, using a method called a Kasiski attack (roughly, this involves looking for repeated strings of characters in the message, and using them to determine the length of the keyword), it’s more secure than a simple shift cipher.

It also creates an interesting new challenge, which still remains a challenge when you move to more secure cryptography systems: if you need to agree on a keyword with your co-conspirator, and your only method of communication is via a tapped line, how do you communicate the keyword?

Exchanging Keys

Prior to the 1960s, any key information used in encoding secret messages had to be shared separately, in a private channel – or passed on a piece of paper. During the Second World War, the ‘unbreakable’ Enigma code was decoded partly due to intercepting enemy codebooks and key lists, containing the settings and codewords for each day, which gave the codebreakers huge insights into how to crack it.

Diffie and Hellman’s answer to this problem was public key cryptography – one of the first practical implementations of a cryptography system where the key could be shared on a public channel, without risk of interception by a third party. Based on mathematical ideas, it completely changed the way cryptography was conducted, and paved the way for further developments leading to forms of encryption still widely used today.

One simple way to understand the process is through modular arithmetic – calculating within a fixed range of numbers. For example, the numbers on a clock are 1-12, but if I asked you what’s four hours after 10 o’clock, the answer is 2 – you can wrap around. Modular arithmetic reduces each number to its remainder on division – for example, modulo 7, 12 is equivalent to 5, and 14 is equivalent to 0.

In Diffie-Hellman key exchange, two parties exchanging a message start by agreeing on a pair of numbers. One number is chosen as the modulus, which all the arithmetic will be conducted modulo, and the second is called the base. We’ll stick to standard cryptographical conventions, which is to say that our two messaging parties should be called Alice and Bob.

Alice and Bob publicly agree to use modulus 23, and base 5.

It’s important that the base is coprime to the modulus – that is to say, if you list all the multiples of the base (5, 10, 15, 20, 25…) and calculate them all modulo 23, they will run across all the possible values 0-23. This is equivalent to saying that 23 shouldn’t be divisible by 5, or have a common multiple less than 23×5 = 115.

Next, each of the two participants chooses a secret number, and raises the base to the power of their secret number: for example, Alice might choose a = 4, and Bob chooses b = 3, meaning Alice calculates 5⁴ mod 23 = 4, and Bob calculates 5³ mod 23 = 10.

Since all of this is modulo 23, there are any number of things Alice and Bob could have chosen to give the answers 4 and 10 – for example, if Alice had chosen a = 26, it would have given the same result – so it’s safe to communicate these two answers publicly, and it won’t give away what Alice and Bob’s secret numbers a and b are.

The next step relies on a clever bit of mathematics. If Alice receives Bob’s value for 5^b mod 23, and raises that to the power of her own secret number a, she’ll get 10⁴ mod 23 = 18. If Bob takes Alice’s value for 5^a mod 23 and raises it to the power of b, he’ll get 4³ mod 23 = 18. It’s not a coincidence that these values are the same!

In fact, it’s a property of this kind of modular arithmetic that in general,

(g^a mod p)^b mod p = (g^b mod p)^a mod p

This means that Alice and Bob both now know the number 18, and can use this as a secret key – for example, in our naive cipher system, this could mean using the 18th word from a text they both own (and they can publicly specify which text, since nobody intercepting will know they’re looking for the 18th word).

In reality, this kind of key exchange can be used for much more secure communications – the maths works at any scale, and it this is an example of a calculation that’s much easier for Alice and Bob than it is for a malicious attacker – raising a number to a power modulo a modulus is relatively easy to compute, but working out the numbers given the answers is in general a very hard problem (called the Discrete Logarithm Problem). Once your numbers are big enough (if your modulus is at least 600 digits long) even the faster computers can’t check all the possibilities in a short enough time to make it useful.

The shared values Alice and Bob calculated and sent (5⁴ mod 23 = 4 and 5³ mod 23 = 10) are called the public keys, and Alice and Bob’s secret numbers (a=4 and b=3) are called the private keys. Each public key set is only used once – since Alice and Bob’s calculation is computationally cheap, they can do it again easily by picking new private keys.

Diffie-Hellman-Merkle Key Exchange

Diffie and Hellman were the first to publish this idea, and did so in the early 1970s, although mathematicians at GCHQ had managed to prove this kind of system was possible in 1969 (but their work was classified and couldn’t be published until later). Diffie and Hellman are clear that their idea was based on a concept developed by Ralph Merkle, and they insist it should really be called Diffie-Hellman-Merkle key exchange.

It was rightly hailed as a huge breakthrough at the time, and some were even concerned that such a secure new system might be too much power to allow just anyone to use – in the late 1970s Hellman found himself in a fight with the NSA over whether he should be publishing his results in international journals, as written about by Ben Orlin following Hellman’s 2017 HLF talk.

On its own, Diffie-Hellman-Merkle isn’t perfect – without authentication (being able to prove that the person you’re receiving the message from is indeed Bob, and not an interloper pretending to be Bob) it’s possible for someone to send you their own public key in place of Alice’s, which would allow them to break your code. This is known as a man-in-the-middle attack, and using D-H-M as a basis, authenticated public key systems have been developed which prevent it.

The principles behind Diffie-Hellman-Merkle key exchange became the basis of RSA encryption – developed by Rivest, Shamir and Adleman, and using a slightly different type of calculation that’s even more difficult to undo (see: the Factoring Problem) – making it practically so difficult to crack that it might as well be impossible, given current computer technology. RSA is used widely for transmitting data securely, and this underlying mathematics has made it possible to build all the complex structures and systems we now rely on for finance, the internet and telecommunications all over the world. Thanks, Diffie and Hellman (and Merkle)!