Factoring and RSA

The first of the two arithmetic problems that carried public-key cryptography from 1977 into the 2020s is integer factoring. This note builds it from the forward direction, shows why the backward direction stops being possible, and then assembles a complete RSA key pair small enough that you can check every step with a pencil.

01.The forward direction is one multiplication

Pick two prime numbers and multiply them.

Take $p = 11$ and $q = 13$. Then

$$n \;=\; p \cdot q \;=\; 11 \cdot 13 \;=\; 143.$$

That is the entire forward direction. One multiplication.

Scale it up and nothing about the difficulty changes. Real RSA uses primes of about $300$ decimal digits each, giving $n$ of about $600$ digits. Multiplying two $300$-digit numbers is something a laptop does in microseconds. The work grows roughly with the square of the number of digits, which is comfortably polynomial, so clause 1 of the trapdoor contract is satisfied without effort.

02.The backward direction, at pencil scale

Now the reverse. Somebody hands you $143$ and asks which two primes multiply to give it.

Try the primes in order.

Is $143$ divisible by $2$? No, it is odd.

By $3$? The digits sum to $1 + 4 + 3 = 8$, which is not a multiple of $3$, so no.

By $5$? It does not end in $0$ or $5$, so no.

By $7$? $7 \cdot 20 = 140$, leaving a remainder of $3$, so no.

By $11$? $11 \cdot 13 = 143$ exactly. Found it.

Five trial divisions. The backward direction was easy here, and it is important to be clear about why: because $143$ is a tiny number, not because the method is good.

03.Why the backward direction stops being possible

Trial division works by testing every prime up to $\sqrt{n}$, because if $n$ has a factor larger than $\sqrt{n}$ it must also have one smaller. For $143$, that means testing primes up to $\sqrt{143} \approx 12$, and there are five of them.

Count what that same strategy costs at cryptographic size. For $n$ around $2048$ bits, $\sqrt{n}$ is around $2^{1024}$, and the number of primes below that is roughly

$$\frac{\sqrt{n}}{\ln \sqrt{n}} \;\approx\; \frac{2^{1024}}{710} \;\approx\; 10^{305}.$$

The observable universe contains something like $10^{80}$ atoms. The number of trial divisions is larger than that by more than two hundred orders of magnitude.

Mathematicians have of course done far better than trial division. The best general method known is the general number field sieve, a descendant of ideas going back to Fermat and Gauss, and its running time is roughly

$$\exp\!\Bigl(c\,(\log n)^{1/3} (\log \log n)^{2/3}\Bigr).$$

That is the subexponential middle band from the previous note. It is a colossal improvement on trial division, and it is still nowhere near enough. The largest RSA modulus ever publicly factored is around $829$ bits, and that took thousands of core-years of computation. Deployed keys are $2048$ or $3072$ bits, and each extra bit makes the gap worse.

So the asymmetry is real. Multiplying is microseconds. Factoring is beyond the reach of every classical machine that exists or is planned.

04.Where the trapdoor lives

Now build the actual scheme, and watch where the secret enters.

Bob picks two primes $p$ and $q$ and computes $n = pq$. He also computes a second quantity from them,

$$\varphi(n) \;=\; (p - 1)(q - 1),$$

which counts how many numbers below $n$ share no factor with it. With $p = 11$ and $q = 13$,

$$\varphi(143) \;=\; 10 \cdot 12 \;=\; 120.$$

Bob then picks a public exponent $e$ that shares no common factor with $\varphi(n)$. Take $e = 7$.

Finally he finds the number $d$ satisfying

$$e \cdot d \;\equiv\; 1 \pmod{\varphi(n)}.$$

This $d$ is called the private exponent, and finding it is quick once you know $\varphi(n)$. Here we need $7d \equiv 1 \pmod{120}$, and $d = 103$ works, since $7 \cdot 103 = 721 = 6 \cdot 120 + 1$.

Bob publishes the pair $(n, e) = (143, 7)$ and tells nobody $p$, $q$, $\varphi(n)$ or $d$.

05.The worked example, end to end

Alice wants to send the message $m = 9$. She has Bob's public key and nothing else.

Encryption. She computes $c = m^e \bmod n$, that is $9^7 \bmod 143$. Doing it by repeated squaring so the numbers stay small:

$$9^2 \;=\; 81,$$ $$9^4 \;=\; 81^2 \;=\; 6561 \;=\; 45 \cdot 143 + 126 \;\equiv\; 126 \pmod{143},$$ $$9^7 \;=\; 9^4 \cdot 9^2 \cdot 9^1 \;\equiv\; 126 \cdot 81 \cdot 9 \pmod{143}.$$

Taking those last two multiplications one at a time, $126 \cdot 81 = 10206 = 71 \cdot 143 + 53$, so that part is $53$. Then $53 \cdot 9 = 477 = 3 \cdot 143 + 48$.

So $c = 48$, and Alice sends $48$.

What Eve sees. She sees $n = 143$, $e = 7$ and $c = 48$. To recover $m$ she would need $d$, to get $d$ she would need $\varphi(n) = (p-1)(q-1)$, and to get that she would need $p$ and $q$ separately. She is back at factoring.

Decryption. Bob computes $m = c^d \bmod n$, that is $48^{103} \bmod 143$, and gets $9$ back.

That $c^d$ returns the original $m$ is guaranteed by a classical result called Euler's theorem, which this book does not derive. The part that matters here is structural rather than computational: $d$ was built out of $\varphi(n)$, and $\varphi(n)$ was built out of $p$ and $q$. The factorisation is the trapdoor.

06.The three clauses, checked

Look back at the contract from the previous note and confirm RSA satisfies all three.

Easy forward. Computing $m^e \bmod n$ is repeated squaring, about $\log_2 e$ multiplications. Fast.

Hard backward without the secret. Recovering $m$ from $c$ without $d$ is believed to require factoring $n$. Infeasible at deployed sizes.

Easy backward with the secret. Computing $c^d \bmod n$ is the same repeated squaring as encryption. Fast.

And the security statement is unusually crisp. Anybody who can factor $n$ can derive $d$ and read everything. That is why "RSA is secure" and "factoring is hard" are treated as the same sentence.

Which is also why RSA has a single point of failure. There is no fallback if factoring turns out to be easy.

07.One caution about this example

Everything above is textbook RSA, and textbook RSA should never be used for anything real. Notice that Alice encrypting $m = 9$ always produces $c = 48$, every time, with no randomness anywhere. Eve can encrypt guesses under the public key and compare. If the message is one of a small set, say a yes or a no, she simply tries both.

Notice also what happens with $m = 100$: encryption returns $100$ unchanged. Some messages are fixed points, and a real scheme has to avoid handing one to an attacker.

Deployed RSA fixes this by padding the message with structured randomness before exponentiating, under a scheme called OAEP. The padding is not optional decoration. But it is also not what this chapter is about, because a quantum computer does not attack the padding. It attacks $n$.

The next note builds the second classical problem, which has a completely different flavour and, as it turns out, exactly the same fatal weakness.