A Brief History of Cryptological Systems

crypto-1024xxx

Below is a brief description of ten different crytological systems used between 650 B.C.E and the present. This is by no means an exhaustive list, notably absent is the work of Ahmad al-Qalqashandi (1355–1418 C.E.), the work of Charles Babbage (1791-1871 C.E.), the Japanese Uesugi and Angōki B-gata (暗号機B型), or Purple, systems from circa 1500 C.E. and 1937 C.E. respectively, and the work of Navajo code-talkers during World War II. However, the concepts presented here are inclusive of the methods employed by these systems.

This text appears in The Secret of Chimera Labs, a point-and-click adventure game from Aircamp Games, the puzzles in which use many of the same techniques.

Table of Contents
Scytale
Julius Caesar
Vigenère Cipher
Le Grand Chiffre
Pigpen Cipher
One Time Pad
ADFGVX
The Enigma Machine
RSA
Quantum Key Distribution
As Used in The Secret of Chimera Labs

Scytale        c. 650 B.C.E.
A simple matrix transposition cipher used by the ancient Greeks and Spartans.

Scytale ribbon being wrapped around rod.
Scytale ribbon being wrapped around rod.
Scytale ribbon unwrapped.
Scytale ribbon unwrapped.

In cryptography, a scytale (also transliterated skytale, Greek σκυτάλη “baton”) is a tool used to perform a transposition cipher, consisting of a cylinder with a strip of parchment wound around it on which is written a message. The ancient Greeks, and the Spartans in particular, are said to have used this cipher to communicate during military campaigns.

The recipient uses a rod of the same diameter on which he wraps the parchment to read the message. It has the advantage of being fast and not prone to mistakes—a necessary property when on the battlefield. It can, however, be easily broken. Since the strip of parchment hints strongly at the method, the ciphertext would have to be transferred to something less suggestive, somewhat reducing the advantage noted.

The scytale message deciphered.
The scytale message deciphered.

From indirect evidence, the scytale was first mentioned by the Greek poet Archilochus, who lived in the 7th century BC. Other Greek and Roman writers during the following centuries also mentioned it, but it was not until Apollonius of Rhodes (middle of the 3rd century BC) that a clear indication of its use as a cryptographic device appeared. A description of how it operated is not known from before Plutarch (50-120 AD).

An alternative hypothesis is that the scytale was used for message authentication rather than encryption. Only if the sender wrote the message around a scytale of the same diameter as the receiver’s would the receiver be able to read it.

Caesar Shift        c. 50 B.C.E.
A mono-alphabetic substitution cipher named for Julius Caesar.

Bust of Julius Caesar.
Bust of Julius Caesar.

A Caesar Shift, also known a shift cipher, Caesar’s Code or Caesar Cipher, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

It is unknown how effective the Caesar cipher was at the time, but it is likely to have been reasonably secure, not least because most of Caesar’s enemies would have been illiterate and others would have assumed that the messages were written in an unknown foreign language.

Diagram indicating Caesar Shift encryption method.
Diagram indicating Caesar Shift encryption method.
Encrypted and Decrypted text using a 3-Step Shift Cipher.
Encrypted and Decrypted text using a 3-Step Shift Cipher.

There is no record at that time of any techniques for the solution of simple substitution ciphers. The earliest surviving records date to the 9th century works of Al-Kindi in the Arab world with the discovery of frequency analysis.

The Confederate Cipher Disc, used during the American Civil War.
The Confederate Cipher Disc, used during the American Civil War.

Often this type of cipher is implemented on a wheel device. A disk or wheel has the alphabet printed on it and then a movable smaller disk or wheel with the same alphabet printed on it is mounted forming an inner wheel. The inner wheel then can be rotated so that any letter on one wheel can be aligned with any letter on the other wheel.



Vigenère Cipher        1553  C.E.
A poly-alphabetic substitution cipher using a series of Caesar Shifts based on a keyword.

Engraving of Giovan Battista Bellaso.
Engraving of Giovan Battista Bellaso.

The Vigenère cipher has been reinvented many times. The method was originally described by Giovan Battista Bellaso in his 1553 book “La cifra del”; however, the scheme was later misattributed to Blaise de Vigenère in the 19th century. Though the cipher is easy to understand and implement, for three centuries it resisted all attempts to break it; this earned it the description le chiffre indéchiffrable (French for ‘the indecipherable cipher’).

