Polyalphabetic ciphers - Vigenere ciphers

The Vigenere cipher is a combination of several Caesar ciphers. Different letters in the plaintext are encrypted with different substitution alphabets.
How it works: Correspondents agree on a keyword. 
To encrypt a plaintext, one writes the keyword repeatedly alongside the plaintext, converts both plaintext and keyword to their numerical equivalents (0-A, 1-B,...25-Z) and adds the corresponding letters modulo 26.
To decrypt a ciphertext, one writes the keyword repeatedly alongside the ciphertext, converts both ciphertext and keyword to their numerical equivalents (0-A, 1-B,...25-Z) and subtracts the corresponding letters modulo 26.

Keyword k=(Subscript[k, 0])(Subscript[k, 1])(Subscript[k, 2])... (Subscript[k, n-1])
Plaintext  x=(Subscript[x, 0])(Subscript[x, 1])(Subscript[x, 2])... 
Ciphertext  y=(Subscript[y, 0])(Subscript[y, 1])(Subscript[y, 2])... , where (Subscript[y, i])= ((Subscript[x, i])+(Subscript[k, (i mod n)]))mod 26

Example: Ecrypt “GOAHEAD” using keyword “WIND”

(({{plain, G, O, A, H, E, A, D}, {x, 6, 14, 0, 7, 4, 0, 3}, {key, W, I, N, D, W, I, N}, {k, 22, 8, 13, 3, 22, 8, 13}, {x+k (mod 26), 2, 22, 13, 10, 0, 8, 16}, {cipher, C, W, N, K, A, I, Q}}))

Example: Decrypt "PWSRPULNB" using keyword "DWIN" 
(({{cipher, P, W, S, R, P, U, L, N, B}, {y, 15, 22, 18, 17, 15, 20, 11, 13, 1}, {key, D, W, I, N, D, W, I, N, D}, {k, 3, 22, 8, 13, 3, 22, 8, 13, 3}, {y-k (mod 26), 12, 0, 10, 4, 12, 24, 3, 0, 24}, {plain, M, A, K, E, M, Y, D, A, Y}}))

Index of coincidence of a ciphertext

Experiment: Pick a pair of letters from a text. What is the probability of two letters being identical? 
Assume that the text has n letters, counting repetitions, distributed as follows: (Subscript[n, 0]) occurences of “A”, (Subscript[n, 1]) occurences of “B”, ... (Subscript[n, 25]) occurences of “Z”, where (Subscript[n, 0])+(Subscript[n, 1])+... (Subscript[n, 25])=n.

Counting Probabilities: Total number of ways in which the experiment can turn out: C(n,2)=((n(n-1))/2).
Total number of ways in which identical pairs can be obtained: C((Subscript[n, 0]),2)+C((Subscript[n, 1]),2)+...C((Subscript[n, 25]),2)=(∑_(i=0)^25)(((Subscript[n, i])((Subscript[n, i])-1))/2)

Definition: The number I=(2/(n(n-1)))(∑_(i=0)^25)(((Subscript[n, i])((Subscript[n, i])-1))/2)=(1/(n(n-1)))(∑_(i=0)^25)(Subscript[n, i])((Subscript[n, i])-1) is called the index of coincidence of the ciphertext. It represents the probability that two letters selected at random from the ciphertext are identical.

The index of coincidence of an alphabet in which each letter has the same frequency is  1/26 ≃ 0.0385 
The index of coincide of the English alphabet is about 0.065

Monoalphabetic substitution (Caesar, Affine, Permutation): I≃ 0.065
Polyalphabetic substitution (Vigenere cipher):  I ≃ (closer to) 0.0385 
Vigenere ciphers from longer keywords have a more uniform distribution of letters, so the index of coincidence is closer to 0.0385. If the keyword is short, then the index of coincidence is closer to 0.065.

Connection between I and the keyword length

Formula (Friedman’s Test): Suppose that a ciphetext with n letters was obtained by a Vigenere encoding using a keyword with length k. Then the length of the keyword is approximatively k ≃((0.0265 n)/((0.065-I)+n(I-0.0385))).

How it works :

Suppose that the ciphertext has n letters and the Vigenere keyword has k letters. Assume for simplicity that n is a multiple of k. We can group the letters of the ciphertext in a table with k columns and n/k rows, where the letters in each column are encoded with the same ciphertext.

Each column is a shift encipherment by an ammount corresponding to the key letter. If we choose a pair of letters at random, then they either:

come from the same column

come from different columns

Let' s analyze these two situations, and compute te probability that the chosen letters are identical.

Case 1.

We have k ways to choose the column and C(n/k, 2) ways to choose a pair of letters from the same column.
Since letters from the same column are encrypted using the same Caesar cipher, they have probabilty 0.065 to be identical. The expected number of identical pairs of letters from the same column is:
S = 0.065*k*C(n/k, 2)

Case 2.

We have C(k,2) ways to choose two distinct columns and n/k ways to choose a letter in the first chosen column, and likewise, also n/k ways to choose a letter in the second column.
Since letters from different columns are encrypted using different Caesar ciphers, they have probabilty 1/26 = 0.0385 to be identical.  The expected number of identical pairs of letters from different columns is:
D = 0.0385*C(k, 2)* ((((n/k)))^2)

Conclusion (Case 1 + Case 2)

The index of coincidence of the ciphertext will be  I ≃ ((S + D)/(C(n,2)))=((0.065*(n-k) + 0.0385*n(k-1))/(k(n-1)))

If we want to guess a probable keyword length k from the index of coincidence of a ciphertext, we take the previous equation and solve for k. We obtain Friedman’s formula: k ≃((0.0265 n)/((0.065-I)+n(I-0.0385)))

Exercise:

The following ciphertext was produced using a Vigenere cipher with a keyword of unknown length k. 
“KIVQXTCQQVRPQOSGWEKVMTRYNHJVUVVKBMDPKVHKWBUWFVZFNOPQOSGWEKVMTRYNHJGDPKOV”.

Write a function that computes the index of coincidence of a ciphertext.

Find an approximation of the length of the keyword, using Friedman's test. Now you know that approximatively k Caesar ciphers were used to encode the text.

Try to break all of them. If frequency analysis does not work, then use the additional information that the cipher block “PQOSG” is an encoding for the plaintext “SOLVE”.

Decode the ciphertext.