Background

"Move closer to your radio kids, it's time for Little Orphan Annie's secret message. Get your decoder rings ready!"

Secret messages have long been the domain of children and spies, but in today's electronic world, cryptography has become increasingly important. From email to bank transactions to cellular communications, the need for privacy has driven the (sometimes hotly debated [see the many articles related to "The Clipper Chip" in WIRED and other magazines]) issue of encryption. Furthermore, the development of public key encryption has placed the ability to secure communications in the hands of the private citizen.

Cryptography is the study of methods of sending messages in disguised form so that only the intended recipients can remove the disguise and read the messge. The message to be sent is called plaintext and the disguised message is called the ciphertext. The text is written using some alphabet which, particularly in modern encryption, is rewritten in numerical form (e.g., A=01, etc.) In addition, the text is usually encoded in blocks of letters. In most encryption systems, the encoding and decoding depend on some key.

For example, Little Orphan Annie would encrypt a message using the (popular, but not very secure) method of shifting each letter of the alphabet by a fixed amount. This amount would then be the "key" for the encryption. If the key was four, then AE, BF, ..., ZD. Note the "wrap around" at the end of the alphabet. This is an example of modulus arithmetic (Z=26+4 4=D (mod 26).) Modulus arithmetic is sometimes called "clock arithmetic" since clocks serve (mod 12 or 24) as an everyday example of using a modulus. More on modulus arithmetic later.

See if you can decode this message.

OCTYV JZFC ZGLWETYP!

Click here for a hint
Click here for the answer

Although the previous example and method of encryption are very simple, it forms the basis of what have been some very popular encoding methods. For example, the "Vigenère cipher" was a popular variation of this method.

In the Vigenère cipher, instead of shifting individual letters, the message is first grouped into blocks of text and these blocks are shifted, where letters within these blocks are then shifted by varying amounts. In mathematical terms, each block is a vector, or n-tuple, of letters, and the key is a vector of shifts.

Modern computers have rendered these, and many other coding methods, useless for secure communications. For example, for messages encrypted using a shift key, it is very easy to generate all possible shifts until the proper key is determined. In addition, these coding methods are flawed in two basic ways: (1) It is necessary to have a secure channel or method of passing the decoding key. If a third party intercepts the key, the code is useless; and (2) Positive identificaton of the sender cannot be guaranteed. It is possible for someone to send an encoded message to oneself and claim (say, to cast aspersion on someone else) it is from a third party. It is these weaknesses that public key encryption addresses.

For further reading on the history and present state of cryptography, see the excellent book by David Kahn [1], or one of the Web sites given in the References.