Possible ways to crack simple substitution ciphers

Question

We had a quiz in class today where we had to break the ciphertext with the key given, but not the algorithm. Suffice to say that I wasn't able to decrypt it within the alloted time of 12 mins and will probably get a 0 on the quiz. So, I was just wondering if there are some kind of standard techniques that are followed when decrypting a simple substitution ciphertext.

Answer 1

When trying to break an unknown cipher, one first needs to figure out what kind of cipher one it is. Generally, a good starting point would be to start with the most common and well known classical ciphers, eliminate those that obviously don't fit, and try the remaining ones to see if any of them might work.

An obvious first step is to look at the ciphertext alphabet: does the ciphertext consist of letters (and if so, in what alphabet), numbers, abstract symbols or some combination of those? If it's letters, does it include spaces, punctuation or case distinctions — and, if it does, do they look like they're also scrambled somehow, or are they perhaps just left as they are in the plaintext?

Compiling a letter (or symbol) frequency table of the ciphertext, and comparing it to the corresponding table of plain English text, can often yield information about the general type of cipher one is dealing with:

• If the ciphertext is written in letters, and their frequencies more or less match those of plain English text (the nonsense phrase ETAOIN SHRDLU is handy to remember for this), you're probably dealing with a transposition cipher. (If the most frequent letters don't quite match, but still look plausible for natural text — mostly vowels and a few simple consonants — it might be a transposition of text in some other language.)

• If the rank–frequency distribution looks similar to that for plain English, but the letters are obviously scrambled (e.g. most frequent letters are G, X and Q instead of E, T and A), the cipher is likely to be a monoalphabetic substitution (possibly combined with transposition).

• If the frequency distribution is closer to uniform than one would expect for natural language, you're probably looking at a polyalphabetic substitution cipher. With experience (and enough ciphertext), one may even be able to guess at the most likely cipher just based on the frequency distribution.

Knowing whether the cipher has a key or not, and what form the key takes (word, number, sequence of numbers, etc.) can also help reduce the range of possibilities. For example, let's say that the ciphertext is uppercase letters with no spaces or punctuation, and that we know it has a key which is a word or a short phrase. That narrows down the likely choices quite a bit:

• If it's a transposition cipher, the obvious thing to try would be columnar transposition and its variants like double transposition.

• If it's a monoalphabetic substitution and has a keyword, the keyword cipher described by mikeazo in his answer is the obvious choice.

• If it's a polyalphabetic substitution, there are more choices. The first ciphers I'd try would be Vigenère, autokey and Playfair; if those don't work out, Beaufort, two-square and four-square may be worth trying too.

Since you already know what the key is supposed to be, testing each cipher should be pretty straightforward: just try to decrypt the message with the key and see if the output makes sense.

Note that, in some cases, effort can be shared between ciphers. For example, the Vigenère and autokey ciphers are identical for the beginning of the message; they only start to behave differently when the end of the keyword is reached. It may also be a good idea to try simple variants of these ciphers, such as switching the encryption and decryption rules around; some of them work equally well in both directions, and may have been used so.

Answer 2

A substitution cipher consist of a mapping from letters in the alphabet to letters in the alphabet (not necessarily the same alphabet, but probably is in this case). There are many forms that a key can take on. Ones I've seen in practice are:

1. The key is the mapping (i.e. a->m, b->x, c->q,...).

2. The key represents a shift. A key of 5 would mean the transformation of a->f, b->g,..., z->e.

3. The key is a word which is used to generate the map. This is often done by writing the alphabet out. Then below, write the key (removing repeated letters), then write the rest of the alphabet, removing letters that are in the key. For example:

abcdefghijklmnopqrstuvwxyz
paswordbcefghijklmnqtuvxyz

You then substitute by finding the letter in the first row and going down the the second row.

Since you were given the key, chances are you had to use one of these methods (or possibly another) to come up with the mapping.

Answer 3

If it is a simple substitution cipher, there are a few standard techniques:

• Frequency analysis. Count how many times each letter appears in the ciphertext. The most common ciphertext-letters probably correspond to the most-common letters in English. The most common letters in English are ETAOINSHRDLU... (in decreasing order of prevalence). Therefore, the letter that appears most frequently in the ciphertext is probably E, T, A, or O, etc., in decreasing order of likelihood.

  Using this information, you can make some tentative guesses, and see if any words seem to start to form.

  If you know how the words are broken up (if the inter-word spaces remain in the ciphertext), you can also do frequency analysis of letters at the end of a word. Here are the most common letters that appear at the end of a word: ETSDNRY.

  You can also do frequency analysis of pairs of letters (digraphs). However, this tends to be harder to take advantage of by hand. Here are some common digraphs (letter pairings): TH, HE, AT, ST, AN, IN, EA, ND, ER, EN, RE, NT, TO, ES, ON, ED, IS, TI. Here are some letters that are often doubled: LL, TT, SS, EE, PP, OO, RR, FF, CC, DD, NN. Therefore, if you see a single letter in the ciphertext that appears twice next to each other, it is likely to be one of those.

• Crib-dragging. If you have some idea of a word that you suspect appears in the message, look for any spot where it could possibly match up. That will give you the mapping for all of the letters in the word. Try applying that mapping to the rest of the ciphertext, and check to see if you get something that seems to start looking right.

  Crib-dragging works best when you have some domain knowledge about the likely content of the message. However, if you know nothing, you can try matching against the most common words in English. Here are some of the most common words in English: THE, OF, ARE, I, AND, YOU, A, CAN, TO, HE, HER, THAT, IN, WAS, IS, HAS, IT, HIM, HIS.