Polyalphabetic Substitution Ciphers
The development of Polyalphabetic Substitution Ciphers was the cryptographers answer to Frequency Analysis. The first known polyalphabetic cipher was the Alberti Cipher invented by Leon Battista Alberti in around 1467. He used a mixed alphabet to encrypt the plaintext, but at random points he would change to a different mixed alphabet, indicating the change with an uppercase letter in the ciphertext. In order to utilise this cipher, Alberti used a cipher disc to show how plaintext letters are related to ciphertext letters
For example, when the disc on the left is set as shown, we see that the plaintext letter "e" (on the outside ring) is encrypted to "Z" (on the inside ring).
Alberti would use this setting for a few letters of the message, and then rotate the inner disc to a different setting for the next few letters, and so on.

As an example we shall encrypt the plaintext "leon battista alberti". To keep with the convention of writing ciphertext in uppercase, we shall invert Alberti's own rule, and use lowercase letters to signify the change.
We start by referencing the starting position of the cipher disc, which in this case is "a" is encrypted as "V", so we start the ciphertext with a lowercase "v". We then encrypt the first few letters as a Caesar Shift, using the ciphertext alphabet given below.
Plaintext: leonbat...
Ciphertext: vGZJIWVOg...
Ciphertext: vGZJIWVOg...
The uppercase letters above encrypt the plaintext letters given. The "v" indicates the starting position of the disc, and the "g" indicates that we need to change the position so that "G" is beneath "a". We then get the new ciphertext alphabet as shown below.
Plaintext: ...tistaa...
Ciphertext: ...gZOYZGGm...
Ciphertext: ...gZOYZGGm...
This time the plaintext letters are encrypted to the ciphertext letters using the ciphertext alphabet above, and the "m" indicates that we are changing alphabet again to get the final ciphertext alphabet below.
Plaintext: ...lberti
Ciphertext: ...mXNQDFU
Ciphertext: ...mXNQDFU
So we get the final ciphertext "vGZJIWVOgZOYZGGmXNQDFU". Notice how the letter "t" is encrypted to "O" first of all, then "Z" and finally "F". This is the essence of a polyalphabetic cipher, that the same plaintext letter is encrypted to a different ciphertext letter each time.
Clearly this is fairly easy to break as you can use the letters that indicate the change to help you. In particular, in this example, the lowercase letter in the ciphertext matches to "a" in the plaintext alphabet. In reality, you would use a different letter, say "g" as the reference plaintext letter, and then the corresponding ciphertext would have been: "bGZJIWVOmZOYZGGsXNQDFU".
The actual cipher that Alberti himself used was slightly different to this, and the disc he used had some numbers on it which he used to indicate when to turn the disc. For example, a number in the plaintext would encrypt to a letter in the ciphertext. When this was decrypted, the number would be revealed, and the disc would be moved so that the ciphertext letter was the new key letter.

Due to the polyalphabetic nature of the Alberti Cipher (that is, the same plaintext letter is not always encrypted to the same ciphertext letter), it was a very secure cipher when it was invented. However, there are lots of hints within the workings of the cipher as to how it works, and although frequency analysis on the whole message will not work, you can do frequency analysis on the bits between the letters that indicate a change of the disc.
Another early example of a polyalphabetic cipher was invented by Johannes Trithemius in the 15th Century. Rather than switching alphabets randomly, and indicating it with an uppercase letter, the Trithemius Cipher has the sender change the ciphertext alphabet after each letter was encrypted. This was the first example of a progressive key cipher, and he used a tabula recta to show all the different alphabets.
Trithemius' idea was to start at the column headed by "A", find the plaintext letter down the far left column, and encrypt this to the ciphertext letter in the first column. You would then move to the next column, and so on.
For example, the plaintext "johannes trithemius" would be encrypted as follows. The "j" would be found down the left column, and mapped to the letter in the column headed by A (shown in red below). This gives "J". The "o" is found down the left column, and traced to the ciphertext in the B column, which is "P" (shown in blue). The "h" (shown in green) gives "J", the "a" (shown in purple) gives "D", and the "n" (shown in pink) gives "R". Continuing in this way we get "JPJDRSKZ BASETRAXKJ".
The tabula recta is very useful as a reference guide, but this could also be done using a cipher disc, by rotating the inner disc by one after each letter is encrypted. The Trithemius Cipher is an incredibly important step in the development of very secure ciphers, however, due to the lack of any key, it is itself quite weak, as every message encrypted using it uses the same method.
A slightly more secure version of this cipher is to choose two ciphertext alphabets before hand, and alternate between which one you use for each plaintext letter. This adds an element of a key to the cipher. For example, we might use the columns headed by F and Q. This is equivalent to using a Caesar Shift of 5 and 16, but alternating between the two. Although slightly more secure, as there is a key and so it can be personalised (and there are 650 possible keys), this is still vulnerable, as a cryptanalyst can perform frequency analysis on the alternate letters.
We are going to continue our journey by looking at the Vigenère Cipher, one of the biggest advances in cryptography until the invention of computers.