Write the ciphertext on a long strip of paper, and again on another long strip. Put one strip above the other, but displaced by a certain number of places (the potential key length). For example, for a displacement of two we have the following:

Mark a $\ast$ each time a letter and the one below it are the same, and count the total number of coincidences. In the text just listed, we have two coincidences so far. If we had continued for the entire ciphertext, we would have counted 14 of them. If we do this for different displacements, we obtain the following data:

We have the most coincidences for a shift of 5. As we explain later, this is the best guess for the length of the key. This method works very quickly, even without a computer, and usually yields the key length.

Now suppose we have determined the key length to be 5, as in our example. Look at the 1st, 6th, 11th, ... letters and see which letter occurs most frequently. We obtain

The most frequent is $G$, though $J\text{,}K\text{,}C$ are close behind. However, $J=e$ would mean a shift of 5, hence $C=x$. But this would yield an unusually high frequency for $x$ in the plaintext. Similarly, $K=e$ would mean $P=j$ and $Q=k$, both of which have too high frequencies. Finally, $C=e$ would require $V=x$, which is unlikely to be the case. Therefore, we decide that $G=e$ and the first element of the key is $2=c$.

We now look at the 2nd, 7th, 12th, ... letters. We find that $G$ occurs 10 times and $S$ occurs 12 times, and the other letters are far behind. If $G=e$, then $S=q$, which should not occur 12 times in the plaintext. Therefore, $S=e$ and the second element of the key is $14=o$.

Now look at the 3rd, 8th, 13th, ... letters. The frequencies are

The initial guess that $L=e$ runs into problems; for example, $R=k$ and $E=x$ have too high frequency and $A=t$ has too low. Similarly, $V=e$ and $W=e$ do not seem likely. The best choice is $H=e$ and therefore the third key element is $3=d$.

The 4th, 9th, 14th, ... letters yield $4=e$ as the fourth element of the key. Finally, the 5th, 10th, 15th, ... letters yield $18=s$ as the final key element. Our guess for the key is therefore

As we saw in the case of the 3rd, 8th, 13th, ... letters (this also happened in the 5th, 10th, 15th, ... case), if we take every fifth letter we have a much smaller sample of letters on which we are doing a frequency count. Another letter can overtake $e$ in a short sample. But it is probable that most of the high-frequency letters appear with high frequencies, and most of the low-frequency ones appear with low frequencies. As in the present case, this is usually sufficient to identify the corresponding entry in the key.

Once a potential key is found, test it by using it to decrypt. It should be easy to tell whether it is correct.

In our example, the key is conjectured to be $(2\text{,}14\text{,}3\text{,}4\text{,}18)$. If we decrypt the ciphertext using this key, we obtain

themethodusedforthepreparationandreadingofcodemessagesis

simpleintheextremeandatthesametimeimpossibleoftranslatio

nunlessthekeyisknowntheeasewithwhichthekeymaybechangedis

anotherpointinfavoroftheadoptionofthiscodebythosedesirin

gtotransmitimportantmessageswithouttheslightestdangeroft

heirmessagesbeingreadbypoliticalorbusinessrivalsetc

This passage is taken from a short article in Scientific American, Supplement LXXXIII (January 27, 1917), page 61. A short explanation of the Vigenère cipher is given, and the preceding passage expresses an opinion as to its security.

Before proceeding to a second method for finding the key, we give an explanation of why the procedure given earlier finds the key length. In order to avoid confusion, we note that when we use the word “shift” for a letter, we are referring to what happens during the Vigenère encryption process.

We also will be shifting elements in vectors. However, when we slide one strip of paper to the right or left relative to the other strip, we use the word “displacement.”

Put the frequencies of English letters into a vector:

Let $A_i$ be the result of shifting $A_0$ by $i$ spaces to the right. For example,

The dot product of $A_0$ with itself is

Of course, $A_i\cdot A_i$ is also equal to .066 since we get the same sum of products, starting with a different term. However, the dot products of $A_i\cdot A_j$ are much lower when $i\ne j$, ranging from .031 to .045:

The dot product depends only on $|i-j|$. This can be seen as follows. The entries in the vectors are the same as those in $A_0$, but shifted. In the dot product, the $i$th entry of $A_0$ is multiplied by the $j$th entry, the $(i+1)$st times the $(j+1)$st, etc. So each element is multiplied by the element $j-i$ positions removed from it. Therefore, the dot product depends only on the difference $i-j$. However, by reversing the roles of $i$ and $j$, and noting that $A_i\cdot A_j=A_j\cdot A_i$, we see that $i-j$ and $j-i$ give the same dot products, so the dot product only depends on $|i-j|$. In the preceding table, we only needed to compute up to $|i-j|=13$. For example, $i-j=17$ corresponds to a shift by 17 in one direction, or 9 in the other direction, so $i-j=9$ will give the same dot product.

