0.5 Polyalphabetic Ciphers

Frequency analysis was a devastating attack on monoalphabetic ciphers and they could no longer be considered secure. The next development in cryptography was Polyalphabetic ciphers. The idea behind the polyalphabetic cipher is that a single letter can be encrypted to several different letters instead of just one.

We will study the Vigenere Cipher, which is a polyalphabetic substitution cipher. The keyspace consists of all ordered permutations of the alphabet and we call it a Vigenere square. You can see there are 25 rows that can be used as keys, each numbered with the amount they are shifted.

There are two ways to use this square to form a polyalphabetic cipher.
1. Cycle through all 25 rows in turn. This would mean every twenty-fifth letter is encrypted with the same key.
OR
2. Create a master-key that specifies which order the keys (or rows) are to be used in. This does not have to include all rows. For example we could use k=(5, 2, 16). and then cycle through these three keys. This would mean every third letter is encrypted with the same key.
For each single letter, you are only using 1 key and encryption and decryption works as with monoalphabetic ciphers.

Examples:
Method 1 - (cycle through all keys in order)
When doing this it is useful to have a printed version of the Vigenere Square and use a ruler to make sure you're using the correct key. We will be using key 1 to encrypt the d, key 2 to encrypt the r, key 3 to encrypt the a, and so on.
Plaintext: dragon dream
Ciphertext: etdktt kznkx

Method 2 - using k=(9, 17, 6, 20, 3)
We will use key 9 to encrypt the d, key 17 to encrypt the r, key 6 to encrypt the a, and so on.
Plaintext: dragon dream
Ciphertext: migarw uxydv

Another way of specifying the key for method 2 is to denote each row by the first letter instead of the number of shifts. Thus, in our example our master-key would be "jrgud". This example is not particularly memorable, but a word could be used as the master-key for method 2. The applet below will let you try out the keyword version of the Vigenere cipher. The numerical master-key is calculated and shown so that you can see the relation between the two notations.

Attacking the Vigenere Cipher
Although the Vigenere Cipher seems to defeat frequency analysis, it was not a perfect solution. If you discover the block length (the length of the key), you can still apply frequency analysis given a long enough message. For example, with a 5-character master-key, you apply frequency analysis on characters four letters apart, since they will have been encrypted with the same key.

The Vigenere cipher is also susceptible to the chosen-plaintext attack. This attack is when the adversary (who is trying to spy on your message) is able to use your cryptographic system to encrypt, but not decrypt. What plaintext would you use to try to crack this cipher? Try out some of your ideas in the applet and see if you can force the ciphertext to give away information. (hint)