Geocaching

About This Series

The first nine caches in this series will help you build your puzzle-solving skills. Each one contains a lesson focusing on a specific skill, examples of how to use that skill, an exercise to test that skill, and a cache to find as a reward. Study the lesson, complete the exercise, and you'll find the location of a geocache.

Each of those caches contains a piece of information you'll need to take the final exam (the tenth cache in the series). Bring some way of recording those clues for later ... paper and pen/pencil would come in handy, or perhaps a camera. (A hammer, chisel, and very large rock would work but probably wouldn't be very handy.)

Lesson 7: Cryptography

Introduction

For as long as there has been communication, there has been a need to share information privately. Ciphers have been used by government officials, military officers, spies, ambassadors, revolutionaries, business owners, religious leaders, and more. Even the Kama Sutra discusses the use of ciphers to help women conceal the details of their liaisons, listing secret writing as #45 in the list of 64 arts that women should study (along with cooking, dressing, massage, the preparation of perfumes, conjuring, chess, bookbinding and carpentry).

This lesson will not teach you enough to become a codebreaker for the NSA. But it will hopefully give you a head start in turning a bunch of nonsense into a set of coordinates. By itself, it won't teach you everything there is to know about every cipher, but it will hopefully get you thinking about ciphers the right way and will give you pointers to resources to use in solving cryto puzzles.

What Is Cryptography?

The word cryptography is derived from Greek words meaning hidden and writing – it is the study of message secrecy.

Encryption is the conversion of ordinary information (plaintext) into unintelligible gibberish (ciphertext). Decryption is the reverse, moving from ciphertext to plaintext. A cipher is a pair of methods for encryption and decryption.