The reason $A_0\cdot A_0$ is higher than the other dot products is that the large numbers in the vectors are paired with large numbers and the small ones are paired with small. In the other dot products, the large numbers are paired somewhat randomly with other numbers. This lessens their effect. For another reason that $A_0\cdot A_0$ is higher than the other dot products, see Exercise 23.

Let’s assume that the distribution of letters in the plaintext closely matches that of English, as expressed by the vector $A_0$ above. Look at a random letter in the top strip of ciphertext. It corresponds to a random letter of English shifted by some amount $i$ (corresponding to an element of the key). The letter below it corresponds to a random letter of English shifted by some amount $j$.

For concreteness, let’s suppose that $i=0$ and $j=2$. The probability that the letter in the 50th position, for example, is $A$ is given by the first entry in $A_0$, namely .082. The letter directly below, on the second strip, has been shifted from the original plaintext by $j=2$ positions. If this ciphertext letter is $A$, then the corresponding plaintext letter was $y$, which occurs in the plaintext with probability .020. Note that .020 is the first entry of the vector $A_2$. The probability that the letter in the 50th position on the first strip and the letter directly below it are both the letter $A$ is $(.082)(.020)$. Similarly, the probability that both letters are $B$ is $(.015)(.001)$. Working all the way through $Z$, we see that the probability that the two letters are the same is

In general, when the encryption shifts are $i$ and $j$, the probability that the two letters are the same is $A_i\cdot A_j$. When $i\ne j$, this is approximately $0.038$, but if $i=j$, then the dot product is $0.066$.

We are in the situation where $i=j$ exactly when the letters lying one above the other have been shifted by the same amount during the encryption process, namely when the top strip is displaced by an amount equal to the key length (or a multiple of the key length). Therefore we expect more coincidences in this case.

For a displacement of 5 in the preceding ciphertext, we had 326 comparisons and 24 coincidences. By the reasoning just given, we should expect approximately $326\times 0.066=21.5$ coincidences, which is close to the actual value.

Using the preceding ideas, we give another method for determining the key. It seems to work somewhat better than the first method on short samples, though it requires a little more calculation.

We’ll continue to work with the preceding example. To find the first element of the key, count the occurrences of the letters in the 1st, 6th, 11th, ... positions, as before, and put them in a vector:

(the first entry gives the number of occurrences of $A$, the second gives the number of occurrences of $B$, etc.). If we divide by 67, which is the total number of letters counted, we obtain a vector

Let’s think about where this vector comes from. Since we know the key length is 5, the 1st, 6th, 11th, ... letters in the ciphertext were all shifted by the same amount (as we’ll see shortly, they were all shifted by 2). Therefore, they represent a random sample of English letters, all shifted by the same amount. Their frequencies, which are given by the vector $W\text{,}$ should approximate the vector $A_i\text{,}$ where $i$ is the shift caused by the first element of the key.

The problem now is to determine $i$. Recall that $A_i\cdot A_j$ is largest when $i=j$, and that W approximates $A_i$. If we compute $W\cdot A_j$ for $0\le j\le 25$, the maximum value should occur when $j=i$. Here are the dot products:

The largest value is the third, namely .0713, which equals $W\cdot A_2$. Therefore, we guess that the first shift is 2, which corresponds to the key letter $c$.

Let’s use the same method to find the third element of the key. We calculate a new vector W, using the frequencies for the 3rd, 8th, 13th, ... letters that we tabulated previously:

The dot products $W\cdot A_i$ for $0\le i\le 25$ are

The largest of these values is the fourth, namely .0624, which equals $W\cdot A_3$. Therefore, the best guess is that the first shift is 3, which corresponds to the key letter $d$. The other three elements of the key can be found similarly, again yielding $c\text{,}o\text{,}d\text{,}e\text{,}s$ as the key.

Notice that the largest dot product was significantly larger than the others in both cases, so we didn’t have to make several guesses to find the correct one. In this way, the present method is superior to the first method presented; however, the first method is much easier to do by hand.

Why is the present method more accurate than the first one? To obtain the largest dot product, several of the larger values in W had to match with the larger values in an $A_i\text{.}$ In the earlier method, we tried to match only the $e$, then looked at whether the choices for other letters were reasonable. The present method does this all in one step.

To summarize, here is the method for finding the key. Assume we already have determined that the key length is $n$.

For $i=1$ to $n$, do the following:

1. Compute the frequencies of the letters in positions $i$ mod $n$, and form the vector W.

2. For $j=0$ to $25$, compute $W\cdot A_j$.

3. Let $k_i=j_0$ give the maximum value of $W\cdot A_j$.

The key is probably $\{k_1\text{,}\dots \text{,}{k}_n\}$.