Shor’s Algorithm: Breaking RSA and ECC Encryption - Part 1

The Crypto Breaker

Shor’s algorithm is a groundbreaking quantum algorithm designed to solve the period finding problem, all within polynomial time.

The period finding problem seeks the smallest $r$ such that:

\[f(x) = f(x + r),\]

and it can be generalized to multivariate functions (functions with multiple inputs). In such cases, the goal is to find periods $r_1, r_2, \ldots, r_n$ such that:

\[f(x_1, x_2, \ldots, x_n) = f(x_1 + r_1, x_2 + r_2, \ldots, x_n + r_n).\]

Why is this problem a big deal? It turns out that the period-finding problem is the key to breaking widely-used encryption schemes like RSA and ECC(elliptic curve cryptography). These encryption schemes rely on problems considered computationally infeasible for classical computers:

• RSA: integer factorization problem
• ECC: elliptic curve discrete logarithm problem

By using Shor’s algorithm efficiently solve the period-finding problem, we can reduce these “hard” problems to ones that quantum computers can solve in polynomial time.

Before We Begin

In this article, we’ll explore how Shor’s algorithm can be applied to break RSA and ECC encryption schemes. While the algorithm shares some similarities with the simpler Deutsch-Jozsa algorithm, Shor’s algorithm is significantly more complex and operates on a much grander scale.

To help navigate this complexity, we’ll take a top-down approach:

• Start with the top-level goal (or problem)
  • Breaking encryption schemes is the top-level goal
• Gradually break down the goal into smaller, more manageable sub-goals:
  • Assume the sub-goals are already achieved: imagine we have access to oracle that can solve these sub-problems
  • Demonstrate how the goal can be achieved: show that if these sub-goals are solved, the higher-level goal can be achieved as well
• Finally, explore how quantum circuits solve the core sub-problems

This approach will help us understand the algorithm’s inner workings and how it fundamentally disrupts classical cryptographic assumptions.

Goal 0: Breaking Encryption Schemes

The ultimate goal is to solve two foundational problems in cryptography:

• Integer factorization problem (IFP), breaking RSA encryption
• Elliptic curve discrete logarithm problem (ECDLP), breaking ECC encryption

These problems are critical to the security of RSA and ECC, respectively. We’ll skip the detailed cryptographic implications and focus on how both problems can be reduced to the period-finding problem, the core challenge Shor’s algorithm addresses. Here’s how these reductions work:

Reducing IFP to the Period-Finding Problem

Goal: Given an integer $N$, find its prime factors.

We assume access to an oracle that can solve the period-finding problem.

1. Pick a random integer $a$ such that $1 < a < N$ and $\gcd(a, N) = 1$. If $\gcd(a, N) \neq 1$, then we have already found a factor of $N$. (Efficient classical algorithms exist for computing the greatest common divisor.)

2. Define the function as $f(x) = a^x \mod N$. This function is periodic with period $r$ such that:

   \[a^{x} \equiv a^{x + r} \mod N,\]

   and we know what $r$ by assumption. The period $r$ is the smallest integer satisfying $a^r \equiv 1 \mod N$.

3. If $r$ is odd, repeat with a different $a$ (proven to succeed with high probability). If $r$ is even, proceed to the next step.

4. Compute:

   \[x = a^{r/2} \mod N.\]

   If $x = \pm 1 \mod N$, choose another random $a$ and repeat the process. Otherwise, proceed to the next step.

5. Compute $\gcd(x \pm 1, N)$ which yields the factors of $N$. This follows from:

   \[x^2 \equiv 1 \mod N \implies (x - 1)(x + 1) \equiv 0 \mod N.\]

The above steps show that the integer factorization problem reduces to the period-finding problem.

Reducing ECDLP to Period-Finding Problem

Goal: Given an elliptic curve $E$ defined over a finite field $\mathbb{F}_p$ and a point $P$ on the curve, find the integer $k$ such that $Q=kP$.

1. Define the function $f(a,b)=aP + bQ$, where $a$ and $b$ are integers. This function maps pairs of integers to points on the curve.

2. The function $f(a,b)$ is periodic due to the finite number of points on the curve. It has periods $r_a$ and $r_b$ such that:

   \[f(a,b) = f(a + r_a, y + r_b).\]

   The periods $r_a$ and $r_b$ can be determined using a period-finding oracle.

3. Solve for $k$ using $k=-r_a r_b^{-1} \mod n$, where $n$ is the order of the curve. This follows from:

   \[\begin{aligned} & aP + bQ = (a + r_a)P + (b + r_b)Q \\ \implies & r_a P + r_b Q = 0 \\ \implies & Q = -r_a r_b^{-1} P. \end{aligned}\]

These steps show that the ECDLP reduces to the period-finding problem.

The Hidden Subgroup Problem

FYI, Both the IFP, ECDLP, and the period-finding problem are instances of a more broad class of problems called the hidden subgroup problem (HSP). The power of Shor’s algorithm lies in its ability to solve these HSPs.

Having reduced the IFP and ECDLP to the period-finding problem, it’s enough to focus on solving this key problem. We’ll continue with this in the next article.