Index of Coincidence

One number answers two questions: which kind of cipher produced this text, and how long its key is.

CryptanalysisPeriod findingdemo

Objectives

Compute an index of coincidence and read it against 0.065 and 0.038.
Say which ciphers move the statistic and which leave it alone.
Recover a Vigenere period from the average index of coincidence of its cosets.

25%

IC = Σ n_i(n_i − 1) / N(N − 1); English ≈ 0.065, random ≈ 0.038.

Source text

Monoalphabetic key

Columnar key

Vigenère keyword

Draw two letters at random. What is the chance they match?

English plaintext	0.0634
monoalphabetic ciphertext	0.0634
columnar transposition	0.0622
Vigenère, key length 8	0.0426
random letters	0.0385

Renaming the letters does not move it. Reordering them does not move it. Mixing alphabets does, and nothing else on this page does. So a drop toward 0.038 says several alphabets are in play before you know anything else about the cipher. Friedman, 1922.

This is a detector, not a break. It tells the attacker which family of cipher they are looking at, which is what decides whether the next hour is spent on frequency analysis or on finding a period. Row two and row three are the two ways a cipher can leave the statistic alone, and both of them lose to a different test.

The same statistic, now on the cosets: m = 1 to 12

m = 1	0.0426
m = 2	0.0512
m = 3	0.0440
m = 4	0.0541
m = 5	0.0427
m = 6	0.0506
m = 7	0.0408
m = 8	0.0655
m = 9	0.0468
m = 10	0.0509
m = 11	0.0439
m = 12	0.0545

Take every m-th letter of the Vigenère row above. If m is the key length, that stream was encrypted with one fixed shift, so it is English with the letters renamed and its IC climbs back to 0.065.

Split the ciphertext this many ways, and look at the streams

Every 8th letter, as 8 separate streams

coset	letters taken (first 24)	its own IC
0	NYYZJWZVJOVMNZAJZGZDGZQY	0.0740
1	PPPZCMNEZWVWQBZLTIKUWZMN	0.0620
2	KGKZRKUUXSJCTZUGGHUKAJRU	0.0675
3	WZVLHRVVSSXGXCQCWPVEVEMS	0.0564
4	URRRUNFQJEBEUCQGGRQALLTY	0.0696
5	SHEVEXYXEVQIMEESWSIHIWLW	0.0783
6	LZWVMZTFEFFVJTPKPWURJYKK	0.0570
7	PIXAIQLQHAVTTIXLPVXPXEIL	0.0589

Coset i is positions i, i+8, i+16, and so on. The row in the table above is the average of the 8 numbers in the last column, and at the true period every one of them sits up near English.

One statistic, two jobs. Whole-text IC said “several alphabets”; coset IC says how many. The peak is at m = 8 with 0.0655, and that is the key length. Multiples of the true period score well too. A stream taken every 16th letter is still one alphabet, so take the smallest peak, not the tallest.

step 1/4

CPE 645 / CS 685

Index of Coincidence

Breaking Hill

Kasiski Examination