Tim helps Tim crack the code

Long time reader, second time caller emailer writes in:

I've always been interested in mystery and codes (going back to 'Mystery Club' in 7th Grade), and today I discovered a cool show on History Channel called Decoded. They were talking about cryptography, specifically frequency analysis. I'm not an educator here but just to make sure we're on the same page: frequency analysis is one method of cracking a cipher by calculating how many times a certain cipher letter appears. From there, one can make a best guess on what the most frequent letters are.

Ok anyway, I've been doing some fun cipher puzzles in my spare time and thought about how this could be code. Say we have a document with a cipher text (letters or numbers, separated by a comma or space). Is it possible to write a code to do a frequency analysis on the ciphertext and maybe even replace the cipher with the results? So if the most frequent cipher are 13 and 77, alter the document and replace 13 and 77, with the most common letters E and T, for example.

This type of statistical analysis works better with longer ciphertext. So I created a substitution cipher that produced the following output. For the sake of simplicity, I didn't replace the punctuation and the spaces

"YETU HTPVI MOF UELCP MOF STC LCRVCU T DOOZ SLXEVW LK MOF ETRV CO VQXVWULIV LC UEV IFNAVSU? HTMNV MOF STC, NFU LU'I COU UVWWLNJM JLPVJM. LHTDLCV EOY MOF YOFJZ WVTSU LK MOFW ZOSUOW UOJZ MOF "MOF ETRV TXXVCZLSLULI, T ZLIVTIV UETU LI JLKV-UEWVTUVCLCD LK COU UWVTUVZ. YV ETRV T ULHV-UVIUVZ SFWV UETU SFWVI 99% OK TJJ XTULVCUI YLUE CO COULSVTNJV ILZV-VKKVSUI, NFU L'H COU DOLCD UO DLRV MOF UETU: L'H DOLCD UO DLRV MOF T CVY VQXVWLHVCUTJ UWVTUHVCU HM SOFILC ZWVTHVZ FX JTIU YVVP. CO, HM SOFILC ETI CO HVZLSTJ UWTLCLCD. CO, L ETRV CO VRLZVCSV UETU UEV CVY UWVTUHVCU YLJJ YOWP, TCZ LU'I CVRVW NVVC UVIUVZ OW TCTJMBVZ LC ZVXUE -- NFU L'H DOLCD UO DLRV LU UO MOF TCMYTM NVSTFIV HM SOFILC UELCPI LU LI DOOZ IUFKK." MOF'Z KLCZ TCOUEVW ZOSUOW, L EOXV. WTULOCTJ XVOXJV JVTRV HVZLSTJ STWV UO UEV HVZLSTJ VQXVWUI. UEV HVZLSTJ VQXVWUI ETRV T HFSE NVUUVW UWTSP WVSOWZ UETC UEV GFTSPI."
-- ZTRLZ YTDCVW XEZ, ISL.SWMXU, 19UE OSU 02.

We can read a file using the command Get-Content (alias cat, gc, type) as we usually do, but let's use a Here-String instead.

PS C:\> $ciphertext = @"
"YETU HTPVI MOF UELCP MOF STC LCRVCU T DOOZ SLXEVW LK MOF ETRV CO VQXVWULIV LC UEV IFNAVSU?
HTMNV MOF STC, NFU LU'I COU UVWWLNJM JLPVJM. LHTDLCV EOY MOF YOFJZ WVTSU LK MOFW ZOSUOW UOJZ
MOF "MOF ETRV TXXVCZLSLULI, T ZLIVTIV UETU LI JLKV-UEWVTUVCLCD LK COU UWVTUVZ. YV ETRV T ULHV-
UVIUVZ SFWV UETU SFWVI 99% OK TJJ XTULVCUI YLUE CO COULSVTNJV ILZV-VKKVSUI, NFU L'H COU DOLCD
UO DLRV MOF UETU: L'H DOLCD UO DLRV MOF T CVY VQXVWLHVCUTJ UWVTUHVCU HM SOFILC ZWVTHVZ FX JTIU
YVVP. CO, HM SOFILC ETI CO HVZLSTJ UWTLCLCD. CO, L ETRV CO VRLZVCSV UETU UEV CVY UWVTUHVCU
YLJJ YOWP, TCZ LU'I CVRVW NVVC UVIUVZ OW TCTJMBVZ LC ZVXUE -- NFU L'H DOLCD UO DLRV LU UO MOF
TCMYTM NVSTFIV HM SOFILC UELCPI LU LI DOOZ IUFKK." MOF'Z KLCZ TCOUEVW ZOSUOW, L EOXV. WTULOCTJ
XVOXJV JVTRV HVZLSTJ STWV UO UEV HVZLSTJ VQXVWUI. UEV HVZLSTJ VQXVWUI ETRV T HFSE NVUUVW UWTSP
WVSOWZ UETC UEV GFTSPI."
-- ZTRLZ YTDCVW XEZ, ISL.SWMXU, 19UE OSU 02.
"@

The we start a Here-String with @" and close it with the matching "@ pair. Now we have a variable $cipher that contains our text. Next, let's get the frequency of each character used in our ciphertext.