To encrypt, a table of alphabets can be used, termed a Vigenère square. At different points in the encryption process, the cipher uses a different alphabet from one of the rows. The alphabet used at each point depends on a repeating keyword.

The Vigenère square or Vigenère table, also known as the tabula recta.
The Vigenère square or Vigenère table, also known as the tabula recta.

Keys are typically single words or short phrases, known to both parties in advance, or transmitted “out of band” along with the message.

The idea behind the Vigenère cipher, is to disguise plaintext letter frequencies, which interferes with applying of frequency analysis. For instance, if P is the most frequent letter in a ciphertext whose plaintext is in English, one might suspect that P corresponds to E, because E is the most frequently used letter in English. However, using the Vigenère cipher, E can be enciphered as different ciphertext letters at different.

The primary weakness of the Vigenère cipher is the repeating nature of its key. If a cryptanalyst correctly guesses the key’s length, then the cipher text can be treated as interwoven Caesar ciphers, which individually are easily broken.

Le Grand Chiffre        1626 C.E.
A nomenclator based cipher made for Louis XIII of France which took over two centuries to break.

Engraving of Antoine Rossignol.
Engraving of Antoine Rossignol.

Antoine Rossignol’s cryptographic skills became known when in 1626 an encrypted letter was taken from a messenger leaving the city of Réalmont, controlled by the Huguenots and surrounded by the French army. The letter told that the Huguenots would not be able to hold on to the city for much longer, and by the end of the day Rossignol had successfully deciphered it. The French returned the letter with the deciphered message, forcing the Huguenots to surrender. He and his son, Bonaventure Rossignol, were soon appointed to prominent roles in the court.

Together, the two devised a code so strong it baffled cryptanalysts for centuries. Commandant Étienne Bazeries managed to break the cipher around 1893, realizing that each number stood for a French syllable rather than single letters as traditional codes did. He guessed that a particular sequence of repeated numbers, 124-22-125-46-345, stood for les ennemis (“the enemies”) and from that information was able to unravel the entire cipher.

One of many nomenclators used to encode the Great Cipher.
One of many nomenclators used to encode the Great Cipher.

The basis of the code cracked by Bazeries was a set of 587 numbers that stood for syllables. There were other variations, and Louis XIV’s overseas ministers were sent different code sheets that encrypted not only syllables but also letters and words. To counter frequency analysis, some number sets were “nulls” meant to be ignored by the intended receipt. Others were traps, including a code-group that meant to ignore the previous code-group.

As a nomenclator cipher, the Great Cipher replaced the names of key generals, references to les ennemis, and other sensitive terms with homophonic substitutions. Code sheets included alternative digits to modify the gender or letter case, so the rules of French composition held true to encryptions as well. Since e is the most commonly used letter in French, the Cipher typically allocated the most code numbers to writing this vowel: in one nomenclature, 131 out of 711 code numbers stood for e.

Pigpen Cipher        c. 1700 C.E.
A simple geometric substitution cipher used by the Freemasons to guard their secrets.

The pigpen cipher uses graphical symbols assigned according to a key similar to the above diagram.
The pigpen cipher uses graphical symbols assigned according to a key similar to the above diagram.

The pigpen cipher (sometimes referred to as the masonic cipher, Freemason’s cipher) is a geometric simple substitution cipher, which exchanges letters for symbols which are fragments of a grid.

The use of symbols is no impediment to cryptanalysis, and this system is identical to that of other simple monoalphabetic substitution schemes. Due to the simplicity of the cipher, it is often included in children’s books on ciphers and secret writing.

The exact origin of the cipher is uncertain, but records have been found which go back to at least the 18th century. Variations of this cipher were used by both the Rosicrucian brotherhood and the Freemasons, who began using it in the early 18th century to keep their records and rites private, and for correspondence between lodge leaders.

Pigpen Ciphertext and plaintext.
Pigpen Ciphertext and plaintext.

Tombstones of Freemasons can also be found which use the system as part of the engravings. George Washington’s army had documentation about the system, with a much more randomized form of the alphabet. And during the American Civil War, the system was used by Union prisoners in Confederate prisons.

Enciphered Text on Tombstone at Trinity Church in New York City.
Enciphered Text on Tombstone at Trinity Church in New York City.

There are many variations of the Pigpen Cipher (in the example below, the symbol for “s” is not standard). The common variants include changing the order from grid, grid, X, X to grid, X, grid, X or even placing the letters alternate positions. One method for changing is to use three grids, using a full stop, or space, to occupy the last position.

