1

I have a problem with RSA Decryption,
if I set $n=3*11=33$ I get $\varphi(33)=20$ and e=3
the first problem is encrypting the Message 12,
when I encrypt $12^3\equiv 12 (mod 33)$
meaning the the encryption is also 12
the second problem is when I check if $12^\varphi(n)\equiv 1 (mod n)$ (from Euler's theorem)
I get 12 instead of 1.

the bigger problem is if I have three users that encrypt the same message but for
different $n_i$,if I know that all the users used the same e=3 and I have all of the $n_i$
how can I know to pair each message for the $n_i$, for example if I have $n_1=11*3\; n_2=17*19\; n_3=22*19$ and I have three encrypted messages $c_1 ,c_2 ,c_3$ and I know all of them used e=3, how can I know how to pair each $c_i$ to $n_i$ so I could calculate the inverse to know the decryption.

Caleb Stanford
  • 45,895
user3453625
  • 13

1 Answers1

0

The problem is that the message $m$ should be coprime with $n$. And here $(m,n) = (12,33) = 3$. Here this is not the case, and even every power of $12$ equals $12$ modulo $33$.

For large (and realistic) values of $n$, if we choose message $m$, the only way $(m,n) \neq 1$ is when $m$ is a multiple of $p$ or $q$, (and then $(m,n) = p$ or $q$) and so choosing the message and checking this condition even breaks this instance of RSA (we can then factor $n$), and this chance is very small for large RSA moduli $n$. But in toy examples like this we can run into this problem...

Henno Brandsma
  • 242,131