Between the decline of the Roman Empire and the rise of Islam, few advances were made in cryptography. That changed during the early 9th century in the Abbasid Caliphate (modern day Iraq) when an Arab philosopher and polymath made an advance in cryptography that would set off a cryptographic arms race that continues to the present day.

Arab innovation

In the 9th century the intellectual center of the world was in Baghdad, the capitol of the Abbasid Caliphate. And more than any other figure, Al-Kindi was at the head of that intellectual revolution. Besides his contributions to philosophy, astronomy, pharmacology, and mathematics, he is considered the inventor of frequency analysis.

Frequency analysis is a method of breaking substitution ciphers based on how often certain letters or symbols occur. In English, for example, the letter “e” occurs more than any other letter therefore the letter that occurs most often in an enciphered English-language message is likely to be “e”. Al-Kindi took this principal further finding the most common combinations of two and three letters to make breaking ciphers more easy.

As these techniques of deciphering messages became more widespread, methods of encryption had to advance to keep pace. At the same time, the need for need for encryption grew as the world grew more connected and messages had to be sent over longer distances.

Nomenclators

The most obvious way to make frequency analysis more difficult is to increase the number of symbols used. One of the most popular methods of doing this in Renaissance Europe was called a nomenclator. In addition to using homophonic substitution, where more than one symbol (typically numbers) could represent a single letter or sylable, nomenclators could also encode whole words.

In the 16th century an imprisoned Mary, Queen of Scots used a nomenclator to plot the overthrow of Queen Elizabeth I. Unfortunately for Mary the code was broken by Elizabeth’s agents and Mary was executed for treason. By the 19th century the Duke of Wellington’s code breaker, George Scovell, had broken the nomenclator of Napoleon which had over 1,200 numbers representing letters, symbols, and words.

Polyalphabetic substitution

Another method to complicate frequency analysis is to use a different substitution scheme for each letter of the cipher text. Whereas a classic Caesar cipher would use one alphabet shifted by a few positions, a polyalphabetic substitution cipher would use multiple alphabets to encode its message.

The most popular of these polyalphabetic systems was developed by Blaise de Vigenère in the late 1500s. Vigenère’s system used a table (referred to as a tableau) of 26 cipher texts, each shifted by one letter more than the previous. To encode a message a key word or phrase was chosen that would be known by both the sender and receiver. The letters of the keyword would determine which cipher to use to encipher each subsequent letter.

For example, if we were to encipher the phrase GETLEARNT with the keyword SHADY we would encipher the letter G with the cipher that begins with the letter S which would be Y. The next letter, E, would be enciphered with the next letter of our keyword, H, giving us L. The full enciphered message would be:

Plaintext:	G	E	T	L	E	A	R	N	T
Key:	S	H	A	D	Y	S	H	A	D
Ciphertext:	Y	L	T	O	C	S	Y	N	W

Although Vigenère was not the first to conceive of a polyalphabetic cipher, his method was the most popular and was considered unbreakable (it was known as the indecipherable cipher) until the 19th century. A variation of the Vigenère cipher, where the key is the same length as the plaintext, is still considered unbreakable and is called a one-time pad.

Next time

The means of cryptography had changed a lot in the years between Al-Kindi’s writings on frequency analysis and the great wars of the 19th century. Frequency analysis had forced cryptographers to come up with better, more secure methods of encryption, but the confluence of the industrial revolution and the two largest wars the world has ever known would change cryptography more in 50 years than it had changed in the past 500.