9
$\begingroup$

Considering the huge amount of RSA certs which have been generated, wouldn't there probably be a small number of certs where one of the primes which may have actually been a composite? Has this ever been a problem in the wild?

I think RSA with such a p & q will fail signature verification & decryption. So in these cases, I don't think the tools would give a proper error message & this may lead to a major confusion.

And if the composite number is in fact a Carmichael number, then I think RSA would work as intended, but would be less secure than it was intended to be.

I know what with enough rounds of the Miller-Rabin algorithm, the probability of something like happening is very small. But I am just wondering if it has happened & been detected

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Related: crypto.stackexchange.com/questions/13083/… $\endgroup$
    – Eugene Styer
    Commented Jul 2, 2021 at 16:17
  • 1
    $\begingroup$ You also need to multiply that by the probability of hitting a Carmichael number first, which is very very low on itself. $\endgroup$
    – Fractalice
    Commented Jul 2, 2021 at 18:05
  • 1
    $\begingroup$ Usually the number of Miller-Rabin tests is set such that the error probability is provably below $2^{-80}$ (or even smaller), but the real error probability is likely much smaller than what one can prove. $\endgroup$
    – j.p.
    Commented Jul 3, 2021 at 8:13
  • 1
    $\begingroup$ And then you have to multiply by the probability that someone is trying to crack the communication of someone with the compromisable certificates. $\endgroup$
    – Barmar
    Commented Jul 3, 2021 at 17:29
  • 1
    $\begingroup$ PGP got by with something much weaker than Miller-Rabin (just the Fermat test with 2,3,5,7). I don't think that this ever led to any practical problem. You can fool such tests, but doing so by chance is very, very unlikely. $\endgroup$
    – John Coleman
    Commented Jul 4, 2021 at 11:48

2 Answers 2

Reset to default
17
$\begingroup$

The probability of accidentally mistaking a composite for a prime, for a number that you chose yourself, is extremely low and quantifiable, as others have mentioned. This is the situation that is considered in the standard analysis of randomized primality tests.

However, there is also a problem of someone maliciously generating a composite that primality tests will mistake as a prime. This can happen with much higher probability. The paper Prime and Prejudice by Albrecht, Massimo, Paterson, and Somorovsky shows how to do such a thing. In particular, they show how to construct a 2048-bit composite that OpenSSL mistakes as prime with probability 1/16, even when ostensibly configured to detect primes with error $2^{-80}$. The paper also describes some problematic consequences of being able to generate composites of this form.

As far as I know, mainstream primality tests in crypto libraries have been fixed in response to this paper.

Improve this answer
$\endgroup$
5
$\begingroup$

I think, it's important to look what is "very small" here:

In this paper (example 6), it's written that for RSA$-2048$ that the probability a false-positive happens is upper bounded by $\frac{1}{10^{80}}$.

I've made the computation with Wolfram Alpha for a smaller key (RSA$-512$):

It's upper bounded by $2^{-73}$, thus it seems also negligible for real-world use-case.

Improve this answer
$\endgroup$

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.