Codes with Two Keys

NPS Discovery Day workshop by David Canright

For millennia, people have needed to keep information secret. One way to do this is to write it down in some kind of code or cipher. This workshop concentrates on a modern way to do this, called Public Key Encryption, that is widely used for secure communication over the Internet and elsewhere. But first some general background...

Caesar's Cipher

Julius Caesar needed to send commands to his troops in a way that the enemy could not read if the message were intercepted, so Caesar invented a cipher. It works by shifting the alphabet by some specified amount. For example, if you choose the letter G to be the key, then you shift the alphabet by 6 letters, so A becomes G, B becomes H, C becomes I, etc., up to T becomes Z, then it "wraps around" so that U becomes A, V becomes B, etc., until finally Z becomes F. Using this cipher, the message COME BACK TO ROME
becomes
IUSK HGIQ ZU XUSK The cartoon below has a Caesar-ciphered caption, using two keys, one for each sentence! See if you can figure them out... The Caesar Cipher SlideRule [PDF graphic, or EPS file] may make it easier.

...xt xmj ywnji yt gwjfp nsyt ymj kfymjw gjfw'x htruzyjw, gzy ny bfx ytt mfwi. Jxud ixu jhyut je rhuqa ydje jxu cejxuh ruqh'i secfkjuh, rkj jxqj mqi jee uqio...

Apologies to Sidney Harris, the author of the original cartoon.

The Gold Bug

My first introduction to ciphers was in the story "The Gold Bug" by Edgar Allan Poe. There the key to finding a pirate's buried treasure involves solving a cipher (where each letter is replaced by a symbol) that is written in invisible ink on parchment. The story presents it as follows:

The following characters were rudely traced, in a red tint, between the death's-head and the goat:
53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!
83(88)5*!;46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-
4)8`8*;4069285);)6!8)4++;1(+9;48081;8:8+1;48!85;4)485!
528806*81(+9;48;(88;4(+?34;48)4+;161;:188;+?;
"But," said I, returning him the slip, "I am as much in the dark as ever."

The story goes on to tell how the hero figures out which symbol is which letter, based on how common different letters are in English (hint: E is most common). Read the story to find out what the hidden message is.

Other Codes

Codes (where words or phrases are replaced by other words) and ciphers (where letters are replaced by other symbols) have been particularly important in international intrigue and military applications. In World War II, the Germans used a complicated machine to produce the "Enigma Cipher"; this machine involved several rotating disks, changing the key in unpredictable ways each letter. But a team of British scientists, including Alan Turing, managed to crack the code.

Public Key Encryption

One weakness of standard codes is the need to communicate a secret key to the recipient. If the key gets intercepted, then the code is broken. A modern approach to this problem is called "public key encryption" (or PKE). Here, a code depends on two keys in such a way that a message encoded using one key can only be decoded using the other key. So a person (say Alice) creates a pair of keys. She tells everybody one key (the "public" key). Then when someone else (say Bob) wants to send Alice a secret message, Bob encodes it using Alice's public key. Even though everyone knows Alice's public key, that does NOT work for decoding the message. Since only Alice knows the other key (the "private" key), then nobody else can decode the message on its way to Alice, but then Alice can decode it using her private key. This way, the secret key never needs to be communicated!

A second application of public key encryption is to encode something using your own private key. Then it would not be secret, because anyone who knows your public key can decode it, but that's not the point. The point is that whoever reads it knows that only you could have sent it, because only you know the secret key. In this way, you can "digitally sign" a message so people know it's from you. (This is called "signature verification".) Of course, these two applications can be combined, so you digitally sign (with your private key) and then encode your message to Bob (using Bob's public key). Then nobody else can read it, but Bob can decode it using his private key, and check your digital signature using your public key. Yes, it all sounds complicated, but modern software automates most of it...

This type of encryption (coding) has become popular for electronic communications. For example, if I want to buy a "PKE Rules!" sweatshirt from the online site "Encryption Unlimited" (names changed to protect the innocent), then my computer sends its own public key to the online site, and then the online site sends back its public key, at which point the two computers can send digitally signed encrypted messages to each other that only the other can read, such as credit card numbers... This results in pretty secure transactions; even if someone tries to read the messages going back and forth, they can't figure them out because they don't have either private key.

I developed a simple DOS demonstration program called PKE to show how this works. This program makes it easy to create pairs of keys, share the public key with your friends, and encode and decode short messages using one key that can only be decoded using the other key. (Warning: this is a "toy" version of encryption, which any real cryptographer could crack easily because the keys are so small; for serious encryption, see below for real software. But it might be good enough to confuse your parents...) This program can also encode ASCII text files.

To install PKE, create a new directory for it and download the compressed program to it, then run pkecomp.exe to uncompress it. See the Help File for more details on using the program, or the How It Works File for the mathematics behind the method, or the About PKE File for general information. For those who are really interested, the source code is also available.

Here are a few links to cryptographic materials on the WorldWideWeb

If you want real encryption, use reputable free software such as
PGP from Network Associates (or from MIT),
or commercial software such as that from RSA Laboratories.

RSA has an extensive site including an excellent "Frequently Asked Questions" page:
RSA Laboratories - Cryptography FAQ

I first got interested in cryptography as a child from reading
"The Gold Bug" by E. A. Poe (a related site is The Edgar Allan Poe Cryptographic Challenge)

Here are some pages about cryptography in general:
Cryptography (from Trinity College, Hartford, CT)
Cryptography (by M. Saberi)

Here are a few related books

The Code Breakers by David Kahn, Simon & Schuster (1996)
The Expert by Lee Gruenfeld
The Transparent Society : Will Technology Force Us to Choose Between Privacy and Freedom? by David Brin

NOTE: All software made available through this page and subsidiary pages is supplied on an "as is" basis, with no warrantees of any kind. The author bears no responsibility for any consequences of using this software.

David Canright -- DCanright@NPS.edu