Skip to main content
Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

The use of RSA for public-key encryption is widely believed to rely on the assumption that factoring is hard. Actually it relies on a stronger assumption than this, namely that the RSA problem is hard.

The RSA problem is the following: given a semiprime $N = pq$ and an exponent $e$ such that $\gcd(e, \varphi(N)) = 1$, efficiently compute $e^{th}$ roots $\bmod N$. It is widely believed that the only way to do this is to compute $e^{-1} \bmod \varphi(N)$ where $\varphi(N) = N - p - q + 1$, and in turn it is widely believed that the only way to do this is to factor $N$ so as to compute $\varphi(N)$. However, strictly speaking both of these are conjectures which are independent of the conjecture that factoring is hard.

So it may be that factoring is hard but that the RSA problem is easy because there is some clever way to avoid these steps and solve the RSA problem without factoring $N$. Note also that we only need to factor semiprimes; it may also be that factoring is hard but that factoring semiprimes is easy.

Post Made Community Wiki by Qiaochu Yuan