Why Does Shor's Algorithm Break RSA and ECC But Not AES?

Shor's quantum factoring algorithm threatens public-key cryptosystems like RSA and elliptic curve cryptography because it efficiently solves the underlying mathematical problems of integer factorization and discrete logarithms. In contrast, symmetric encryption standards like AES do not rely on these algebraic structures, leaving them resistant to Shor's algorithm and only vulnerable to a much weaker quadratic speedup from Grover's search algorithm.

The Mathematical Foundation of Shor's Algorithm

Shor's algorithm is a quantum algorithm designed to find the period of a periodic function in polynomial time. Specifically, for a function \(f(x) = a^x \bmod N\), a quantum computer uses the Quantum Fourier Transform (QFT) to determine the smallest positive integer \(r\) such that:

\[a^r \equiv 1 \pmod{N}\]

On a classical computer, finding this period requires exponential time as \(N\) grows large. On a sufficiently powerful fault-tolerant quantum computer, Shor's algorithm finds \(r\) in \(O((\log N)^3)\) operations. This exponential speedup is possible because quantum superposition and interference allow the QFT to extract global periodicities from a function's outputs.

Why RSA and ECC Are Vulnerable

Both RSA and Elliptic Curve Cryptography (ECC) are asymmetric (public-key) systems whose security depends on one-way mathematical functions with hidden algebraic structure.

RSA and Integer Factorization

RSA security relies on the difficulty of factoring a large semiprime \(N = p \cdot q\) into its prime factors \(p\) and \(q\). Once the period \(r\) of \(f(x) = a^x \bmod N\) is found using Shor's algorithm, if \(r\) is even and \(a^{r/2} \not\equiv -1 \pmod{N}\), then \(\gcd(a^{r/2} - 1, N)\) and \(\gcd(a^{r/2} + 1, N)\) yield nontrivial factors of \(N\). This completely breaks RSA's private key generation.

Elliptic Curve Cryptography and Discrete Logarithms

ECC relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP). Given a base point \(P\) on an elliptic curve and a public key point \(Q = kP\), an attacker must find the scalar \(k\). Because the points on an elliptic curve form a finite abelian group, a variant of Shor's algorithm can solve the discrete logarithm problem over this group in polynomial time, recovering \(k\) and breaking ECC.

Why AES Remains Resilient

The Advanced Encryption Standard (AES) is a symmetric-key block cipher, not a public-key system. Instead of relying on number-theoretic problems like factoring or discrete logarithms, AES transforms plaintext into ciphertext through multiple rounds of substitution, permutation, mixing, and key addition (a substitution-permutation network).

Because AES lacks a clean, exploitable algebraic group structure or periodic function, Shor's algorithm cannot be applied to it. There is no hidden period \(r\) for the Quantum Fourier Transform to extract.

The Impact of Grover's Algorithm on AES

While Shor's algorithm does not threaten AES, another quantum algorithm called Grover's algorithm does apply to symmetric ciphers. Grover's algorithm performs an unstructured search over a space of \(2^n\) possible keys in \(O(2^{n/2})\) operations, providing a quadratic speedup over classical brute-force search.

For AES-128, Grover's algorithm reduces the effective security level from \(2^{128}\) to \(2^{64}\) operations. However, this quadratic speedup is easily countered by doubling the key length. AES-256 maintains an effective quantum security level of \(2^{128}\) operations, which remains computationally infeasible even for large-scale quantum computers.