PS C:\> ($ciphertext | Select-String -AllMatches "[A-Z]").matches | 
group value -noel | sort count -desc

Count Name
----- ----
   90 V
   76 U
   58 L
   55 T
   53 O
   47 C
   31 W
   29 E
   29 S
   28 Z
   28 I
   27 F
   22 M
   21 J
   19 H
   15 D
   15 X
   13 R
   12 Y
   10 N
   10 K
    8 P
    4 Q
    1 G
    1 B
    1 A

We start by piping the ciphertext into the Select-String cmdlet where we use the regular expression "[A-Z]" to select each alphabet character individually. The AllMatches switch is used to return all the characters instead of just the first one found. The results are passed down the pipeline into the Group-Object cmdlet (alias group) to give us the count. The NoElement switch (shortened to noel) is used to discard the original objects as we don't need them in the output.

Let's save the letters into a variable so we can use it later for substitution.

PS C:\> $cipherletters = ($ciphertext | Select-String -AllMatches "[A-Z]").matches | 
group value -noel  | sort count -desc | % { $_.Name }
PS C:\> $cipherletters
V
U
L
T
O
C
W
...

We used the same command as above, except with the added ForEach-Object cmdlet (alias %) where the value of the Name property is output and stored in our variable.

Now that we have our letters sorted by their frequency we need to compare them with the statistic frequency of characters in the English language.

e  12.702%
t  9.056%
a  8.167%
o  7.507%
i  6.966%
n  6.749%
s  6.327%
h  6.094%
r  5.987%
d  4.253%
l  4.025%
c  2.782%
u  2.758%
m  2.406%
w  2.360%
f  2.228%
g  2.015%
y  1.974%
p  1.929%
b  1.492%
v  0.978%
k  0.772%
j  0.153%
x  0.150%
q  0.095%
z  0.074%

We aren't going to worry about the percentages and we'll just get the letters in order. Later we'll map the two data sets together for our replacement.

PS C:\> $freqletters = "e","t","a","o","i","n","s","h","r","d","l","c","u",
"m","w","f","g","y","p","b","v","k","j","x","q","z"

Now for a quick substitution.

PS C:\> $replacedtext = $ciphertext
PS C:\> for ($i=0; $i -lt 26; $i++) { $replacedtext =  $replacedtext -creplace 
$cipherletters[$i], $freqletters[$i] }

We use a For loop to count from 0 to 25 where $i is used as the iterator. The iterator is used to match the Nth item in each array (remember, base zero) and use the mapped characters for replacement. The CReplace operator is used for a case sensitive replacement as our cipher letters are upper case and our clear text letters are lower case. This is done to prevent double substitution.

Now to see what our output looks like.

PS C:\> $replacedtext
"phot wokel uic thank uic ron anyent o fiid raghes av uic hoye ni ejgestale an the lcbzert?
woube uic ron, bct at'l nit tessabmu makemu. awofane hip uic picmd seort av uics dirtis timd
uic "uic hoye oggendaratal, o daleole thot al mave-thseotenanf av nit tseoted. pe hoye o tawe-
telted rcse thot rcsel 99% iv omm gotaentl path ni nitareobme lade-evvertl, bct a'w nit fianf
ti faye uic thot: a'w fianf ti faye uic o nep ejgesawentom tseotwent wu riclan dseowed cg molt
peek. ni, wu riclan hol ni wedarom tsoananf. ni, a hoye ni eyadenre thot the nep tseotwent
pamm pisk, ond at'l neyes been telted is onomuqed an degth -- bct a'w fianf ti faye at ti uic
onupou berocle wu riclan thankl at al fiid ltcvv." uic'd vand onithes dirtis, a hige. sotainom
geigme meoye wedarom rose ti the wedarom ejgestl. the wedarom ejgestl hoye o wcrh bettes tsork
serisd thon the xcorkl."
-- doyad pofnes ghd, lra.rsugt, 19th irt 02.

Well, that isn't great. It looks like the only words successfully decryted are "the" and "been". There are a few more techniques for cryptanalysis of this type of cipher

With a bit of tweeking and adjustment of the frequency letters we can end up with the following.

"What makes you think you can invent a good cipher if you have no expertise in
the subject? Maybe you can, but it's not terribly likely. Imagine how you would react
if your doctor told you "You have appendicitis, a disease that is life-threatening if
not treated. We have a time-tested cure that cures 99% of all patients with no
noticeable side-effects, but I'm not going to give you that: I'm going to give you a
new experimental treatment my cousin dreamed up last week. No, my cousin has no
medical training. No, I have no evidence that the new treatment will work, and it's
never been tested or analyzed in depth -- but I'm going to give it to you anyway
because my cousin thinks it is good stuff." You'd find another doctor, I hope.
Rational people leave medical care to the medical experts. The medical experts have a
much better track record than the quacks."
-- David Wagner PhD, sci.crypt, 19th Oct 02.

Let's see if Hal is a better cracker than I am.

Hal gets cracking

Gah. I was always terrible at these puzzles as a child. Maybe my shell can help!

