Diffie and Hellman discovered it was possible to remedy the problem of key distribution. But it took too long to do, and so a search was made for a solution that could operate more quickly. Eventually Public Key Cryptography was invented, started by Diffie and finished by Rivest, Shamir and Adleman.
The crucial part of the system was that one key was used to encode the message, and a different key could be used to decode it, such that the decoding key could not be worked out from the encoding key. Each person on the Internet can have their own set of two keys, and freely publish the encoding key. Therefore, if I wanted to send my friend Paul an encoded message, all I would have to do is to look up his encoding key, code the message using it, and when Paul receives it he can decode it using his key. Even with his mother tapping the phone lines, if she knows both the message and the encoding key, she cannot decode the message without Paul's decoding key. Since Paul never needs to send this to anyone, his mother cannot intercept it.
For this to work, there was a need for a special one-way function. The function should be easy to perform in one direction (encoding) but so hard to perform in the reverse direction (decoding) that it was effectively impossible. This function would be the public encoding key. Then there needed to be a way that the reverse function (decoding) could be made simple with one extra piece of information. This is the secret private key.
For example, imagine Paul wants to send a message to me. He knows that my encryption method (like the public encryption key) is to write the message on a piece of string, thread it through one of my needles, and throw the needle into a big haystack. The message is safe, since trying to find it is like looking for a needle in a haystack (!). It's possible, but very hard and time-consuming (like trying to decode the message without the secret private decryption key).
However, I know the secret key, which is that my needles are all made of iron. So I can use a big magnet and find the needle in no time and retrieve the message. Anyone can drop messages to me in the haystack, and only I can find them. No-one else need ever know how I do it since I never tell anyone that they are iron needles.
The only other way to find the needle is the brute-force method, by getting a whole hoard of people rummaging through the haystack until it is found. As long as I use a big enough haystack and a small enough needle, no-one but I will ever retrieve my needle except for me.
After a long time searching, such a function was found, which depends on modular arithmetic and factorisation into prime numbers. This was developed into RSA.
RSA is much slower than DES (100 to 10000 times slower, depending on how much of the DES procedure is implemented in hardware rather than software). This is its only major disadvantage compared to DES. This is not a huge problem though, as this is largely overcome with the Pretty Good Privacy system.
The security of RSA is second to none, which is why it is the accepted standard on the Internet, as well as in military and government codes. As long as the prime numbers used are big enough, it takes too long to factor them by brute force, and there is no other known way. However, in The Code Book by Simon Singh, he gives his readers a challenge of ten codes to break. The tenth, and hardest, of these, is one encoded with RSA of a standard comparable to that of various banks. In October 2000, after just over a year, a group of Swedish jugglers broke the tenth and last challenge. They had no more access to computing power than many of the public, so it is likely that banks may be reconsidering the size of prime numbers that they are using, and increasing them.
The only known way to break RSA successfully is to attempt to guess certain parts of the message, and decode from there. If a fragment can be solved, the rest follows fairly easily. This is generally prevented by the addition of some random data into the encrypted text.