Learning RSA: decryption yields inconsistent result after modular arithmetic

Question

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 = m^e mod n = 5¹⁷ 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 = 80¹²³ mod 209 = 49!!

What am I doing wrong?

Thanks!!

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)$ — kelalaka, Commented Sep 1, 2022 at 21:14
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). — fgrieu, Commented Sep 4, 2022 at 9:08

poncho · Accepted Answer · 2022-09-01 21:16:58Z

4

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

answered Sep 1, 2022 at 21:16

poncho

150k11 gold badges230 silver badges368 bronze badges

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

Add a comment |

Pablo D · Accepted Answer · 2022-09-01 21:15:04Z

1

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

answered Sep 1, 2022 at 21:15

Pablo D

1155 bronze badges

Add a comment |

2 Answers 2