0
$\begingroup$

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,

$\endgroup$
8
  • 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, 2020 at 15:17
  • 1
    $\begingroup$ @kelalaka . Yes the dupes answer my question. Thanks $\endgroup$ Oct 3, 2020 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, 2020 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, 2020 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, 2020 at 19:32

0

Browse other questions tagged or ask your own question.