Score:1

Crypto

RSA Vulnerability when the Encrypted M is not coprime with N

Chen

7/4/23, 12:27 AM

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?

120

0 + 0

rsa

fgrieu

7/4/23, 7:00 AM

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$.

kelalaka

7/4/23, 7:57 PM

RSA is a trapdoor permutation. Does this imply you anything?

Score:3

Crypto

meshcollider

7/4/23, 12:46 AM

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.

0 + 0

Chen

7/4/23, 4:56 PM

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?

Chen

7/4/23, 5:23 PM

Would using OAEP on a C that is not coprime with N dissolve the issue?

fgrieu

7/4/23, 5:34 PM

@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$.

Chen

7/4/23, 5:48 PM

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?

Chen

7/4/23, 6:04 PM

and why would that be impossible? Would it be still possible with a probability of success of 1/p + 1/q?

meshcollider

7/4/23, 8:23 PM

@Chen it would be no different to an attacker just guessing random factors of $N$ :)

poncho

7/4/23, 9:17 PM

@Chen: for practical sized $p, q$, that is, $2^{-1024}$ or smaller, $1/p + 1/q$ is effectively "impossible"

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: RSA Vulnerability when the Encrypted M is not coprime with N

TH: ช่องโหว่ RSA เมื่อ M ที่เข้ารหัสไม่ได้อยู่ร่วมกับ N

RO: Vulnerabilitatea RSA atunci când M criptat nu este coprime cu N

RU: Уязвимость RSA, когда зашифрованное M не взаимно просто с N

VI: Lỗ hổng RSA khi M được mã hóa không đồng nguyên tố với N

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.