History of cryptography: From antiquity to quantum future

Cryptocurrencies would not exist without the science of encryption and decryption. Modern cryptography, the cornerstone of secure communication, is the result of nearly 4,000 years of technological development. What protects billions of online transactions, sensitive data, and messages started from ancient tomb inscriptions. Here is our deep dive into the fascinating history of cryptography.

What is cryptography?

The word cryptography comes from two Greek words — kryptos (hidden) and graphien (to write). In layperson's terms, it is the science of writing codes and ciphers for secure communication. A cipher is an algorithm for encryption or decryption.

Cryptography should not be confused with encryption — a more narrow term for the process of encoding and decoding information. Meanwhile, cryptanalysis is the science of deciphering data and revealing hidden messages in plain text.

Over the centuries, cryptography has evolved from primitive symbol replacement to sophisticated digital encryption methods. The more adept people become at cracking encrypted messages, the stronger the drive for its advancement.

First cryptographic systems

People of nearly all major ancient civilizations modified transmitted information. For example, symbol replacement was used for Egyptian and Mesopotamian writings.

The earliest examples in the tomb of Khnumhotep II, an Egyptian noble, are 3,900 years old. An inscription carved into the main chamber contained hieroglyphics that differed from the usual ones. Instead of hiding the message, those replaced symbols enhanced its linguistic and aesthetic appeal.

Cryptography for secret messages

The first known example of protecting sensitive information occurred about 3,500 years ago. One Mesopotamian scribe used cryptography to hide a formula for pottery glaze, which was used on clay tablets.

Later in antiquity, people found another use for cryptography — concealing military information, a purpose it still serves today. For instance, the Spartans wrote messages on parchment paper laid over a cylinder of a specific size. The recipient could not decipher the encrypted message unless they had a similar cylinder to wrap it around.

Spies used coded messages in ancient India as early as the 2nd century BC. Arthashashtra, a Sanskrit treatise on statecraft, economics, war, and other subjects, describes passing assignments in "secret writing."

Caesar cipher

The most sophisticated type of cryptography in the ancient world emerged in the Roman Empire in 100 BC. The Caesar cipher, a substitution cipher, made messages unintelligible by shifting letters by a particular number of places down the Latin alphabet.

The recipient, therefore, had to know the system and the number of alphabet places. Julius Caesar used this method to exchange messages with his army generals at war.

Vigenère cipher

In 1553, Giovan Battista Bellaso described polyalphabetic substitution for alphabetic texts. This technique was more secure than the Caesar cipher. It used a series of Caesar ciphers that were interwoven and based on the letters of a keyword.

Blaise de Vigènere got the credit for this invention three centuries later. In 1863, the Vigènere cipher was cracked by Friedrich Kasiski.

Middle Ages and Renaissance cipher systems

Substitution ciphers remained the standard throughout the Middle Ages. Meanwhile, the importance of cryptography grew along with the development of cryptanalysis — the science of cracking ciphers and codes.

The first systematic deciphering method emerged around 800 AD. A prominent Arab mathematician, Al-Kindi, developed frequency analysis, a decryption technique for substitution ciphers. As a result, cryptography had to advance further to remain useful.

However, it took cryptographers over six centuries to develop a solution — the polyalphabetic cipher. In the 1460s, Leone Alberti developed an encoding system that involved two distinct alphabets — the alphabet used for the original message and the one in which the encoded message appeared. Alberti is known as the "father of Western cryptology" for this invention.

The combination of polyalphabetic cipher and substitution ciphers significantly enhanced encoding security. Without the knowledge of the original alphabet, frequency analysis was useless.

More methods emerged during the Renaissance. In 1553, an Italian cryptologist, Giovan Battista Bellaso, envisioned a text autokey cipher, the first cipher using a proper encryption key. The recipient had to know the agreed-upon keyword to decode the message. This system was considered unbreakable for four centuries.

Bacon's (Baconian) cipher

In 1605, Sir Francis Bacon, a prominent polymath and statesman, invented binary encoding known as Bacon's cipher. It replaced each plaintext letter with a group of five formed with As and Bs. For example, A was replaced by aaaaa, D by aaabb, etc.

Technically, this was a method of steganography — hiding a secret message — rather than a cipher. It concealed a message not in the content of a text but in its presentation.

In the 1790s, Thomas Jefferson described the cipher wheel, a concept well ahead of his time. Although Jefferson may have never built this machine, the wheel became the basis for American military cryptography. This system for complex encoding — 36 rings of letters on moving wheels — was used until as late as the 1940s.

19th century: Paradigm shift

