Cryptography and Cryptanalysis – A Brief Look at How We Keep Information Private
There has been a competition playing out through the centuries. It’s a struggle of those with a secret and those who want to uncover it. It’s the story of cryptography and cryptanalysis.
Each side is constantly trying to outfox the other. Peter Baofu described the competition this way, it is “the never-ending cycle of replacing old broken designs” of cryptography and “new cryptanalytic techniques invented to crack the improved schemes.” In fact, “in order to create secure cryptography, you have to design against [all] possible cryptanalysis.” This means that both sides are in a never-ending arms race.
In his book, The Future of Post-Human Mass Media, Peter Baofu describes two main types of cryptanalysis: Classical and Modern Cryptanalysis. In this blog, we’ll look at the Classical Period to see how this cat and mouse game has played out through time.
One of the earliest forms of “secret codes” is the Substitution Cipher where each letter of the message is systematically replaced by another set of predetermined letters. “The Caesar Cipher,” in its most famous form was used by Julius Caesar himself (1st century, B.C.E):
“Each letter in the plaintext is ‘shifted’ a certain number of places down the alphabet. For example, with a shift of 1, A would be replaced by B, B would become C, and so on.”
Another technique was Steganography, which literally means: “covered writing.” Steganography is the art of concealing a message in plain sight. Mehdi Khosrowpour recounts one of the first recorded instances (in the 5th century, B.C.E):
“Demaratus, a Greek who lived in Persia, smuggled a secret message to Sparta under the cover of wax.” It “was to warn Sparta that Xerxes, the King of Persia, was planning an invasion … by using his great naval fleet. He knew it would be very difficult to send the message to Sparta without it being intercepted. Hence, he came up with the idea of using a wax tablet to hide the secret message. In order to hide the secret message, he removed all the wax from the tablet, leaving only the wood underneath. He then wrote the secret message into the wood and recovered the tablet with the wax.”
Classical Cryptanalytic Response
While the strength of steganography relies on the concealment of the message; substitution ciphers were designed to remain a secret even if the message fell into enemy hands. As long as the cipher was not revealed, it remained a fairly reliable means of securing messages.
All that changed with the first recorded technique of cryptanalysis: Frequency Analysis. This technique “can be traced back to the 9th-century [C.E.], when the Arabian polymath Abu Yusef Yaqub ibn Ishaq Al-Kindi (also known as ‘Alkindus’ in Europe), proposed in A Manuscript on Deciphering Cryptographic Messages.” It comes from the observation that certain letters appear more often than others in a given language (the letter “E,” for example, occurs most often in English). There are also common letter pairings (like “TH” in English).
So, in the case of the Caesar Cipher where the plaintext message is:
meet me at the theater
If each letter is shifted one letter in alphabet, it becomes:
nffu nf bu uif uifbufs
Frequency analysis would note that the most common letter in the ciphertext is “f” (which would suggest it is an “e”) and only letter pairing is “ui” (which would suggest the “u” is “t” and the “i” is “h”). If we replace these portions of the ciphertext we reveal:
_eet _e _t the the_te_
With these two facts of frequency analysis alone we have more than half the message deciphered. With a few logical leaps we could decipher the remaining the five letters.
The Classical Cryptography Counterattack
Over the centuries other ciphers were introduced like the Polyalphabetic Substitution Cipher. Here a repeating, offset key is used to encrypt the plaintext (see picture, courtesy of the Library of Congress). First perfected by Johannes Trithemius in 1518, the person encoding the message would switch alphabets for each letter of the message.
So, “meet me” would now become: “lcbp gy,” a ciphertext that simple frequency analysis could not break since most of the letter and pairing statistics of a given language are not easily recognized.
It was the use of math to break a cipher that led to our current arms race in data security. You need longer keys to encrypt your data and prevent a brute force attack; which, in turn, means you need faster computers to break the encryption; which, in turn, means you need longer keys; etc.
Unlike today, however, it took centuries to break a cipher back then. Now, it is just decades. From the Hebern Electric Super Code Cipher Machine in the 1920s, to the Enigma Machine of the 1930s and 40s, to the Data Encryption Standard (DES) of the 1970s and 80s, each seemed invincible until enhanced cryptanalytic techniques or greater computing power toppled it. Our current cryptography is reliable and secure, but quantum computers loom on the near horizon and their non-binary logic could brute force attack our current public key cryptography and make them insecure.
Fortunately, NIST has already planned for this threat and called for replacements to our current standards, well before it is a crisis.
Syncsort offers NIST-certified encryption solutions to help you protect and secure sensitive information. For more details read the eBook: Encryption, Tokenization, and Anonymization for IBM i: A Quick Guide to Protecting Sensitive Data