Diffie-Hellman.

"He spends much of his time in front of a computer workstation, but he looks as if he would be equally comfortable in a Bombay ashram." - Simon Singh, regarding Diffie.

The Diffie-Hellman key exchange was the first publicly known answer to having a secure means of exchanging keys efficiently without the sender and receiver meeting in person. During the early 1970's, Whitfield Diffie and Martin Hellman were among the very few who believed that such a process can exist. They focused on developing a one-way function. Sure enough, in 1976 at Stanford University, after many months of hard work they used a combination of exponents and modular arithmetic and defied the mainstream of cryptography at the time. Diffie-Hellman key exchange uses the concept of discrete logarithms. Discrete logarithms are all of the exponent indexes for a primitive root(s) of all of the integers between and including 1 to P - 1 for a modulo prime number P. That is, for a primitive root R raised to all powers of 1 to (P - 1) mod P there exist no integer results that are repeating.

Key Exchange

Let's say that Alice wants to send a secret key to Bob. Alice and Bob each select a random integer, say Alice picks X and Bob picks Y, such that 0 < X < P & 0 < Y < P, where P is some known and publicly agreed upon prime number. They each then compute a corresponding A and B integer value in conjunction with some known and publicly agreed upon primitive root of P called R, for instance, A = (R^X) mod P, similarly for Bob B = (R^Y) mod P. The randomly selected X & Y values are kept private, i.e. never even transmitted encrypted or otherwise, while the computed A & B values are public and exchanged and don't even need to be encrypted. Alice then calculates the key K = (B^X) mod P and Bob does the same by K = (A^Y) mod P; notice that Alice's version of K will equal Bob's version of K below. Ultimately, the key that both Alice and Bob calculates is K = R^XY mod P.

Example

P = 19 <-- Would be some very large prime.
R = 2 <-- This has to be a primitive root of P.

X = 8 <-- Alice privately & randomly chooses, where X < P.
Y = 11 <-- Bob privately & randomly chooses, where Y < P.

A = 2⁸ mod 19 = 9 <-- Where 9 is publicly sent to Bob.
B = 2¹¹ mod 19 = 15 <-- Where 15 is publicly sent to Alice.

Alice computes K_A = 15⁸ mod 19 = (2¹¹ mod 19)⁸ mod 19
Bob computes K_B = 9¹¹ mod 19 = (2⁸ mod 19)¹¹ mod 19

and as you can see K_A = K_B = K = 5 for both calculations. So, the significance is to have a large P.

Security

The strength in the Diffie-Hellman key exchange exists in the fact that the eavesdropper will never see the key in plaintext or even come across an encrypted version of it. The eavesdropper can see the other numbers namely the prime number, the primitive root and Alice's and Bob's public keys, but never Alice's or Bob's secret number because those secret numbers don't need to be transmitted. Thus the keys are only computed at the end points via a one way method. By only having P, R, A and B, the opponent has to compute the discrete logarithm and not the easy exponents mod a prime. The computation then becomes infeasible, hence the one-way process. The opponent would only know that A = R raised to some number mod P and likewise for B. The opponent also only knows that the key is equal to A raised to some power mod P and likewise for B, as in the following: [KEY?] = A^? mod P. The missing number is not enough information for the opponent given that A (as well as B) and P are very large. Currently, the only quickest known way asymptotically for computing discrete logarithms mod a prime integer is e^{((ln(P))(1/3) * ln(ln(P)))(2/3)} which is unfeasible for very large prime numbers.

Links

http://www.linuxjournal.com/article.php?sid=6131
http://www.rsasecurity.com/rsalabs/faq/3-6-1.html
http://networking.earthweb.com/netsecur/article/0,,12340_624441,00.html