7
$\begingroup$

I started reading the book Cryptanalysis of RSA and its variants by M. Jason Hinek and I stumbled upon a phrase that intrigued me:

plaintext messages that are relatively prime to the modulus (i.e., $gcd(m, N) > 1$) should be avoided, since their ciphertexts $c = m^e\; mod \; N$ reveal the factorization of the modulus.

Firstly, if $m$ is relatively prime to $N$, shouldn't $gcd(m, N) = 1$?

Secondly, how is it possible to extract the factorization of $N$ by choosing a bad message $m$?

$\endgroup$
  • 2
    $\begingroup$ This may be a typo in the book (or your quote)? (-> "plaintext messages that are not relatively prime to the modulus (i.e. $\gcd(m,N)>1$)...") $\endgroup$ – SEJPM Jul 23 '16 at 11:56
  • 1
    $\begingroup$ I don't get this argument though; sure, an adversary might just happen to notice that $m^e$ is not relatively prime to $N$, and hence factor $N$. But it's equally likely they would notice, say $(m + s)^e$ is not relatively prime to $N$, for any particular $s$; by that line of reasoning, any input message is unsafe. $\endgroup$ – Thomas Jul 23 '16 at 14:11
  • 1
    $\begingroup$ It's possible to reveal the factorization of a semi-prime by publishing a factor. Surprise, surprise. $\endgroup$ – CodesInChaos Jul 23 '16 at 15:10
  • 3
    $\begingroup$ The wording is strange because you do not usually have to avoid picking bad messages. Accidentally picking an $m$ that is not co-prime to $N$ is equivalent to just randomly guessing one of the factors, which is exceedingly unlikely for properly sized moduli. The only thing I can think of is if you, for some strange reason, decide that you want to purposefully encrypt one of the prime factors of $N$ as part of a protocol. That is a bad idea and should definitely be avoided. $\endgroup$ – Travis Mayberry Jul 24 '16 at 2:06
2
$\begingroup$

Firstly, it's not co-prime to the modulus, so $\gcd(m,N)$ would be greater than $1$.

Secondly, $N$ is the product of two (and only two) prime numbers $p$ and $q$, so if $\gcd(m,N)>1$, then you know $m$ is one of the factors (and prime factors) of $N$.

$\endgroup$
  • 1
    $\begingroup$ ... and $N/m$ would be the other one respectively... $\endgroup$ – SEJPM Jul 23 '16 at 11:59
2
$\begingroup$

If you choose m such that gcd(m,N) #1, it implies that gcd(m,N)= p, one of the primes composing N, and in this case the code is broken. But you could always choose random numbers r, and calculate gcd(r,N), looking for the case its not equal 1. This is equivalent to factor N, and there are algorithms more efficient than this that factor N. On the contrary, if you can choose what to encrypt, you may check gcd(m,N) before sending and than change m if its not 1.

$\endgroup$
  • $\begingroup$ However, I should add that to the best of my knowledge, this test (of gcd(m,N)) is not part of the signature or public encryption standards, probably because the probability of such coincidence is very low. $\endgroup$ – Evgeni Vaknin Jul 27 '16 at 18:58
  • $\begingroup$ The probability of it happening by chance is indeed so low that in most cases there is no need to verify it. Also if a party who didn't poses the private key were to do that verification and it happened to fail, it would mean the key at that point had already been broken. The case where you need to consider the risk is if you are designing something which will manipulate the private key material. It means don't do things like calculating a signature of one of your primes without a hashing step. $\endgroup$ – kasperd Dec 2 '17 at 0:46

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.