In May 1975 Whitfield Diffie and Martin Hellman conceived of what is today called public-key cryptography. They published their ideas in November of the next year. Public-key cryptography is the breakthrough that has become the basis for essentially every secure protocol suggested since.

The problem that Diffie and Hellman addressed was that of key management. Designing secure algorithms for encryption was fairly well understood. The problem was handling the keys. Prior to Diffie and Hellman, two parties who wished to communicate securely would have to exchange keys in some manner. Typically this would be done either through a trusted third party, or via a separate secure channel. Both methods had drawbacks.

What Diffie and Hellman proposed was to use the concept of one-way functions. A one-way function in this context is one that is significantly more difficult to calculate in one direction than the other.

The slide shows the RSA algorithm, developed by Rivest, Shamir, and Adleman in 1977. By combining the difficulty of factoring a prime number with the ease of generating large prime numbers (using a probabilistic algorithm), a key could be split into a public and a private part.

Factoring primes is an old problem. Probably the first algorithm was by Eratosthenes (c.276 - 194 BC), a remarkable man who, other than having been librarian at the famous Alexandrian library, calculated the earth’s circumference with an error of 16.5%. It is generally believed that factoring will remain a very difficult problem, although there is no proof of this yet. 666*v