Exchanging shared keys is not easy to do. In days gone by, these keys (oftentimes one-time pads) had to be exchanged in person - think of the spy in the movie with the briefcase handcuffed to the wrist - and this made the process unwieldy and generally unusable.
What was needed was a way to generate a symmetric key over a public channel, in scenarios where the parties wishing to communicate did not have any prior knowledge of each other. In doing so, some bits used to create the key could be publicly known, but mixed together with a private key that only the intended parties were privy to. The key was then used to securely encrypt the communications using a symmetric cipher. For a long time it was considered academically possible to publicly exchange keys for subsequent private communication, but it wasn’t until Whitfield Diffie, Martin Hellman and Ralph Merkle published their public key exchange algorithm in 1976 that the problem was considered “solved” (see the patent). Incidentally, it has since become known that the GCHQ had demonstrated the viability of public key cryptography in 1969.
Diffie-Hellman-Merkle (DHM) is commonly used to generate a shared symmetric key when using public key cryptography and is used by authenticated protocols such as TLS to provide for forward secrecy.
Here is the simplified DHM algorithm:
A, which is a calculation of a (small) prime number
graised to Alice’s private key
a, modulo a very large prime number
p. Generally, the larger the prime
pthe more secure the key (the modulus is the key space):
A = ga (mod p)
B, using the same primes
p, with his own private key
B = gb (mod p)
Each party then sends the other the result of their computations, i.e.:
- Alice sends Bob -> A = ga (mod p)
- Bob sends Alice -> B = gb (mod p)
Alice then does the same computation in Step 1 using modular exponentiation, raising Bob’s calculated result
Bto her private key:
s = Ba (mod p)
Bob then does the same computation in Step 2 using modular exponentiation, raising Alice’s calculated result
Ato his private key:
s = Ab (mod p)
Alice and Bob have now generated the same number
s, a shared key! They can now safely encrypt and decrypt their communications using this shared key with some symmetric key cipher.
I find this to be absolutely beautiful. It’s math, not magic. And you can trust it.
Incidentally, before DHM, the only groups that had access to military-grade encryption was, well, the military and the government. By putting the ability to encrypt our communications into the public domain, Diffie, Hellman and Merkle enabled citizens spanning the globe to retain a sense of privacy that is seen as a bug, and not a feature, of the Internet.