The cache is not at the posted coordinates
About This Series
This series is based on the original puzzle solving 101 by ePeterso2. The first twelve 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.
When you check your coordinates, each cache will reveal a piece of information you'll need to take the final exam (the thirteenth cache in the series).
Lesson 05: Other Ciphers
Other ciphers is really a term that specifies "any cipher that is not a substitution cipher". This makes it a very large topic of which we can only scratch the surface here. This page will list some of the more common (and some less common) ciphers used in Calgary puzzles with tips to solve them.
General solving strategies
While each type of cipher has its own characteristics and thus its own way of solving, there are some general techniques that can be employed to help you narrow down the search space.
What cipher am I dealing with?
The first thing to do when dealing with a cipher is to determine what kind of cipher it is. Is it a substitution cipher (see Lesson 4) or is it something else? Sometimes there is a clue in the name of the cache hider (see Lesson 2), sometimes the title or the description provides a clue. Read the entire cache page carefully and highlight anything that looks a little weird. In a good puzzle, there are hints and clues that will either point you to the cipher or the key (or both). The worst (difficult?) puzzles only have a short piece of cipher text without any clue on what the encoding might be. Sure you'll be able to crack even that text, but it is less fun than a puzzle that has cleverly disguised hints.
If there is a reasonable amount of cipher text and you don't have a clue on where to start, there is a handy website that compares the cipher text against a long list of ciphers known to the American Cryptogram Association. Just drop your cipher text in the 'cipher' box and click 'Compare'. The most likely ciphers will be displayed at the top (the ones with the lowest numbers). This will help you narrow down your search!
Index of coincidence
Another hint on what type of cipher has been used can be derived from the Index of coincidence. This number indicates if the frequency of characters in the ciphertext is equal to that of plain text or if it is totally different. If it is equal, we're probably dealing with a substitution (mono-alphabet) or transposition cipher. If on the other hand the frequency is different we're probably dealing with a poly-alphabet cipher (the topic of this lesson). The index of coincidence is very useful in cracking the Vigenère cipher as we shall see.
Transposition ciphers
A transposition cipher shuffles the characters of the plaintext according to some predefined method, usually involving rearranging the letters into rows or columns and then taking them in a systematic way to transpose the letters. The article on wikipedia does an excellent job in listing out the most common variants of this type. It is interesting to see that a simple shuffling of the characters is still used in many modern computer ciphers. Naturally instead of characters they are shuffling bits but the principle stays the same. Some common transposition ciphers are:
Solving a columnar transposition
A columnar transposition cipher consists of three steps:
- Write the plaintext out in a predefined number of columns.
- Reorder the columns based on a keyword or key sequence
- Write each of the columns as the cipher text
With this knowledge of the construction of this cipher, one of the first things to do in solving it is to determine the column length. It would help to know if the cipher uses a complete (all columns are the same length), or an incomplete (different column lengths) variant. Usually the incomplete version is seen, but sometimes the message is padded with characters to make it complete.
For each possible number of columns, write out the grid (in column first order). Look for combinations of letters in adjacent columns that often go together like TH or QU. If you have found the correct number of columns, the remaining part of the cipher is anagramming the columns to find plaintext.
Let's try it out on this piece of text. The keyword is TAGE (German for "DAYS").
Since the keyword is 4 characters long and the message contains 15 characters, we need to do an incomplete columnar transformation:
- First we need to determine the column lengths for each of the columns. We will have three columns of four characters and one column of three characters since 3*4 + 1*3 = 15.
- To determine the original order of the 'long' columns, we need to look at the keyword. The longest columns will be on the left side of the keyword (first few characters), the shorter columns will be on the right side. For the keyword 'TAGE' this means that the T,A and G columns have four characters and the E column has three characters.
- We know from the encoding process that the message will be scrambled based on the keyword so instead of TAGE we should use AEGT for the column headings of the encoded message.
Write the message under the columns: (remember that the E column only has 3 characters)
AEGT
----
RDIF
YTSA
TGTU
R TA
Then reorder the columns:
TAGE
----
FRID
AYST
UTTG
ART
Now simply read the text row by row: FRIDAYSTUTTGART or "Friday: Stuttgart".
Fractionating ciphers
| |
1 |
2 |
3 |
4 |
5 |
| 1 |
F |
R |
A |
C |
T |
| 2 |
I |
O |
N |
B |
D |
| 3 |
E |
G |
H |
K |
L |
| 4 |
M |
P |
Q |
S |
U |
| 5 |
V |
W |
X |
Y |
Z |
A fractionating cipher divides a single character in the plaintext into muliple characters in the ciphertext. A simple example would be Morse Code where each character is translated in one or more dots and dashes. More advanced ciphers use a grid of 5x5 or more rows and columns. Usually this grid is initialized with a code word like the one shown on the right which is initialized with the word "FRACTIONATION" (double characters are ignored). Using the shown grid we can translate "HELP" into "33 31 35 42", which can be operated on further. When the fractionating cipher is combined with a transposition cipher, it makes it very difficult to determine which ciphertext characters make up one plaintext character. The bifid, trifid and ADFGVX ciphers all use this approach.
The bifid cipher
This cipher uses substitution, transposition and fractination and is very difficult to crack if you don't have the key. The encoding is relatively straight forward. Say we would like to encode "MONDAY: HILFE" ('hilfe' is German for 'help') using the 5x5 grid shown above and a period of 7:
We then write the coordinates of the plaintext characters:
M O N D A Y H I L F E
4 2 2 2 1 5 3 2 3 1 3
1 2 3 5 3 4 3 1 5 1 1
No we read the numbers per group, top row first:
42 22 15 31 23 53 43 23 13 15 11
Finally use the grid to translate the numbers back to characters:
To decode, write the characters out in their period, convert them into numbers, regroup the numbers and finally look up the numbers in the grid. Let's give it a try with the following text, assume it also uses a period of 7:
Step 1: regroup the message according to the period
Step 2: look the characters up in the 5x5 matrix and put the indices under the characters
C K I Z V U K H F E I A G
14 34 21 55 51 45 34 33 11 31 21 13 32
Step 3: write the indices vertically (per group)
1434215 331131
5514534 211332
Step 4: read off and regroup the indices:
15 45 31 44 25 13 54 32 31 11 13 33 12
The final step is to look these indices up in the 5x5 matrix which gives "TUESDAYGEFAHR" or Tuesday: Gefahr (German for Danger).
The trifid cipher works the same, but has three coordinate indices. It uses a 3x3x3 matrix which can hold 27 characters.
The ADFGVX cipher
| |
A |
D |
F |
G |
V |
X |
| A |
Z |
D |
2 |
0 |
J |
3 |
| D |
P |
9 |
8 |
7 |
E |
W |
| F |
C |
5 |
S |
Y |
M |
N |
| G |
K |
L |
F |
O |
G |
H |
| V |
V |
1 |
A |
I |
T |
Q |
| X |
B |
U |
6 |
X |
4 |
R |
The ADFGVX cipher uses only the characters A, D, F, G, V and X (hence its name). Those characters were chosen because their Morse Code is entirely different, making it difficult to make transmission mistakes. The cipher is an extension from the ADGVX cipher which uses a 5x5 grid or 25 different characters. Adding one more character allowed the encoding of 36 characters, enough to get the alphabet and the numbers in. This allowed a significant shortening of the messages, which makes the cipher more secure.
Like any fractionating cipher, the plaintext is first converted using the 6x6 grid. The grid can be initialized with any keyword or (like we did on this page) just with a random sequence of characters. For this encoding we used the sample matrix shown on the right:
C O M E A N D G E T M E
FA GG FV DV VF FX AD GV DV VV FV DV
Then the message is encoded using a transposition cipher. Let's say we used the keyword GEOCACHE (removing double characters):
G E O C A H
-----------
F A G G F V
D V V F F X
A D G V D V
V V F V D V
Now we need to sort the letters in the transposition key:
A C E G H O
------------
F G A F V G
F F V D X V
D V D A V G
D V V V V F
Finally we can read the cipher text off in columns: FFDDG FVVAV DVFDA VVXVV GVGF. To decode, just reverse the steps. Give it a try with the following message. Use the 6x6 grid as shown above and the keyword 'HILFE'. One caveat: since the message has 28 characters and 'HILFE' has 5, you're doing an incomplete columnar transformation (see above). With 28 characters and a 5 character keyword, there are 3 columns of 6 characters and 2 columns of 5 characters. Use the example in the transposition cipher section to help you do the decoding for this cipher.
AVVAV VDDDF DDFFG VXFFF DADXA GVA
Poly-alphabet ciphers
A 'simple' substitution cipher uses one (scrambled) alphabet. Each plaintext character is translated into only one cipher character. This property makes this kind of cipher extremely vulnerable to frequency analysis. The invention of poly-alphabet prevented that since it used multiple alphabets, each one in a different order. It would take a few hundred years before cryptographers had again caught up and developed methods to crack those ciphers. One of the most well known ciphers of this sort is the Vigenère cipher which is used in some Calgary crypto puzzles.
The Vigenère cipher
The Vigenère cipher was not invented by Blaise de Vigenère. Instead it was invented by Giovan Batista Belaso. Vigenère did make the cipher popular though. The cipher is an extension of the simple substitution cipher. Instead of a single alphabet it uses many alphabets, given in the next tableau:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
To encode the text "HELLO DARLING" with the keyword "ROSE" find the letter of the key in the left column and the letters of the plaintext in the top row. The cipher character is at the intersection of the column and the row.
Plaintext: HELLO DARLI NG
Key: ROSER OSERO SE
Ciphertext: YSDPF RSVCW FK
Here you see the biggest weakness of the cipher: the keyword is repeated. For each character of the keyword a regular substitution cipher is done which can be broken by frequency analysis. The first thing a cryptographer does is to determine the keyword length. This can be done by using the Index of coincidence. A good approach for repeating-key ciphers is to copy the ciphertext into rows of a matrix having as many columns as an assumed key length, then compute the average index of coincidence with each column considered separately; when this is done for each possible key length, the highest average I.C. then corresponds to the most likely key length. As this is a lot of calculations, there are applications and websites that can do this for you. Take a look at this website. It allows you to calculate the I.C. for various period lengths.
A stronger variant of the cipher is Autokey (which was invented by de Vigenère). In this version the entire plaintext message is used to encrypt itself:
Plaintext: HELLO DARLI NG
Key: ROSEH ELLOD AR
Ciphertext: YSDPV HLCZL NX
In this variant the key is not repeated, making the discovery of the key a lot harder. The key to cracking this cipher is that the key is plain text. Using this property one can search for common words like 'the' and see if that encrypts into something sensible. Try decoding the next message with keyword DANKE ('thank you' in German):
Polygraphic substitution ciphers
The biggest weakness of substitution ciphers and to a lesser extent poly-alphabet ciphers, is their susceptibleness to frequency analysis. The polygraphic substitution ciphers work on groups of characters at a time instead of single characters as with the mono- and poly-alphabet ciphers. Examples of these are Four Square, Playfair and the Hill cipher. Wikipedia has excellent descriptions of how each of these ciphers work.
Homophone ciphers
The homophone cipher is another attempt to counter breaking the cipher with frequency analysis. With a homophone cipher one plaintext character can be mapped onto multiple cipher characters. The most frequent characters will be mapped to the most cipher characters to minimize the vulnerability to frequency analysis. For instance we can take the frequency of characters in English and translate it in the following table:
A 9 12 33 47 53 67 78 92
B 48 81
C 13 41 62
D 01 03 45 79
E 14 16 24 44 46 55 57 64 74 82 87 98
F 10 31
G 06 25
H 23 39 50 56 65 68
I 32 70 73 83 88 93
J 15
K 04
L 26 37 51 84
M 22 27
N 18 58 59 66 71 91
O 00 05 07 54 72 90 99
P 38 95
Q 94
R 29 35 40 42 77 80
S 11 19 36 76 86 96
T 17 20 30 43 49 69 75 85 97
U 08 61 63
V 34
W 60 89
X 28
Y 21 52
Z 02
Although the message below contains multiple characters 'S', none of the numbers are the same. Try decoding the message given the table above.
76 63 66 79 33 52 34 46 35 96 61 13 23 75
Book ciphers
Another technique to counter frequency analysis is to use a book as the alphabet. Each plaintext character is replaced by the location of that character in the book. Depending of the size of the book or key text, this cipher is a variant to the homophone cipher. The cipher is characterized by the use of numbers. They can be single numbers (like offset into a text) or a combination of numbers (Chapter x, paragraph y, character z).
Try decoding the next message yourself using the text of the previous paragraph:
40, 1, 4, 15, 7, 99, 35, 34, 6, 13, 2, 200, 37, 38
Resources
There are many more classical ciphers and to describe them all would make this page even longer. The examples might have given you some motivation to learn more about the exiting world of codes and ciphers. Some useful resources that might help you on your way are listed below.
Practice Puzzles
Calgary has many great cipher puzzles that allow you to fine tune your skills. A few of the challenges are:
Puzzle 05: Beep-Beeeep Beeeep-Beep-Beep
The date is April 24, 1918. It was late at night when Lieutenant Georges Painvin suddenly heard the telegraph make the beeps he came to love and hate. He hated them when he could make no sense of the message, but with each new transmission he became more and more familiar with the cipher. The lives of thousands of people depended on his efforts to crack this code! He quickly grabbed his notepad and began to jot down the sequence of dots and dashes that the telegraph was putting in his ear.
-.. -..- -..- -.. ...- ...- ...- -..- --. -.. --. --. -..- ..-. -..- --. ...- ..-. --. ...- ...- ...- -.. -..- -..- --. -.. .- -.. ...- --. -.. -.. -..- ...- -.. ...- -..- --. -..- .- ...- ...- --. ...- -..- --. -..- --. --. -..- -..- ...- --. --. ...- ...- -.. -..- -.. ...- --. ...- -..- ...- -..- -..- ...- -..- --. --. .- .- -..- ..-. ...- ...- --. ...- --. .- -.. --. ...- ...- -..- ..-. -..- --. .- --. ...- .- -..- ..-. ..-. .- --. ...- --. --. ..-. --. -.. ...- ...- --. ..-. ..-. -..- .- -..- -.. -..- -.. -..- ...- -.. -.. ...- -.. ...- ..-. -.. --. --. --. -.. -.. --. ..-. ..-. .- -..- ...- ..-. ...- ..-. -..- -.. ..-. -.. -..- ..-. --. -..- ..-. ..-. -..- --. -..- ...- --. -..- -..- ..-. -.. ..-. -.. ...- ...- -.. .- -..- ..-. -..- --. ..-. ...- -..- --. ...- .- ..-. ...- -..- ...- .- -..- -.. ..-. -.. -.. ...- -.. -..- --. .- ...- --. --. -..- ..-. -..- --. ...- ...- ...- -..- -.. --. -..- --. -..- --. ...- -..- ..-. --. -..- ...- -..- -.. ..-. ...- -..- ...- ..-. -..- ..-. ...- -..- --. --. --. ...- .- ..-. -.. -..- ..-. -.. .- -..- -.. -.. -..- .- -..- -..- --. --. -.. ..-. -.. -..- ...- .- -.. -.. --. ...- .- --. ..-. --. ..-. ...- -.. ..-. ...- ...- -.. -..- ..-. --. ..-. ..-. -..- ..-. ..-. --. --. --. -..- ..-. -..- -.. ..-. ..-. --. ..-. --. --. -.. -.. ..-. ...- ...- -..- ...- --. --. ...- --. --. -..- ...- ...- -.. -.. --. -..- -..- --. -..- ..-. ...- ..-. -..- .- ..-.
As soon as the transmission had stopped, George went to work. He had recently discovered that the Germans rotated their keys and had a different key for each day of the week. He was confident he could probably make quick work of this message. He tried a couple of things and when he saw what the result was, he was surprised! It appeared that the Germans were on to him! Intrigued by this fact he decided to relay the message to his commanding officer as quickly as possible. Surely he would send a battalion of highly trained geocachers to check out the listed coordinates. If you would like to see for yourself what they found, decode the message and make your way over there. But be careful!
