6
$\begingroup$

In the RSA algorithm, if an attacker wants to get $d$, the attacker does this simply by encrypting random messages $m < N$.

If the attacker finds a message $m_1$ that the attacker can not encrypt since $\gcd(N ,m_1) \neq 1$, does this help the attacker in any way in any way?

I don't know why the $\gcd(m,N)$ has to be $1$. What happens if $\gcd(m,N) \neq 1$?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
12
$\begingroup$

What happens if $\gcd(m,N) \neq 1$?

Actually, RSA works just fine; we have $((m^e)^d) \equiv m \pmod N$ in all cases, includes ones which $m$ and $N$ are not relatively prime.

What is an issue is if someone notices that $\gcd(m, N) \neq 1$. If that is the case (and $m \ne 0$), then $\gcd(m, N)$ is a nontrivial factor of $N$, that is, either $p$ and $q$, and so that rather leaks the factorization of $N$.

Now, the probability of guessing $m$ that is not relatively prime to $N$ is astronomically small for the sizes of $N$ we use in practice, and so we don't worry about it.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Addition: In Rivest, Shamir, and Adleman's work as of April 1977 (references), the proof required $\gcd(m,N)\neq1$. And, including in the published paper, $p$ and $q$ are large random primes but not explicitly distinct (nor explicitly independent). If we allow $p=q$ (modern expositions of RSA do not), $\gcd(m,N)\neq1$ is required for reversible encryption. That condition also ensures reversible encryption in some variants of RSA that have been investigated, including $N=p^2\cdot q$. $\endgroup$
    – fgrieu ♦
    Commented Apr 8, 2018 at 12:35
  • $\begingroup$ @fgrieu: as for the original proof of RSA, well, people have since created sharper proofs that hold in general. As for nonsquare free varients of RSA, I consider them exactly that, varients, and not the original RSA. $\endgroup$
    – poncho
    Commented Apr 8, 2018 at 16:51

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.