RSA and integer factoring
RSA signature
In textbook RSA, only with a private key \(d\) can we generate a signature
\[\sigma \leftarrow m^{d}\equiv m \pmod{N}\]but anyone with the public key \((e,N)\) can verify that
\[\sigma^e \equiv m \pmod{N}\]The keys are constructed from two random prime numbers \(p,q\) such that
\[de\equiv 1 \pmod{\phi(N)}\]where \(\phi(N)=(p-1)(q-1)\) is Euler’s totient function for such \(N\).
Warning
Anyone gaining knowledge of \(p\) or \(q\) can recover the private key \(d\) by computing either \(\gcd(p,N)\) or \(\gcd(q,N)\).
Details
Important
The most efficient classical algorithm to factorize an \(N\) of length \(b\) bits, the GNFS, has complexity approximately
\[e ^ {3 b^{1/3} \cdot (\log b)^{2/3}}\]A 3072-bit RSA public key provides \(\approx 128\) bits of security against a classical computer. [BGGHTZ_22]
Warning
Shor’s algorithm to factorize an \(N\) of length \(b\) bits has complexity approximately
\[b^3\]. A 3072-bit RSA public key would provide \(\approx 34\) bits of security against a quantum computer running Shor’s algorithm. More recent estimates suggest it is possible to reach an efficiency closer to \(b^2\).
RSA and Shor’s algorithm
Note
Finding the period of the function \(a^k \mod N\) allows recovering the factors of \(N\).
Order of group elements
The order of a group element \(x\) is the smallest integer \(k\) for which \(a^k \equiv 1 \mod N\).
If no such \(k\) exists, the element is said to have infinite order. If it does, the subset \({a^j} \subseteq G\) is a subgroup of G generated by a, and its order is \(k\).
The order of every group element is a divisor of the number of group elements.
The order of the group \(G\) is the number of group elements in \(G\).
Lagrange’s theorem: the order of any subgroups of G is a divisor of the order of G itself.
Important
If \(x\) is a non-trivial solution to \(x^2-1\equiv 0 \pmod{N}\), then \((x\pm 1)\mid N\).
Warning
The factors of \(N\) can be efficiently recovered by \(\gcd(N,x\pm 1)\).
Consider the solutions to
\[ \begin{align} x^2 & \equiv 1 \pmod{N} \\ x^2 - 1^2 & = 0 \pmod{N} \\ (x+1)(x-1) & = 0 \pmod{N} \\ N & \mid (x+1)(x-1) \end{align} \]\({1,-1}\) are solutions for any \(N\). There will be other solutions \(\neq \pm 1\) when \((x+1)(x-1)\) is divided by \(p\) or \(q\).
Example
Can’t we just use bigger keys?
No. Quantum algorithms for this particular problem scale much better than their classical best equivalent – polynomial (\(\approx n^2\)) vs. sub-exponential (\(e ^ {3 b^{1/3} \cdot (\log b)^{2/3}}\)), respectively. To keep using RSA with acceptable levels of securitty, we would have to increase public key sizes to terabytes.
