The Story of Cryptography

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: The Caesar Box and the Vigenère 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 will 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 throughout the United States and beyond. The rapid expansion, though, also brought on a great deal of scrutiny by cryptographers. So, when the DES was defeated in 1997 by a brute-force key guessing attack, it was time for an update that was warmly welcomed by its critics.

In 1997, the National Institute of Standards and Technology 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. During the selection process, cryptographers debated and attempted to break the various ciphers. Ultimately, three ciphers from the Rijndael family of ciphers (developed by Belgian cryptographers) were selected to be the AES.

The Technicalities

The three selected variants have a 128-bit, 192-bit, and 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. The only feasible attack against the full version of AES would use “side-channel analysis,” in which 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, thus far, reduces the effective key lengths of the three variants to 126-, 189.9-, and 254.3-bits. However, all of these key lengths are still infeasible to brute-force on modern computing hardware. Therefore, AES is still considered to be secure.

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. Simply put, an elliptic curve is a plane algebraic curve created by an non-singular equation - meaning, when drawn, the curve never intersects itself. If a line on the curve intersects two points in the curve, it will always intersects a third. This third point represents the public key. Every point on the curve (at the x and y coordinates) satisfies an equation. Furthermore, 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 D-H, 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 D-H, 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 are 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 attacks with modern systems. However, it has one very significant shortcoming: you cannot process encrypted data. Adding or multiplying the ciphertexts of two AES-encrypted values does not 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 use 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.” 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, cryptographers 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. This is 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.