Until the 19th century, specialists in cryptography primarily focused on encryption or cryptanalysis. As a result, they developed ad hoc approaches using rules of thumb.

During the Crimean War, Charles Babbage, an English polymath and inventor of the first mechanical computer, described mathematical cryptanalysis of polyalphabetic ciphers. His work was later redeveloped and published by Friedrich Kasiski, a Prussian infantry officer and archeologist.

Edgar Allan Poe, an American writer and poet, was also fascinated with ciphers and breaking them. In the 1840s, he caused a public stir by solving ciphers submitted by Alexander's Weekly (Express) Messenger readers. Poe also described cryptography methods in an essay used by novice British cryptanalysts who worked with German codes and ciphers during World War I. Cryptanalysis is also a prominent theme in Poe's story The Gold-Bug.

In 1882, Frank Miller, an American banker, described a system for securing telegraphy called the one-time pad. Over three decades later it was patented by Gilbert Vernam, an AT&T Bell Labs engineer. To this day, it remains the only unbreakable encryption technique, although its applications are very limited. It requires the use of a pre-shared, random and single-use key that must match the size of the message.

In the late 19th century, Auguste Kerckhoffs, a Dutch linguist, published a paper entitled La Cryptographie Militaire (Military Cryptography). It included six principles of cipher design, such as making the key easily changeable and memorable without notes. The best-known tip — Kerckhoffs's principle — states that security must depend solely on the key, rather than another system component or the secrecy of the encryption algorithm.

Rotor machine as type of cipher device

In 1917, American inventor Edward Hebern unveiled the earliest example of a rotor machine — an electro-mechanical machine containing parts of a standard typewriter and an electric typewriter connected via a scrambler. However, this method was broken by using letter frequency.

Hebern embedded the key in a rotating disc geared to the typewriter keyboard. The substitution table, or alphabet, changed slightly after every key press. Thus, the machine turned basic substitution into polyalphabetic substitution like the Vigènere cipher, but without manual lookup of the ciphertext.

The following year, German engineer Arthur Scherbius created another analog cryptography machine – the Enigma – which was widely used by the German military. Unlike the Hebern rotor machine, it had multiple rotating wheels to encode classified messages.

World War II: Enigma cipher

The breaking of the Enigma cipher was critical for the outcome of the war. The Nazi forces' method rendered their messages theoretically indecipherable without another Enigma. One would have to go through around 150 million million possibilities!

However, using early computer technology and a Polish invention — the Bomba — a team of scientists, cryptographers, and mathematicians led by Alan Turing cracked the Enigma code. What helped them was one flaw in coding and the fact that every Axis powers' message contained the same phrase.

Enigma machines encrypted each letter as a letter different from itself. After realizing that every encrypted message ended with "Heil Hitler," Turing's team found a way to decipher every message, a discovery that was critical for the victory of the Allied nations.

In 1945, Claude E. Shannon of Bell Labs published an article that marked the beginning of cryptography as we know it today — A mathematical theory of cryptography. Yet even in the 1970s, the US government treated encryption as a matter of national security, and research on it was classified. Cryptographic devices were even rated as munitions, and their use was limited to war, diplomacy, and espionage.

Cryptographic techniques for private use: Lucifer cipher

Eventually, secret codes started serving the needs of ordinary citizens. Businesses finally realized the value of encryption and began researching its applications for intellectual property protection. That was when the first civilian-use encryption algorithms appeared. Their first set — a cipher called Lucifer — was developed by IBM.

The company submitted one of the Lucifer versions to the US National Bureau of Standards. After some enhancements by the National Security Agency, it was accepted as the national Data Encryption Standard (DES). Finally, in 1977, it became the official Federal Information Processing Standard (FIPS) of the United States.

Lucifer combined transposition and substitution encryption. It was a block cipher, as its algorithm operated on groups of bits with fixed lengths. Such ciphers are usually based on symmetric-key algorithms with the same cryptographic keys for plaintext encryption and ciphertext decryption.

Some of the NSA's changes made Lucifer better protected against various forms of cryptanalysis. Others may have enabled the agency to break the cipher if necessary.

However, what led to Lucifer's cracking was not a vulnerability but a brute force attack exploiting its key space. The small key size allowed submissions of passcode combinations until a correct guess. In 1999, Lucifer was deciphered in 22 hours and 15 minutes.

Information Age

When computers emerged, cryptography became increasingly sophisticated. The modern standard for many devices and systems — 128-bit mathematical encryption — is incomparably stronger than any analog predecessor.

