The Code Book: The Secret History of Codes and Code-breaking. Simon Singh

Alberti, Trithemius and Porta all made vital contributions, the cipher is known as the Vigenère cipher in honour of the man who developed it into its final form. The strength of the Vigenère cipher lies in its using not one, but 26 distinct cipher alphabets to encrypt a message. The first step in encipherment is to draw up a so-called Vigenère square, as shown in Table 3, a plaintext alphabet followed by 26 cipher alphabets, each shifted by one letter with respect to the previous alphabet. Hence, row 1 represents a cipher alphabet with a Caesar shift of 1, which means that it could be used to implement a Caesar shift cipher in which every letter of the plaintext is replaced by the letter one place further on in the alphabet. Similarly, row 2 represents a cipher alphabet with a Caesar shift of 2, and so on. The top row of the square, in lower case, represents the plaintext letters. You could encipher each plaintext letter according to any one of the 26 cipher alphabets. For example, if cipher alphabet number 2 is used, then the letter a is enciphered as C, but if cipher alphabet number 12 is used, then a is enciphered as M.

      If the sender were to use just one of the cipher alphabets to encipher an entire message, this would effectively be a simple Caesar cipher, which would be a very weak form of encryption, easily deciphered by an enemy interceptor. However, in the Vigenère cipher a different row of the Vigenère square (a different cipher alphabet) is used to encrypt different letters of the message. In other words, the sender might encrypt the first letter according to row 5, the second according to row 14, the third according to row 21, and so on.

      To unscramble the message, the intended receiver needs to know which row of the Vigenère square has been used to encipher each letter, so there must be an agreed system of switching between rows. This is achieved by using a keyword. To illustrate how a keyword is used with the Vigenère square to encrypt a short message, let us encipher divert troops to east ridge, using the keyword WHITE. First of all, the keyword is spelt out above the message, and repeated over and over again so that each letter in the message is associated with a letter from the keyword. The ciphertext is then generated as follows. To encrypt the first letter, d, begin by identifying the key letter above it, W, which in turn defines a particular row in the Vigenère square. The row beginning with W, row 22, is the cipher alphabet that will be used to find the substitute letter for the plaintext d. We look to see where the column headed by d intersects the row beginning with W, which turns out to be at the letter Z. Consequently, the letter d in the plaintext is represented by Z in the ciphertext.

      Keyword W H I T E W H I T E W H I T E W H I T E W H I

      Plaintext d i v e r t t r o o p s t o e a s t r i d g e

      Ciphertext Z P D X V P A Z H S L Z B H I W Z B K M Z N M

      Table 4 A Vigenère square with the rows defined by the keyword WHITE highlighted. Encryption is achieved by switching between the five highlighted cipher alphabets, defined by W, H, I, T and E.

      To encipher the second letter of the message, i, the process is repeated. The key letter above i is H, so it is encrypted via a different row in the Vigenère square: the H row (row 7) which is a new cipher alphabet. To encrypt i, we look to see where the column headed by i intersects the row beginning with H, which turns out to be at the letter P. Consequently, the letter i in the plaintext is represented by P in the ciphertext. Each letter of the keyword indicates a particular cipher alphabet within the Vigenère square, and because the keyword contains five letters, the sender encrypts the message by cycling through five rows of the Vigenère square. The fifth letter of the message is enciphered according to the fifth letter of the keyword, E, but to encipher the sixth letter of the message we have to return to the first letter of the keyword. A longer keyword, or perhaps a keyphrase, would bring more rows into the encryption process and increase the complexity of the cipher. Table 4 shows a Vigenère square, highlighting the five rows (i.e. the five cipher alphabets) defined by the keyword WHITE.

      The great advantage of the Vigenère cipher is that it is impregnable to the frequency analysis described in Chapter 1. For example, a cryptanalyst applying frequency analysis to a piece of ciphertext would usually begin by identifying the most common letter in the ciphertext, which in this case is Z, and then assume that this represents the most common letter in English, e. In fact, the letter Z represents three different letters, d, r and s, but not e. This is clearly a problem for the cryptanalyst. The fact that a letter which appears several times in the ciphertext can represent a different plaintext letter on each occasion generates tremendous ambiguity for the cryptanalyst. Equally confusing is the fact that a letter which appears several times in the plaintext can be represented by different letters in the ciphertext. For example, the letter o is repeated in troops, but it is substituted by two different letters – the oo is enciphered as HS.

      As well as being invulnerable to frequency analysis, the Vigenère cipher has an enormous number of keys. The sender and receiver can agree on any word in the dictionary, any combination of words, or even fabricate words. A cryptanalyst would be unable to crack the message by searching all possible keys because the number of options is simply too great.

      Vigenère’s work culminated in his Traicté des Chiffres (‘A Treatise on Secret Writing’), published in 1586. Ironically, this was the same year that Thomas Phelippes was breaking the cipher of Mary Queen of Scots. If only Mary’s secretary had read this treatise, he would have known about the Vigenère cipher, Mary’s messages to Babington would have baffled Phelippes, and her life might have been spared.

      Because of its strength and its guarantee of security, it would seem natural that the Vigenère cipher would be rapidly adopted by cipher secretaries around Europe. Surely they would be relieved to have access, once again, to a secure form of encryption? On the contrary, cipher secretaries seem to have spurned the Vigenère cipher. This apparently flawless system would remain largely neglected for the next two centuries.

      From Shunning Vigenère to the Man in the Iron Mask

      The traditional forms of substitution cipher, those that existed before the Vigenère cipher, were called monoalphabetic substitution ciphers because they used only one cipher alphabet per message. In contrast, the Vigenère cipher belongs to a class known as polyalphabetic, because it employs several cipher alphabets per message. The polyalphabetic nature of the Vigenère cipher is what gives it its strength, but it also makes it much more complicated to use. The additional effort required in order to implement the Vigenère cipher discouraged many people from employing it.

      For many seventeenth-century purposes, the monoalphabetic substitution cipher was perfectly adequate. If you wanted to ensure that your servant was unable to read your private correspondence, or if you wanted to protect your diary from the prying eyes of your spouse, then the old-fashioned type of cipher was ideal. Monoalphabetic substitution was quick, easy to use, and secure against people unschooled in cryptanalysis. In fact, the simple monoalphabetic substitution cipher endured in various forms for many centuries (see Appendix D). For more serious applications, such as military and government communications, where security was paramount, the straightforward monoalphabetic cipher was clearly inadequate. Professional cryptographers in combat with professional cryptanalysts needed something better, yet they were still reluctant to adopt the polyalphabetic cipher because of its complexity. Military communications, in particular, required speed and simplicity, and a diplomatic office might be sending and receiving hundreds of messages each day, so time was of the essence. Consequently, cryptographers searched for an intermediate cipher, one that was harder to crack than a straightforward monoalphabetic cipher, but one that was simpler to implement than a polyalphabetic cipher.

      The various candidates included the remarkably effective homophonic substitution cipher. Here, each letter is replaced with a variety of substitutes, the number of potential substitutes being proportional to the frequency of the letter. For example, the letter a accounts for roughly 8 per cent of all letters in written English, and so we would assign eight symbols to represent it. Each time a appears in the plaintext it would be replaced in the ciphertext by one of the eight symbols chosen at random, so that by the end of the encipherment each symbol would constitute roughly 1 per cent of the enciphered text. By comparison, the letter b accounts for only 2 per cent of all letters, and so we would assign only two symbols to represent