The Risks of RSA

This document outlines the theoretical methods by which RSA can be broken using quantum computing, specifically leveraging Shor's algorithm.

1, RSA Overview

RSA relies on the difficulty of factoring large integers into their prime components.
The public and private keys are derived as follows:

Select two large prime numbers, \(p\) and \(q\).

Compute \( N = p \cdot q \) (the modulus)

Compute \( \phi(N) = (p-1)(q-1) \) (Euler's totient function)

Choose an encryption exponent \(e\) such that \( 1 < e < \phi(N) \) and \( \gcd(e, \phi(N)) = 1 \)

Compute the decryption exponent \( d \) as the modular multiplicative inverse of \( e \) modulo \( \phi(N) \):
\( e \cdot d \equiv 1 \pmod{\phi(N)} \)

The public key is \( (e, N) \), and the private key is \( d \).

2, Breaking RSA with Shor's Algorithm

Shor's algorithm efficiently factors the modulus $N$ by exploiting quantum Fourier transforms (QFT). The steps are:

Select a random integer \(a\), where \(1 < a < N\).
Compute \( \gcd(a, N) \). If \( \gcd(a, N) > 1 \), then \( N \) is factored.
If \( \gcd(a, N) = 1 \), determine the order \( r \) of \( a \) modulo \( N \):
\[ a^r \equiv 1 \pmod{N}. \]
Use the quantum Fourier transform to find the period \( r \) efficiently.
If \( r \) is even, compute:
\[ p = \gcd(a^{r/2} - 1, N), \quad q = \gcd(a^{r/2} + 1, N). \] If \( p \) and \( q \) are non-trivial factors, \( N \) is factored as \( N = p \cdot q \).

3, Conclusion

To ensure security in a quantum era, transitioning to post-quantum cryptography, such as lattice-based or hash-based cryptographic schemes, is essential.