Public Key Cryptography

"In God we trust. Everybody else we verify using PGP!" - Tim Newsome.

Origins

The Public Key (PK) cryptosystem is one of the most recent and significant breakthroughs of modern cryptography. PK crypto was first publicly introduced by Whitfield Diffie and Martin Hellman in 1976. However, I have found sources stating that the PK cryptosystem may have originated elsewhere. For instance, Admiral Inman, a one-time director of the NSA back in the 1960's, may have secretly came up with PK crypto. Another source says that it could have came out of the GCHQ (Government Communications Headquarters), the follow up to Bletchley Park, in England during the late 1960's as well. These two other areas of the potential birth of PK crypto are not entirely surprising due to the secretive nature of secure communications during the Cold War.

Asymmetry vs. Symmetry

Instead of the symmetrical and conventional cryptography that deals with substitution and permutation and requiring a single key for both encryption and decryption, PK cryptography is based on number theory and is asymmetric. Although, one approach is not anymore superior in security than the other, PK crypto is a more robust way to ensure authentication, key distribution and confidentiality. The PK crypto attraction lies in the notion that the private key is never shared therefore unlikely to travel through a network to be intercepted, where as a session key could be intercepted. However, the down side to PK cryptography is that it's slower. PK cryptosystems can be primarily used for setting up sessions by encrypting and sending a session key and can also be used for short messages such as encrypting a credit card number, etc. The session key is then used for the secret key during a symmetric session. For instance, two parties wishing to secretly communicate can use RSA to encrypt a session key and then use perhaps Triple-DES to exchange messages.

Encryption/Decryption Process

Encryption and decryption involved within a PK cryptosystem simply consists of encrypting a message with a recipient's public key and sending it to the recipient. The recipient then decrypts the ciphertext with his/her own complementary private key. For instance, using the traditional Alice and Bob model, if Alice wants to send Bob an encrypted message Alice needs to use Bob's public key, which is in the public domain. When Bob receives Alice's encrypted message, Bob decrypts it with his own private key. The importance of this process is that the private key should be kept secret, i.e. it never has to be transmitted anywhere encrypted or not. The sending party doesn't even have to know the receiver's private key. A popular and easy example of this process is using freeware called PGP, Pretty Good Privacy, which is described below in more detail.

Authentication

Another nice feature of PK crypto is that it also provides the ability to authenticate. How does Bob feel confident that the message came from Alice? Well, Alice can digitally sign her message by using her private key to encrypt it and then Bob can decrypt it with Alice's public key confirming a match. The two keys are related so it would produce a valid plaintext message, where as if the message is invalid i.e. still looks like ciphertext, then it did not (supposedly) come from Alice. However, keep in mind that by only digitally signing a message does not ensure confidentiality. The message can be decrypted/verified by anyone since Alice's key is in the public domain.

The trick is to pull double duty as conceptually described in the figure below. Alice would digitally sign the plaintext message M by encrypting it with her private key S_A. She then would encrypt that with Bob's public key P_B. When Bob receives this encrypted message he would decrypt it with his private key S_B and then decrypt/verify it once more with Alice's public key P_A. This ensures both confidentiality and authentication.

Conditions

On a more cryptographic and complexity-theoretic note, the following conditions must be met:

1. Generating a key pair should be computationally easy.
2. Generating a ciphertext using the receiver's key should be computationally easy.
3. Decrypting a ciphertext using a private key should be computationally easy.
4. It should be computationally infeasible to get the private key with only the public key.
5. It should be computationally infeasible to get the plaintext of a ciphertext with the public key.

"My laptop and its PGP software provide me with a level of security that is beyond the combined efforts of all the world's code-breaking establishments" - Simon Singh.

PGP

PGP, which stands for Pretty Good Privacy, was developed in 1991 by Phil Zimmermann. During the early 1990's Zimmermann faced opposition from RSA Data Security, Inc. on patent infringements, and the FBI for exporting a potential weapon. Throughout the mid 1990's Zimmermann worked out a patent agreement with RSA Data Security, Inc., and Zimmermann's PGP gained way too much momentum worldwide for the Feds to do anything. Still to this day, there is very strong debate for and against widespread encryption. Both sides have legitimate reasons and it seems that those who support it are winning. However, with the unfortunate events on September 11, 2001, the pendulum is swinging back the other way. What ultimately tips the scales are the big corporations wanting to maximize every selling opportunity via the Internet. Overall, society ought to realize the importance of going either direction at anytime. If crimes unbearably increase then society ought to lean towards those who oppose widespread encryption, and vice-versa.

Anyway, PGP is a good example of a PK cryptosystem for exchanging secure e-mails. The techniques used within PGP were not new at its birth, but it was actually the first time that RSA, IDEA (International Data Encryption Algorithm) and digital signing, all combined into a friendly user interface, could be run on a personal computer. All of the intricate processes involved are ideally shielded from the user, thus the user can simply encrypt his or her messages with a few entries and mouse clicks. PGP is free and is actually a fun way to communicate with your friends with a real encryption experience. Of course, PGP provides a means for authentication by digitally signing encrypted e-mails. Furthermore, it comes with full and detailed documentation on how to use it. If you feel that you need more privacy with e-mail for (hopefully legitimate) reasons you see fit, then as a suggestion, go ahead and download it from: http://www.pgpi.com.

Links

http://www.pcwebopaedia.com/TERM/P/public_key_cryptography.htm
http://www.nwfusion.com/info/idginvite.htm
http://www.faqs.org/faqs/cryptography-faq/part06/
http://world.std.com/~franl/crypto.html