RSA simple exercise

Question

An exercise asks me to encrypt with RSA a message m=10. The public key e=11 and the private key d=11. The modulo is 60.

So i tried first to cipher this way: C=10^11 mod 60=40

So 40 is my ciphertext.

Then the exercise asks me to decrypt it.

So I did M=40^11 mod 60

But the result is 40 again when it should be 10.

How is it possible? Where am I wrong?

Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. — José Carlos Santos, Aug 25 '21 at 10:02
@A Typically, it is assumed that the modulus (in this case 60) and the message $m$ are relatively prime. Because this is not the case and because the modulus is not square-free, the usual algorithm doesn’t work correctly. — Ben Grossmann, Aug 25 '21 at 10:09
@BenGrossmann: No, it is not necessary that $n$ and $m$ are co-prime. RSA works regardless. The problem here is that $60$ is not the modulus $-$ see my answer. — TonyK, Aug 25 '21 at 10:11

score 4 · Answer 1 · answered Aug 25 '21 at 10:10

$60$ is not the modulus $-$ it can't be, because it is not a product of two primes.

We see that the product of the public key and the private key is $121$, so each is the inverse of the other modulo $60$; this suggests that $60$ is $\varphi(n)$, where $n$ is the modulus.

To find the modulus $n=pq$, look for primes $p$ and $q$ such that $\varphi(n)=(p-1)(q-1)=60$. Then it all works nicely $-$ you should find that $(10^{11})^{11}\equiv 10\bmod n$.

Yes you were right, it was 77. Thank you! – Jhon Aug 25 '21 at 10:15 — Jhon, Aug 25 '21 at 10:15

RSA simple exercise

1 Answers1