One Time Pad        1882 C.E.
An encryption system based on a random key that is used only once.

An example of a Cold War era codebook.
An example of a Cold War era codebook.

A one-time pad is an encryption technique that cannot be cracked if used correctly. In this technique, a plaintext is paired with a random secret key (or pad). If the key is truly random, is at least as long as the plaintext, is never reused in whole or in part, and is kept completely secret, then the resulting ciphertext will be impossible to decrypt or break. Practical problems have prevented one-time pads from being widely used.

Frank Miller in 1882 was the first to describe the one-time pad system for securing telegraphy.

The next one-time pad system was electrical. In 1917, Gilbert Vernam invented a cipher based on teleprinter technology.

Three example code sheets.
Three example code sheets.
Encryption using Pad 1 above as the key in a Vigenere encipherment.
Encryption using Pad 1 above as the key in a Vigenere encipherment.

The next development was the paper pad system. Diplomats had long used codes and ciphers for confidentiality and to minimize telegraph costs. For the codes, words and phrases were converted to groups of numbers (typically 4 or 5 digits) using a dictionary-like codebook. The final discovery was by Claude Shannon in the 1940s who recognized and proved the theoretical significance of the one-time pad system.

Encryption and decryption method for a one time key.
Encryption and decryption method for a one time key.

Despite Shannon’s proof of its security, the one-time pad has serious drawbacks in practice. The theoretical perfect security of the one-time-pad applies only in a theoretically perfect setting; no real-world implementation can provide perfect security because practical considerations introduce potential vulnerabilities.

ADFGVX        June, 1918  C.E.
A fractionating transposition and substitution cipher using a modified Polybius square.

An ADFGVX Polybius cipher matrix.
An ADFGVX Polybius cipher matrix.

ADFGX and the successor ADFGVX were developed by the German intelligence officer Fritz Nebel (1891 – 1967). ADFGX was used for the first time at the 5th of March in 1918 during World War I. Only a few months later, on the 1st of June, an extended version of this cipher called ADFGVX was used.

On the 2nd of June, the French crypt analyst Geoges Painvin managed to break the encoding for a German radio message.

The transmitted messages were only composed of the characters A, D, F, G, V and X. These characters were chosen because they are easily distinguishable in the Morse Code.

The encoding procedure according to ADFGVX consists of two phases. For the first phase (substitution) a Polybius cipher matrix is used. For the message “timerevealssecrets” the character ‘t’ will be substituted according to the matrix shown above to XV. (row X and column V).

Encrypting a message using the above modified Polybuis Square.
Encrypting a message using the above modified Polybuis Square.
Transposition encipherment of one ADFGVX  Polybuis  square to another.
Transposition encipherment of one ADFGVX Polybuis square to another.

Transposition is used for the second phase of encoding. The matrix is entered row by row, but read out column by column. A keyword (“MYKEY”), is choosen and assigned to each column. The letters of the keyword are then rearranged alphabetically. To get the ciphertext, the matrix is read out column by column from the top to the bottom. The resulting ciphertext is:

Resulting ciphertext from the above ADFGVX encipherment and transposition matrix.
Resulting ciphertext from the above ADFGVX encipherment and transposition matrix.

To decode an ADFGVX cipher, the substitution matrix and the keyword have to be known. However, the result of the substitution step is not very secure. The transposition is mainly responsible for the security of the cipher. Without the second phase this cipher would be no more secure than a Caesar Shift.

The Enigma Machine        1st verion 1923 C.E.
A portable electro-mechanical rotor cipher machine used by the German Military in WWII.

Model "Enigma 1", used during the late 1930s and during the second world war.
Model “Enigma 1”, used during the late 1930s and during the second world war.

The Enigma was invented by the German engineer Arthur Scherbius at the end of World War I. Early models were used commercially from the early 1920s, and adopted by military and government services of several countries, most notably Nazi Germany before and during World War II.

German military messages enciphered on the Enigma machine were first broken by the Polish Cipher Bureau, beginning in Dec. 1932. The Poles reverse engineered the device, using theoretical mathematics and subsequently they designed mechanical devices for breaking Enigma ciphers, including the cryptologic bomb.

On 25 July 1939, in Warsaw, the Poles initiated French and British military intelligence representatives into their Enigma-decryption techniques. During the war, British cryptologists decrypted a vast number of messages enciphered on Enigma. The intelligence gleaned from this source, codenamed “Ultra” by the British, was a substantial aid to the Allied war effort.

