Kasiski Examination

Repeated n-grams, the distances between them, and a vote on their factors scored as excess over chance.

CryptanalysisPeriod findingdemo

Objectives

Collect repeat distances from a polyalphabetic ciphertext and factor them.
Explain why the plain gcd of every distance fails on a real message.
Score factor votes against chance and recover the key length.

33%

Distance between two copies of a repeat = a multiple of the key length.

Vigenère keyword

Plaintext

n-gram length

ciphertext

NPKWU SLPYP GZRHZ IYPKV REWXZ ZZLRV VAJCR HUEMI WMKRN XZQZN UVFYT LVEUV QXFQJ ZXSJE EHOWS SEVFA VVJXB QFVMW CGEIV TNQTX UMJTZ BZCCE TIAZU QQEPX JLGCG SKLZT GWGWP PGIHP RSWVZ KUVQI UXDUK EAHRP GWAVL IJXZZ JELWY EQMRM TLKIY NUSYW KLZEG CGSUY NBEHR EKLJC ZSHXS VDMLG NRUPZ TOJRW SYOIC EYOZR BANEQ SNEKW UVCPR CZZZL NXJXM CZWNR UJMMZ WUMJL JCXYC SEXCM YXNKV EILZL RRZWC MGVQR FQJZK MGMJE OIRIG SCHWG GRVHZ SONAP YSWWJ CTHNR UJPZE WVKEM AGORT RFXCQ TK

A repeated plaintext fragment that lands on the same key offset repeats in the ciphertext too, so the distance between two copies is a multiple of the key length. Kasiski, 1863.

Repeats, their distances, and the factors of each

gram	at	distance	factors up to 12
NRU	220 → 268	48	2 3 4 6 8 12
NRU	268 → 348	80	2 4 5 8 10
CGS	123 → 195	72	2 3 4 6 8 9 12
FQJ	62 → 310	248	2 4 8
GCG	122 → 194	72	2 3 4 6 8 9 12
KLZ	126 → 190	64	2 4 8
KWU	2 → 248	246	2 3 6
LJC	207 → 279	72	2 3 4 6 8 9 12
QJZ	63 → 311	248	2 4 8

The plain gcd of every distance here is 2. One coincidental repeat poisons it, which is why the textbook version fails on real messages and the practical version votes on factors instead.

Factor votes over 16 distances, bar = excess over chance

m = 2	16 votes	8.0 over chance
m = 3	6 votes	0.7 over chance
m = 4	15 votes	11.0 over chance
m = 5	2 votes	-1.2 over chance
m = 6	6 votes	3.3 over chance
m = 7	0 votes	-2.3 over chance
m = 8	15 votes	13.0 over chance
m = 9	4 votes	2.2 over chance
m = 10	2 votes	0.4 over chance
m = 11	2 votes	0.5 over chance
m = 12	5 votes	3.7 over chance

Raw vote counts always favour 2 and 3. A random distance is divisible by p about 1/p of the time, so the winner has to be scored on the excess over chance or every message looks like it has a two-letter key. Scored that way the answer is m = 8. A period is not a key. All this bought is the knowledge that the message is 8 Caesar ciphers interleaved. Splitting it into 8 cosets and solving each one is what returns the keyword and the message, and that is the next attack in this module, From Period to Key.

step 1/3

CPE 645 / CS 685

Kasiski Examination

Index of Coincidence

Breaking Vigenere