If I understand correctly, for RSA to work we need the message(cleartext) M $\in Z_n$ and gcd(M,n)=1. That is M coprime to n. This is to fulfil the requirement for Eulers theorem. How does RSA make sure this is the case, and wouldn't this mean that some cleartext cannot be encrypted? Thanks,

  • 1
    $\begingroup$ dupe 1 Can RSA be used to encrypt p?. and the real dupe Does RSA work for any message M? $\endgroup$
    – kelalaka
    Oct 3 '20 at 15:17
  • 1
    $\begingroup$ @kelalaka . Yes the dupes answer my question. Thanks $\endgroup$ Oct 3 '20 at 15:29
  • $\begingroup$ @kelalaka . I have a question to the answer of you linked question. However, I do not have enough rep to comment about this there. Maybe you know this: If two distinct primes p,q both divide a number z, will their product also divide Z? $\endgroup$ Oct 3 '20 at 19:15
  • $\begingroup$ Of course, they will divide. One can prove it like if $p|z$ then there is a $k_p$ such that $z = p p_k$ and similarly $z = q q_k$. Now look at $p p_k = q q_k$. here you can conclude that $p|q_k$ since $p$ and $q$ are distinct. then write $q_k = p q_p$ then $z = p q q_p$. The rest is obvious... $\endgroup$
    – kelalaka
    Oct 3 '20 at 19:21
  • $\begingroup$ @kelalaka . I am not following why $p | q_k$. For this to be true $p_k/q$ would have to be an integer right? but how can you be sure this is the case? my apologies if this is trivial. $\endgroup$ Oct 3 '20 at 19:32

Browse other questions tagged or ask your own question.