From wax tablets to elliptical curves. A Brief History of Cryptography (Part One)

With this article we inaugurate the section "what about cryptos?" in which we will insert a few articles regarding the fundamentals of cryptocurrencies.

Specifically, let's kick off with this 3-article series, taken entirely from the respective articles published on our Osintops.com project here, with which we will take a short journey (certainly not exhaustive) in the history of cryptography from its origins, as they have come down to us through the writings of some historians, passing through the algorithms and methods that have marked a turning point, up to mentioning the elliptical cryptography, from which the Bitcoin protocol drew.

In apologizing to those who have spent countless hours studying these cryptographic algorithms and to the more skilled readers, I want to clarify that this is not intended to be a technical article or intended for experts in the subject. Rather, it is the first step of a journey that will serve to become familiar with some very popular terms and concepts.
Perhaps it will help us better understand what is under the hood of some procedures that we now take for granted, which we carry out with mechanical gestures, such as electronic signatures.

The book “ The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography" by Simon Singh was a great source of inspiration for me and a stimulus to delve into these topics. I think it is an exciting starting point for all those who approach this subject, even if only out of pure curiosity.

Men have always had the need to be able to send communications that were understandable only to the people for whom they were intended. At the same time other men tried to understand its meaning, thus starting the perennial competition between inventors and code solvers.

This need for confidentiality in communications reached such a level of importance that it was soon seen fit to create an appropriate branch of science, cryptography. On the other hand, cryptanalysis is the discipline that studies the methods for restoring the plain text, starting from the encrypted message without knowing the key.

The first methods to hide a message

In the Bible we can observe one of the oldest ancient cryptographic methods. In the book of Jeremiah, in fact, some words have been replaced by others (Babel has been transcribed with the word Sheshakh) using a monoalphabetic substitution cipher called Atbash, in which the first letter of the alphabet is replaced by the last, the second by penultimate and so on, until obtaining an inverted alphabet.

Among the first authors to narrate examples of cryptography we find the historian Herodotus who, in his Histories dedicated to the wars between the Greeks and the Persians in the fifth century BC, states that it was the secret writing that saved Greece from Xerxes, king of the Persians. He tells of an episode in which, to get a message to Leonidas (king of the Greeks) who then decreed the victory of the Greeks over the Persians, the wax was scraped off a writing tablet and the message was engraved on the underlying wood, covering the tablet again with wax. This trick turns out to be one of the first examples of steganography known to date, a technique considered the ancestor of cryptography since, as the etymology of the word itself suggests, it serves to cover and not to encode a message (from the Greek steganós = covered and gráphein = to write).

Methods to hide messages were also studied and adopted in the Asian continent. In particular, in China, the message to be transmitted was painted on strips of silk. These strips, rolled up, were covered in wax and ingested by the messenger. Once at its destination, the message was recovered with techniques that I prefer not to imagine. They were probably the first "ovulators", at present famous for transporting another type of goods :-).

Over the following centuries, almost all civilizations have adopted methods and stratagems to conceal and make it difficult to decipher the messages deemed important. This system, albeit very ingenious, had the major limitation of leaving the message unencrypted, even if covered up.

An important step forward in this virtual battlefield was the development of cryptography (from the Greek kryptós = hidden), going from hiding the message by concealing it in the most disparate ways so as not to let it be found by anyone who was not the recipient, to hiding the meaning of the message, encrypting it with alterations agreed with the recipient, who only had to reverse the procedure, obtaining the original text.
Encryption can be done in two ways: by substitution and by transposition.

In substitution cryptography it is necessary to swap each letter of the alphabet with another, shifting the alphabet by a constant number of positions. With this method the position of the letters within the alphabet always remains the standard one, both in the original message and in the one used for encryption.

One of the first and most famous examples of this encryption method was the so-called Caesar Cipher, the use of which by Julius Caesar himself was narrated in his De bello gallico.

Transposition encryption, on the other hand, causes the letters of the original message to swap places with each other, effectively forming an anagram. To increase the security of this method, it should be used on long enough messages.

Ultimately, if in substitution encryption each character of the original message is simply shifted by a predetermined number of positions, always retaining its original place within the alphabet, in transposition encryption each letter represents itself, but is placed in a different position, mixing the letters and thus forming a large anagram of the sentence.

Over the centuries it has been seen that these methods were rather weak, also because of the birth of cryptanalysis, a science born of Arab civilization in the Middle Ages which set itself the goal of interpreting messages without knowing the relative keys.

