§12 RSA Problem

The Factoring Experiment $\operatorname{Factor}_{\mathscr{A}, GenModulus}(n)$

• Let $GenModulus$ be a polynomial-time algorithm that, on input $1^n$, outputs $(N, p, q)$ where $N = pq$, and $p, q$ are $n$-bit primes except with probability negligible in $n$.
• The Factoring Experiment $\operatorname{Factor}_{\mathscr{A}, GenModulus}(n)$:
  1. Run $GenModulus(1^n)$ to obtain $(N, p, q)$.
  2. $\mathscr A$ is given N, and outputs $p' , q' > 1$.
  3. $\mathscr A$ succeeds and the output of the experiment is defined to be $1$ if $p' \cdot q' = N$, and $0$ otherwise.

The Factoring Assumption

• Definition. Factoring is hard relative to $GenModulus$ if for all probabilistic polynomial-time algorithms $\mathscr A$ there exists a negligible function $\epsilon$ such that

  $$\Pr[\operatorname{Factor}_{\mathscr{A}, GenModulus}(n) = 1] \le \epsilon(n)$$

• The Factoring Assumption is the assumption that there exists a $GenModulus$ relative to which factoring is hard.

The RSA problem

• Corollary 2 of Fermat’s Little Theorem for $\mathbb{Z}^*_N$: Fix $N > 1$. For integer $e > 0$, define the function, $f_e : \mathbb{Z}^*_N \rightarrow \mathbb{Z}^*_N$ by $f_e(x) = [x^e \bmod N]$.
  1. If $\gcd(e, \phi(N)) = 1$, then $f_e$ is a permutation, i.e., a bijection.
  2. Moreover, if $d = e^{-1}$ mod $\phi(N)$, then $f_d$ is the inverse of $f_e$.
• The RSA Problem is: Given $N, e, y$, compute $[y^{e^{-1}} \bmod N]$.

$GenRSA$

• Let $GenRSA$ be a probabilistic polynomial-time algorithm that on input $1^n$, outputs a modulus $N$ that is the product of two $n$-bit primes $p, q$, as well as integers $e, d > 0$ with $\gcd (e, \phi(N)) = 1$ and $ed = 1 \bmod \phi(N)$.
  • Such a $d$ exists since $e$ is invertible modulo $\phi(N)$.
  • The algorithm may fail with probability negligible in $n$.

The RSA Experiment $\operatorname{RSA-inv}_{\mathscr{A}, GenRSA}(n)$

• The RSA Experiment $\operatorname{RSA-inv}_{\mathscr{A}, GenRSA}(n)$:
  1. Run $GenRSA(1^n)$ to obtain $(N, e, d)$.
  2. Choose a uniform $y \in \mathbb{Z}^*_N$.
  3. $\mathscr A$ is given $N, e, y$ and outputs $x \in \mathbb{Z}^*_N$.
  4. $\mathscr A$ succeeds and the output of the experiment is defined to be $1$ if $x^e = y \bmod N$, and $0$ otherwise.

The RSA Assumption

• Definition. The RSA problem is hard relative to $GenRSA$ if for all probabilistic polynomial-time algorithms $\mathscr A$, there exists a negligible function $\epsilon$ such that

  $$\Pr[\operatorname{RSA-inv}_{\mathscr{A}, GenRSA}(n) = 1] \le \epsilon(n)$$

• The RSA Assumption is the assumption that there exists a $GenRSA$ algorithm relative to which the RSA problem is hard.

Algorithm $GenRSA$

• Algorithm $GenRSA$. Input: Security parameter $1^n$. Output: $(N, e, d)$.
  1. Run $GenModulus(1^n)$ to obtain $(N, p, q)$.
  2. Compute $\phi(N) = (p - 1)(q - 1)$.
  3. Choose $e > 1$, such that $\gcd(e, \phi(N)) = 1$.
  4. Compute $d := [e^{-1} \bmod \phi(N)]$. Return $(N, e, d)$.

Recall: Extended Euclidean Algorithm eGCD

• Extended Euclidean Algorithm eGCD:

  • Input: Integers $a, b$ with $a ≥ b > 0$.

  • Output: $(d, X, Y)$ with $d = \gcd(a, b)$ and $Xa + Yb = d$.

  • If $b$ divides $a$ return $(b,0,1)$;

  • Else compute integers $q, r$ with $a = qb + r$ and $0 < r < b$,

    Set $(d, X, Y) := \operatorname{eGCD}(b, r)$ (note that $Xb+Yr=d$),

    Return $(d, Y, X - Yq)$.

• The Extended Euclidean algorithm gives $[X \bmod b]$ as the multiplicative inverse of $a \bmod b$, and $[Y \bmod a]$ as the multiplicative inverse of $b \bmod a$ when $\gcd(a, b) = 1$.

— Mar 17, 2023

§12 RSA Problem by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.