Verifying the Substitution Cipher Folklore

A substitution cipher has each letter substituted with another. Cryptography folklore has it that simple substitution ciphers are trivial to break by looking at the letter frequencies of the encrypted text. I tested the folklore and the results were not quite what I was expecting.

Here is a series of examples I prepared for a course on the use of Unix command-line tools.

Encryption

Bob fetches a copy of Jane Austen's Pride and Prejudice and encrypts it with a rot13 cipher. (Each letter is substituted with the one 13 places after it.)

curl -L http://www.gutenberg.org/ebooks/1342.txt.utf-8 >pride-and-prejudice.txt
tr '[A-Za-z]' '[N-ZA-Mn-za-m]' <pride-and-prejudice.txt >secret
head -40 secret

Gur Cebwrpg Thgraoret RObbx bs Cevqr naq Cerwhqvpr, ol Wnar Nhfgra

Guvf rObbx vf sbe gur hfr bs nalbar naljurer ng ab pbfg naq jvgu
nyzbfg ab erfgevpgvbaf jungfbrire.  Lbh znl pbcl vg, tvir vg njnl be
er-hfr vg haqre gur grezf bs gur Cebwrpg Thgraoret Yvprafr vapyhqrq
jvgu guvf rObbx be bayvar ng jjj.thgraoret.bet


Gvgyr: Cevqr naq Cerwhqvpr

Nhgube: Wnar Nhfgra

Cbfgvat Qngr: Nhthfg 26, 2008 [RObbx #1342]
Eryrnfr Qngr: Whar, 1998
Ynfg hcqngrq: Sroehnel 15, 2015]

Ynathntr: Ratyvfu


*** FGNEG BS GUVF CEBWRPG THGRAORET ROBBX CEVQR NAQ CERWHQVPR ***




Cebqhprq ol Nabalzbhf Ibyhagrref





CEVQR NAQ CERWHQVPR

Ol Wnar Nhfgra



Puncgre 1


Vg vf n gehgu havirefnyyl npxabjyrqtrq, gung n fvatyr zna va cbffrffvba

Derived Frequency Tables

Alice, faced with the secret text, creates a function that creates a string of letters based on the frequency of their occurrence. This can then be readily passed to the Unix tr program.

freqlist()
{
  # Add a newline after each character
  sed 's/./&\
/g' |
  sort |
  uniq -c |  # Count number of occurrences
  sort -rn | # Order by frequency
  # Output letters in order of frequency
  awk 'BEGIN { ORS = ""} /[A-Za-z]/ { print $2 }'
}
echo bbbooooa | freqlist

oba

Decryption Using the Frequency Tables

Alice, then fetches a copy of Fyodor Dostoyevsky's The Brothers Karamazov and uses its frequency table to decrypt the secret file.

curl -L http://www.gutenberg.org/files/28054/28054-0.txt >karamazov.txt
tr $(freqlist <secret) $(freqlist <karamazov.txt) <secret | head -40

xie zsaGeyt Cutenbesg MTaak ac zshde ond zseGudhye, bw Oone Kurten

xihr eTaak hr cas tie ure ac onwane onwfiese ot na yart ond fhti
olmart na sertshythanr fiotraeves.  Dau mow yapw ht, ghve ht ofow as
se-ure ht undes tie tesmr ac tie zsaGeyt Cutenbesg Whyenre hnyluded
fhti tihr eTaak as anlhne ot fff.gutenbesg.asg


xhtle: zshde ond zseGudhye

Kutias: Oone Kurten

zarthng Pote: Kugurt 26, 2008 [MTaak #1342]
Eeleore Pote: Oune, 1998
Wort updoted: Rebsuosw 15, 2015]

Wonguoge: Mnglhri


*** qxKEx LR xBIq zELOMFx CZxMNTMEC MTLLV zEIPM KNP zEMOZPIFM ***




zsaduyed bw Knanwmaur Jalunteesr





zEIPM KNP zEMOZPIFM

Tw Oone Kurten



Fioptes 1


It hr o tsuti unhvesrollw oyknafledged, tiot o rhngle mon hn parrerrhan

Analysis

freqtable()
{
  # Add a newline after each character
  sed 's/./&\
/g' |
  sort |
  uniq -c |  # Count number of occurrences
  sort -rn   # Order by frequency
}
paste <(freqtable <pride-and-prejudice.txt) <(freqtable <karamazov.txt) |
head -26

 113924  	 326094
  70342 e	 179662 e
  47281 t	 135591 t
  42154 a	 119653 o
  41137 o	 118778 a
  38428 n	 100838 n
  36272 i	  95854 h
  33881 h	  94224 i
  33292 r	  88808 s
  33291 s	  79674 r
  22246 d	  64746 d
  21282 l	  61446 l
  15441 u	  45870 u
  13426 	  38943 m
  13401 m	  37557 y
  13394 c	  36483
  12654 y	  32540 w
  12177 f	  31728 c
  11922 w	  30709 f
  10160 g	  30629 ,
   9280 ,	  28299 g
   8386 p	  22813 .
   8249 b	  21469 p
   6396 .	  19873 b
   5811 v	  18626 v
   3553 "	  12940 k

As you can see, the first two rows match the picture given in cryptology texts: the most frequent letters are indeed e and then t. However, then things get messier: o and a are swapped, as are h and i and r and s. Jane Austen's book contains 124 thousand words and yet a simple frequency analysis did not yield a good-enough decryption. Decrypting a message of only a few lines would be even more difficult. The moral of the story is that, contrary to what's often claimed in cryptology books, decrypting a simple substitution cipher may be easy but it's definitely not trivial.

Comments   Toot! Tweet Share