This is the final post in a three-part series on the history of cryptography. In the first post, we explored encryption algorithms that pioneered some of the core components of encryption: Caesar’s Box and the Vigenere Cipher. From there, the second post describes some of the historical cryptographic milestones of the 20th century: the Enigma machine, the Data Encryption Standard (DES), and the invention of asymmetric encryption.
In this post, we’ll explore how cryptography has evolved in the 21st century. Beginning with DES’s replacement, AES, this post explores the use of Elliptic Curve Cryptography (ECC) and some of the areas of cryptographic research currently being explored today: homomorphic encryption and post-quantum cryptography.
The Advanced Encryption Standard
The Data Encryption Standard (DES) was the first encryption algorithm publicly endorsed by the US government. As a result, it was rapidly adopted in the US and beyond and also subjected to a great deal of scrutiny by cryptographers. When the DES was defeated in 1997 by a brute-force key guessing attack, it was time for an update.
In 1997, NIST put out a call for proposals for the Advanced Encryption Standard (AES). This resulted in the submission of fifteen candidate ciphers from around the world and a three-year selection process where cryptographers debated and attempted to break the various ciphers.
In the end, three ciphers from the Rijndael family of ciphers (developed by Belgian cryptographers) were selected as the AES.
The three variants have a 128-bit, 192-bit, or 256-bit secret key. All three variants use a 128-bit block size (organized into 4 4-byte rows) and multiple rounds. Each round but the last includes four steps:
SubBytes: Application of S-Boxes to transform the state
ShiftRows: Shifting of the last three rows by 1, 2, or 3 bytes
MixColumns: Combination of the four bytes in each column of the state
AddRoundKey: Exclusive-or (XOR) of the state with the round key
Before the rounds begin, an AddRoundKey operation is performed, and the last round does not include MixColumns. One difference between the different variants is the number of rounds: 10, 12, or 14. The other significant difference is the key schedule used to derive the 128-bit round keys from the 128-bit, 192-bit, or 256-bit secret key.
Security of the AES
AES is currently considered a secure cipher as the only feasible attacks against the full version of AES uses side-channel analysis, where power consumption, electro-magnetic emissions, etc. are measured and used to infer internal values of the state of the cipher. Other attacks against AES either operate on a reduced number of rounds or have a limited effect on the security.
The best known attack reduces the effective key lengths of the three variants to 126, 189.9, and 254.3 bits. All of these key lengths are infeasible to brute-force on modern computing hardware.
Elliptic Curve Cryptography
In the previous post in this series, we discussed the invention of asymmetric encryption and how algorithms using it are still considered secure. However, the security of these algorithms is based upon the key length used. As computing improves, brute force attacks on longer keys become feasible, forcing a move to even larger secret keys.
Elliptic curve cryptography (ECC) provides a limited solution to this problem. Elliptic curves are mathematical functions with a specific structure with operations that map to operations over the integers. Addition of two points on an elliptic curve is equivalent to multiplication of two integers, and exponentiation in the integers is equivalent to multiplication of points on an elliptic curve. As a result, it is possible to construct the same “hard” mathematical problems used in asymmetric cryptography using elliptic curves.
The benefit of using elliptic curve cryptography instead of traditional integer-based algorithms like RSA and Diffie-Hellman is an increased level of security with shorter key lengths. According to NIST, a 256-bit ECC private key provides equivalent security to a 3072-bit RSA key. ECC-based asymmetric algorithms also consume less energy than their integer-based counterparts, making them more efficient and usable as well.
However, the security advantages of ECC only apply to brute force attacks exploiting key lengths. The ECC algorithms use the same underlying mathematical “hard” problems as RSA and Diffie-Hellman, meaning that an attacker who finds an “easy” solution to these “hard” problems can attack ECC-based encryption as well.
Next-Gen Cryptography
The Advanced Encryption Standard (AES) and Elliptic Curve Cryptography are in common use today, but they’re largely “solved” problems. Some of the cryptographic algorithms currently in development today, like homomorphic encryption and post-quantum cryptography, are designed to expand the applications of cryptography or solve problems created by improvements in computing systems.
Homomorphic Encryption
Modern cryptography works very well at protecting sensitive data against attack with modern systems. However, it has one very significant shortcoming: you can’t process encrypted data. Adding or multiplying the ciphertexts of two AES-encrypted values doesn’t produce the sum or product of their corresponding plaintexts. This means that data must be decrypted in order to be processed, and encryption only protects data at rest and data in transit.
Homomorphic encryption is designed to change this. A fully homomorphic encryption algorithm allows the user to perform arbitrary computations on a ciphertext and then decrypt the result to the correct plaintext (with all computations applied).
The first fully homomorphic encryption algorithm was proposed by Craig Gentry in his 2009 PhD thesis. Since then, the first has been actively expanded by Gentry and others to help improve the efficiency, security, and usability of FHE algorithms.
Post-Quantum Cryptography
Another area that is getting a lot of attention in the cryptography space is that of post-quantum cryptography. In previous posts, we discussed how asymmetric encryption is based upon mathematical “hard” problems. With these problems, legitimate operations (multiplication and exponentiation) are polynomially difficult, but their inverses (factoring and logarithms) have a difficulty that grows exponentially with the length of the numbers used.
This asymmetry allows asymmetric cryptosystems to be developed that are usable but can achieve an arbitrary level of security against attack. However, this only works if these problems remain “hard”, and an algorithm developed by Peter Shor in 1994 makes it possible for quantum computers to break this assumption. When quantum computers grow powerful enough, traditional asymmetric encryption will be broken.
In anticipation of this day, cryptographer are actively developing post-quantum asymmetric cryptography algorithms. These algorithms are based on mathematical problems that are “hard” for quantum computers as well. Several of these problems and algorithms exist, but there is still active research in the field to develop new ones and test existing ones to ensure that secure alternatives are available when traditional asymmetric cryptography breaks.
Wrapping Up
The goal of this three part series is to provide an introduction to the history of cryptography. Beginning with historical ciphers, moving to 20th century encryption systems, and concluding with modern cryptographic algorithms, this series highlights the inventions with the greatest impact on the cryptographic algorithms that we use today.