Since the 1990s, computer scientists have been developing quantum cryptography, elevating available protection. Then, in the 2000s, cryptocurrencies came into existence.

Public-key cryptography (asymmetric encryption)

Algorithms introduced in 1977 — the RSA algorithm and the Diffie-Hellman key exchange algorithm — marked a watershed between classic and modern cryptography. Two aspects made them revolutionary:

• security based on the theory of numbers
• secure two-party communication without a shared secret

The RSA system, named after the initials of Ron Rivest, Adi Shamir, and Leonard Adleman, was the first-ever public key cryptographic system.

As cryptography no longer required secret codebooks, eavesdropping on the key exchange was not a concern. The idea that the encryption key can be public, with decryption requiring just one secret key — a private key – was groundbreaking. This concept is the bedrock of modern cryptography.

In 1976, Whitfield Diffie and Martin Hellman published the first paper on cryptography combining public keys and private keys. While the keys are interrelated, calculating the private key from the public key is computationally infeasible.

Advanced Encryption Standard (AES)

The cracking of Lucifer sped up the advent of a more sophisticated standard. AES, which officially replaced DES in 2001, uses four crucial elements:

• a symmetric-key algorithm
• a subset of the Rijandael block cipher
• longer keys (128, 192, and 256 bits)
• block size of 128 bits

After the National Institute of Standards and Technology (NIST) (previously the National Bureau of Standards) approved the AES, the US government adopted it as the federal government standard. To this day, it remains the first and only cipher that is public, accessible, and approved by the NSA for top-secret classified information.

Transport Layer Security (TLS)

A critical component of online data protection systems is TLS encryption. It ensures secure input transmission — for example, between a web server and a browser or between a mail server and a mail app. TLS combines asymmetric encryption, symmetric encryption, and multiple algorithms to provide security so high that the world's biggest supercomputers cannot crack it.

TLS is a successor to SSL (Secure Socket Layer), and these terms are often used interchangeably. The addresses of websites with an SSL certificate begin with https instead of http. Such connections prevent eavesdropping on your internet traffic, whether you enter a password or credit card number or email your friends or family. Furthermore, TLS verifies the authenticity of the peer (server) before any data transfer.

Public Key Infrastructure (PKI)

PKI has broader applications than TLS, as it combines processes, technologies, and policies. Apart from securing websites, it protects private systems, identities, devices, users, and files.

PKI underlies authentication, from email to VPN to IoT devices. For example, it encrypts your messages online and verifies nodes to internal Wi-Fi. Furthermore, such digital certificates are customizable and scalable — they can size up or down to accommodate any IoT device or system.

Cryptography for cryptocurrencies

Cryptocurrencies are based on advanced cryptographic techniques for authenticating transactions and ensuring the security of data stored on blockchains. These include:

• Digital signatures — cryptographic mechanisms that verify the authenticity and integrity of data.
• Hash functions — functions that map arbitrary-sized data for computationally and storage space-efficient forms of access.
• Asymmetric (public-key) cryptography — a framework using a pair of private and public keys instead of a single key.

Elliptic-curve cryptography (EEC)

In 2005, Elliptic-curve cryptography (ECC) algorithms allowing shorter encryption keys entered wide use. This advanced scheme enhances security while saving computing power and making data encryption accessible to all. Today, ECC is becoming the preferred standard for digital privacy and security in different fields:

• Smart cards (for example, bank cards and ID cards)
• Smartphones and IoT devices
• Cryptocurrencies
• Online messengers (Signal, Telegram, and WhatsApp)
• Internal communications (for example, in US government organizations)

Elliptic Curve Digital Signature Algorithm (ECDSA)

This form of cryptography underlies Bitcoin and other blockchains. ECDSA provides extra security to ensure that funds can only be used by their rightful owners. It is also used in messaging apps and TLS.

Quantum computers and the future of cryptography

However reliable the existing public key algorithms may be, none are guaranteed to remain secure. Future advances in mathematical analysis and the advent of high-capacity quantum computers could render them vulnerable. As a result, there are efforts to develop post-quantum cryptography to prepare for a time when this threat materializes.

Quite a few modern symmetric ciphers have been broken. Notable examples include A5/1 and A5/2, the ciphers for GSM cell phones; WEP, the first scheme for Wi-Fi encryption; and CSS, an encryption system for DVDs. Asymmetric ciphers may also be broken if they have poor designs or implementations.

Finally, new cryptographic algorithms address the threat of side-channel attacks — exploiting data about how computer systems are implemented, such as power consumption and cache memory use. The recommended key size is growing, while the computing power required for encryption breaking is increasingly accessible and cheap.