How Shor’s algorithm can break RSA

8 min readAug 5, 2020

An explanation of the maths behind RSA, shor’s algorithm and how quantum computing can break the encryption.

How asymmetric encryption works — E.G RSA

RSA works with a pair of keys to encrypt-decrypt. A public key which everybody can access to encrypt the messages and a private key, only owned by the proprietary and it is used to decrypt the messages.

Alice uses Bob’s public key to encrypt the message

Bob receives the messages and decrypt it with his private key

Lest make a comparison with a mailbox.

Everybody knows where Bob’s mailbox is (public key), but only Bob have the key to open it (private key).

The algorithm

The algorithm is based on the fact that finding the factors of a large composite number is difficult: when the factors are prime numbers, the problem is called prime factorization. It is also a key pair (public and private key) generator.

Note that we are going to use small numbers so this will be a simplified version.

The required length for the algorithm to work is at least 1024 bits. For example, find the factors of 15 is easy (3,5) but find the factors of this number with 250 digits (829 bits) It’s not.

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

So the algorithm is similar to put a lock on your door and bars on your windows, it doesn’t guarantee you wont have stuff stolen from your home, but does make it take more time and more work.

Let’s get into the maths

This is the smallest possible value for the modulus n for which the RSA algorithm works.

Now say we want to encrypt the message m = 7

The ciphertext C = 13. And the decrypted text is m = 7

Breaking the algorithm

It all starts with a big number, N, that you’ll need to find the factors of to break into some encrypted data.

As you don’t know what those factors are, you can make a guess, a number g that is less than N. We don’t need the guess to be a pure factor of N it could also be a number that shares some factors with N.

Numbers that share factors are ok because of Euclid’s algorithm a method to check for and find common factors. So, to find a factor of N, we don’t have to guess a factor of N — guessing numbers that share factors with N works, too, thanks to Euclid. If the algorithm finds any shared factors with N we can just divide N by this factor and get the other factor.

But for the big numbers used in encryption, it’s astronomically unlikely that any single guess will share a factor with N. So, we are going to use a mathematical trick to get a better guess.

Mathematical trick 1

For any pair of whole numbers that don’t share a factors, if you multiply one of them by itself enough times, you’ll eventually arrive at some whole number multiple of the other number, plus 1.

So for our number N and our not so good g guess we’re guaranteed that some power of g is equal to some multiple of N, plus 1 .

If we rearrange this equation we get.

And we can find shared factors using Euclid’s algorithm

If this is it why couldn’t we use this to get our factors of N and break the encryption?

Problems

One of the new guesses might itself be a multiple of N, in which case the other would be a factor of m and neither would be useful to us in any way.

The power “p” might be an odd number , in which case p/2 isn’t a whole number and so our guess taken to the power of p/2 probably isn’t a whole number either.

for a random starting guess, it turns out that at least 3/8 ths of the time (37.5%) neither of these problems happens

3. The biggest problem is, How do we find p?

For a clasical computer, calculate how many times do we have to multiply a number for itself to get a multiple of N + 1 is really hard.

The Quantum advantage

Unlike a normal computation which gives only one answer for a given input, a quantum computation can simultaneously calculate a bunch of possible answers for a single input by using a quantum superposition.

The key behind fast quantum computations is to set up a quantum superposition that calculates all possible answers at once while being cleverly arranged so that all of the wrong answers destructively interfere with each other.

The key behind fast quantum computations is to set up a quantum superposition that calculates all possible answers at once while being cleverly arranged so that all the wrong answers destructively interfere with each other.

For doing that we will use Shor’s algorithm!!!

Mathematical trick 2

If we take our guess to a random power , it’s probably going to be some other number more than a multiple of N lets say “r” more, if we raise our guess to that random power plus p, it’s again “r” more than a multiple of N . If we raise our guess to that random power plus 2 p, it’s again “r” more than a multiple of N. And so on.

So the power p that we’re looking for has a repeating property where if we take another power and add (or subtract) p to it, the amount more than a multiple of N stays the same.

Quantum

If we take the superposition of all possible powers and measure the “amount more than a multiple of N part, then we’ll randomly get one of the possible “amounts more than a multiple of N” as the output. This means we must be left with a superposition of purely the powers that could have resulted in a remainder of “r”.

And in our case, because of the repeating property, those powers are all numbers that are “p” apart from each other. So the numbers repeat with a frequency of 1/p.

Fourier transform

Fourier transform is a mathematical transform that decomposes a function (often a function of time, or a signal) into its constituent frequencies.

Quantum Fourier transform

When you put IN a superposition of numbers, you get out a superposition of superpositions and the sine waves add together or subtract and cancel out. If you put in a superposition of numbers that are all separated by an amount p, all those sine waves interfere so that what you get out, is the single quantum state representing 1/p!!

As long as p is even we can now finally raise our guess to the power p over two and add or subtract one, and as long as we don’t get an exact multiple of N, we are guaranteed to have a number that shares factors with N. And therefore we can use Euclid’s algorithm those factors

Let’s Code

This code is from a lab from Qiskit summer school. The code will be python, and we will use qiskit for the circuit implementation. We will factor N=15

1. Initializing the qubits

We will need to initialize our qubits as described above by applying a Hadamard gate on each of the 𝑛 measurement qubits. We will also set the target qubits to |1⟩, since that is the eigenstate onto which the unitary operator 𝑈 will be applied. Here, |1⟩ is initialized by applying an 𝑋 gate on the last qubit.

2. Modular exponentiation

We have created a function called a_x_mod15 below which takes in two arguments, a and x, and implements the unitary operator

𝑈=𝑎𝑥 mod 15

Note that the function a_x_mod15 creates a 4-qubit unitary controlled by an additional fifth qubit. In order to use this gate, you will need to append it to your quantum circuit using Qiskit's circuit.append() function by passing in the five qubits in a list containing the control qubit first, followed by the four target qubits.

3. Implementing the inverse quantum Fourier transform

The last step before measuring the first 𝑛n qubits is the implementation of the inverse quantum Fourier transform.

4. Shor Program

You will get a circuit like this

In order to run your quantum circuit and get the measurement outcomes, you simply need to run Qiskit's execute function as follows.

Note: We are using the qiskit simulator we are not running the circuit on a real quantum device.

We get this result

We can now convent the values from binary to Numbers

Measured 8
Measured 12
Measured 4
Measured 0

Note: The values on the picture are writen from the less significant bit (botton number) to the most significant bit (top number)

We can finaly postprocess clasically our solutiuon checking the constraints

Measured 8
(1, 15)
Measured 12
(5, 3)
Measured 4
(5, 3)
Measured 0
(1, 15)

And we finally get the Factors 3 and 5!!!!!

Why haven’t I lost my security on the Internet yet?

That is because the biggest actual quantum implementations of Shor’s algorithm don’t have enough memory to hold more than a few bits, which only allows factoring small numbers.

To break the number I wrote at the beginning of the post, the one with 250 digits, will take 5900 quantum bits that’s far away of todays quantum computers.