The security of RSA

The security of the RSA system relies on the difficulty of factoring (N) – the product of two large primes. Since the RSA method is used to protect the majority of websites, this means our modern, inter-connected, digital world relies on no-one being able to quickly and easily factor large numbers.

Nowadays the vast majority of websites are encrypted before being sent over the internet to your browser. This happens every time you visit any webpage that starts “https”, and not just when logging in to a website using a password. The public key algorithm used will almost certainly be either RSA or Diffie-Hellman (or an elliptic curve variant).

If an adversary could easily factor (N), they would then know the same secret information that Alice knows (namely (p) and (q)) and could therefore find (d) via the same approach Alice took.

One could ask whether RSA can be broken without factoring. However, any reasonable mathematical break will actually enable Eve to find the factorisation of (N).

Here’s one such attack.

Let’s suppose that Eve has discovered (phi(N) = (p-1)(q-1)). This already means that the RSA system is broken, but Eve can actually find the factorisation of (N) needing nothing more than the quadratic formula.

To summarise, Eve knows the value of (N) (because it’s public) and the value of (phi).

Since (N=pq), we know that (q=N/p). And since (phi=(p-1)(q-1) = pq-p-q+1) we can substitute for (q), obtaining

[phi = N – p – N/p + 1.]

Multiplying both sides by (p) yields

[p phi = N p – p^2 – N + p]

which can be rearranged into a quadratic equation

[p^2 – p(N+1-phi) + N = 0.]

Substitute in the values for (N) and (phi), and then this can be solved for (p) using the quadratic formula! The formula will give you two roots. One will be (p), the other will be (q).

Your turn!

Try the following exercise, to check your understanding; use the comments to ask any questions you may have, but be careful not to give away the answer!

Knowing (N=2,430,101) and (phi(N) = 2,426,892) find the two prime factors of (N).

As we shall see in our last set of resources, quantum computers threaten this trapdoor function, by being able to quickly factorise large integers.