The Coincidence Test
The problem
A message has been intercepted, 445 letters long, and a clerk has tallied how many times each letter of the alphabet appears in it. Before anyone spends a week on it, someone has to answer two questions. Is it a simple substitution (one fixed cipher alphabet for the whole message), or has it been enciphered with a repeating keyword, so that the cipher alphabet changes from letter to letter? And if it is the second, how long is the keyword?
Here is the tally:
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 15 | 17 | 10 | 9 | 11 | 26 | 22 | 17 | 14 | 19 | 22 | 16 | 13 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 6 | 11 | 8 | 6 | 11 | 32 | 22 | 10 | 24 | 35 | 22 | 27 | 20 |
The tool for the job is William Friedman’s index of coincidence. Pick two letters from the message at random, without putting the first one back. The chance that they are the same letter is
κo = Σ n(n − 1) / ( N (N − 1) )
where n is a letter’s count, N = 445 is the length of the message, and the sum runs over all 26 letters. Two further figures are needed:
- κp = 0.067. The same quantity for ordinary English, which is what a simple substitution would leave behind, since it only renames the letters.
- κr = 0.0385 (that is 1/26). The value for letters drawn at random, which is what a long, well-mixed polyalphabetic cipher tends towards.
For a repeating keyword, Friedman’s estimate of its length is
K ≈ (κp − κr) / (κo − κr)
What is κo for this message, to four decimal places? And what keyword length does the estimate give, to the nearest whole number?
Notes
- Keep every digit your calculator offers until the last step. κo and κr are close together, so the difference κo − κr is small, and rounding κo early throws away most of the precision in K.
- You do not need the n(n − 1) terms one at a time. Σ n(n − 1) = Σ n² − Σ n, and Σ n is just N. A
calculator with a statistics key (
Σ+) keeps both of those sums for you. - The estimate is statistical, so it is not a measurement. It comes out as a fraction, and you round it. The solution says how far to trust it.
- This needs an addition somewhere, so no slide rule.
Hint
Click for a hint
Square each of the 26 counts and add the squares up. Subtract N from that total, then divide by N(N − 1) = 445 × 444. The result is κo. A quick check on the magnitude: it must lie somewhere between κr and κp, because the message is neither pure English nor pure noise.
Many calculators have a statistics key, Σ+. Each press adds the number in X to a running Σx and
its square to a running Σx², so you key the counts in once and then recall the two totals. Without
one, an RPN stack will do: 15 ENTER × squares a count, and a + after the next one adds it to the
running total sitting beneath it.
For the second part, κp − κr = 0.0285 is a fixed number, and κo − κr is a small difference. Divide the first by the second.
Solution
Click to reveal the solution
The sum of squares. Squaring the 26 counts and adding them gives
Σ n² = 9131
so, since Σ n = N = 445,
Σ n(n − 1) = 9131 − 445 = 8686
N (N − 1) = 445 × 444 = 197,580
The index of coincidence.
κo = 8686 / 197580 = 0.043962
Answer (part 1): κo = 0.0440.
This sits close to the random figure 0.0385 and well below English’s 0.067. A simple substitution would have left κo near 0.067, because renaming letters does not change how unevenly they are used. So this is not a simple substitution. The message uses several cipher alphabets.
The keyword length.
κo − κr = 0.043962 − 0.0385 = 0.005462
κp − κr = 0.067 − 0.0385 = 0.0285
K ≈ 0.0285 / 0.005462 = 5.218
Answer (part 2): about 5 letters. (Round κo to 0.0440 first and K comes out as 5.18, which still rounds to 5. Round it to 0.044 and you get the same. Round it harder, to 0.04, and the answer is nowhere near.)
How far to trust it. The message really was enciphered with a five-letter keyword, so the estimate is right here. It is not always so lucky. The same 445-letter plaintext, enciphered with other five-letter keywords, gives κo values that put the estimate anywhere from about 3.5 to about 10.6. The cause is plain from the size of κo − κr, which is only about 0.005. A change of a few counts moves it by a fifth. Friedman’s test is a way to decide between one alphabet and several, and to get a rough idea of the key length, which would then be checked by other means. It is not a way to read off the answer.
Check. κo must lie between 0.0385 and 0.067, and 0.0440 does. ✓
Calculator solutions
Every machine below follows the same plan. Get Σn, the sum of the counts, and Σn², the sum of their squares, subtract N, divide by N(N − 1) to get κo, then use κo to get K.
The HP-42S, HP-15C, HP-41C and HP-25 have a statistics key, Σ+, that does the totals for you. Type a
count, press Σ+, and it adds the count to Σx, adds its square to Σx², and shows how many counts are in
so far. The HP-48GX sums a whole list with one command. The MK-61 has no statistics key, so it squares
each count with ENTER and × and adds it to the running total on the stack. The 26 counts in table
order are:
15 17 10 9 11 26 22 17 14 19 22 16 13 6 11 8 6 11 32 22 10 24 35 22 27 20
HP-42S
Σ+ keeps Σx in R11 and Σx² in R12 (the default statistics registers).
CLΣ clear the statistics registers
15 Σ+ display: 1, the count so far
17 Σ+ display: 2
10 Σ+ display: 3
… one Σ+ for each remaining count, in table order
20 Σ+ display: 26. R11 = Σn = N = 445, R12 = Σn² = 9131
RCL 12 Σn²
RCL − 11 − N
RCL ÷ 11 ÷ N
RCL 11 1 − ÷ ÷ (N − 1): this is κo
Display: 0.0440 in FIX 4, and 0.043962 with more digits.
0.0385 − κo − κr
0.0285 X<>Y ÷ 0.0285 ÷ (κo − κr)
Display: 5.2179, so a keyword of about 5 letters.
HP-15C
Σ+ keeps the count in R2, Σx in R3 and Σx² in R4. The 15C powers up in FIX 4. x≷y is the swap key.
f CLEAR Σ clear the statistics registers
15 Σ+ display: 1, the count so far
17 Σ+ display: 2
10 Σ+ display: 3
… one Σ+ for each remaining count, in table order
20 Σ+ display: 26. R3 = Σn = N = 445, R4 = Σn² = 9131
RCL 4 Σn²
RCL − 3 − N
RCL ÷ 3 ÷ N
RCL 3 1 − ÷ ÷ (N − 1): this is κo
Display (FIX 6): 0.043962, which is 0.0440 to four places.
0.0385 −
0.0285 x≷y ÷
Display (FIX 4): 5.2179 → about 5 letters.
HP-41C
The 41C powers up in FIX 4. Σ+ keeps Σx in R11 and Σx² in R12. It uses R11 to R16, so at least 17 data
registers (SIZE 017) must be allocated. The 41C has no recall arithmetic, so each step is a plain
RCL. X<>Y is the key labelled x≷y.
CLΣ clear the statistics registers (gold x≷y)
15 Σ+ display: 1, the count so far
17 Σ+ display: 2
10 Σ+ display: 3
… one Σ+ for each remaining count, in table order
20 Σ+ display: 26. R11 = Σn = N = 445, R12 = Σn² = 9131
RCL 12 RCL 11 − Σn² − N
RCL 11 ÷ ÷ N
RCL 11 1 − ÷ ÷ (N − 1): this is κo
Display (FIX 6): 0.043962 → 0.0440.
0.0385 −
0.0285 X<>Y ÷
Display (FIX 4): 5.2179 → about 5 letters.
HP-48GX
The 48 sums a list in one command, so the 26 counts go in once, as a list. Left-shift + opens the
braces { }; type the counts with SPC between them, then ENTER. ΣLIST is in the MTH menu: MTH,
LIST, then the ΣLIST key. The x² key (left-shift √x) squares every element of a list at once.
{ 15 17 10 … 27 20 } ENTER the 26 counts as one list
DUP ΣLIST Σn = N = 445
SWAP x² ΣLIST Σn² = 9131
OVER − Σn² − N
OVER ÷ ÷ N
SWAP 1 − ÷ ÷ (N − 1): this is κo
Result: 0.0439619394676, or 0.0440 to four places.
0.0385 ENTER − κo − κr
0.0285 ENTER SWAP ÷ 0.0285 ÷ (κo − κr)
Result: 5.21792673995, about 5 letters.
To keep it, key the same words between « and » and press STO into a name. It then turns any list of
counts into κo:
« DUP ΣLIST SWAP SQ ΣLIST OVER − OVER ÷ SWAP 1 − ÷ »
HP-25
Press f FIX 6 first. The HP-25 takes a moment over each key, so let the display settle before the
next one. Σ+ keeps Σx in R7 and Σx² in R6.
f CLEAR REG clear the registers, including the statistics ones
15 Σ+ display: 1, the count so far
17 Σ+ display: 2
10 Σ+ display: 3
… one Σ+ for each remaining count, in table order
20 Σ+ display: 26. R7 = Σn = N = 445, R6 = Σn² = 9131
RCL 6 RCL 7 − Σn² − N
RCL 7 ÷ ÷ N
RCL 7 1 − ÷ ÷ (N − 1): this is κo
Display: 0.043962 → 0.0440. Then press f FIX 4, and
0.0385 −
0.0285 x≷y ÷
Display: 5.2179 → about 5 letters. The stack holds at most four numbers, and this routine never puts more than three on it.
Elektronika MK-61
В↑ is the Enter key, ↔ swaps X and Y.
1 5 В↑ × 15²
1 7 В↑ × + add 17²
1 0 В↑ × + add 10²
… the same four keys for each of the remaining counts
2 0 В↑ × + Σn² = 9131
4 4 5 − 4 4 5 ÷ 4 4 4 ÷ κo
Display: 4.3961939 −02, that is 0.043962.
0 . 0 3 8 5 −
0 . 0 2 8 5 ↔ ÷
Display: 5.2179271 → about 5 letters. The MK-61 carries eight digits and the subtraction κo − κr cancels about one of them, so its last two digits sit a little off the HP machines’ 5.21793.
TI-84
Enter the 26 counts into list L1 (STAT → Edit), then on the home screen:
sum(L1²) 9131 (sum( is in 2nd STAT → MATH)
(Ans-445)/(445*444) 0.043961939… κo
0.0285/(Ans-0.0385) 5.21792674… K
Results: κo ≈ 0.0440, K ≈ 5.2 → about 5 letters. 1-Var Stats on L1 also shows Σx = 445
and Σx² = 9131 directly.
Casio fx-991
Put the machine in STAT mode, choose 1-VAR, and enter the 26 counts in the table. Leave the table
(AC), then open the statistics menu (SHIFT 1 on a ClassWiz; SHIFT 1 also on the fx-991ES)
and read the sum Σx² (it shows 9131) and Σx (445). Then, on the calculation screen:
(9131 − 445) ÷ (445 × 444) 0.043961939… κo
0.0285 ÷ (Ans − 0.0385) 5.21792674… K
Results: κo ≈ 0.0440, K ≈ 5.2 → about 5 letters.
Bonus: The Coincidence Counter
For programmable calculators only.
What this is for. The main challenge was one tally, worked once, by hand. A bureau that is watching a whole day’s traffic gets dozens of tallies, and each one needs the same routine: square the twenty-six counts, add them up, work out κo, then turn it into a keyword length. Done by hand that is slow, and one slipped digit in a sum of squares quietly gives a wrong answer. The job is a good fit for a program, because every tally goes through the same steps. You key in the counts, the calculator does everything else, and you read the answer.
Writing it teaches three things that carry over to any program that processes a list:
- Accumulate as you go. The program never stores the 26 counts. As each one arrives it adds the count to a running N and its square to a running Σ n², then forgets it. Two totals are all that the formula needs, and they fit in two registers.
- Control a loop by counting. The program has to know when the input has ended. A count of zero is a real entry (some letters never appear), so zero cannot be the signal. It has to count the entries instead.
- Guard the division. The formula divides by κo − κr, and that can be zero or negative. A program that just divides will print a confident-looking number that means nothing.
The task. You key in the 26 letter counts one after another, in alphabetical order (A first, Z
last), pressing R/S after each. The program is not told N: it has to add the counts up itself. After
the 26th count it stops with the key-length estimate K in X and κo in Y, using the same
κp = 0.067 and κr = 0.0385 as before.
How to read the result. κo in Y tells you which kind of cipher you are looking at: near 0.067 means a single alphabet, near 0.0385 means many. K in X turns that into a rough keyword length (an answer near 1 means there is no keyword at all). It is an estimate, and a short tally can be badly off. That is why the program should report it honestly, not dress it up.
One case needs care. If κo is no larger than κr, the formula divides by zero or gives a negative length, and means nothing: the tally looks like pure noise, not a keyword. In that case the program must stop with K = 0 in X (meaning “no estimate”), and κo still in Y.
Test it on these four tallies. Each has 26 counts, A to Z:
| Case | Counts, A to Z |
|---|---|
| A | 28 13 11 9 49 9 9 21 16 0 4 10 7 22 25 5 1 31 27 33 11 4 7 0 6 0 |
| B | 13 18 22 17 17 18 16 17 12 2 14 8 10 9 32 9 4 25 31 12 5 8 10 8 15 6 |
| C | 10 7 7 12 13 11 18 16 22 7 21 11 16 19 3 11 7 10 9 40 14 11 14 22 16 11 |
| D | 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 |
Click for a hint
Three registers do the work: one for N, one for Σ n², and one that counts down from 26. A count of zero is a real entry, so it cannot be used to say “that was the last one”. Use the counter.
When the program resumes after R/S, the count you typed is sitting in X. Add it to the N register,
then square it (ENTER ×) and add that to the Σ n² register. Then decrement the counter, and go
round again while it is not zero. The 26th pass falls out of the loop.
At the end, κo = (Σ n² − N) / (N (N − 1)). Compute d = κo − 0.0385 before dividing, and test it. If d is not above zero, put 0 in X instead. Save κo in a register so that it is easy to leave it in Y.
Click to reveal the solution
| Case | N | κo | K |
|---|---|---|---|
| A | 358 | 0.0654 | 1.0596 |
| B | 358 | 0.0471 | 3.3129 |
| C | 358 | 0.0462 | 3.7188 |
| D | 260 | 0.0347 | 0 (no estimate) |
What the cases are. Case A is plain, unenciphered English, so κo comes out near κp and K is about 1: one alphabet. Case B is the same text enciphered with a three-letter keyword, and K = 3.3 is a fair estimate. Case C is enciphered with a seven-letter keyword, and the estimate is 3.7, nowhere near seven. It is a reminder that a tally this short cannot be trusted to give the length. Case D is a perfectly flat tally, ten of every letter: κo = 0.0347 is below κr = 0.0385, so there is no estimate and the program returns 0.
The method. Keep N, Σ n² and a counter of the letters still to come. After each count n:
N ← N + n
Σn² ← Σn² + n²
When the counter reaches zero:
κo = (Σn² − N) / (N (N − 1))
d = κo − 0.0385
K = 0.0285 / d if d > 0
K = 0 otherwise
Why a counter and a guard. The tally for case A contains three zero counts, so no value of a count can mark the end of the input. And case D shows the formula’s blind spot: a tally that looks more random than random gives d < 0 and a negative K, which a program that only divides would show as a plausible-looking number.
Programs
Programs follow for the HP-42S, HP-15C, HP-41C and Elektronika MK-61. Open the one for your calculator,
key it in once, start it, then key in the 26 counts, pressing R/S after each. The text to the right of
a listing explains it; do not key it in. For case B, the counts to key in are:
13 18 22 17 17 18 16 17 12 2 14 8 10 9 32 9 4 25 31 12 5 8 10 8 15 6
HP-42S
This program uses 38 lines. Press PRGM, key in the lines, press PRGM again. The loop uses DSE,
which subtracts 1 from the counter and skips the next line when it reaches zero.
01 LBL 01 start
02-04 0 STO 01 STO 02 N = 0, Σn² = 0
05-06 26 STO 03 counter
07 LBL 02 top of the loop
08 STOP wait for a count
09 STO+ 01 N + n
10-12 ENTER × STO+ 02 Σn² + n²
13 DSE 03 counter − 1; skip the next line when it is zero
14 GTO 02 more counts: round again
15-19 RCL 02 RCL 01 − RCL 01 ÷ (Σn² − N) / N
20-23 RCL 01 1 − ÷ ÷ (N − 1): this is κo
24 STO 04 keep κo
25-26 0.0385 − d = κo − κr
27 X≤0? d not above zero?
28 GTO 03 then no estimate
29-31 0.0285 X<>Y ÷ K = 0.0285 / d
32-33 RCL 04 X<>Y K in X, κo in Y
34 STOP
35 LBL 03 no estimate
36-38 RCL 04 0 STOP X = 0, Y = κo
To run it, start it and key in the counts. For case B:
XEQ 01
13 R/S
18 R/S
22 R/S
… the rest of the 26 counts, each followed by R/S
6 R/S
After the last R/S, K ≈ 3.3129 is in X. Press X<>Y to see κo ≈ 0.0471.
HP-15C
g P/R toggles program mode. LBL 1 is f LBL 1. The tests are g x=0 (the g × key) and
g x≤y (g ÷); each runs the next line only when it is true. STO + is STO then +. The 15C works at
its own speed, so after each R/S wait for the program to stop before keying in the next count.
f LBL 1 start
0 STO 1 STO 2 N = 0, Σn² = 0
2 6 STO 3 counter
f LBL 2 top of the loop
R/S wait for a count
STO + 1 N + n
ENTER × STO + 2 Σn² + n²
1 STO − 3 counter − 1
RCL 3 g x=0 counter zero?
GTO 3 then finish
GTO 2 else round again
f LBL 3 all 26 counts in
RCL 2 RCL 1 − RCL 1 ÷ (Σn² − N) / N
RCL 1 1 − ÷ ÷ (N − 1): this is κo
STO 4 keep κo
0 . 0 3 8 5 − d = κo − κr
0 x≷y g x≤y d not above zero?
GTO 4 then no estimate
0 . 0 2 8 5 x≷y ÷ K = 0.0285 / d
RCL 4 x≷y R/S K in X, κo in Y, stop
f LBL 4 no estimate
RCL 4 0 R/S X = 0, Y = κo
To run it, start it and key in the counts. For case B:
GSB 1
13 R/S
18 R/S
… the rest of the 26 counts, each followed by R/S
6 R/S
The display then shows K: ≈ 3.3129.
HP-41C
LBL is the gold shift of STO, GTO the gold shift of RCL, and the tests are X=0? (gold ÷) and
X<=Y? (gold +); each runs the next line only when it is true. STO + is STO then +. The 41C is
slow: wait for the program to stop before keying in the next count.
LBL 01 start
0 STO 01 STO 02 N = 0, Σn² = 0
26 STO 03 counter
LBL 02 top of the loop
R/S wait for a count
STO + 01 N + n
ENTER × STO + 02 Σn² + n²
1 STO − 03 counter − 1
RCL 03 X=0? counter zero?
GTO 03 then finish
GTO 02 else round again
LBL 03 all 26 counts in
RCL 02 RCL 01 − RCL 01 ÷ (Σn² − N) / N
RCL 01 1 − ÷ ÷ (N − 1): this is κo
STO 04 keep κo
0.0385 − d = κo − κr
0 X<>Y X<=Y? d not above zero?
GTO 04 then no estimate
0.0285 X<>Y ÷ K = 0.0285 / d
RCL 04 X<>Y R/S K in X, κo in Y, stop
LBL 04 no estimate
RCL 04 0 R/S X = 0, Y = κo
To run it, start it and key in the counts. For case B:
XEQ 01
13 R/S
18 R/S
… the rest of the 26 counts, each followed by R/S
6 R/S
The display then shows K: ≈ 3.3129.
Elektronika MK-61
This program uses 63 of the machine’s 105 steps. Put the machine in program mode (F ПРГ), key it in,
and leave it with F АВТ. С/П is the run/stop key. A conditional jump takes its two-digit address as
one step and jumps when its test is false: F x=0 06 goes back to step 06 while the counter is not
zero, and F x≠0 47 goes to step 47 when d is zero, and F x<0 51 goes to step 51 when d is not
negative. ↔ swaps X and Y; В↑ is the Enter key. A number typed straight after a recall replaces it,
so each constant follows a В↑.
00-05 0 x→П 1 x→П 2 2 6 x→П 3 N = 0, Σn² = 0, counter = 26
06 С/П top of the loop: wait for a count
07-10 x→П 5 П→x 1 + x→П 1 N + n
11-16 П→x 5 В↑ × П→x 2 + x→П 2 Σn² + n²
17-21 П→x 3 В↑ 1 − x→П 3 counter − 1
22-23 F x=0 06 not zero: round again
24-28 П→x 2 П→x 1 − П→x 1 ÷ (Σn² − N) / N
29-34 П→x 1 В↑ 1 − ÷ x→П 4 ÷ (N − 1): κo, kept in register 4
35-42 В↑ 0 . 0 3 8 5 − d = κo − κr
43-44 F x≠0 47 d = 0: no estimate
45-46 F x<0 51 d ≥ 0: go and divide
47-50 П→x 4 В↑ 0 С/П no estimate: X = 0, Y = κo
51-62 В↑ 0 . 0 2 8 5 ↔ ÷ П→x 4 ↔ С/П K in X, κo in Y
To run it, start it and key in the counts. For case B:
БП 0 0 С/П
1 3 С/П
1 8 С/П
… the rest of the 26 counts, each followed by С/П
6 С/П
The display then shows K: ≈ 3.3129. The MK-61 works to eight digits, and the subtraction κo − κr costs it one of them, so its last digits sit a little off the HP machines’.
Sources
- William F. Friedman introduced the index of coincidence in The Index of Coincidence and Its Applications in Cryptography (Riverbank Publication No. 22, 1922); see the Index of coincidence article for the bibliographic details and for κp ≈ 0.067 and κr = 1/26.
- The key-length estimate (κp − κr) / (κo − κr) and the definition of κo are given in the Friedman test section of the Vigenère cipher article.
Solvable on: HP-42S, HP-15C, HP-41C, HP-48GX, HP-25, Elektronika MK-61, TI-84, Casio fx-991