How a 17th century cipher became the basis of an unbreakable 20th century cipher

One of the most interesting ciphers designed to eliminate the vulnerability to symbol frequency analysis was the Vigenere cipher. Which later became the basis of unbreakable one-time pads.

The majority of ciphers referenced in historical or fiction works belong to the same family of ciphers — monoalphabetic ciphers. We have already dove into the main vulnerability of this encryption method, which is a probability of cracking the cipher by analyzing the symbol frequency pattern. This is something that was assessed long before any computer ever existed.

One of the most renowned and interesting ciphers designed to eliminate this flaw was the Vigenere cipher. It was attributed to a 17th century French diplomat, yet was actually created by two individuals, independent of each other. Curiously, Blaise Vigenere was not one of them, he just proposed this cipher to Henry III, and the cipher claimed its current name in the 19th century.

The first reference to the cipher can be found in Leon Battista’s book Tractate on Ciphers. He is famous for being the first to propose the theory that would later become linear perspective in paintings. The idea behind the cipher was quite simple, but it brought cryptography to a completely new level, marking the dawn of polyalphabetic ciphers.

In a monoalphabetic cipher, each symbol of the plaintext is substituted by a constant symbol of the cipher text — it’s like using another alphabet. It does not matter, whether the replacements are random, or based on a certain shift value in the alphabet (like in the Caesar cipher), whether they are letters or numbers or any other symbols.

As it was vividly described in Sir Arthur Conan Doyle’s “The Adventure of the Dancing Men,” the substituting symbols can be even pictograms, but that does not spare the cipher from the common vulnerability: one can make assumptions of the keywords used in the encrypted text, or analyze the frequency of a certain symbols in the message, or take other guesses.

Your humble servant once did — just for fun — use this method to decrypt an email, which was delivered in an alternative encoding scheme. And it wasn’t that hard to decode, even without a particular skill or decent computing power.

A polyalphabetic cipher uses a number of different substitute alphabets in cycles. Take the Vigenere’s cipher, and here’s the pattern: we take the Cesar’s cipher as the basis and compile a table that includes all possible shift values:

Infosec history: How a 17 century cipher became the basis of an unbreakable 20 century cipher

Thus we have 26 different substitute alphabets and now we need to decide on the principle of substitution. A simple change to the next alphabet for each new letter would be a decent sophistication element, but once we employ the key phrase, the cipher becomes super hard to break.

Since we started with ancient stories, let’s take VINTAGE as our keyword. In order to encipher a phrase like THINK ABOUT, we need to repeat the key phrase until it matches the length of the plaintext:

Infosec history: How a 17 century cipher became the basis of an unbreakable 20 century cipher

Now, for each of the symbols of the source text we employ the substitute, which is located in the row starting with the letter of the keyword and in the column starting by the letter of the plaintext. For instance, the first letter is replaced by the symbol, which is located in the crossing of the T-column and the V-row – which is “O”.

Infosec history: How a 17 century cipher became the basis of an unbreakable 20 century cipher

The deciphering, then, is the opposite process: we find the rows which correspond to the letters of the keyword, find the cipher letters and then write down the letters which mark the columns, getting the plaintext.

It’s fascinating that the original idea, as designed by Alberti, presupposed a special disk with rotating alphabet rings, and the table, which we described above, was proposed later by another contributor. The disk described in the tractate of 1446 was used, by the Confederates during the Civil War in the US.

Infosec history: How a 17 century cipher became the basis of an unbreakable 20 century cipher

Image source: Wikipedia

In general, the cipher was reputed as quite reliable, was even rendered ‘unbreakable’ by the mathematician Charles Lutwidge Dodgson (a.k.a. Lewis Carrol) and praised by Scientific American Magazine. Yet, its more famed iteration was introduced later as ‘The Gronsfeld Cipher.’ The major difference from its foregoer was the limitation of the replacement alphabets to 10 (according to the number of digits) and the fact that the keyword was a number.

What’s interesting is that the Vigenere cipher was susceptible to cryptic analysis, provided certain conditions. By assessing some characteristics, it was possible to define the length of the key, and then, by analyzing rows of letters, enciphered by the same row of the table, one could employ a standard method based on the frequency of certain letters in the language.

The first to perform a successful attack on a modification of the Vigenere cipher back in 1854 was no one other than Charles Babbage, a pioneer of computing, but the analysis was published by another researcher, Friedrich Kasiski nine months later.

Strange as it seems, it helped to fortify the cipher. One of the enhancements was the use of the keyword, which is equal in length to the message itself, thus eliminating a possibility of frequency analysis.

However, this upgrade brought about another vulnerability: the use of sensible text as a key phrase provided a cryptoanalyst with some statistic information about the key, serving another hint on the venture to decipher the text.

But this idea fueled the next improvement – the use of random sequence of symbols as a keyword.

As a result, this idea was deployed in the concept of one-time pads (OTP). Such ciphers once became unbreakable and were used in the sphere of civil and military cryptography. But this is a story for another day.

Tips