Today, RSA is one of the most widely used encryption protocols in the world and protects various applications from the prying eyes of attackers – unless these attackers have a quantum computer. The security properties of RSA are based on the belief that computers need a certain amount of time to solve a hard problem. Quantum computers can solve some of these problems much more efficiently than classical computers so that they are able to break the RSA protocol.

Needed Building Blocks

The attack on RSA using a quantum computer is best described by first looking at the building blocks of the attack.

RSA

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.

Calculating the Period of a Function Using a Quantum Program

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.

Euclidean Algorithm

The Euclidean algorithm efficiently calculates the greatest common divisor gcd of two numbers.

Assembling Shor’s Algorithm

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.

Quantum Part

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:

1. The order of a modulo N is called r and defined as the exponent of a modulo N equal to one:
   

   a^r mod N = 1

2. We define ƒ_a as follows
   

   ƒ_a(x) = a^x mod N

Notice that ƒ_a has the following properties:

ƒ_a( r ) = a^r mod N = 1

ƒ_a(x+y) = a^x+y mod N = a^x * a^y 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.

Classical Part

With a probability of at least 50% we will receive an r from the quantum computer which has the following two properties:

1. r is an even number.
2. Neither a^r/2 + 1 nor a^r/2 – 1 is a multiple of N.

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:

a^r mod N = 1

⇔ (a^r/2)² mod N = 1

⇔ (a^r/2)² – 1 mod N = 0

⇔ (a^r/2 – 1)(a^r/2 + 1) mod N = 0

Because neither a^r/2 + 1 nor a^r/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(a^r/2 – 1, N) = p or q

The second factor can be found by dividing N with the factor x.

Boom, RSA is Broken!

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!

Are Other Protocols Safe?

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

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.

Asymmetric Encryption

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

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

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.

Conclusion

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.

Additional Material

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.

About the Author

Noah Berner obtained a bachelor’s degree in computer science and a master’s degree in quantum engineering from ETH Zurich. In addition to information security in complex data processing systems, his research interests include quantum key distribution protocols and physical quantum computing architectures. (ORCID 0000-0003-4320-097X)

Links

• https://apps.dtic.mil/sti/pdfs/ADA606588.pdf
• https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.5183&rep=rep1&type=pdf
• https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions
• https://michaelnielsen.org/qcqi/QINFO-book-nielsen-and-chuang-toc-and-chapter1-nov00-acro5.pdf
• https://qiskit.org/textbook/preface.html