The need to transmit concealed messages is as old as civilization itself. In classical cryptography, an encoded message is known as a cipher, and cryptanalysis is the science of decoding them. One of the earliest known mentions of cryptography is found in the Kama Sutra, written around 4th century AD, but based on manuscripts dating back to the 4th century BC. Among many other things, this text advises women to learn the art of secret writing to safekeep knowledge of romantic affairs. One recommended technique was randomly pairing letters of the alphabet and disguising a message using the pairings as a key. Another early example of cryptography comes from Israel around 500BC. The Atbash cipher is a simple substitution where letters are swapped for each other in reverse alphabetical order.
Al-Kindi, an Arab mathematician, published “Manuscript for the Deciphering Cryptographic Messages.” That document is the earliest written example of cryptanalytic techniques, including a description of frequency analysis. That is the frequency that letters typically occur in a language assists in decoding any simple substitution cipher. The Arab’s advanced cryptographic knowledge was considered a secret science, almost lost to history upon the defeat of its empire, and only re-discovered relatively recently. The western world developed its cryptographic knowledge gradually, over the course of the following millennium.
polyalphabetic ciphers came into use. These ciphers used a mixed alphabet for encryption and involved occasionally switching alphabets. This was the first major advance against frequency analysis. A cipher disk, such as shown below, could be used for concealing and revealing messages. The center wheel can be turned to assist encoding and decoding a message.
the Vigenere Cipher was published. The Vigenère cipher involves the use of multiple encryption alphabets, with a key-word for determining how they are applied. This polyalphabetic substitution is easy to understand and implement, remaining unbroken for three centuries.
In the 1600s,
the cryptographers of French King Louis XIV created what was known as the Great Cipher which didn’t submit to cryptanalysis until nearly 1900. This cipher used a set of 587 different numbers to represent each syllable and included ‘null’ numbers meant to prevent frequency analysis.
Throughout the history we’ve discussed so far, knowledge of cryptography and cryptanalysis was sparse, and people who used it were generally overconfident in the systems used. As a modern science, cryptography begins during the 19th century. Edgar Allen Poe was passionately interested in cryptanalysis, believing it required simple logic and reasoning. In 1859 he published a notice in Philidelphia’s Alexander’s Weekly Messenger claiming he could break any substitution cipher, and invite readers to submit challenging ciphers which he proceeded to decrypt. Poe later published an essay on cryptographic methods that was used as an introduction British cryptanalysts working to break German codes during World War I.
Cryptography begins integration with mechanical devices during the 20th century. In 1917, Bell Labs engineer, Gilbert Vernam invented a polyalphabetic stream cipher in which a previously prepared key is combined character by character with the plaintext message to produce the ciphertext. This breakthrough led to the development of the one time pad, the first unbreakable cipher. To be unbreakable, the key must be entirely random, with as many characters as the plaintext, never reused, and remain a secret. Vernam’s key was created with a teleprinter and led to the creation of electromechanical cipher machines.
During World War II,
cipher machines gained popularity, and great advances were made in both cryptography and cryptanalysis. The most widely known cipher machine was made at the end of World War I, in Germany. The Enigma Machine had a set of interchangeable rotors; pressing letters on the keyboard caused its rotors to spin — lighting up the encoded substitute letter. The rotors would change position for each character so that if you typed the same letter twice a different substitute would be used the second time. The Germans produced monthly sheets with different codes for each day, and in this way, the enigma machine’s cipher remained unbroken for several years. To ensure strong encryption, the Germans used a plugboard that swapped two letters before being sent to the rotors for encryption. This system increased the possible initial configurations into the trillions; however, it also created an important weakness.
Enigma was designed so that it was impossible for a character to go through the encryption process and return its own value. Meaning you would always get a different value than the one entered. This feature introduced a vulnerability, allowing plug positions to be deduced by brute force. In 1932 that weakness was discovered by a Polish mathematician, who mathematically determined the detailed structure of the German Enigma machine. Before the end of that decade, Alan Turing designed an electro-mechanical device called Bombe, allowing Britsh cryptanalysts to automate the process.
In addition to the Enigma machines, the Germans also created a One Time Pad. The Lorenz machine was a similar rotor stream cipher device combining the plaintext message with a stream of characters using an XOR function to produce the ciphertext. By design, each message required a new configuration of the rotors so that each encryption key was used only once. However, in August of 1941, a message was transmitted that was not received correctly. The receiving operator sent an unencoded message asking for the transmission to be sent again. This prepared the codebreakers, and when the message was re-sent, they did not change the rotor settings. To make things worse, the second message was sent with slight variations.
When used properly with a random key, the Lorenz cipher was indecipherable by frequency analysis. This fatal mistake, however, allowed codebreakers to determine details of how the rotors worked. Armed with this knowledge, huge cryptanalysis machines were built to aid in the brute force decoding of German encoded messages. Eventually, these electro-mechanical devices gave way to the first programmable digital computers. The initial prototype of the Colossus was in use in 1943, with a total of ten different models used throughout the war effort. This breakthrough allowed the Allies to obtain high-level military intelligence from intercepted German telegraphs.
Throughout recorded history, up until the 1970’s, the art of encryption was a highly secretive practice. Its primary use was to keep state secrets and coordinate military effort. Its secretive nature is especially understandable as knowledge of an encryption method almost invariably led to deciphering its secrets.