1
$\begingroup$

I have tested out with a few test cases, it seemed like the ciphertext $M^e$ of RSA is always coprime with N when e=3. Is there a reason why? What would happen if the ciphertext $M^e$ is not coprime with M when e=3?

$\endgroup$
2
  • 3
    $\begingroup$ When $(N,e)$ is a valid RSA public key with $N$ the product of two distinct secret primes $p$ and $q$, there's probability about $1/p+1/q$ that a random message $M$ is such that $M^e$ is not coprime with $N$. Since both $p$ and $q$ must be large (hundreds of decimal digits) for RSA to be secure, that probability is entirely negligible in actual use of RSA. The question is considering something that in actual use won't occur for random or pseudorandom $M$, or for $M\in[1,N)$ chosen by one not knowing (nor able to find) the factorization of $N$. $\endgroup$
    – fgrieu
    Mar 4, 2022 at 7:00
  • $\begingroup$ RSA is a trapdoor permutation. Does this imply you anything? $\endgroup$
    – kelalaka
    Mar 4, 2022 at 19:57

1 Answer 1

3
$\begingroup$

When $N = pq$ is the product of two primes, the only numbers which aren't coprime to $N$ are those that contain either $p$ or $q$ as a factor. It is certainly possible to have $M^3$ divisible by either $p$ or $q$ so your observation is not true in general. An example:

$$ M = 42\\ N = 7*13 = 91\\ M^3 \equiv 14 \pmod{91} $$ Clearly 14 and 91 are not coprime - they both share $7$ as a factor. Computing the GCD of $c = M^3$ and $N$ thus leaks $7$ as a factor of $N$, breaking RSA.

$\endgroup$
7
  • $\begingroup$ Ok, I did not think of this. In that case, it is a severe security vulnerability, since by taking the GCD of the ciphertext(C) and N leaks p or q? $\endgroup$
    – Chen
    Mar 4, 2022 at 16:56
  • $\begingroup$ Would using OAEP on a C that is not coprime with N dissolve the issue? $\endgroup$
    – Chen
    Mar 4, 2022 at 17:23
  • $\begingroup$ @Chen: I don't get what you means by "using OAEP on C"; but using OAEP to produce the input $M$ for raw RSA encryption $M\mapsto C=M^e\bmod N$ for otherwise secure $N$ is practically certain to "dissolve the issue", if there was one. Now we can safely encipher multiples of $p$ or $q$. Again, even when not using OAEP, there is no practical issue, because choosing $M$ or $C$ in $[1,n)$ with $\gcd(C,N)\ne1$ is impossible for one not knowing (nor able to find) the factorization of $N$. $\endgroup$
    – fgrieu
    Mar 4, 2022 at 17:34
  • $\begingroup$ Sorry, I meant to use OAEP on M. Do you mean that to chose a M that gives $gcd(C,N)≠1$ on purpose is impossible without knowing p and q? $\endgroup$
    – Chen
    Mar 4, 2022 at 17:48
  • $\begingroup$ and why would that be impossible? Would it be still possible with a probability of success of 1/p + 1/q? $\endgroup$
    – Chen
    Mar 4, 2022 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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