blog dds

2005.04.27

Solving Singh's Substitution Cipher

Many of us enjoy playing with encryption algorithms. Simon Singh, before a book promotion trip to Greece, published a "substitution cipher with a twist". I would consider solving a substitution cipher aimed at the general public unfair, but the "twist" made me curious.

The cryptogram's text reads as follows:

GPJDB, SB MDJTP, DOJ DQWP PO HTDOG UPDMJTOHW, D MDSST, DO DJNTMDQ
OPGPMTPKW ZPM UTW QTOYW GP NDWPOMB, D GMTP PZ IDMJTODQW, D GMTP,
GPP, PZ TOWTHOTZTIDOG VPQTGTITDOW (SPKHUG DOJ VDTJ ZPM SB D MTIU DOJ
IPMMKVGDOHQP-IDODJTDO SDOYTOH IPMVPMDGTPO) TOZPMN KW DQQ PZ UPF PKM
IPKOGMB OPF MTWYW JBTOH PZ WGDMXDGTPO.D MKNPKM, GUDGW NB TOTGTDQ GUPKHUG
DW T WFTGIU PZZ NB MDJTP, MKNPKM PM VPWWTSQB D UPDL
(At the time of this writing, no hint was published on the web page). There was definitely a twist in the cryptotext, because the cipher resisted all my attempts to decode it by substituting the letter E (the most common letter in English). Working on words, did not get me much further: substituting the DOJ sequence with THE (or, remembering the twist, its reverse EHT) did not get me much further.

I then tried grep and various pattern matches (based on letter substitutions) on the English dictionary available on Unix, but none seemed to give any useful results.

cd /usr/share/dict
grep '^.e.t.$' words
grep '^.e.e..e..$' words
grep '^.e.e..e..$' words | wc -l
grep '^.e....t...e.t.t..t.$' words
grep '^......t.....t.t..t.$' words
grep '^......e.....e.e..e.$' words
grep '^.e..e.t..e.$' words
egrep '^.(.)\1$' words
grep thte words
grep '^eh..e..e..$' words
grep '^eh...e..e..$' words
grep -i '^eh...e..e..$' words
grep '^..a$' words
grep '^..i$' words
grep '^i..$' words
grep '^a..$' words
grep '^.a.k.sa..$' words
Finally, I decided to stop assuming specific letter substitutions, and work on specific substitution patterns. I thus concentrated on words with repeated letters. My first attempt was at TOWTHOTZTIDOG. Note the repetitions:
TOWTHOTZTIDOG
12 1 21 1  2
Expressing these as an extended regular expression allowed me to look for such a word in the dictionary:
egrep -i '^(.)(.).\1.\2\1.\1..\2.$' words
and out came the (single) result:
INSIGNIFICANT
12 1 21 1  2
TOWTHOTZTIDOG
This gave me many more letters:
W -> S
H -> G
Z -> F
I -> C
D -> A
G -> T
From then on, a simple examination of the cyphertext with the replaced letters allowed me to guess more words, and more substitutions.
  1. Guessing AND gives J->D
  2. Guessing TODAY gives B->Y
  3. Guessing BY gives S->B
  4. Guessing RADIO gives M->R
  5. Guessing ADMIRAL gives N->M
  6. Guessing NOTORIOUS gives K->U
  7. Guessing HIS gives U->H
  8. Guessing LINKS gives Y->K
  9. Guessing HOAX gives L->X
  10. Guessing SWITCH gives F->W
Thus the cleartext is:
TODAY, BY RADIO, AND ALSO ON GIANT HOARDINGS, A RABBI, AN ADMIRAL
NOTORIOUS FOR HIS LINKS TO MASONRY, A TRIO OF CARDINALS, A TRIO,
TOO, OF INSIGNIFICANT POLITICIANS (BOUGHT AND PAID FOR BY A RICH AND
CORRUPTANGLO-CANADIAN BANKING CORPORATION) INFORM US ALL OF HOW OUR
COUNTRY NOW RISKS DYING OF STARVATION.A RUMOUR, THATS MY INITIAL THOUGHT
AS I SWITCH OFF MY RADIO, RUMOUR OR POSSIBLY A HOAX

And the twist? The above text does not contain any instance of the letter E!

Read and post comments    AddThis Social Bookmark Button


Creative Commons License Last modified: Wednesday, April 27, 2005 10:16 am
Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.