Breaking Monoalphabetic Substitution

The English histogram beside the ciphertext histogram, then singles, digraphs, trigraphs, and cribs.

CryptanalysisFrequency analysisdemo

Objectives

Match a ciphertext histogram to the English one and read off the first three letters.
Use digraph and trigraph counts to extend a partial key.
Explain why a keyspace of 26! is no defense against a statistic.

25%

A one-to-one letter map moves every count to a new name. It moves no count.

Substitution key (26 letters, each used once)

Plaintext

ciphertext, 372 letters

LITLI GXSRI QCTRO TRITK TQYZT KZITK TVGXS RIQCT WTTFQ ZODTY GKLXE IQVGK RZGDG KKGVQ FRZGD GKKGV QFRZG DGKKG VEKTT HLOFZ IOLHT ZZNHQ ETYKG DRQNZ GRQNZ GZITS QLZLN SSQWS TGYKT EGKRT RZODT QFRQS SGXKN TLZTK RQNLI QCTSO UIZTR YGGSL ZITVQ NZGRX LZNRT QZIGX ZGXZW KOTYE QFRST SOYTL WXZQV QSAOF ULIQR GVQHG GKHSQ NTKZI QZLZK XZLQF RYKTZ LIOLI GXKXH GFZIT LZQUT QFRZI TFOLI TQKRF GDGKT OZOLQ ZQSTZ GSRWN QFORO GZYXS SGYLG XFRQF RYXKN LOUFO YNOFU FGZIO FU

English beside the ciphertext

English

E	12.7%
T	9.1%
A	8.2%
O	7.5%
I	7.0%
N	6.8%
S	6.3%
H	6.1%
R	6.0%
D	4.3%
L	4.0%
C	2.8%

ciphertext, monoalphabetic key

T	10.2%
G	9.7%
Z	9.7%
Q	8.9%
K	7.0%
R	6.7%
L	5.9%
I	5.6%
F	5.1%
O	5.1%
S	4.8%
X	3.8%

Substitution renames the letters. It does not change how often they occur, so the shape of the histogram survives the cipher. The tallest ciphertext bar is E. The next two are level, so counting single letters runs out here.

Frequency analysis, step by step

1. singles

T ×38 G ×36 Z ×36 Q ×33 K ×26 R ×25 L ×22 I ×21 map the tallest to E, then try the next two both ways.

2. digraphs

ZI ×9 IT ×8 GK ×8 ZG ×8 QF ×8 FR ×8 English: TH HE IN ER AN RE. Doubles: LL SS EE OO.

3. trigraphs

QFR ×7 ZIT ×5 GDG ×4 DGK ×4 IGX ×3 English: THE AND ING ION ENT.

4. other

one-letter words are A or I.

Everything above this line is a measurement. This is the attack. The counts hand you a partial map, the partial map hands you partial English, and reading the partial English hands you the rest. Run the three stages in order, then repair what they got wrong by typing over it.

Your map: ciphertext letter above, your guess below

0 / 26 mapped

Ciphertext, and what your map recovers

LITLI

_____

GXSRI

_____

QCTRO

_____

TRITK

_____

TQYZT

_____

KZITK

_____

TVGXS

_____

RIQCT

_____

WTTFQ

_____

ZODTY

_____

GKLXE

_____

IQVGK

_____

RZGDG

_____

KKGVQ

_____

FRZGD

_____

GKKGV

_____

QFRZG

_____

DGKKG

_____

VEKTT

_____

HLOFZ

_____

IOLHT

_____

ZZNHQ

_____

ETYKG

_____

DRQNZ

_____

GRQNZ

_____

GZITS

_____

QLZLN

_____

SSQWS

_____

TGYKT

_____

EGKRT

_____

RZODT

_____

QFRQS

_____

SGXKN

_____

TLZTK

_____

RQNLI

_____

QCTSO

_____

UIZTR

_____

YGGSL

_____

ZITVQ

_____

NZGRX

_____

LZNRT

_____

QZIGX

_____

ZGXZW

_____

KOTYE

_____

QFRST

_____

SOYTL

_____

WXZQV

_____

QSAOF

_____

ULIQR

_____

GVQHG

_____

GKHSQ

_____

NTKZI

_____

QZLZK

_____

XZLQF

_____

RYKTZ

_____

LIOLI

_____

GXKXH

_____

GFZIT

_____

LZQUT

_____

QFRZI

_____

TFOLI

_____

TQKRF

_____

GDGKT

_____

OZOLQ

_____

ZQSTZ

_____

GSRWN

_____

QFORO

_____

GZYXS

_____

SGYLG

_____

XFRQF

_____

RYXKN

_____

LOUFO

_____

YNOFU

_____

FGZIO

_____

Bold is the ciphertext; under each column is your map applied letter for letter, with _ wherever you have not guessed yet. The line does not have to be right to be useful: one word you recognize anywhere in it fixes several letters at once, and those letters open more words.

Frequency does not solve the cipher. It starts it. The stages come out wrong wherever the counts are ambiguous. Two letters tie, and rank order has to break the tie by guessing, so the map they build is a hypothesis, not an answer. What finishes the job is reading: the partial English above tells you which boxes to overwrite, and every correction makes the next one easier.

al-Kindi wrote this down around 850 CE, and it has never stopped working on a cipher that maps one letter to one letter. A machine does it without reading anything: score a candidate key by trigram log-probability, swap two letters, keep the swap when the score improves. Nothing searches 26!; the attacker walks downhill through it in seconds. The keyspace was never the defense.

step 1/4

CPE 645 / CS 685

Breaking Monoalphabetic Substitution

Breaking Caesar

Breaking Playfair