RSA Problem.
Given a modulus $N$ and integer $e>2$, such that $\gcd(e, \varphi(N))=1$.
By the Corollary 2 of the Fermat’s Little Theorem (see it in P2), we know that exponentiation to the $e$-th power mod $N$ is a permutation on $(\mathbb{Z}/N)^{*}$;
For any $y\in (\mathbb{Z}/N)^{*}$, let $[y^{1/e} \mod{N}]$ be the unique element which yields $y$ when raised to the $e$-th power mod $N$, i.e., the $e$-th root of $y$ mod $N$.
If $e\cdot d\equiv 1\pmod{\varphi(N)}$, then raising to the $d$-th power is the inverse of raising to the $e$-th power, that is, for any $g\in (\mathbb{Z}/N)^{*}$, $(g^e)^d \equiv g\pmod{N}$. Therefore, if $y=g^e$, $y^{1/e}=g=y^d\pmod{N}$.
RSA problem is essentially finding $e$-th root of $y$ mod $N$: Given $N,e,y$, compute $[y^{1/e}\mod{N}]$. Note that $e>2$ and $\gcd(e, \varphi(N))=1$, $\gcd(y, N)=1$.
RSA Experiment
Similarly, we have the RSA experiment $\mathtt{RSA}$-$\mathtt{inv}_{\mathscr{A}, GenRSA}(n)$, where GenRSA is an efficient 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, \varphi(N))=1$ and $ed\equiv 1\pmod{\varphi(N)}$.
Adversary $\mathscr{A}$ with $N,e$ and a uniform $y\in (\mathbb{Z}/N)^{*}$ needs to efficiently compute the corresponding $x$.
Definition. RSA problem is hard relative to GenRSA if for all probabilistic polynomial time algorithm $\mathscr{A}$, there exists a negligible $\varepsilon(n)$ that $\Pr[\mathtt{RSAinv}_{\mathscr{A}, GenRSA}(n)=1]\leq \varepsilon(n)$.
The RSA Assumption is the assumption that there exists a GenRSA algorithm relative to which the RSA problem is hard. Note that GenRSA can be constructed from GenModulus.
RSA and Factoring
The hardness of RSA problem could be reduced to the hardness of factoring problem, which is to say, one could efficiently solve RSA problem if he could efficiently solve factoring problem.
Assume there exists an efficient algorithm $\mathscr{A}$ that could factorize $N$ into two distinct primes $p,q$, then we could construct an efficient $\mathscr{A}’$ that could solve RSA problem.
- $\mathscr{A}’$ runs $\mathscr{A}(N)$ and obtain two distinct odd primes $p,q$ that $N=pq$.
- $\mathscr{A}’$ simply computes $\varphi(N)=(p-1)(q-1)$.
- $\mathscr{A}’$ computes $d\equiv e^{-1}\pmod{\varphi(N)}$ with extended Euclidean algorithm.
- $\mathscr{A}’$ could compute $y^{1/e}$ mod $N$ efficiently by computing $y^d$ mod $N$.
RSA 问题本质上是求模意义下的 $e$ 次方根。注意 RSA 问题中的模数 $N$ 是两个不同的大奇质数 $p,q$ 之积。
RSA 问题的巧妙之处在于，利用群的 closure 性质与费马小定理可得，模意义下的 $e$ 次方根与模意义下的 $d$ 次方幂是等价的；其中 $\gcd(e, \varphi(N))=1$, $d\equiv e^{-1} \pmod{\varphi(N)}$. 也就是说，如果敌手得知 $\varphi(N)$，那么他就能通过计算得出 $d$，从而轻松解决 RSA 问题。
然而得知 $\varphi(N)$ 也是困难的；这由 Factoring problem 的困难性保证。对于只有两个质因数 $p,q$ 的模数 $N$, $\varphi(N)=\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)$。所以，得到 $\varphi(N)$ 的前提是成功将 $N$ 分解为 $p,q$。
著名的 RSA 公钥加密就应用了这一性质：在该加密中，公钥 $pk=e$, 私钥 $sk=d$。加密 $Enc_{pk}(m)=m^e$，解密 $Dec_{sk}(c)=c^d$ (均在 mod $N$ 意义下)。RSA 问题的困难性保证了任意不持有私钥的敌手无法由密文 $c=m^e$ 破解消息 $m$ (即，得到 $c$ 在模 $N$ 意义下的 $e$ 次方根)。