RSA Assumption

The RSA assumption states that the RSA function $x\mapsto x^e\mathrm{mod}n$ is hard to invert: given a modulus $n=pq$, a public exponent $e$, and a value $y$, no efficient adversary can find $x$ such that $x^e\equiv y(\mathrm{mod}n)$. It was introduced alongside the RSA cryptosystem — RSA78.

Assumption

The assumption is parameterized by a group generator $\mathsf{GrGen}$ that, on input $1^{\lambda }$, outputs an RSA modulus $n=pq$ (the product of two large primes) together with a public exponent $e$ coprime to $\varphi (n)=(p-1)(q-1)$ and the corresponding private exponent $d\equiv e^{-1}(\mathrm{mod}\varphi (n))$.

RSA Problem

In the RSA game, the adversary is given an RSA instance $(n,e,y)$ and must produce the RSA inverse: an $x$ such that $x^e\equiv y(\mathrm{mod}n)$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{rsa}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(n, e, d) \gets \GrGen(1^\secpar)$
\State $x \getsr \ZZ_n^*$
\State $y \gets x^e \bmod n$
\State $\hat{x} \gets \calA(1^\secpar, n, e, y)$
\Return $[\hat{x}^e \equiv y \pmod{n}]$
\end{algorithmic}
\end{algorithm}

RSA is hard for $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{rsa}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\text{rsa}}(\lambda )=1\right]$$

is negligible.

Known Results

• RSA ⇒ TDP
• TDP ⇒ PKE
• RSA ⇒ FAC: the factors of $n$ give $\varphi (n)$ and hence $d$ — RSA78. Recovering $d$ from $(n,e)$ is deterministic polynomial-time equivalent to factoring $n$ when $p,q$ have equal bit length and $ed\le n^2$ — May04. Whether factoring hardness implies RSA hardness is open in the standard model; for small $e$, an algebraic reduction from factoring would itself yield a factoring algorithm — BV98.
• RSA ⇔ FAC in the generic ring model — AM09, DLO24
• Hard-core bit: predicting the least significant bit of $x$ from $(n,e,x^e\mathrm{mod}n)$ with non-negligible advantage is probabilistic polynomial-time equivalent to inverting RSA — ACGS88.

Variations

Strong RSA

The strong RSA assumption strengthens the standard assumption by allowing the adversary to choose the exponent $e$ itself (subject to $e>1$). Formally, the adversary outputs a pair $(\hat{x},\hat{e})$ with $\hat{e}>1$ and ${\hat{x}}^{\hat{e}}\equiv y(\mathrm{mod}n)$. Introduced by BP97 and FO97. With a collision-resistant hash it yields EUF-CMA signatures in the standard model — CS99; with a division-intractable hash, hash-and-sign signatures — GHR99. It also yields statistically hiding commitments to integers — FO97, DF02.

Φ-Hiding

The Φ-hiding assumption states that, given $n$ and a prime $e\le n^{1/4-\epsilon }$, it is hard to determine whether $e\mid \varphi (n)$ — CMS99; for $e>n^{1/4}$ Coppersmith’s method decides it efficiently — KOS10. It underlies the polylogarithmic-communication single-server PIR of CMS99.

Attacks

• Shor’s algorithm: a quantum computer can factor $n$ in polynomial time and thus break RSA entirely — Shor97
• Wiener’s attack: when the private exponent satisfies $d<n^{1/4}$, RSA can be broken via continued-fraction approximation of $e/n$.
• Small-exponent attacks: encrypting the same short message under many independent RSA public keys with a small exponent $e$ (e.g., $e=3$) allows recovery via the Chinese Remainder Theorem (Håstad’s broadcast attack).
• Chosen-ciphertext attacks: textbook RSA (without padding) is not CCA-secure; OAEP padding is required in practice.

Participates in

Builds on RSA Assumption

• Φ-Hiding ⇒ cPIR (via Φ-Hiding)
• RSA ⇔ FAC
• RSA ⇒ FAC
• RSA ⇒ IND-CCA PKE (RSA-OAEP)
• RSA ⇒ IND-CCA KEM
• RSA ⇒ PKE
• RSA ⇒ TDP
• Strong RSA ⇒ COM (via Strong RSA)
• Strong RSA + CRHF ⇒ DS (via Strong RSA)
• Strong RSA ⇒ RSA (via Strong RSA)

Produces RSA Assumption

• Strong RSA ⇒ RSA