That's certainly the way it's often presented ("The Code Book" gives the history you describe), but there's an important omission. And I am a *serious* cryptogeek, so just take what I say as gospel, OK?
Diffie and Hellman's seminal 1976 paper, "New Directions in Cryptography", didn't just talk in the abstract about the possibility that we may someday be able to arrange secret communication over insecure channels: it presented the first protocol, Diffie-Hellman. Here's how it works.
First, we choose a big prime p. This prime needs to have some nice properties, but it's not a secret; if an RFC specifies a protocol is to use D-H, it might just specify what value of p to use directly, and everyone participating uses the same p. All arithmetic takes place mod p, so where you see "g^x" think "g^x mod p". At the same time, we choose a number g, which is usually small, like 2 or 3. (technical note: g must be a generator of the group Z*p.)
Now, you and I want to communicate, so we generate random secrets; I generate x and you generate y. We then calculate and send each other g^x and g^y. Now, I calculate (g^y)^x, and you calculate (g^x)^y, and we end up with the same number, g^xy. We can then use this as a cryptographic key for a conventional cryptosystem like Triple-DES (or Rijndael, these days). The easiest way known for the attacker to find g^xy given only g^x and g^y is to find the "discrete log" of g^x, where x = log_g(k) iff g^x =k And today, discrete logs are a hard problem if p is big enough.
So it was this protocol that turned established thinking on its head. With this protocol, two parties start with no shared secret, communicate over a channel where the eavesdropper can hear everything, and end up with a secret they can use to build a secure channel and cut the eavesdropper out. The publication of RSA brought PK technology a huge bound forward: it gave us public/private keypairs you could encrypt and decrypt with directly (ie real trapdoor functions), digital signatures, and a new fundamental problem (integer factorisation) that can sit at the heart of a PK protocol. But the popular perception is that Diffie and Hellman plucked the idea that such a thing might be possible out of thin air, and it ain't so: they had already shown that such seemingly insoluble challenges could be solved.
Paul Crowley aka ciphergoth. Crypto and sex politics. Diary.
[ Parent ]