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

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

$\endgroup$
  • 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 Apr 8 '18 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 Apr 8 '18 at 16:51

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.