Polyalphabetic Ciphers: Vigenere and the Autokey

Breaking it: find the key length first

A polyalphabetic cipher is a set of monoalphabetic ciphers interleaved. So if you know the key length, you have already won: take every ninth letter of the ciphertext and you have a monoalphabetic cipher on that column, which the chapter on frequency analysis broke. The whole attack therefore reduces to finding the key length.

There are two classical methods.

Kasiski's method. If two identical plaintext sequences happen to line up with the same part of the key, they produce identical ciphertext sequences. So look for repeated sequences of three or more letters in the ciphertext, measure the distances between them, and the key length is likely to be a common factor of those distances. In the example above, the sequence VTW appears twice, nine letters apart, and the key is nine letters long.

The index of coincidence. This one is more reliable and is what the program below uses. The index of coincidence of a text is the probability that two letters drawn at random from it are the same letter. For English it is about 0.0667, because English is lumpy. For a text whose letters are uniformly spread it is 1 in 26, which is about 0.0385.

Now the trick. Guess a key length m. Split the ciphertext into m columns, taking every mth letter. If the guess is right, each column was enciphered with a single shift, so each column is a monoalphabetic cipher on English and its index of coincidence should be close to English's 0.0667. If the guess is wrong, the columns mix several shifts and their index will be near 0.0385.

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def letters(s):
    return "".join(c for c in s.upper() if c in ALPHABET)

def vigenere(text, key, sign=1):
    t, k = letters(text), letters(key)
    return "".join(ALPHABET[(ALPHABET.index(t[i])
                             + sign * ALPHABET.index(k[i % len(k)])) % 26]
                   for i in range(len(t)))

def ic(s):
    t = letters(s)
    n = len(t)
    if n < 2:
        return 0.0
    return sum(t.count(c) * (t.count(c) - 1) for c in set(t)) / (n * (n - 1))

plain = "wearediscoveredsaveyourself"
key = "deceptive"
cipher = vigenere(plain, key)
print("plaintext :", letters(plain))
print("key       :", (letters(key) * 4)[:len(letters(plain))])
print("ciphertext:", cipher)
print("decrypted :", vigenere(cipher, key, -1))
print()

long_plain = ("the examination section will publish the seat numbers for the theory "
              "papers on the college notice board and on the college website before "
              "the end of this month so that every student can check the hall and the "
              "date of each paper well before the examination begins")
long_cipher = vigenere(long_plain, "deceptive")
print("index of coincidence of the plaintext :", "%.4f" % ic(long_plain))
print("index of coincidence of the ciphertext:", "%.4f" % ic(long_cipher))
print("English is about 0.0667, a flat random text about 0.0385")
print()
print("average index of coincidence of the columns, for each assumed key length:")
best = []
for m in range(1, 13):
    cols = [long_cipher[i::m] for i in range(m)]
    avg = sum(ic(c) for c in cols) / m
    best.append((avg, m))
    print("   length %2d  %.4f" % (m, avg))
best.sort(reverse=True)
print()
print("the three highest:", ", ".join("%d (%.4f)" % (m, a) for a, m in best[:3]))
print("the real key length is", len("deceptive"))

plaintext : WEAREDISCOVEREDSAVEYOURSELF
key       : DECEPTIVEDECEPTIVEDECEPTIVE
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ
decrypted : WEAREDISCOVEREDSAVEYOURSELF

index of coincidence of the plaintext : 0.0736
index of coincidence of the ciphertext: 0.0409
English is about 0.0667, a flat random text about 0.0385

average index of coincidence of the columns, for each assumed key length:
   length  1  0.0409
   length  2  0.0395
   length  3  0.0473
   length  4  0.0397
   length  5  0.0401
   length  6  0.0444
   length  7  0.0393
   length  8  0.0402
   length  9  0.0717
   length 10  0.0392
   length 11  0.0419
   length 12  0.0419

the three highest: 9 (0.0717), 3 (0.0473), 6 (0.0444)
the real key length is 9

Read four things out of that run.

The cipher did its job. The plaintext's index of coincidence is 0.0736, a little above English's average because this passage repeats words like "the" and "examination". The ciphertext's is 0.0409, close to flat random. Frequency analysis on the ciphertext as a whole is dead.

Key length 9 stands out, and by a wide margin. 0.0717 against 0.0473 for the next best. This is what makes the method practical: you do not need judgement, you take the largest.

The second best is a divisor of the answer, and that is not a coincidence. Length 3 scores 0.0473 because 3 divides 9: splitting into three columns groups key positions 1, 4 and 7 together, so each column mixes three shifts rather than nine and is lumpier than random even though the guess is wrong. So a divisor of the true length scores above the ordinary run, and the rule for reading the table is to take the largest good score, not the first: if 3 were taken as the answer, 9 would be missed. Length 6 at 0.0444 is not a divisor of 9 and is simply noise, which is the honest caution: on a sample of 216 letters the low scores sit between 0.0392 and 0.0444 and a single value in that band means nothing.

0.0717 is above English's 0.0667, which looks wrong and is not. Each column is a monoalphabetic cipher on a sample of only twenty-four letters, and the index of coincidence of a small sample is noisy. The method finds the key length; it does not measure English precisely.

After the key length: recovering the key

