RSA ⇒ FAC

Fully-black-box reduction · standard model · RSA78 · security loss: tight: one factoring call; RSA advantage equals factoring success on GrGen’s moduli

Statement

If RSA is hard for $\mathsf{GrGen}$, then factoring the moduli $n$ that $\mathsf{GrGen}$ outputs is hard, since the factors of $n$ yield the decryption exponent $d$ — RSA78.

Sketch

Given an RSA challenge $(n,e,y)$, run the factoring algorithm on $n$; if it returns a prime factor $p$, set $q=n/p$, compute $d\equiv e^{-1}(\mathrm{mod}\varphi (n))$ with $\varphi (n)=(p-1)(q-1)$, and output $y^d\mathrm{mod}n$. The output is correct whenever factoring succeeds, so the RSA advantage equals the factoring success probability on the moduli $\mathsf{GrGen}$ outputs.

Notes

• The reduction preserves the modulus distribution of $\mathsf{GrGen}$. This is the distribution of the factoring game (independent uniform $\lambda$-bit primes) when $\mathsf{GrGen}$ samples $p,q$ that way and then picks $e$ coprime to $\varphi (n)$; a $\mathsf{GrGen}$ with fixed $e$ conditions $p,q$ on $\gcd (e,\varphi (n))=1$ — folklore.
• Whether factoring hardness implies RSA hardness is open in the standard model; against generic ring algorithms the two are equivalent (RSA ⇔ FAC) — AM09, DLO24.