Welcome back, time traveler!
It was only moments ago when we first embarked on our journey to discover cryptography, the art of making a message secret through history. With this three-part blog series, I want to observe with you the underlying concepts, play with various mechanisms through historical anecdotes, and see their evolution until today.
In the first part of our journey through time, we explored cryptography in the ancient and medieval years. Before we climb back up our time machine again, make sure you revise your time travel preparation guide!
It’s time for our next big jump, so buckle up!
The evolution of cryptography 1470 AD – 1940 AD
The Cipher Disk
We are in Italy in the middle of the 15th century. Look at this ingenious system; it is an encryption disk created by Leon Battista Alberti.
Source: WikipediaThis disk is a substitution cipher tool that can be used either by leaving the mobile part in the same position (monoalphabetic cipher) or by periodically moving the mobile part (polyalphabetic cipher).
Polyalphabetic encryption uses several symbols to replace the initial symbol. If the position of the character is used to change the cipher character, not only a cipher letter replaces several characters, but the frequency of an original character can no longer be easily determined. That's why frequency analysis loses a lot of its efficiency.
Let's try to find the evolution of this kind of cipher and play with it.
The letter that betrayed her
We are in London at the end of the 16th century. Mary, the former Queen of Scotland is sentenced to death. But what happened? Mary is guilty of high treason; she plotted against Queen Elizabeth of England. The evidence includes coded letters exchanged with a group of Catholic aristocrats. They were led by Anthony Babington who gave his name to the case: Babington Plot. The encryption consisted of the combination of a substitution algorithm and the use of symbols instead of the alphabet.
Source: WikipediaWait, my informant gives me some details about Mary's letters. Ok, I'm confused; I thought we would encounter some short of protection for the frequency analysis, but unfortunately, this is not the case. The letters were coded using a substitution ciphering, the nomenclator, and they were indeed decoded by Thomas Phelippes. Queen Mary was trapped because she was relying on secret communication that was not secure enough.
We have seen that the monoalphabetic substitution was easily breakable thanks to the frequency analysis. The nomenclature version is not that helpful for us, so let's go back to our search for a new cipher.
The Vigenère cipher
We haven’t jumped forward in time, but we did transport from England to France, and we are tracking another polyalphabetic cipher. One of the most famous polyalphabetic ciphers is the Vigenère cipher. In fact, Giovan Battista Bellaso is the creator of this method, and the Vigenère cipher is a variant. Well, how does it work? Basically, it is a combination of multiple applications of the Caesar code — it applies the Ceasar code several times, each time changing the shift at every character. To encrypt a message, instead of keeping the same shift, a table named Tabula recta, or Vigenère table, is used. This table contains all possible Caesar ciphers (26). Each line shifts cyclically to the left compared to the previous.
Source: WikipediaIf only one line is used to encrypt and decrypt the message, it is a simple Caesar code. But if you change the cipher for each character, it becomes a polyalphabetic cipher. To define which line to use for a character, a keyword or keyphrase must be defined beforehand. This word or phrase will be repeated to be at least as long as the message we want to encrypt. Then, for each character, we will take the line that begins with the letter from the key.
Let's play with an example:
The first cipher character is at the intersection of the colon starting with c and the row starting with h; there we find j. The second character is at the intersection of the colon starting with r and rows starting with e; there we find v. Then we continue until the end of the plaintext to encrypt it.
Did you manage to create the cipher text?
This method is more robust than the Alberti cipher as it is not periodic and so it is harder to break. However, the key could also be used on Alberti's disk to encrypt and decrypt messages.
This cipher will be known as unbreakable for three centuries! Some messages were decoded, but no method was reproducible to break any messages.
Let's find out how cryptanalysts broke this new awesome cipher.
Babbage, the Vigenère cipher slayer
We jumped three centuries ahead, and we are now in the middle of the 19th century. A “new” cipher is submitted to the Journal of the Society of the Arts in 1853 by John Hall Brock Thwaites, an amateur cryptographer. Charles Babbage, a famous scientist, and pioneer in computer science declares that it is only a variant of Vigenère's cipher. There follows a public challenge; the goal is to find the key from the original text and the encrypted result. Charles Babbage was not able to resist and will find the key to the greatest disarray of Thwaites (poor, Thwaites!).
Without this event, we probably wouldn't know that he was already able to break this encryption. We have to look at the geopolitical context to understand how such a discovery can remain secret. At that time, the Crimean war was raging, and being able to decipher communications deemed unbreakable is a considerable tactical advantage. It is safe to assume that Charles Babbage was bound to military secrecy to keep this advantage from becoming known to the enemy.
Finally, it will be Friedrich Kasiski, a German infantry officer and cryptographer, who will publish the method of resolution which will bear his name: Kasiski examination. The method starts from a weakness of the Vigenère encryption; the key is repeated to encrypt the message. The basic principle is to find the repetitions in the ciphered words and to check the gap between these repetitions. This gap will be used to define the size of the key. Once the key size is found, the cipher can be divided into simple ciphers and decrypted using frequency analysis.
Let's try this method! We will start with the text that has been decoded thanks to the frequency analysis.
Wpwoh dov dh eglf vr hjcjrkiw tikv xjxu ylxmovv keaioi wlj eoeucutjqq ojy? Iqziaes, vr fj eghlgneov, wlj tfzw rjeeu ws ge mqqk jnpwjl yo ugqh yo bp dzjrbih hnsutlfztjqq sk tig flfrbewiws. Jh lx ns oqw xme dcvi, ttigu gmascfxjrjuwmhs ncb fj utgg wzci cv xme gkuwy lfvwiw fsgtyjnda rv yhf wvyfl qqvmyipp rj aoxgow fne errxoocqxx.
I used this Vigenère cipher online tool to encrypt the text.
Now, we have to search for a repetitive group of symbols and the distances between them. You can do it by hand, but I prefer to use the Vigenère Cryptanalysis (Kasiski's Test) option in the online tool.
The result is six-character long. Now we will split our ciphered text and analyze each group related to the same key character. It will look like this:
Then, for each letter, we will apply the frequency analysis, and find the key and the matching character exactly like Caesar's code.
Finally, we get:
We are lucky because we used computer tools for our example. I’ll let you imagine the complexity of such a task before the computer era.
I'm talking about computers, but I probably should have talked about machines instead. And speaking of machines, there is one that has become a fundamental part of modern history and is now legendary.
Let's discover it!
World Wars decrypted
The 19th century will see the acceleration of scientific discoveries, especially with the electrification of communications. Samuel Morse will participate in the advent of the electric telegraph, and an associated alphabet: the Morse code. The Morse code is based on the sequence of electrical pulses. In fact, it is a simple substitution of a character by a composition of two types of pulses, one short and one long. If you are familiar with binary code, you will easily understand why it is considered the first digital code.
The wireless telegraph appears at the very beginning of the 20th century and uses the Morse alphabet. History repeats itself, a means of communication spreads and so does the need to secure messages. The Morse code is readable by everyone and therefore requires a layer of encryption. Some codes that were considered inviolable, such as the ADFGVX cipher, were quickly broken. It is with this in mind, just at the end of World War I that a German engineer, Arthur Scherbius, created a legendary brand of encryption machine: Enigma.
Source: WikipediaHere we are, during World War II, fighting against the Nazi army. Each intercepted communication can reveal important information and change the course of the war. The Enigma machine will be the communication weapon of the German army which will make it evolve little by little towards the most complex model.
Basically, it is a polyalphabetic cipher with code modification for each character. Each time you type a character on the keyboard, the wheel will move like a distance counter, so the code is different for each character. Moreover, a plug board is used to switch 10 characters and improve complexity. To understand deeply how this marvel of electro-mechanical technology works, I invite you to watch this excellent video.
To realize the power of this encryption machine, let's take it apart and study its mathematics. First, we need to choose 3 wheels among 5: 5x4x3= 60 possibilities Then, we define the initial position of rotors that are composed of the 26 alphabetic characters; 26 * *26 ** 26= 17 576 possibilities. Now the hard part is the plugboard. We need to manipulate the whole alphabet, all permutations available; 26! But we use only 10 permutations, which means 6 characters are ignored; we can divide by 6! We do not care about the order; we can divide by 10! The a->b or b->a permutations are the same: we can divide by 2^10. The whole equation for this part is:
26! / (6! 10! 2^10) = 150 738 274 937 250
Finally:
60 * 17 576 * 150 738 274 937 250 = 158 962 555 217 826 360 000
(wheel choice) * (initial rotor position) * (switchboard) = mind blow
This is a huge number, and what it means is that the code is unbreakable without finding a way to reduce the possibilities and any technique to abstract from the manual resolution.
Ok, maybe I went a little fast, and there are still a lot of unknowns. First of all, the machines must have the same initial settings to be able to decrypt the message; it is then a matter of typing the encrypted message on the machine. The machine does not emit a signal; for each character typed, a light lights up under the result, and an operator must transmit it on paper or via other means of communication. The settings change every day following a specific booklet which is changed every month to prevent the booklet from being compromised. Legend has it that the German Navy used soluble ink to destroy the data easily.
Thanks to documents recovered by the French military intelligence, a Polish mathematician and cryptologist Marian Rejewski aided by Jerzy Różycki and Henryk Zygalski, found the first breach to break the codes on some versions of the Enigma in December 1932. They created a machine called bomba kryptologiczna, the cryptologic bomb.
Whether for technical reasons or because of the deteriorating political situation, the Polish decided to share their findings with their French and British allies in July 1939.
This is where the genius Alan Turing, widely considered to be the father of theoretical computer science and artificial intelligence, intervenes with his team at Bletchley Park.
Enigma had several weaknesses. One of them is that a letter can never be replaced by itself. This means that if we know a piece of the message in plain text, we can match it to the encrypted message and eliminate all positions with a common letter. Now, it happens that every morning, at 6 o'clock, a weather message was sent starting with the weather report "wetterbericht" in German and ending with "heil hitler". This is an entry point for a Known-plaintext attack, also called a crib attack. To reduce the number of possibilities, they developed a machine called Bombe (in honor of its predecessor bomba). To make it simple, it allowed discarding Enigma settings that could not work by successive guesses. Then, all that was left to do was to check all the possibilities that were not discarded by hand. These "cryptographic bombs" represent the first step toward modern computers.
Harry Hinsley, the English historian and cryptanalyst, considered that this work shortened World War II by two years and saved over 14 million lives.
There are countless things to see and explore about this period and the scientists who are at the origins of modern computing, but I’m afraid our time in this period has come to an end!
Getting ready for the final jump
We have reached the end of this second ballad. I hope you have enjoyed it, and that you have been able to discover new things and glimpse the concepts of modern cryptography. Our next stop will be the United States of America in the 1970s.
Rest, and see you soon for a new escapade in the fabulous universe of computer sciences and the configuration of an encryption key!
This is a companion discussion topic for the original entry at https://traefik.io/blog/the-evolution-of-cryptography-in-modern-history/