0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Do you have a link to the media from Khan University you reference? $\endgroup$ Mar 3, 2016 at 10:02
  • $\begingroup$ youtube.com/watch?v=IY8BXNFgnyI at 2:19 he mentions a "second one-way function" which is the prime factorization of the phi number $\endgroup$
    – theupandup
    Mar 3, 2016 at 10:08
  • $\begingroup$ 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. $\endgroup$
    – user9070
    Mar 3, 2016 at 16:28
  • $\begingroup$ Not to nit-pick, but isn't factorization the way to attack the trap door function instead of the trap door function itself? $\endgroup$
    – Maarten Bodewes
    Mar 4, 2016 at 8:33

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I don't fully understand your answer. The only "difficult" part of this problem is factoring for N, right? $\endgroup$
    – theupandup
    Mar 3, 2016 at 10:06
  • $\begingroup$ 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. $\endgroup$
    – Ruggero
    Mar 3, 2016 at 10:09
  • $\begingroup$ 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) $\endgroup$
    – SEJPM
    Mar 3, 2016 at 11:29
2
$\begingroup$

Short answer:

They work together; they protect $d$, which is the RSA private key.

  1. Prime factorization is for Key distribution.
    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)$.

  2. Modular exponentiation is for encryption and decryption.
    So even knowing $e$ and $n$ or even $m$ it can be extremely difficult to find $d$.

$\endgroup$
2
  • 1
    $\begingroup$ We've got a top 4 user with the nickname D.W. . It would be nice if you would choose another nickname to avoid confusion. $\endgroup$
    – Maarten Bodewes
    Mar 4, 2016 at 8:18
  • $\begingroup$ Sure, but have to wait till next month because of the website's policy. Cannot imagine how popular is my nickname! Sorry for the inconvenience. $\endgroup$
    – Leo.W
    Mar 4, 2016 at 9:58
-1
$\begingroup$

It's because there's no known real way to calculate massive prime numbers quickly and effectively. I forget where I saw it but there is a picture of a chart showing how a computer can calculate the primes of the n value, but as they get massive it slows even the fastest computers down. So with no real formula for calculating primes it takes a while.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.