0
$\begingroup$

I am still studying for my crypto 101 and I have a problem with one exercise that I can't find where I'm wrong...

We have p=11 and q=19 (so n=p*q=209) and e=17. I need to encrypt m=5 with RSA system.

So: Crypt_Msg = me mod n = 517 mod 209 = 80

Ok... now I want to decrypt that value (Crypt_Msg=80)...

First of all d = inverse(e, n) = inverse(17, 209) = 123

Decrypt_Msg = 80123 mod 209 = 49!!

What am I doing wrong?

Thanks!!

$\endgroup$
2
  • 2
    $\begingroup$ The inverse is according to $\phi(n) = (p-1)(q-1)$ See Wiki RSA. Of course, $\lambda(n)$ as Carmichael's totient function is better to $\phi(n)$ $\endgroup$
    – kelalaka
    Sep 1, 2022 at 21:14
  • 1
    $\begingroup$ Moderator note: it would be nice to accept the answer that best addresses the question, by clicking the checkmark ✓ icon next to it. Benefits include rep for you and who wrote the answer (even if that's the person who asked the question and makes the tick), and marking the question as answered so that it's less prone to show up as a "top question" (the only other mean we have for the later is to downvote the question). $\endgroup$
    – fgrieu
    Sep 4, 2022 at 9:08

2 Answers 2

4
$\begingroup$

d = inverse(e, n) = inverse(17, 209) = 123

That's wrong; it should be either:

$$d = \text{inverse}(e, (p-1)(q-1)) = \text{inverse}(17, 180) = 53$$

or

$$d = \text{inverse}(e, \text{lcm}(p-1,q-1)) = \text{inverse}(17, 90) = 53$$

(In this case, both methods give the same private exponent; that happens sometimes...)

Also, you have:

$6^{17} \bmod 209 = 80$

When I compute $6^{17} \bmod 209$, I get 206...

$\endgroup$
1
  • $\begingroup$ There was a typo. m was 5, not 6. $\endgroup$
    – Pablo D
    Sep 1, 2022 at 21:40
1
$\begingroup$

Ok... my fault. To calculate d is equals to inv(e, ϕ(n))

$\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.