This article deals with the history of encryption and is the first part of two articles about this topic. All techniques were described in a chronological order. In this part of the article I deal with:
- Scytale and transposition cipher
- ROT 13 and Caesar cipher
- Maria Stuart and Babington Plot
- Le Chiffre indéchiffrable (Vigenére square)
With the use of public transmission paths for discrete information, it was neccessary to transmit the information safe and secret. A Information represents (at least for sender and receiver) a sequence of tokens that makes sense to them. Without any sense, it would be just a message. We can define the word information as a message with sense and meaning. Just the sender and the receiver know the logic of the message (to create an information). Well, this is the ideal case, but it is not the reality. Normally, a few more people as the sender and the receiver know the logic and the meaning of a sequence of tokens. The sender and, it’s counter part, the receiver have to consider a technique, to keep the message secure. In the history of humantiy, we found a few examples for encryption methods with political and economical background. But the encryption of private messages was also used, to keep a affair secret. A lot of women used cryptography to send intimate messages to her lovers. In this article, I will try to cover the important examples, to show how necessary encryption is.
The franziscian-monk Roger Bacon was the first, who published a book about encryption methods “Abhandlung über die geheimen Künste und die Nichtigkeit der Magie” (Treatise on the secret arts and nullity of magic). This was happened in the 13th century. Bacon mentioned a few algorithms to encrypt a text with the normal alphabet. For instance “Atbash” (Atbasch) is a simply monoalphabetic substitution with the following rules.
As you can see in the table, the source alphabet was mirrored by the target alphabet. There is nothing special! But how to crack this cipher? To reveal the solution, you have to find out the target language (english, german, e.g.) and after that, you have a table with a letter from the alphabet and the occurring probability of the letter in the specific language (frequency table). With this table, you can find out, how the letters are exchanged. This substituation of two letters is called a bigram (n-gram). In addition to that, you can simply exchange the letters, if you know the applied algorithm and all neccessary parameters. But, this is not the normal case.
Example of a frequency table
|letter||frequency in %|
This table shows the frequency of occurence from all possible letters in the english language.
Nearly all encryption methods, that were invented in this era, works with monoalphabetic substitution. After that, the encryption algorithms were oriented on encoding words (not just simple letters). The mix of encoding words and encrypting letters is called nomenclature codes. This codes works with a substitution table and can also be cracked with a frequency analysis and the semantic knowledge of syllables and words. It would be a great help, to have the knowledge about the sense and the motivation of the message. Often, you can interpret half decrypted parts of a message and try to test any words related to the motivation of the text. To know the syntactic and semantic structure of the encrypted text, is the key of decrypting such nomenclature codes. In the subsequent chapters, I will talk about encryption methods in detail.
Scytale and transposition cipher
To encrypt a plain text with a transposition method means to change the position of a letter in a text. In contrast to the substitution, the transposition method performs no exchange of letters (monoalphabetic substitution), just a change of their positions. This method is immune against frequency analysis. The reason is, that the frequency analysis (at least in this case) can approximatly decide, which language was used to encrypt the message. But why “approximatly”? The frequency analysis can compare the frequency of occurence of every letter, with a frequency table of every language. The frequency table of the language, which matches best with the frequency table of the encrypted message is probably the language of the encrypted message (implied that the cipher works just with transposition). A mixture of transposition and substitution prevents the message from finding out the natural language.
Scytale | source: wikipedia.org
A Scytale is a stick (cylinder) with a strip of paper (or earlier parchment) wound around it. The number of corners is the key to decrypt the text. The sender writes the message on the parchment of his stick. After that, he or she sends a courier to the receiver. The receiver has a stick with the same number of corners and can wound the piece of parchment around his stick. When the receiver has the right stick, he or she can read the decrypted text. This method was used by the Spartans and the ancient greeks to encrypt military messages. The security of a Scytale was really strong. With the idea, to develop a lot of sticks with a different number of corners, the Scytale was assailable. After the invention of mechanically en- and decryption the Scytale as tool was obsolete, but the concept was still used.
ROT 13 and Caesar Cipher
Julius Caesar (dictator of the Roman Republic), known for his assertiveness and wisdom, used a simple (but in his era really strong) method to encrypt his messages to the generals and centurions. He used a technique similar to the Atbasch example above. Of course, Caesar lifes a few decades earlier, but he also knows the idea of monoalphabetic substitution. His cipher can be named ROTx (Rotate x), in which the x is a number, that describes the number of positions to rotate. ROT13 is a special case of the Caesar cipher and the name was created by Usenet users in 1980. This cipher is a Caesar cipher with the shifting factor 13 (x equals 13). Example:
In Caesars era, that cipher was strong, but later, arab scholars invented the frequency analysis method to break such ciphers.
Maria Stuart and Babington Plot
Maria Stuart was born on 8th december of 1542. In 1543 she was crowned as Queen of the Scots. After any affairs, marriages and conspiracies Maria Stuart was deposed and escaped to england. There she was arrested. After 18 years of imprisonment, she has a ray of hope. She receives letters from Anthony Babington. Babington encrypted his letters with nomenclature codes and Maria Stuart knows to decrypt the text. At first she received a paper of all nomencalature codes. After that, Babington sends all encrypted messages. The spy’s of Walsingham, the security minister of queen Elizabeth, analyze the messages that Maria Stuart received. Thomas Phelippes was one of the spy’s. After a couple of message and doing frequency analysis with this message, Phelippes cracks the cipher and decrypt all messages. He found out, that Maria Stuart and Babington planning a assassination against the queen Elizabeth. Then, Walsingham forces Phelippes (who was a genius in faking fonts) to write an encrypted letter to Maria Stuart to find out, which people are the insurgents and the accomplices. After this attack from Walsingham (today, it would be called “Man-in-the-middle-attack”), Maria Stuart was executed in England.
This example makes clear, how risky encryption and the decryption of it can be. This nomenclature code can be decrypted by application of the frequency analysis. But one condition is, that the cracker must know, whether all symbols are substituated, words are encoded or both methods are used. With this knowledge, you can crack this nomenclature codes with a simple frequency analysis.
Le Chiffre indéchiffrable (Vigenére square)
After the invention of the frequency analysis from the arab scholars, the security of the monoalphabetic substitution was broken. Blaise de Vigenére, a french diplomat, used an idea from the italian polymath Leon Battista Alberti to invent a method called polyalphabetic cipher. This cipher works with 26 (because of 26 letters in the latin alphabet) alphabets side by side. Every alphabet starts with another letter. Have a look on the image below:
The Vigenére cipher works with a key phrase. Consider the following example:
|plain text||HELLO WORLD|
|key phrase||KEYKE YKEYK|
|encrypted result||RIJVS UYVJN|
But how does it work? The decryption of a message, that is encrypted with a Vigenére square was, in the era of invention, really strong. You must have the right Vigenére square to decrypt the text. Another renewal was the encryption key. The key was used to encrypt the message. So, the receiver needs the right Vigenére square and the correct key phrase. Now, here comes the explaination of the example above.
The text to encrypt is “HELLO WORLD”. We use the key phrase “KEY” for the encryption. If the key phrase is shorter than the message, then the key phrase will be repeated so long as the length of the plain text will be reached. So, our key phrase is “KEYKEYKEYK”. With our correct Vigenére square, we can start to encrypt the message. The square has a extra alphabet on the upper side and also on the left side. For the first letter from the plain text we have a look on the alphabet in the header row. We call this position plain1(H). After that, we have a look on the left side and we keep our focus on the first letter of the key phrase. This position has the name keyphrase1(K). Now, we have the position of the letter of the plain text and the position of the letter in the key phrase. The cell, were plain1(H) and keyphrase1(K) join together, is the letter of our encrypted text. For that example cell(plain1(H), keyphrase1(K)) = R. For all other letters, the algorithm is the same.
For the era of invention, the polyalphabetic substitution was very strong. The cryptoanalysts countered with a few procedures and algorithms to crack the cipher. One algorithm was used to detect the key length. Some methods to detect the key length with redundancy of natural languages are the Kasiski-test (method of Charles Babbage) and the Friedman-test. In case of a short text, a good method is to find out which words can be placed at the beginning of the text. For instance, the first word “HELLO” is more likely then the word “HFAKF” or other senseless combinations. So the range of possible n-gram’s falls rapidly. So you can appreciate a possible key with a brute force attack. In the best case, you can try to find the key. After you found out any possible parts of the key, you have a simple Caesar cipher, which you crack with the frequency table (precondition: knowledge about the used source language).
The One-Time-Pad (OTP) method is a encryption method that is, when it is used correctly, safe and theoretically not breakable. The concept behind this encryption is, that the key (One-Pad) is used just one time. The second constraint is, that the key phrase is as long as the plain text. Here are any other constraints. The key…
- must be secret
- must be unpredictable and random
- may only be used one time
The recipient receives a bundle of x One-Time-Pad keys. With the keys, the receiver can respond x/2 messages and can answer x/2 messages. There are a lot of methods to en- and decrypt messages. Just one example is the Vigenére square.
As I mentioned a few sentences before, this procedure is absolutly safe (because of the key length). That is a big advantage. On the other hand, it is a high expenditure to bring new keys to the receiver/sender. Furthermore, this method needs a central position, that generates the keys. And last but not least, a strong disadvantage is the way of exchange the keys, which can be attacked. This can be called a Man-in-the-Middle-attack. As you can see, the OTP method is safe, but not practicable with a high number of messages.
This was the first part of my “History of Encryption” series. The second part will deal with:
- Enigma machine
- Public Keys
- Pretty Good Privacy
- Quantum cryptography