I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please?

Let $N=3869$ and be the product of two distinct unknown odd prime numbers $p$ and $q$ such that $(p − 1)(q − 1)$ is not divisible by $3$. Show that there are exactly nine messages which are unchanged by RSA encryption using the public key $(N, 3)$.

Also explain how to find p and q if at least four of these messages are known.


If it is unchanged by the private key, then surely it is also unchanged by the public key (and vice versa). Thus, you must find the number of solutions to $m^3=m\pmod{N}$. This amounts to solving two different equations $m^3=m\pmod{p}$ and $m^3=m\pmod{q}$ and combining them using the Chinese remainder theorem. In each case, $m=0$ is a solution, and also the two solutions to $m^2=1$ (modulo the prime). Hence, there are nine solutions modulo $N$.

I haven't solved the next part, but it might be useful to note that having four solutions means, by the Pigeonhole principle, that there will be enough messages so that they will give at least two different values modulo both $p$ and $q$.

  • $\begingroup$ I do not understand why we need to solve $m^{3}$=$m$ ($mod$ $N$). Where does the 3 come from in particular? Also from your response am I right in saying m=0,1 and -1 are three of the messages? If so, how do you find the other 6. Can you explain please? $\endgroup$ – Jed May 3 '15 at 19:11
  • $\begingroup$ The $3$ comes from the public key (this is decrypting the message $m$). And $0,-1,1$ are three of the messages modulo $p$ and modulo $q$: use the Chinese remainder theorem to get all nine from these. $\endgroup$ – Kyle Miller May 3 '15 at 19:53
  • $\begingroup$ I understand what the Chinese remainder theorem is. However I do not know how to use the Chinese remainder theorem to get the other 6 messages, because I do not know what p and q are? Could you explain this part please? $\endgroup$ – Jed May 3 '15 at 19:59
  • $\begingroup$ In your post you said $N$ is the product of two odd primes $p$ and $q$. Since they are coprime, there are $a$ and $b$ such that $ap+bq=1$. Then, $m=0,ap,-ap,bq,ap+bq,-ap+bq,-bq,ap-bq,-ap-bq$ are the messages. $\endgroup$ – Kyle Miller May 3 '15 at 22:24
  • $\begingroup$ Thanks that helps. Finally do you know how to find p and q if at least four of these messages are known? $\endgroup$ – Jed May 3 '15 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.