A diagram of a three rotor Enigma’s electric circuit enciphering “d” as “A”.
A diagram of a three rotor Enigma’s electric circuit enciphering “d” as “A”.

The Enigma Machine enciphers a message with a basic substitution cipher. The Enigma accomplishes this substitution by a series of hidden electrical connections. Second, these connections are placed in a set of rotors which rotate [‘Scamblers’ in the above diagram], changing the electrical connections and thus the substitution cipher. This rotation is what made the Enigma code so difficult to crack – it meant that every letter in a message was enciphered using a different substitution cipher, because the rotors would rotate after every letter was entered.

RSA        1977 C.E.
One of the first practical public-key cryptosystems.

Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.
Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.

RSA is a public-key cryptosystem and is widely used for secure data transmission. In such a system, the encryption key is public and differs from the decryption key which is kept secret.

In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977. Clifford Cocks, an English mathematician working for GCHQ, had developed an equivalent system in 1973, but it was not declassified until 1997.

Diagram illustrating RSA encryption and decryption.
Diagram illustrating RSA encryption and decryption.

The algorithm has three steps: key generation, encryption and decryption. RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key.

An analogy to public-key encryption is that of a locked mail box with a mail slot. The mail slot is exposed and accessible to the public – its location (the street address) is, in essence, the public key. Anyone knowing the street address can go to the door and drop a written message through the slot. However, only the person who possesses the key can open the mailbox and read the message.

RSA uses exponentiation modulo, a product of two very large primes, to encrypt and decrypt, performing both public key encryption and public key digital signature. Its security is connected to the extreme difficulty of factoring large integers, a problem for which there is no known efficient general technique.

Quantum Key        1984 C.E..
Guarantees secrecy and randomness through the laws of physics.

Quantum cryptography was first proposed by Stephen Wiesner, who, in the early 1970s, introduced the concept of quantum conjugate coding. His seminal paper titled “Conjugate Coding” was rejected by IEEE Information Theory but was eventually published in 1983. In this paper he showed how to store or transmit two messages by encoding them in two “conjugate observables”, such as linear and circular polarization of light, so that either, but not both, of which may be received and decoded.

In 1984, building upon this work, Charles H. Bennett and Gilles Brassard proposed a method for secure communication based on Wiesner’s “conjugate observables”, which is now called BB84.

Diagram illustrating quantum key distribution process.
Diagram illustrating quantum key distribution process.

In 1990 Artur Ekert developed a different approach to quantum key distribution based on peculiar quantum correlations known as quantum entanglement.

The most well known and developed application of quantum cryptography is quantum key distribution (QKD), which is the process of using quantum communication to establish a shared key between two parties (Alice and Bob) without a third party (Eve) learning anything about that key, even if Eve can eavesdrop on all communication between Alice and Bob. This is achieved by Alice encoding the bits of the key as quantum data and sending them to Bob; if Eve tries to learn these bits, the messages will be disturbed and Alice and Bob will notice.

Quantum computers may become a technological reality; it is therefore important to study cryptographic schemes that are allegedly secure even against adversaries with access to a quantum computer. The study of such schemes is often referred to as post-quantum cryptography. The need for post-quantum cryptography arises from the fact that many popular encryption and signature schemes (such as RSA) can be broken using on a quantum computer.

As used in The Secret of Chimera Labs

Rocketry Lab desk in 'The Secret of Chimera Labs'.
Rocketry Lab desk in ‘The Secret of Chimera Labs’.

The above write us on various cryptographic systems are used in The Secret of Chimera Labs as part of a puzzle. The names (Scytale, Caesar, etc…) are the first part of a two layered substitution cipher. The given on the yellow note found in the game’s server room, are encoded to the roman numeral beside their. Elsewhere in the game, those roman numerals correspond to another alphabetic set, which can be used to solve the puzzle.

'A History of Cryptology' as found in 'The Secret of Chimera Labs'.
‘A History of Cryptology’ as found in ‘The Secret of Chimera Labs’, used as a clue to solve on of the game’s many puzzles.

The Secret of Chimera Labs is available for download on The AppStore, Google Play, and Amazon.

 
 
 
 
 
 



Wikipedia (https://www.wikipedia.org/) and Simon Singh’s The Code Book were used as a source for this article.
Sections of this text were taken from their respective Wikipedia pages. Reusing Wikipedia Content.

Leave a Reply

Your email address will not be published. Required fields are marked *