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.
