Studying Cryptography in Historical Order (Part 1)
Welcome to my new series where I’ll be writing blogs on Cryptography in historical order. We’ll explore the origins and evolution of Cryptography over the years and also mention the methods developed to break them which brings the necessity of inventing new ciphers as older ones became vulnerable and insecure.
This Blog consists of 3 parts:
- Overview
- Ancient cryptography (BC)
- Caesar Cipher Explained
[+] Overview
The need to conceal messages and their meaning (i.e., encrypting them) likely emerged soon after the invention of writing. The history of encryption is long, with origins seen in religious uses in ancient Egypt, and military applications in Greek and Roman cultures, through to its pivotal roles during the World Wars and the creation of the first computers, to finally arrive at its modern use in the era of the World Wide Web.
Today, encryption plays a vital role in modern life, often transparent to users, securing transactions across insecure communication channels like the internet. Let’s take a look at the history of encryption algorithms in order to understand their significance over time.
[+] Ancient cryptography (BC)
900 BC: Egyptian Civilization — Use of Non-standard Hieroglyphs
While cryptography looked different in early civilizations, The earliest and first known evidence of the use of cryptography (in some form) dates from 1900 BCE in Egypt. when non-standard hieroglyphs were carved into the wall of the main chamber of the tomb of nobleman Khnumhotep II, The hieroglyphics used were different than the usual ones, in a process now known as symbol replacement. However, these hieroglyphs weren’t necessarily a secret code and are not considered to be a serious attempt at hiding information by experts, Rather, they changed the form of writing to make it appear more dignified.
People had different opinions on the main purpose of these non-standard hieroglyphs. Whether they were intended to appear more dignified, to intrigue or amuse onlookers, remains a mystery. However, it is generally believed that they were not meant to hide secret information
1500 BC: Babylonian — General use of cuneiform script.
In 1500 BC, a Mesopotamian scribe used cryptography where a tablet was found that contained an encrypted formula or recipe for pottery glaze. This example is the first known use of cryptography to hide secret information.
500 BC: Hebrew — Atbash Cipher (first substitution cipher)
Cryptographic techniques began to evolve. The first recorded substitution cipher is the Atbash Cipher, used in the Hebrew world around 500 BC when writing the book of Jeremiah. The Word “Atbash” derives from the first two letters Aleph and Taw and the last two letters Bet and Shin in the Hebrew alphabet.
The Atbash Cipher was a simple fixed substitution cipher where the first letter of the alphabet was substituted with the last, the second with the second last, and so on (A to Z, B to Y, etc.). It offers no variation, making it less versatile. Although rudimentary, it added another layer of secrecy to written texts. A Representation of Atbash Cipher on The Alphabetic Letters can be Presented like this
500- 650 BC: Spartans
Scytale Cipher (First transposition Cipher)
The first recorded instance of encryption being used for military purposes dates back to around 500–650 BC. Ancient Spartans used an early transposition cipher to scramble the order of the letters in their military communications. This allowed secret messages to be sent and received using a device called the ‘skytale’. This device was used by Spartans in the 5th century BCE to send messages between Greek warriors. But wait what is a Transposition Cipher? well just bare with me and everything will be crystal clear.
Birth of Steganography
Steganography is the art of hiding and concealing written messages, such that no one but the sender or receiver even suspects their existence. Steganography also originates from Greece.
According to Herodotus, a Greek historian known as the “Father of History,” Histiaeus devised a clever method of steganography to communicate secretly. Histiaeus, a Greek general and statesman, needed to send a message discreetly. To achieve this, he shaved the head of one of his trusted servants. Then, using a method such as tattooing or possibly incising the message into the scalp, he concealed the message on the servant’s head while the hair was still short. Once the message was applied and the servant’s hair had grown back, the servant was sent on a mission, appearing as if carrying no message at all. The intended recipient, upon receiving the servant, would then shave the servant’s head again to reveal the hidden message. This method was a creative form of steganography, relying on the temporary concealment of the message until it could be revealed by a specific action (shaving the head). It illustrates the lengths to which ancient civilizations went to ensure the secrecy of their communications, even in the absence of modern encryption techniques. Here is an example to Visualize it.
Another well-known tale regarding hidden messages also originates from Greece. In this case, Demaratus (a Spartan king) wrote a warning about a forthcoming attack on Greece from Persia on a wooden tablet, and then covered it with wax, and then sent it appearing to be empty when checked by Persian soldiers. Upon receiving the tablet, the recipient would melt the wax to reveal the hidden message. This method illustrates early steganography techniques where the message was hidden in plain sight, relying on the secrecy of the method rather than encryption.
150 BC: Polybius Square
The Polybius square, also known as the Polybius checkerboard, is a device invented by the ancient Greeks Cleoxenus and Democleitus and made famous by the historian and scholar Polybius around 150 BCE. It was developed for telegraphy. Telegraphy is the long-distance transmission of messages where the sender uses symbolic codes, known to the recipient, rather than a physical exchange of an object bearing the message. so the Polybius square effectively allowed letters to be easily signaled using a numerical system creating a way to communicate text messages through a series of numerical signals.
The device ( Polybius Square ) partitioned the alphabet into five tablets with five letters each (except for the last one with only four). There are no surviving tablets from antiquity. Letters are represented by two numbers from one to five, allowing the representation of 25 characters using only 5 numeric symbols. The original square used the Greek alphabet laid out as follows:
With the Latin alphabet, In order to fit the 26 letters of the alphabet into the 25 cells created by the table, the letters ‘i’ and ‘j’ are usually combined into a single cell. Originally there was no such problem because the Greek alphabet has 24 letters.
Each letter is then represented by its coordinates in the grid. For example, “BAT” becomes “12 11 44”. The 26 letters of the Latin/English alphabet do not fit in a 5 × 5 square, two letters must be combined (usually I and J as above, though C and K is an alternative).
Note that, a table of bigger size could be used if a language contains a large number of alphabets. Alternatively, a 6 × 6 grid may be used to allow numerals or special characters to be included as well as letters.
In The Histories, Polybius specifies how this device could be used in fire signals, where long-range messages could be sent using torches raised and lowered to signify the column and row of each letter. This was a great leap forward from previous fire signaling, which could send prearranged codes only (such as, ‘if we light the fire, it means that the enemy has arrived’).
The Polybius square is also used as a basic cipher called the Polybius cipher. This cipher is quite insecure by modern standards, as it is a substitution cipher with characters being substituted for pairs of digits, which is easily broken through frequency analysis (an attack we are going to mention later). The concept of the Polybius Square influenced the development of various cryptographic techniques such as the Fractionning ciphers and many others, in addition, it can be combined with other cryptographic methods such as the ADFGVX cipher, and Homophonic cipher and also During the Medieval and Renaissance periods.
100–44 BC: Cryptography in Ancient Romans
The ancient Greeks were known to use ciphers (a cipher is an algorithm used for encryption or decryption), to transform a message and to share secret messages with army generals at war. To share secure communications within the Roman army, Julius Caesar is credited for using what has come to be called the Caesar Cipher, Otherwise known as a substitution cipher wherein each letter of the plaintext is replaced by a different letter determined by moving a set number of letters either forward or backward within the Latin alphabet. , each character of the plain text is substituted by another character, forming the cipher text. For example, A becomes D, B becomes E, C becomes F — do you spot the shift of 3?
The Caesar cipher is quite a simple cipher but was very effective and successful in the time of Julius Caesar because very few people could read and write.
The Atbash cipher was the first substitution cipher invented, and the Scytale was the first transposition cipher used for military purposes. However, you might wonder why the Scytale or Atbash cipher did not gain the same fame as the Caesar cipher. The Caesar cipher is more famous due to its association with Julius Caesar who is a well-documented historical figure, which has cemented its place in history. Its simplicity and ease of understanding make it an accessible educational tool, and its frequent appearance in popular media and educational curriculums further enhances its recognition. Additionally, the widespread influence of Roman history in Western culture has helped maintain the Caesar cipher’s prominence over other ancient ciphers.
0–400?: Other Early Uses of Cryptography
These aren’t the only examples, though. There has been evidence of the use of cryptography in almost every major early civilization. In early India, “Arthashashtra,” an ancient work on statecraft written by Kautilya, also known as Chanakya, describes how assignments were given to spies in “secret writing.”
[+] Caesar Cipher Explained
Explanation
The Caesar cipher also known now as the shift cipher or additive cipher is a substitution cipher or, more specifically, a simple monoalphabetic substitution cipher that has a very simple method of encryption. For a Caesar shift, we have a key. The key is the number by which we shift the alphabet since this provides a unique way to describe the ciphertext alphabet easily. (if you don't know what is monoalphabetic substitution cipher then you have to wait for the next blog :) )
The Key used by Caesar was a shift by 3. Each character was shifted by a fixed number of places (3 places) to the left or to the right. , so the character ‘A’ was replaced by ‘D’, ‘B’ was replaced by ‘E’, and so on. The characters would wrap around at the end, so ‘X’ would be replaced by ‘A’. Julius Caesar only used the number 3 as a shift Although we can generalize that method and use any shift other than 3
If you remember the Atbash cipher Which doesn't use a key to encrypt the plaintext or we can say that it only allows the use of a single ‘key’ (‘A’ will always encrypt to ‘Z’, ‘B’ will always encrypt to ‘Y’, etc), meaning that if someone knows a document has been encrypted using the cipher, it would be fairly trivial for them to decrypt it. However, the Caesar cipher provides 25 different ‘keys’ which makes the cipher stronger than the Atbash Cipher.
Algebraic representation
The shift cipher (Caesar cipher) also has another description using modular arithmetic. For the mathematical statement of the cipher, the letters of the alphabet are encoded as numbers
Both the plaintext letters and the ciphertext letters are now elements of the ring Z(26). Also, the key, i.e., the number of shift positions, is also in Z(26) since more than 26 shifts would not make sense (27 shifts would be the same as 1 shift, etc.). The encryption and decryption of the shift cipher follows now as:
Example
If we have the key = 3. Then we will be shifting by 3 to the right to encrypt, as shown in the figure below.
The recipient needs to know that the text was shifted by 3 to the right to recover the original message.
Using the same key to encrypt “TRY HACK ME”, we get “WUB KDFN PH”.
Keyspace
The Caesar Cipher can use a key between 1 and 25. With a key of 1, each letter is shifted by one position, where A becomes B, and Z becomes A. With a key of 25, each letter is shifted by 25 positions, where A becomes Z, and B becomes A. A key of 0 means no change; moreover, a key of 26 will also lead to no change as it would lead to a full rotation. Consequently, we conclude that Caesar Cipher has a keyspace of 25; there are 25 different keys that the user can choose from.
Cryptoanalysis
Breaking Caesar Cipher using brute force attack.
If it is known that a Shift Cipher has been used, but the key is unknown, then it is fairly simple to break the code by a simple brute force attack.
Three important characteristics of this problem enabled us to use brute-force cryptanalysis:
- The encryption and decryption algorithms are known.
- There are only 25 keys to try.
- The language of the plaintext is known and easily recognizable.
This simply means using a trial-and-error approach to attack the cipher. The main weakness of the Shift cipher is the fact that there are only 26 keys, and hence ciphertext alphabets, one of which is the identity mapping that leaves the plaintext unaltered. For this reason, the Brute Force method of attack is very effective on the Shift cipher.
Consider the case where you have intercepted a message encrypted using Caesar Cipher: “YMNX NX FQUMF GWFAT HTSYFHYNSL YFSLT MTYJQ RNPJ”. We are asked to decrypt it without knowledge of the key. We can attempt this by brute forcing, i.e., we can try all the possible keys and see which one of them makes the most sense.
In the following figure, given the intercepted ciphertext “THIS IS ALPHA BRAVO CONTACTING TANGO HOTEL MIKE.”, where we do not know what key has been used, but we do know that a Shift Cipher has been implemented, we must first try a key of 1, then a key of 2, then a key of 3 and so on, until a plaintext that makes sense is returned. we noticed that the key being 5 makes the most sense:
Another high-powered contemporary of Julius Caesar. It is very unlikely that another key will produce a second plaintext that makes sense, so we can assume that this is the correct plaintext (although, with a computer, it would not take long to check the remaining 20 possibilities).
There are two difficulties with this method. The first is that we were lucky in our example above, that we only had to do the decryption 5 times, but it is equally likely that a key of 24 could have been used, and then the time to perform the breaking of the code would be substantial. This is a problem that has been largely overcome by the invention of computers, which can perform all 26 possible calculations in a matter of seconds.
The second problem with the above method is that the message intercepted could be longer than two words, and hence performing each decryption could take a significant amount of time. The way around this is fairly simple, and that is to just look at the first two or three words of the intercept, and perform the calculations on these. You will still find the key, by finding the key that deciphers those words into a meaningful phrase, and can then use the key to decrypt the rest of the message as you would if you had known the key to start with.
Note (Know the Language of the Plaintext)
The third characteristic is significant. If the language of the plaintext is unknown, then the plaintext output may not be recognizable. Furthermore, the input may be abbreviated or compressed in some fashion, again making recognition difficult. For example, the Figure below shows a portion of a text file compressed using an algorithm called ZIP. If this file is then encrypted with a simple substitution cipher (expanded to include more than just 26 alphabetic characters), then the plaintext may not be recognized when it is uncovered in the brute-force cryptanalysis.
The hardest part of breaking a Caesar Box is figuring out the language of the message that it encodes. Once the code cracker figures this out, two scenarios are considered. Either the “attacker” utilizes a technique such as frequency analysis, or they use what is referred to as a brute force attack.
Breaking Caesar Cipher using Frequency analysis
Bruteforcing can be fairly easy against the Shift Cipher if you know that it has been used. However, in reality, it is unlikely that as an interceptor you would know which cipher has been used. There is a general method for attacking all monoalphabetic ciphers called Frequency Analysis. which we are going to talk about in the next blog.
It is easy to see that such ciphers depend on the secrecy of the system and not on the encryption key. Once the system is known, these encrypted messages can easily be decrypted. In fact, substitution ciphers can be broken by using the frequency of letters in the language.
well, that's the end of my first blog in that series see you in the next one where we will talk about Cryptography in the Medieval and the Renaissance, which it introduce Frequency analysis, Polyalphabetic substitution ciphers, and how to break them.