Why has the message $P$ to be relative prime to $n$ in RSA encryption?

This should be fault? \begin{align} C &\equiv P^e \pmod{n} \\ &\equiv 101112^{11111357} \pmod{9998000099} \\ &\equiv 3316546434 \pmod{9998000099} \end{align}

  • $\begingroup$ Please do not use pictures for critical portions of your post. Pictures may not be legible, cannot be searched and are not view-able to some, such as those who use screen readers. I have edited your question to reflect this principle. It is possible that I unintentionally changed the meaning of your question. Please proofread the question to ensure this has not happened. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 19 '18 at 17:23
  • 1
    $\begingroup$ There is no need for the message to be relatively prime to the modulus in RSA. Why do you think this? $\endgroup$ – Matthew Towers Jan 19 '18 at 18:11

$P$ can be any number $< n$, encryption will work. It will produce a valid ciphertext for which decryption still works.

It's also a very small probability (for realistically sized $n$) that this would happen anyway. If anyone were to randomly generate some $P$ and notice that the gcd of $P$ and $n$ was not $1$, that person would have factored $n$ and broken this RSA-instance.

Your example does have gcd of $P$ and $n$ equal to $1$.


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.