Public Key Encryption

Public Key, or two-key encryption, is based on a mathematical phenomenon developed by three mathematicians at MIT. The formula is given below. However understanding what public key encryption can do does not depend on understanding the formula as much as the following principle.

Notice that a number can represent a message. Each character of the message can be represented by one or two bytes of computer memory. For example, the number 65 represents capital 'A' in common usage. A string of bytes can represent a phrase of words, or a long number depending on how you interpret it. Operating on that number with one key of a pair creates a number that is called the encrypted message, because the second key can convert it back to the original number.

How it is used:

for confidentiality
To keep wrong eyes from reading message: The message is encrypted with the reader's public key and sent. If intercepted along the way, nobody else can read it because only the reader's private key can unlock it.
for integrity
To be sure message hasn't been tampered with to change its text: The message is signed by the sender. This involves a checksum or some other summary of the message (e.g. add up the numeric values of all the characters) which is then encrypted with the sender's private key. The reader performs the same checksum or summary on the message receiveed, then uses the sender's public key to find the checksum/summary number they sent with the message. If the checksums match, the message is intact.
for authentication
To be sure message is really from the sender: If the sender's true public key is known, the message is simply encrypted or signed by the sender and sent. The reader decrypts it with the public key, which proves only the sender could have sent it.
The tricky part is getting the sender's public key if not already possessed. Otherwise a counterfeit sender could send a message along with their own public key purporting to be from the true sender. In this case, the true sender should send their public key in a certificate.
A certificate is a message that contains the sender's personal information such as name and e-mail address, along with their public key, which is signed by a trusted authority. Certificate authorities such as Veri-Sign do this for a fee. The reader's e-mail program or web browser comes with some trusted certificate authorities' public keys hard-coded into the program, so if the certificate authority really signed it, the program can decrypt it and trust it.
for non-repudiation
So the sender can prove they sent the message and it was received: The recipient's program signs the message received with a date/time stamp and automatically sends it back to the sender. The sender decrypts that returned message with the recipient's public key. If it works, the true recipient recieved the message.
secure World Wide Web connections
To exchange data over a web connection without danger of eavesdroppers intercepting it: Web browsers use a Secure Sockets Layer (SSL) protocol. The browser and the server both know a conventional encryption protocol that is faster than two-key encryption. For a trivial example, they could say "Add number x to the first byte of the message, y to the second, z to the third, then repeat the sequence for the whole message." In order to work, though, they would have to agree on what numbers to use for x,y, and z. (In real life the code is more complex, of course.) In SSL, one computer makes up a number to use for the secret code and encrypts it with the other computer's public key. Once they both know the secret code, they proceed with encryption "on-the-fly."

The formula:

The operation that encrypts a number is:

(T^E) mod PQ

where T is the original text (number)

P and Q are large prime numbers

mod is modulus (remainder after division)

E is a number less than PQ such that E and (P-1)(Q-1) have no prime factors in common.

Similarly, the operation that decrypts the encrypted number is:

(C^D) mod PQ

where C is the encrypted text (number)

D is a number such that DE divided by (P-1)(Q-1) has a remainder of one.

The public key consists of the number E and the product PQ. The private key is the number D (and of course PQ, which is publicly known). An in-depth discussion of this mathematics is available at Francis Litterio's website, http://world.std.com/~franl/crypto/rsa-guts.html. More information is available at RSA Security's FAQ collection on digital security topics, including two-key (RSA) encryption.