# Does RSA have two trapdoors?

I watched some videos from Khan Academy explaining the algorithm for RSA encryption/decryption. They explained that there are two trapdoors, modular exponentiation being one and prime factorization being the other. Is this true though? As the videos went on it made it seem like prime factorization was what made the inverse of modular exponentiation difficult to solve. Did I misunderstand something, or is modular exponentiation just a naturally difficult problem to compute?

• Do you have a link to the media from Khan University you reference? – Henrick Hellström Mar 3 '16 at 10:02
• youtube.com/watch?v=IY8BXNFgnyI at 2:19 he mentions a "second one-way function" which is the prime factorization of the phi number – theupandup Mar 3 '16 at 10:08
• You're right. The problem is actually evaluating $\phi(n)$ in order to compute the multiplicative inverse. The best known way to do this is to factorize $n$ first. – user9070 Mar 3 '16 at 16:28
• Not to nit-pick, but isn't factorization the way to attack the trap door function instead of the trap door function itself? – Maarten Bodewes Mar 4 '16 at 8:33

Defining RSA Problem as finding $m$, having $N,e,c$ where $c=m^e \mod N$ and $N=pq$, two unknown same-size prime numbers.

So far the best generic method we know to solve this is to factor $N$.

But there might be other methods, so far unknown, to compute the $e$-th root of $c$ and recovering $m$.

This is different from the discrete logarithm problem, where the exponent is secret. This is just computing an $e$-th root. We know how to compute roots modulo a prime, we don't know how to compute roots modulo a composite number of unknown factorization.

Note: for bad choices of m (i.e. without the use of padding) or $e$ or $d$ (the private exponent) there are practical attacks that recovers $m$ without factoring. For example the Weiner's or Coppersmith's attack. In particular the method of Coppersmith does compute $e$-th roots if $e$ and $m$ are small enough therefore it is not a generic method.

The RSA Problem is at least as easy as factoring. But there might be other, so far unknown, easier way to compute $e$-th roots without factoring.

• I don't fully understand your answer. The only "difficult" part of this problem is factoring for N, right? – theupandup Mar 3 '16 at 10:06
• We know how to solve it by factoring N. But there might be other unknown methods. It is at least as easy as factoring, but it could be easier. It is, in fact, easier for some bad choices of the scheme parameters. Coppersmith's method computes $e$-th roots when $m$ is small enough. – Ruggero Mar 3 '16 at 10:09
• In fact, if you can solve the DLP everyhwere efficiently (as quantum computers can IIRC), you can also break RSA. $c^d\equiv m\pmod n$ is an instance of the DLP, if you can solve it, you broke RSA given only one known plaintext. In practice this is blocked by $m$ containing sufficient randomness to be unpredictable (because it's not the message but the encoded message) – SEJPM Mar 3 '16 at 11:29

They work together; they protect $d$, which is the RSA private key.
So one can not find $p$ and $q$ from $n$, where $n = p * q$, and therefore cannot find $d \equiv e^{−1} \pmod{\varphi(n)}$, where $\varphi(n) = \varphi(p)\varphi(q) = (p − 1)(q − 1) = n − (p + q − 1)$.
So even knowing $e$ and $n$ or even $m$ it can be extremely difficult to find $d$.