0
$\begingroup$

I have this problem: In RSA algorithm considering $n=33$ (modulus) and public exponent $e=3$, calculate the corresponding private exponent $d$.

I know that $d = e^{-1} \pmod{\varphi(n)}$ and $\varphi(n) = (p – 1) (q – 1)$ but I don't know $p$ and $q$.

How can I do this?

$\endgroup$
  • $\begingroup$ So you're been given a public key, and asked to compute the private key. That is, by definition, hard (although for small numbers you can probably just try combinations of p, q until one works). That is why RSA is considered safe. $\endgroup$ – Mike Ounsworth May 9 '15 at 16:23
  • $\begingroup$ @MikeOunsworth Things can't be "hard by definition". It is unknown whether the RSA problem is hard — although for small $n$, it certainly isn't. $\endgroup$ – yyyyyyy May 9 '15 at 16:47
  • $\begingroup$ Well it's known that the RSA problem is at maximum as hard as the integer factorization problem, but the lower bound is missing... And nothing is hard for bad parameters. $\endgroup$ – SEJPM May 9 '15 at 16:58
  • 1
    $\begingroup$ You could factor $n$. 33=3*11 $\endgroup$ – CodesInChaos May 9 '15 at 20:55
1
$\begingroup$

If I'm understanding your question right, you want to obtain $d$ from given $n$ and $e$.

You'll have to factor $n=33=3*11$ and as $N=p*q$ you have obtained your $p=11$ and $q=3$. Now proceed as usual with calculating the inverse.

As pointed out correctly above, you can't easily generalize this approach to larger numbers as factoring $n$ will be infeasible. Now you see how to factor the number but for larger numbers even the best algorithms fail.
Concerning your $e=3$ I'd consider using Coppersmith's attacks on low exponent RSA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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