Vagrant
Noah Berner
The Attack on RSA with a Quantum Computer
The attack on RSA using a quantum computer is best described by first looking at the building blocks of the attack.
The encryption protocol RSA, which was named after its authors Rivest, Shamir and Adleman, is one of today’s most widely used encryption schemes. Among other things, it is used in TLS to securely exchange the keys between server and client and thus protects the communication between websites like electronic banking and end-user devices.
RSA is an asymmetric cryptographic scheme, meaning that for the en- and decryption two different keys are used. The key that is used to encrypt data is called the public key. As the name suggests, the public key is public and can be shared with any party with whom one wants to communicate. It is expected that any attacker also knows the public key.
The key used for decryption of the data is called the private key. The private key has to be kept secret and cannot fall into the hands of the attacker or be calculated by them.
The security of the RSA protocol is based on the assumption that it is hard to factor a number N = p * q, which is the product of two prime numbers p and q, back into these two factors. The fastest known algorithm on a classical computer needs
O(2∛n)
time units to accomplish this task, where n is the number of bits of the number N. Thus, the runtime of the classical algorithm that receives N as input and returns the two factors p and q as output is exponential in the number of bits n.
One of the most important building blocks of Shor’s algorithm is a quantum program that calculates the period r of a periodic function
ƒ(x) = ƒ(x + r)
In other words, the program calculates the distance r after which the output of the function is repeated.
The quantum program uses the quantum Fourier transform to calculate the period r. The quantum Fourier transform is the quantum computing equivalent to the discrete Fourier transform but can perform this operation exponentially faster than a classical computer. This is the decisive time advantage that will allow us to break RSA in a reasonable amount of time.
The Euclidean algorithm efficiently calculates the greatest common divisor gcd of two numbers.
Now that we have seen the essential building blocks, we assemble them into an algorithm that is able to factor the number N into its secret factors p and q in polynomial (i.e., sub-exponential) time. The American mathematician Peter Shor has developed such an algorithm in 1994 which is now named after him and known as Shor’s algorithm.
We choose a number a which does not have any common factors with N. This property can easily be checked using the Euclidean algorithm, as it is equivalent to the statement that the greatest common divisor of a and N is one.
gcd(a, N) = 1
Once we have found a suitable candidate a we define the following two things:
ar mod N = 1
ƒa(x) = ax mod N
Notice that ƒa has the following properties:
ƒa( r ) = ar mod N = 1
ƒa(x+y) = ax+y mod N = ax * ay mod N = ƒa(x) * ƒa(y) mod N
The crucial observation after all these definitions is that ƒa is a periodic function with the period r:
ƒa(x+r) = ƒa(x) * ƒa( r ) = ƒa(x) * 1 = ƒa(x)
With the aforementioned quantum program, we can calculate the period r of ƒa in polynomial time. Once r is calculated with the quantum computer, we will use classical algorithms to process r and find the factors of N.
With a probability of at least 50% we will receive an r from the quantum computer which has the following two properties:
If both of these properties hold for a we can find the prime factors of N. Otherwise, we will let the quantum computer calculate a new r by choosing a different value for a.
With an r that fulfills the above requirements, we make the following observation:
ar mod N = 1
⇔ (ar/2)2 mod N = 1
⇔ (ar/2)2 – 1 mod N = 0
⇔ (ar/2 – 1)(ar/2 + 1) mod N = 0
Because neither ar/2 + 1 nor ar/2 – 1 are a multiple of N, these two numbers must share a non-trivial factor with N. This factor can be calculated using the Euclidean algorithm
x = gcd(ar/2 – 1, N) = p or q
The second factor can be found by dividing N with the factor x.
We were able to use Shor’s algorithm to calculate the secret prime factors p and q in polynomial time.
O(poly(n))
This allows an attacker to calculate the private key, just as the original owner of the key did when they started the RSA protocol. Thus, the private key is in the hands of the attacker, and we have successfully broken RSA!
You probably ask yourself whether other encryption protocols are also in danger of being weakened by the existence of quantum computers. The answer to that question depends on whether we talk about symmetric or asymmetric protocols.
Symmetric encryption algorithms are not affected by Shor’s algorithm as they rely on different hard problems to be secure. Quantum programs that solve these hard problems exponentially faster than classical programs have not been discovered yet. This could of course change in the future and whether such algorithms can exist or not is an open research question.
Shor’s algorithm can be generalized so that it solves all problems of the hidden subgroup problem for finite Abelian groups. One of those problems is the discrete logarithm problem on which the security of the Diffie-Hellman key exchange and the elliptic-curve cryptography is based. Thus, none of today’s most used asymmetric encryption protocols is safe.
Even if quantum computers with enough qubits that have a reasonable noise level to break RSA with its current problem sizes are at least a few years away, this situation is still unsatisfactory. We present two possible remedies.
Post-quantum cryptography, i.e., the cryptography that is safe in the era of quantum computers, is a field of research that develops classical asymmetric encryption schemes that are neither vulnerable to classical nor quantum attacks. At the moment, NIST is in the process of certifying and standardizing such algorithms.
Quantum Key Distribution uses quantum physics to exchange keys whose security is tied to the laws of physics rather than the computational power of attackers. Thus, even if an attacker has a quantum computer at their disposal, they cannot reconstruct the key. The disadvantages of quantum key distribution are the limited range and throughput as well as the cost of using new hardware.
The attack on RSA shows that if we enter an era where quantum computers with enough qubits exist, that we need new ways to perform asymmetric encryption. Otherwise, the secure communication of today is no longer possible. There are already alternatives to the quantum unsafe status quo, but these are not yet fully developed and need more time and investment before they become viable.
Readers who would like to dive deeper into quantum computers and their algorithms will find a good resource in the textbook of Qiskit as well as the great book Quantum Computation and Quantum Information by Nielsen and Chuang.
Disclaimer: This article is written for a broad audience and as such, some of the mathematical statements have been simplified and should not be used to derive further statements.
Our experts will get in contact with you!
Noah Berner
Noah Berner
Our experts will get in contact with you!