2
$\begingroup$

I was reading this question about generating primes for RSA keys. The answers point out that most implementations of of the algorithm use probabilistic prime-ness checking algorithms. The answer by @tylerl made the most sense to me:

That is, if the test uses a randomly-chosen value (the "witness") which serves as the basis for the test. If the test passes, then the number is probably prime, but possibly not. We can repeat the same test with a new "witness", and if the test passes again then we have increased our certainty. We can continue to re-test as many times as we want until we've reached the level of certainty that we need.

This (and the other answers) heavily imply that we're never actually 100% certain that the numbers we've chosen for a key are actually prime.

  • Do any implementations follow up the probabilistic prime checks with exhaustive checks? I'm guessing not, because RSA key generation has to be pretty fast (compared to the heat death of the universe) to be useful.

  • What "level of certainty" do we "need" for RSA keys?

  • Is this an actual downside? If a non-prime number is used in an RSA key, to what degree would the search space of a brute force attack be decreased?

    I'm torn on this, because as I understand it, a brute force attack relies on factoring the key, which is difficult for the length of numbers we've chosen. If we're 99.99...% certain a number is prime, then the most likely thing we've done is selected a number that's a product of two or more reasonably large primes. That would imply that the brute force attack is only a few orders of magnitude easier to conduct; according to some fancy math, the RSA algorithm has orders of magnitude to spare.

  • Are there better attacks that will succeed in much less time that could work by assuming one or both of the secret numbers are non-prime? Even if this is one-in-a-billion chance, if the attack is fast enough, it seems like its worth it.

Improve this question
$\endgroup$
6
  • $\begingroup$ Implementations definitely do not "follow up the probabilistic prime checks with exhaustive checks". $\:$ However, there might be implementations that "follow up the probabilistic prime checks with" $\hspace{.68 in}$ zero-error checks. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Jun 22, 2015 at 23:28
  • $\begingroup$ And, there are certainly implementations that use provable primality techniques, such as Shawe-Taylor $\endgroup$
    – poncho
    Commented Jun 22, 2015 at 23:58
  • $\begingroup$ @poncho : $\;\;\;$ I'm aware of this old result, which I believe is thoroughly obsoleted by the Bernstein paper I linked to in my previous comment. $\:$ Do you know of any other provable primality techniques such that [[the yielded [core public] and [core private] operations are always inverses of each other] and [provably, if RSA is secure then RSA-with-that-technique is secure] and [that technique's expected runtime is provably in $O\hspace{.02 in}(n^4\hspace{-0.05 in}\cdot \hspace{-0.04 in}polylog(n))$]]? $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Commented Jun 23, 2015 at 0:56
  • 1
    $\begingroup$ The question is very similar to this one. To summarize my answer: if it accidentally happened that we use a composite, most likely the RSA key pair would fail on first use (in a PKI: when the certification request is checked, thus thus wrong key would not get certified). Another option, so unlikely that the combination of bad luck and a hardware defect is not enough to cause it, is that it was picked a Charmichael number instead of a prime, in which case RSA will work. $\endgroup$
    – fgrieu ♦
    Commented Jun 23, 2015 at 4:39
  • 1
    $\begingroup$ Level of certainity? Chance of error should be $2^{-112}$ or less for 2048-bit RSA, $2^{-128}$ for 3072 and $2^{-256}$ for 15360-bit RSA. Is it a downside to use RSA with more than two primes? No, it's actually used and known as "multi-prime RSA", usually with 3-5 primes. And please note: The best known algorithm (the general number field sieve) doesn't work faster if the factors are smaller, it all depends on the size of the product... $\endgroup$
    – SEJPM
    Commented Jun 23, 2015 at 11:57

0

Reset to default