Join Log in
Score:7
avatar Crypto

Has there ever been any real world consequences of using probabilistic primality tests for RSA or other similar systems?

et flag
user93353

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

872
2 + 5
rsa
Eugene Styer avatar
dz flag
Eugene Styer
Related: https://crypto.stackexchange.com/questions/13083/rsa-with-composite-numbers
1
Reply
Fractalice avatar
in flag
Fractalice
You also need to multiply that by the probability of hitting a Carmichael number first, which is very very low on itself.
1
Reply
cn flag
j.p.
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.
1
Reply
br flag
Barmar
And then you have to multiply by the probability that someone is trying to crack the communication of someone with the compromisable certificates.
1
Reply
John Coleman avatar
jp flag
John Coleman
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.
1
Reply
Score:15
avatar Crypto
us flag
Mikero

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.

0 + 0
Score:3
Ievgeni avatar Crypto
cn flag
Ievgeni

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 smaller key (RSA$-512$):

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

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.