1
$\begingroup$

If I have a 2048 bit value used as the modulus for an RSA exchange, and OpenSSL's BN_is_prime() has determined that that value is not a prime, does that mean that OpenSSL has found a strong Rabin-Miller witness? If so, if we could get OpenSSL to output the witness(es), how might that help us in the factorization of the value?

$\endgroup$
7
  • $\begingroup$ Do you really mean Diffie-Hellman (which typically doesn't use specifically 'semiprime' values)? Or, do you mean RSA? $\endgroup$ – poncho Jan 17 '17 at 23:45
  • $\begingroup$ I have updated the question to explicitly state RSA and remove the assertion that the key is semiprime. I only know that OpenSSL's primality test says that the key is not a prime. $\endgroup$ – namreeb Jan 18 '17 at 0:16
  • $\begingroup$ If you could factor integers that way, don't you think this would make factorization an easy problem? $\endgroup$ – Thomas Jan 18 '17 at 0:20
  • $\begingroup$ I suppose it depends on your definition of 'easy'. If you mean trivially easy, I'd be surprised if that were the case. If you are being intentionally vague, then you're really just restating my question. I want to know if having identified MR witnesses makes factorization easier by any non-trivial amount, and if so, how. $\endgroup$ – namreeb Jan 18 '17 at 0:23
  • $\begingroup$ OpenSSL routinely makes Rabin-Miller tests on the factors of RSA keys that it generates; but for factors that end up used, these tests never conclude that the factor is composite. Are you asserting that OpenSSL makes Rabin-Miller tests on an RSA public modulus? If yes, what's the justification or source? $\endgroup$ – fgrieu Jan 18 '17 at 11:26
2
$\begingroup$

does that mean that OpenSSL has found a strong Rabin-Miller witness?

Yes, it does.

if we could get OpenSSL to output the witness(es), how might that help us in the factorization of the value?

No, it wouldn't help; for most composite numbers, the vast majority of values are Rabin-Miller witnesses (it's provable that at least $\frac{3}{4}$ always are, but for most composites, the ratio is very close to 1). By far the most frequent for the Rabin-Miller to claim compositeness is that the random value $x$ is a value for which $x^{n-1} \ne 1 \bmod n$ (and so you never hit a 1 or a -1 in the sequence); such a value $x$ proves that $n$ is not prime, but gives no indication of the factorization of $n$. Now, if you found an $x$ for which you fail for the other reason; because Rabin-Miller hit a 1 without hitting a -1 first, such an $x$ would immediately yield a factorization. However, such values of $x$ occur only extremely rarely in practice.

$\endgroup$

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.