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.
- Pairs of keys can be found such that:
- One key operates on a number (a message) to create an
encrypted number (message)
- Which cannot be reversed by any other operation using that
- But the second key can operate on the encrypted number to
reproduce the original number (message).
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
- 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 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
More information is available at
Security's FAQ collection on digital security topics, including two-key