The detailed operation of a cipher is controlled by both the cipher method and by a key. A key is a secret parameter to the cipher, known only to the sender and the intended receiver of an encrypted message. (Yes, I know that's not exactly true about public key algorithms, Mr. or Ms. Cryptography Expert. Sheesh.)

The method of solving a puzzle that involves cryptography is conceptually very simple: figure out the cipher, and figure out the key. The process of figuring out those two pieces of information and revealing the message is called cryptanalysis.

Classical vs. Modern Ciphers

A classical cipher is one that operates on an alphabet of letters and is typically performed by hand (with paper and pencil) or with simple mechanical devices (such as a scytale). Modern ciphers operate on bits and bytes and require specialized computer hardware and software. The overwhelming majority of ciphers you’ll find in puzzle caches are classical ones.

(Interesting Historical Tangent: Encryption software may also be considered a munition, as dangerous as weapons and military vehicles. Until 1996, encryption software could not be exported to other countries since U.S. Government International Traffic in Arms Regulations (ITAR) prohibited the export of anything stronger than 40-bit encryption. Unfortunately, 40-bit encryption isn't strong enough to protect information over the internet - the fact that the regulations were changed just as the internet was entering a rapid growth phase is no coincidence.)

Simple Substitution Cipher

A substitution cipher is very simple – replace every letter of the alphabet with some other letter or symbol. The key to this cipher is the mapping of one set of letters to another.

Caesar

The Caesar cipher is named after Julius Caesar, who made use of it to communicate securely with his trusted lieutenants.

Caesar used this cipher with an offset (key value) of 3. To encrypt a letter in a message, he would find the 3rd letter in the alphabet after the one he wanted to encrypt. A would become D, B would become E, and so on (and if he went beyond Z, he’d start over again at A).

A cipher wheel is a disc consisting of an inner and outer wheel with the alphabet written around the edge of both wheels. By turning one of the wheels by the offset value, For this reason, the Caesar cipher is often called “ROT” (short for “rotate”), and “ROT” is often followed by the offset amount. So Caesar's cipher would be called "ROT3". The cipher wheel shown below implements ROT7 (going from inside out) or ROT19 (going from outside in).

The hint in a cache description page is encrypted using a Caesar cipher with an offset of 13 (aka, ROT13). This value is convenient because the encryption and decryption methods are exactly the same – A encrypts to N, and N encrypts to A.

Atbash

The Atbash cipher substitutes each letter of the alphabet with the letter at the opposite end of the alphabet. For instance, A goes to Z, B goes to Y, C goes to X, etc. The name “Atbash” comes from its origins in the Hebrew language, where the letter aleph goes to tav, beth goes to shin, etc. The method can be used in any language that has an ordered alphabet.

Cryptogram

You’ve probably seen cryptograms in newspapers, near the comics and the crossword puzzle. A cryptogram is a puzzle consisting of a short quotation encrypted using a simple substitution cipher. The mapping from plaintext to ciphertext letters is random – there is no ordering to the ciphertext letters, like there is in the Caesar and Atbash ciphers. The puzzle is to figure out the mapping and reveal the quotation.

Pigpen

One of the more famous substitution ciphers that doesn’t use an alphabet is the Pigpen cipher (also called the Masonic or Freemason’s cipher). The key to this cipher is the arrangement of letters in a grid like so:

To encrypt a message, each letter is replaced with its symbol in the grid. For example:

Other Symbols

A substitution cipher doesn’t have to use just letters. Any set of symbols can be used, including:

• numbers, (A = 1, B = 2, etc. is very common),
• font symbols (other than letters and numbers),
• computer codes (such as ASCII or EBCDIC),
• pictures (I once solved a cryptogram that used photos of insects),
• barcodes (on the backs of packages or envelopes),
• Morse code (or -- --- .-. ... .   -.-. --- -.. .),
• semaphore flags (or clock faces),
• presses on the telephone keypad (2 is A, 22 is B, 222 is C, 3 is D, etc.),

and more.

Polyalphabetic Cipher

The fundamental problem with all simple substitution ciphers is that they can be attacked using a cryptanalysis method called frequency analysis. This is just a fancy way of saying “count the number of times each letter or symbol appears in the ciphertext”. The letter that appears the most is probably E, followed closely by T, A, O, I, and N.

Complex substitution ciphers were developed to foil attempts to break the code via frequency analysis. The goal of these methods is to try to get all symbols in the ciphertext to appear with roughly the same frequency.

A polyalphabetic cipher is one in which a single ciphertext letter does not correspond to a single plaintext letter. The letter A at one point in the ciphertext may decode to a completely different letter than an A at a different point.

Tabula Recta

If the cipher wheel is one of the primary tools used in substitution ciphers, then the tabula recta is one of the primary tools used in polyalphabetic ciphers. A tabula recta looks like this:

Vigenère

The Vigenère cipher is one of the most common ones which uses a tabula recta. The cipher requires the sender and receiver to agree upon a word to use as they cipher key. For example, suppose the plaintext to be encrypted is:

ATTACKATDAWN

The sender chooses a keyword and repeats it until it matches the length of the plaintext. For example, the keyword “LEMON” would give the full encryption key:

LEMONLEMONLE

Use the plaintext letters as the row and the key letters as the column. Then replace each letter in the plaintext with the corresponding cell from the tabula recta. For the first letter in this example, the letter at row A column L is L. Next, the letter at row T column E is X. After that, the letter at row T column M is F. The complete ciphertext is then:

LXFOPVEFRNHR

Autokey

Ironically, Vigenère did not invent the cipher that bears his name - it was actually invented by Giovan Batista Belaso in 1553. The cipher that Vigenère invented in 1586 is called the autokey cipher. Due to an erroneous attribution of credit in the 19th century, Vigenère's name is unfortunately associated forever with a much weaker cipher than the one he invented. The autokey cipher is sometimes called the "Vigenère autokey" cipher to distinguish it from the "Vigenère" cipher.

The autokey cipher is similar to the Vigenère cipher, but with a different method of constructing the key that makes the encryption method much stronger. Instead of repeating the key word over and over again, the key starts with the keyword followed by the plaintext message itself. So the key in the above example would be:

LEMONATTACKA

Enigma

Enigma is one of the most sophisticated polyalphabetic ciphers ever created. It was developed by the German military and used heavily during World War II. The tale of how the Enigma cipher was broken is a fascinating story to read.

An enigma machine consists of a set of 3 or more interchangeable rotors, rings of letters that can be placed onto the rotors in any of 26 positions, a plugboard that can be used to transpose one letter into another, a keyboard for entering plaintext letters, and a lampboard for reading ciphertext letters. The value of the key to a message encrypted with Enigma would be the specific rotors used, the number of rotors, the position of each ring of letters on the rotor, the starting position of each rotor, the connections on the plugboard, and a chosen key word. Pressing a letter on the keyboard would turn the rotors and cause a light on the lampboard to turn on, indicating the encrypted or decrypted letter.

Polygraphic Ciphers

A polygraphic cipher is one that uses groups of letters instead of single letters as the basic units of encryption. For instance, AA could be replaced with QJ, AB with RU, etc. With single letters in a simple substitution cipher, there are only 26 possibilities for how each letter is encrypted, but with two-letter groups in a polygraphic cipher there are 676 possibilities. This makes such ciphers much more difficult to crack.

Polybius Square

Some common polygraphic ciphers make use of an arrangement of letters known as a Polybius square. The basic square lists the letters in order from left-to-right and top-to-bottom (I and J are treated as the same letter), like this:

Tap Code

The tap code, which uses a Polybius square, has been used by prisoners to communicate by tapping on pipes or walls. To encode a letter, a prisoner would tap a number of times equal to the letter row, pausing, then a number of times equal to the letter column, then pausing again. So the word "THE" would be "tap tap tap tap (pause) tap tap tap tap (pause) tap tap (pause) tap tap tap (pause) tap (pause) tap tap tap tap tap".

Playfair

Playfair is a cipher that regularly appears in puzzle caches, cryptic crosswords, and a variety of other contexts. The Playfair cipher was not invented by Lord Playfair, but by his friend Charles Wheatstone.

While a standard Polybius square has the letters in left-to-right, top-to-bottom order, the Playfair grid begins with a key word (with duplicate letters removed), then followed by all remaining letters in the alphabet in order. The letter J is not used, and the letter J in the plaintext is replaced with the letter I before encryption. For example, the Playfair square using the word "CIPHER" as the key would look like this:

See the Wikipedia page on Playfair for details of how to use the cipher.

Four-square Cipher

The four-square cipher uses two key words and four Polybius squares arranged in a 2x2 grid. It is a very strong polygraphic cipher that corrects a relative weakness in the Playfair cipher. In Playfair, if AB encrypts to XY then BA encrypts to YX, so knowing one pair automatically gives you the other pair. In four-square, AB may encrypt to a completely different pair than BA.

Transposition Ciphers

A transposition cipher changes the position of letters in the plaintext to form the ciphertext. For instance, suppose the plaintext is:

EIGHTFOURSEVEN

One way to encrypt it is to write the plaintext evenly divided across three lines, like so (padding it with random letters at the end to make the lines even):

EIGHT
FOURS
EVENX

Now read the letters down each column to create the ciphertext:

EFEIOVGUEHRNTSX

Other patterns include spirals, alternating left-to-right and right-to-left rows, and more. Any pattern can work as long as the sender and receiver agree.

Book Cipher

A book cipher uses some lengthy text as an encryption key. Common texts include dictionaries, religious books (such as the Bible), government documents (such as the Declaration of Independence), and more.

A book cipher encrypts each letter in the plaintext by referencing the same letter at some position in the key document. To encrypt a plaintext letter, replace it with a set of numbers that can be used to locate the letter in the document. A triplet of numbers could indicate the page number, line number, and word number in the line.

Cryptanalysis

The ultimate goal of cryptanalysis is to reveal the hidden message. This means determining both the cipher and the key.

Experiment

Don’t be afraid to try anything. Most of your experiments will not yield the plaintext message, so don’t be discouraged just because one attempt didn’t work.

Guess the Cipher and the Key

The cache itself may have hints as to what the cipher and key are. In fact, it may tell you explicitly one or both of those things. If not, it might strongly suggest through hints as to what they might be.

Look for Pigpen, Morse code, and semaphore symbols – they’re easy to identify and tell you right away what the cipher and key are.

Guess the Plaintext

Remember the advice from the first lesson in this series: Begin with the end in mind. You ultimately want a set of coordinates, so look for ways in which that could be expressed. If you see two rows of letters, the first row might be the latitude and the second row the longitude. Try replacing the first or last letters of a row with “NORTH” or “WEST”. Look for “NORTH TWENTY SIX”, “NORTH TWO SIX”, or “TWENTY SIX DEGREES” in the first row … if the message was encrypted using a simple substitution cipher, that may give you enough information to unlock much of the rest of the key.

Look for Fragments of Plaintext

It is rare for cryptanalysis methods to yield the entire key and plaintext message all at once. Cryptanalysis usually involves piecing together fragments of the plaintext message slowly. Look for words or pieces of words to appear as you experiment. And try to find words or phrases you expect to appear, based upon what you think the message contains.

Short segments of plaintext that are known (or suspected) to appear in the ciphertext are called cribs.

Look for Words and Sentences

If the letters in the ciphertext appear look like badly spelled words, they probably are. A ciphertext with spaces, punctuation, and capitalization are all indicators that the message has been encrypted using a simple substitution cipher. Look for common words, such as single letter words like “A” and “I”, or three-letter words like “THE” and “AND”. Try replacing the letters in your ciphertext with those letters and see if any other words start to appear.

One way to add security to an encrypted message is to remove the spaces and punctuation and to capitalize all of the letters.

Perform a Frequency Analysis

Count the number of times each letter appears in the ciphertext. The most common letters in the English language are (in order of decreasing frequency):

E T A O I N S H R D L U

Replace the most common ciphertext letter with E, the next most common ciphertext letter with T, the next with A, and so forth. If that doesn’t work, try shuffling the T, A, O, I, and N letters around until the cleartext starts to make things that look like real words.

(Those letters should look familiar to you – they’re probably the ones you guess first when playing Hangman. And if they’re not, they should be.)

Look for Pairs of Letters

If the ciphertext consists of pairs of letters, that’s a strong sign it might be encrypted with Playfair. Also, if none of the pairs of letters contains a duplicate letter (such as “EE” or “QQ”), that’s another sign it might be using Playfair, since that cipher never generates a pair of duplicate letters. If the ciphertext is not grouped into pairs, try grouping it into pairs to see if there are any duplicate letter pairs or not.

Look for Groups of Numbers

If your ciphertext is made up of pairs or triplets of numbers, it is possibly a book cipher, especially if the ciphertext is related to a reference document in some way. Look for clues in the puzzle as to what the reference document might be.

Resources

Wikipedia's cryptography portal is an excellent starting point for looking up cipher information. Wikipedia also has an entire category devoted to classical ciphers.

There are a number of free online tools available to help you analyze and use all of these ciphers and more.

Exercise 7: Embassy Sweets

I'm still trying to figure out what went wrong.

Her name is Ingeborg, the daughter of the ambassador from Norwegia. As a duchess, she's 37th in line for ascension to the throne.

We met innocently enough, both wandering the racks at Borders. I'll never forget the first time I spotted her ... her long flowing flaxen hair, narrow face, pale skin, and infectious smile. It was love at first sight for both of us.

Our most recent date was heavenly ... the wine (Mocha Java Zinfandel), the food (northern Italian), the dessert (ice cream sundaes with hand-mixed fixins) ... we talked, we ate, we laughed. After dinner we poked our noses into the shops, as she was searching for a new coat to wear when she returned home for the winter. We even lazily fantasized about buying a house together some day as we walked on the beach hand in hand.

But that was weeks ago. I haven't heard from her since ... my phone calls are never answered, my email and voice mail messages are never returned. And she's never on IM anymore.

Yesterday morning, I found a strange note dropped through the mail slot of the door of my apartment. It smells of her perfume and is written in her careful hand. But I don't speak Norwegish, so I can't make any sense of it.

I've gotta run ... someone just rang the doorbell, and there's a black sedan in the driveway ... this doesn't look good for me ...

Once you finish this exercise, you might be ready to try to tackle this. Note: I said "might".