# Public Key Encryption

Public key encryption, discovered by Martin Hellman and Whitfield Diffie in 1976,
was created to solve the problems of traditional codes. Imagine Bob wants to
send a secret message to his friend Bill, but Kurt the Kracker, sorry, Cracker, wants to listen in.
Bob encrypts his message using a unique digital "key" (basically a really big
number1), and then sends the message off to Bill. Unless Bill knows the key,
he won't be able to read the message, and this is where the problem comes in.
How can Bob get the key to Bill without Kurt intercepting. Short of
meeting in the dead of night and exchanging the key by torchlight there's not a
lot they can do.

Idealy then, it would be best to have separate keys for encoding and decoding.
A "public" key could be given out which can only encrypt messages can be given
out far and wide, while a "private" key, one for decryption, would be jealously
guarded by Bob and given to no-one else. And that's what public key
encryption allows. But such a system is more difficult than it sounds, after
all, if you can encode a message, can't you just reverse the steps to decode
it?

The trick with public key cryptography is that the public key can be easily
calculated from a private key, but given only the public key, the private key
is immensely difficult to compute. Even with the fastest super-computers
working flat out it can still take many, many years to break it. A rubix cube
is a great example of this. Hell to solve, but very easy to mix up. With public
key encryption NP-Complete problems are used. These are a special bunch of
computer problems which computer experts think2 cannot be solved in a short
amount of time, and so can be adapted to generate the public keys from a randomly
chosen private one.

Although public key encryption is around 1000 slower than traditional encryption, the extra security is mostly considered well worth it, as there is much less chance of someone finding your key (since you keep it safe and protected somewhere on your hard drive, and don't ever give it to anyone). This extra security means that public key encryption is can now be used to "fingerprint" documents and emails, with a specially generated "signature" unique to the text. If the text is changed, or if someone tries to fake a message from scratch, then the signature won't match up to the document and the encryption program will sound the alarm. In most professional email clients today, an encryption program known as PGP can be used for this.

PGP (Pretty Good Privacy) is the most popular public key encryption program in the world today. Programmed by
Phil Zimmerman, it relies on the ultra-secure RSA cryposystem3, and is free

1Even a relativitly small key, such as one which is 128 bit, the number is still somewhere around the range of 300 million million million million million million (or 2 to the
power of 128 for any mathematicians out there).
2There may be an extremely clever way of solving NP-Complete problems but if
there is, it has been discovered yet (and computer boffins have been trying for
30 years!)
3Something the American NSA (National Security Agency) tried to hush up
because it was considered too powerful for ordinary people like me and you to
have!