One of the pioneers of what would later become a real scientific discipline was a scientist of Arab origins (not surprisingly!), Abū Yūsuf Yaʿqūb ibn Isḥāq al-Kindī, known as Al-Kindi. In addition to being a philosopher and having had the merit of importing the thoughts of the great Greek philosophers into the Arab world, he was the first to devise a method which made it possible to decipher a text by analyzing the frequencies of the letters used, laying the foundations for creating frequency analysis cryptanalysis.

All this has led, over time, to the search for increasingly complex methods in order to make the job of deciphering messages more difficult.

The history of cryptography has seen artistic personalities of the caliber of Leon Battista Alberti at its service, who used two cipher alphabets for the first time, or Blaise de Vigenère who, with his Vigenère Table, adopted 26 cipher alphabets, laying the foundations for modern encryption systems.

With the invention of the radio, by Guglielmo Marconi in 1894, people began to think about remote communication and, of course, to apply message encryption techniques, especially in the military sphere. Given the simplicity and speed of communication of texts via radio waves, efforts to create ever more complex encryption methods increased and parallel attempts at decryption intensified.

Since it was above all during the world wars that these coded messages assumed extreme importance, a battle within a battle was created: if on the one hand traditional weapons were used to gain positions in the enemy camp, on the other front the weapons were represented by numbers, spaces and letters. One of the first radio encryption methods was invented by the Germans and was called ADFGVX.

Subsequently, in an attempt to create an inviolable system, an American engineer and mathematician, Claude Shannon, adapted Vigenère 's system, however introducing the concept of a random key, inserted into a sheet filled with random letters which, with hundreds of other similar sheets, formed a block, an identical copy of which would be used by both the sender and the recipient: hence the name of single- use block cipher (= one-time pad cipher), considered the Holy Grail of cryptography since it was many years an absolutely safe method.

The cipher machines

At the end of this brief historical review of cryptographic methods, certainly not exhaustive, we cannot fail to mention the Enigma cipher machine, conceived by the German inventor Scherbius and adopted by the military forces of the Reich. This ingenious device, in the shape of a typewriter, made it possible to type the message (in the clear text) on the keys and to see the encrypted text appear on a viewer which lit up the letters corresponding to the already encrypted message. The main invention of this machine was located inside, where 2 or 3 rotating exchangers were placed which, with each pressure of the keys, rotated by one position thus providing a very high possibility of combinations.

We could imagine a hypothetical operator sitting in front of this cipher machine, pressing the keys on the letters of the keyboard of the Enigma machine reporting the message to be sent (in clear text). After pressing the key, the electrical impulse crossed the rotors following a path defined by the position of the same and returned back thanks to a reflector, always crossing the rotors. Following this path, the impulse illuminated the light of the letter resulting from the encryption on a special viewer, which the operator then proceeded to transcribe. With each further press of the keys the rotors rotated one position at a time (there were 26 for each rotor, at the end of the revolution of the first rotor, the second would move one position and so on) allowing so the operator to use a polyalphabetic substitution cipher. Since this system could also be used to decrypt messages received with the same system, it was essential to position the rotors of the sending and receiving machines in the same position. This was made possible by means of a register of the daily positions of the rotors distributed to all the units used, through which each operator could have adjusted their rotors based on what was reported in the same, it was a sort of daily calendar of the positions to be applied.

It was thanks to the efforts of Polish analysts in the first place and then a brilliant team of English cryptanalysts that the German messages were deciphered.

In the Government School of Codes and Digits, established in Bletchley Park in England, the brightest minds of England were recruited to solve the puzzle called Enigma.

The intuition of the young mathematician Alan Turing was decisive in this dispute.

Based on his studies concerning a programmable universal logic machine, called Turing machine, he had a calculator built, called Bomb, which was able to quickly determine the initial positions of the rotors of the Enigma machine, thus allowing the decipherment of the entire message. On the subject, in addition to countless books, ranging from historical accounts to science fiction, we like to point out the beautiful film The Imitation Game.

A few years later, in Bletchley Park, in order to decipher the messages of the German cipher device Lorenz SZ40/42, which represented the evolution of the Enigma machine, the mathematician Newman, always starting from Turing's studies on the universal machine, built the Colossus calculator, which was not only decisive in decrypting thousands of messages considered indecipherable at the time, but represents the first example of a programmable computer in the history of information technology, laying the foundations for the creation of modern electronic computers.

These exceptional facts have remained unknown for many years, due to the secrecy imposed by the British government, which forced all the protagonists to absolute secrecy and ordered the destruction of the electronic calculators built.

Part two