Once the length is 9, take column 0, which is every ninth ciphertext letter starting at the first. It was produced by shifting English by one fixed amount, so run the Caesar break of the earlier chapter on it: try all 26 shifts and take the one whose letter frequencies fit English best. That gives the first letter of the keyword. Repeat for the other eight columns. The whole key falls out, and with it the message.

This is why the length of the keyword matters so much. A keyword of length 9 on the 216-letter message above gives each column 24 letters, which is thin but workable. A keyword as long as the message gives each column one letter, and then there is nothing to count, which is the one-time pad of the next chapter.

The autokey cipher: the improvement that does not work

Vigenere himself proposed a better scheme. The trouble with a repeating keyword is exactly that it repeats, so use the plaintext itself to extend the key: start with the keyword and then continue with the plaintext.

key        D E C E P T I V E W E A R E D I S C O V E R E D S A V
plaintext  W E A R E D I S C O V E R E D S A V E Y O U R S E L F
ciphertext Z I C V T W Q N G K Z E I I G A S X S T S L V V W L A

There is now no period at all, so Kasiski's method and the index of coincidence both have nothing to find. And the cipher is still broken, because the key is English. The attacker guesses a short piece of key, decrypts a few letters, and if the result is English then those plaintext letters are also key letters further along, which decrypt more, which give more key. The attack propagates through the message from any correct guess. The statistical structure of the plaintext leaked into the key, and that is fatal.

The lesson is worth an answer of its own: removing the period is not enough. The key must also be unpredictable.

Distinctions that carry marks

What beginners get wrong here

Thinking Vigenere is unbreakable. It was called le chiffre indechiffrable for three hundred years and it is broken by a schoolchild with a spreadsheet. Any answer claiming it is secure is wrong.

Forgetting to find the key length first. The attack is two stages, and the first stage is the whole difficulty. An answer that jumps to "then use frequency analysis" has skipped the part being examined.

Reading the index of coincidence backwards. A high index means lumpy, English-like text, so a high score means the guessed length is right. Low means flat and wrong.

Taking the smallest good score as the key length. A divisor of the true length scores well too, so take the largest clear winner and treat a smaller good score as a hint that its multiple is the answer.

Thinking the autokey cipher is a real improvement. It removes the period and keeps the predictability, which is the wrong half of the problem to solve.

Quick revision

• Polyalphabetic: several cipher alphabets, selected by the key. Vigenere: C = (p + k) mod 26 with k the key letter, keyword repeated.
• The keyword's length is the period, and the ciphertext's letter frequencies are flattened towards 1 in 26.
• Break in two stages: find the key length, then solve each column as a Caesar cipher.
• Kasiski: repeated three-letter sequences; the key length divides the distances between them.
• Index of coincidence: the chance two random letters are equal. English about 0.0667, flat text about 0.0385. Split into m columns and take the m with the highest average.
• In the run, the true length 9 scored 0.0717 and its divisor 3 scored 0.0473, so take the largest clear winner; the other low scores sat between 0.0392 and 0.0444 and mean nothing individually.
• Autokey: keyword then plaintext, no period, still broken, because the key is English. Removing the period is not enough: the key must be unpredictable.

Test yourself

1. Define a polyalphabetic cipher and give the Vigenere rule. A cipher that uses a set of related monoalphabetic substitution rules, with the key selecting which rule applies at each position. In Vigenere the key is a keyword repeated to the message length, and each plaintext letter is shifted by the value of the key letter above it: C = (p + k) mod 26, with decryption p = (C - k) mod 26.

2. Encrypt CIPHER with the keyword KEY. The key stream is K E Y K E Y, that is 10, 4, 24, 10, 4, 24. C is 2 giving 12, which is M. I is 8 giving 12, which is M. P is 15; 15 plus 24 is 39; 39 modulo 26 is 13, which is N. H is 7 giving 17, which is R. E is 4 giving 8, which is I. R is 17; 17 plus 24 is 41; 41 modulo 26 is 15, which is P. The ciphertext is MMNRIP.

3. Why does Vigenere defeat simple frequency analysis? Because one plaintext letter is enciphered with different shifts at different positions, so its frequency is spread over as many ciphertext letters as the key is long. The ciphertext's letter distribution flattens towards uniform, and the correspondence between a ciphertext letter's count and a plaintext letter is destroyed.

4. What is the index of coincidence, and what are its values for English and for random text? The probability that two letters drawn at random from a text are the same letter. For English it is about 0.0667; for text whose letters are uniformly distributed it is 1 in 26, about 0.0385.

5. How is the index of coincidence used to find the key length? Guess a length m, split the ciphertext into m columns by taking every mth letter, and average the index of coincidence of the columns. If m is right each column is a single-shift cipher on English and the average is high; if m is wrong the columns mix shifts and the average is near 0.0385. The best-scoring m is the key length, and its divisors also score above the rest, which confirms the answer.

6. Describe Kasiski's method. Find sequences of three or more letters that repeat in the ciphertext. Such a repetition usually arises because the same plaintext lined up with the same part of the key, so the distance between the two occurrences is a multiple of the key length. Taking the common factors of several such distances gives the key length.

7. What is the autokey cipher, and why is it still broken? The key is the keyword followed by the plaintext itself, so the key never repeats and there is no period for Kasiski or the index of coincidence to find. It is broken because the key is ordinary English and therefore predictable: a correct guess at a short stretch of key reveals plaintext, and that plaintext is itself key material further along, so a single correct guess propagates through the whole message.