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.

Guessing AND gives J->D
Guessing TODAY gives B->Y
Guessing BY gives S->B
Guessing RADIO gives M->R
Guessing ADMIRAL gives N->M
Guessing NOTORIOUS gives K->U
Guessing HIS gives U->H
Guessing LINKS gives Y->K
Guessing HOAX gives L->X
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!

Comments Toot! Tweet Share