1
$\begingroup$

Let's say that we have a classic RSA encryption, with n = p*q. For a given C, I saw on internet the RSA might be weak if we know that the plaintext M and n have a common factor. However, I wasn't able to find a proof of that.

We know that $M=C^e \space mod\;n$, with e being the public key. I tried to say that $M = a + k*n$, with a and k being positive integers, and to redo the algorithm. Therefore :

$C = M^e\;mod\;n = (a + k*n)^e\;mod\;n = a^e\;mod\;n$

And

$M = C^d\;mod\;n = a^{d*e}\;mod\;n$

However, this sounds useless, since we don't know a (even with brutal force, we would have to many values to compute if $n$ is big) and $d$, obviously since it's the private key. Does anyone can help me on this one?

$\endgroup$

1 Answer 1

3
$\begingroup$

For a given C, I saw on internet the RSA might be weak if we know that the plaintext M and n have a common factor. However, I wasn't able to find a proof of that.

It's quite simple; we know both $C$ and $n$; if $M$ has a common factor with $n$, so does $C$. So, we can just compute $\gcd(C, n)$. Since we know that $M$ and $n$ have a common factor, then this is not 1; we assume that $C < n$, so it's not $n$. Hence, that has to be a proper factor of $n$; if $n$ is a product of two primes, this will then be one of them, and so the two prime factors of $n$ are then $\gcd(C, n)$ and $n / \gcd(C, n)$.

Once we have the factorization of $n$ then (assuming we know the value $e$), computing $d$ is straight-forward.

$\endgroup$
2
  • $\begingroup$ @Marth83: better? $\endgroup$
    – poncho
    Commented Mar 23, 2022 at 14:43
  • $\begingroup$ Yes, that's what I was wondering, thanks! $\endgroup$
    – Marth83
    Commented Mar 23, 2022 at 14:48

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.