William F. Friedman, a famous cryptographer in the U.S. Army, developed a probability/combinatorics method to help break the Vigenère cipher in the 1922. Known as the Friedman Test or the Index of Coincidence, this means of estimating keyword length and finding the keyword revolutionized cryptanalysis and mathematics at the time.
Methodology:
- Index of Coincidence: Given a ciphertext string, s, the attack first calculates the probability of picking two identical characters from s. If s is a monoalphabetic cipher, this probability is about 0.0685, while if s is a polyalphabetic cipher, it's about 0.0385.
Formula:
IndCo(s) =
∑i=126 ni(s)(ni(s) - 1) / (N(N-1)) = # of ways to pick 2 identical letters from s / # of ways to pick any 2 letters from s
where ni is the count of the i-th letter in s, and N is the total number of letters.
- Polyalphabetic Cipher Confirmation: By analyzing the IndCo(s) of the text, you can estimate the keyword length used. Given, for example, that the IndCo(s) = 0.04, roughly 0.0385, you can infer s was likely encoded using a polyalphabetic cipher like Vigenère.
- Key Length Estimation: Begin by testing key length 2, separating the ciphertext into two groups and calculating the Index of Coincidence for each string. If the indices of coincidence are high, the key length is probably 2. If not, try key length 3, 4, ..., until it's high for each string.
- Mutual Index of Coincidence: The next step you can take is to compute the Mutual Index of Coincidence. Used in conjunction with the Index of Coincidence to decrypt the ciphertext, the Mutual Index of Coincidence of two strings s1, s2 is the number of ways to pick two identical characters from s1 and s2. Using the formula below, if the key length is 2, then calculate MutIndCo(s1, s2 + 0) where s1 and s2 are the two strings and s2 is not being shifted at all. If the formula returns a low decimal value, i.e. 0.004, then try shifting s2 by 1, giving a new string. Then, calculate MutIndCo(s1, s2 + 1) and repeat with s2 + 2, ..., + 25 or until you get a value close to 0.0685. This confirms the shift value and you can solve B1 = B2 + k. Start at B1 = A, thus, B2 = A + k, and look through the alphabet until you get a real word. This is the keyword and you can now decrypt the ciphertext. This is more complicated with longer key lengths and requires calculating MutIndCo(s1, si), solving each solution in terms of B1, and then looking through the alphabet.
Formula:
MutIndCo(s, t) =
∑i=126 ni(s) · ni(t)
/ (Ns · Nt) = # of ways to pick identical letters from s and t / # of ways to pick any letter from s and t
where ni(s) and ni(t) are the counts of the i-th letter in s and t, and Ns, Nt are the total number of letters in s and t.
- Decryption Using Keyword: With the help of a Vigenère table, you can use the keyword to decrypt by matching the key and ciphertext letters to the plaintext letters.
As All the Light We Cannot See not only follows the story of Marie-Laure, but also of Werner Pfennig, a Nazi soldier in the surveillance unit. While his role was to locate and destroy illegal radio transmissions, it is possible that these broadcasts were being intercepted and decoded using Friedman's Attack.