Getting the frequency counts is just a matter of piling up a bunch of shell primatives:

$ sed 's/[^A-Z]//g; s/\(.\)/\1\n/g' cyphertext | grep '[A-Z]' | 
    sort | uniq -c | sort -nr
     90 V
     76 U
     58 L
     55 T
     53 O
...

Notice there's two substitutions in the sed program. The first eliminates anything that's not an uppercase letter. The second puts a newline after each letter in the remaining text. So what I get is each letter from the input text on a line by itself.

Unfortunately, sed doesn't give me a good way to deal with the newlines in the original message. So after the last letter on each line I'm going to get the newline I add with sed, followed by the newline from the original input file. This gives me blank lines in the sed output and I don't want them! The next grep in the pipeline takes care of only giving me the lines that have letters on them.

From there I sort my output and then use "uniq -c" to count the occurrences of each letter. The final "sort -nr" gives me the counts in descending order.

Now let's add a little awk:

$ sed 's/[^A-Z]//g; s/\(.\)/\1\n/g' cyphertext | grep '[A-Z]' | 
    sort | uniq -c | sort -nr | awk 'BEGIN {ORS = ""} {print $2}'
VULTOCWSEZIFMJHXDRYNKPQGBA

The awk I've added prints out the letters from my frequency chart. Normally awk would print them out one per line, just like they are in the input. But in the BEGIN block I'm telling awk to use the null string as the "output record separator" (ORS) instead of the usual newline. That gives me the letters all on one line without any whitespace.

Why is this useful? Because now I can do this:

$ cat cyphertext | tr $(sed 's/[^A-Z]//g; s/\(.\)/\1\n/g' cyphertext | grep '[A-Z]' |
                        sort | uniq -c | sort -nr |awk 'BEGIN {ORS = ""} {print $2}') \
                      etaoinshrdlcumwfgypbvkjxqz
"prot wokel uic trank uic hon anyent o giid hafres av uic roye ni ejfestale an tre 
lcbzeht? woube uic hon, bct at'l nit tessabmu makemu. awogane rip uic picmd seoht av 
uics dihtis timd uic "uic roye offendahatal, o daleole trot al mave-trseotenang av nit 
tseoted. pe roye o tawe-telted hcse trot hcsel 99% iv omm fotaentl patr ni nitaheobme 
lade-evvehtl, bct a'w nit giang ti gaye uic trot: a'w giang ti gaye uic o nep 
ejfesawentom tseotwent wu hiclan dseowed cf molt peek. ni, wu hiclan rol ni wedahom 
tsoanang. ni, a roye ni eyadenhe trot tre nep tseotwent pamm pisk, ond at'l neyes been 
telted is onomuqed an deftr -- bct a'w giang ti gaye at ti uic onupou behocle wu 
hiclan trankl at al giid ltcvv." uic'd vand onitres dihtis, a rife. sotainom feifme 
meoye wedahom hose ti tre wedahom ejfestl. tre wedahom ejfestl roye o wchr bettes 
tsohk sehisd tron tre xcohkl."
-- doyad pognes frd, lha.hsuft, 19tr iht 02.

What I did there was take my pipeline and put it inside "$(...)" so that the output of the pipeline becomes the first argument to my tr command. The letters in the list produced by my pipeline get replaced in with the letters in the standard English frequency chart.

Unfortunately, as Tim found out, the standard frequency chart doesn't work. Actually, my results are different from Tim's first attempt. I think he was cheating some where to get his "the"'s decoded correctly!

If at first you don't succeed, try, try again. We could just keep trying different permutations of our frequency list:

$ freqlist=$(sed 's/[^A-Z]//g; s/\(.\)/\1\n/g' cyphertext | grep '[A-Z]' | 
             sort | uniq -c | sort -nr |awk 'BEGIN {ORS = ""} {print $2}')
$ permute etaoinshrdlcumwfgypbvkjxqz | 
     while read replace; do 
        misspell=$(cat cyphertext | tr $freqlist $replace | spell | wc -l); 
        [[ $misspell -lt 10 ]] && echo $replace && break; 
        (( $((++c)) % 1000 )) || echo -n . 1>&2; 
     done

First I assign the frequency analysis of my cyphertext to a variable so I don't have to keep recomputing it.

Next I cheat a whole lot by using a script I wrote a long time ago called permute that produces a list of all possible permutations of its input. My while loop reads those permutations one at a time and tries them via tr. The output of tr goes into spell which will give a list of the misspelled words. I count the number of misspelled words with "wc -l". If the number of misspellings is small, then I've probably found the right replacement list. In that case I'll output the $replace list that seems to work and terminate the loop with break.

The last line of the loop is the trick I showed you in Episode #163 for showing progress output in a loop. Every 1000 permutations tried, we'll output a dot just so you know that things are working.

Be prepared for a lot of dots, however. Unfortunately there are 26! = 4E26 possible permutations, which might take you-- or your computer-- more than a little while to test. Brute force really isn't a practical solution for this problem. But I wanted to show you that there is a solution that you could implement in shell (modulo my dirty little permute script), even if it is a lousy one.