If you swim in a sea of mathematical proofs and frequent crypto analysis, this post is not for you. However, if you’re like me and work in a space in which cryptography effects your day-to-day work in a significant and meaningful way, yet you’re not usually exposed to its inner workings, read on! This post will help to demistify the core issue that quantum computing poses to modern cryptographic algorithms.
I recently read the following statement (source):
In 1994 Shor presented a quantum algorithm that can be used to solve the factorization and discrete logarithm problems in polynomial time, thus completely breaking RSA and ECDSA
While I was able to understand the gist of the statement, the finer points were lost on me. Why are discrete logarithm problems important? How do RSA and ECDSA make use of them? Polynomial time is faster than previously thought possible, but how much faster? This post analyzes the statement in-depth, and unpacks the various terms and nuances for non-crypto-experts like myself.
Who is Shor Anyway?
Peter Shor is a professor at MIT, where he researches applied mathematics as it applies to quantum computing. His most famous contribution to the field, as referenced by the statement we’re analyzing, is an algorithm devised in 1994 while working at the famed Bell Laboratories. His algorithm solves the problem of factoring integers at a rate significantly faster than any previously known technique.
What Makes an Algorithm “Quantum”?
When speaking of algorithms typically used to solve complex computational problems, they typically fall into one of two buckets:
- classical - This is what most people envision when thinking of an algorithm. It involves a discrete set of steps that happen sequentially. Modern computers work exclusively off of classical algorithms.
- quantum - Algorithms that make use of quantum concepts, namely superposition and entanglement. These algorithms, unlike classical approaches, do not rely on a sequence of discrete steps, thereby making different kinds of computation possible.
Note here that the most significant part about the term “Quantum” in our statement is not to imply that an inherently faster medium. Instead, we have a fundamentally different model of performing computations, such that previous assumptions on an attacker’s ability to perform a “computationally feasible” attack are no longer valid. The power of Shor’s algorithm is that it takes advantage of new approaches offered by quantum computing to solve the old problem of factoring integers in a radically more efficient way.
The Factorization Problem
RSA is based on a core concept: it takes a really long time to factor a subprime number. Since a “Subprime” number is simply the product of 2 prime numbers, these factorizations rely on finding 2 relatively large numbers that can be multiplied together to make a known constant (N). If anyone were to solve the problem of factoring large subprime numbers quickly, they would effectively have the ability to break RSA.
The Discrete Logarithm Problem
What the factorization problem is to RSA, the discrete logarithm problem is to DSA and ECDSA. For more on how this works, I would highly recommend this Khan Academy Video - it succinctly explains this problem far more clearly than this author could hope to. What’s important for the above statement, is that the discrete logarithm problem has also effectively been busted by Shor’s algorithm.
Finally, we come to the question of “how fast is polynomial time”? In order or fastest => slowest, here are a few time categories with examples of integer factorization algorithms:
- polynomial (Shor’s)
- sub-exponential (Dixon, Quadratic Sieve)
Most folks familiar with algorithms understand that exponential is slow - like slow enough to take several human lifetimes to solve a problem of any significance on the most beefy of machines. Sub-exponential is still slow, but remains fuzzy in its definition. Since the gap between polynomial time and exponential is so large, classes of algorithms that peform far better than tyical exponential algorithms, but are still significantly slower than polynomial time are often put here. For the purposes of doing something like breaking RSA’s integer factorization problem, all known non-quantum sub-exponential algorithms remain in the “computationally infeasible” category.
However, polynomial algorithms bear the monickers “tractible”, “feasible”, or even “efficient”. These algorithms spell doom for cryptographic functions, as their reduced complexity puts solving difficult mathematical problems in the realm of possibility.
This is Why We Can’t Have Nice Things
Therefore, since Shor’s algorithm puts the mathematical problems that undergird RSA and ECDSA in the realm of “tractable”, and quantum computers are on the horizon, we can call RSA and ECDSA effectively “broken”. Is anyone exploiting this algorithm today? No. Is it something that should drive us towards new cryptographic algorithsm? Most definitely! More to come on what some of these algorithms look like… for non-experts like me.