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?

Improve this question
$\endgroup$
4
  • $\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
    Commented May 9, 2015 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
    Commented May 9, 2015 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
    Commented May 9, 2015 at 16:58
  • 1
    $\begingroup$ You could factor $n$. 33=3*11 $\endgroup$
    – CodesInChaos
    Commented May 9, 2015 at 20:55

1 Answer 1

Reset to default
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.

Improve this answer
$\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.