4
$\begingroup$

There exist certain attacks that can be used against RSA keys whose prime factors are of specific forms, such as one by Coppersmith.

How common are these RSA keys? If you generate primes randomly, is there a realistic risk of choosing a weak prime number? Does this risk, if realistic, vanish if you always choose $p$ and $q$ to be safe primes?

$\endgroup$
  • 1
    $\begingroup$ To cite the HAC (chaper 4.4.2: strong primes): "it is now believed that strong primes offer little protection beyond that offered by random primes, since randomly selected primes [...] will satisfy the constraints with high probability." Additionally it is said that you should use strong primes anyways as the induced overhead is minimal (~20% longer generation) $\endgroup$ – SEJPM Mar 8 '16 at 21:18
  • 1
    $\begingroup$ I'd say that issues with the random number generator are the main cause of concern and possibly unbalanced $p$ and $q$ after that. I don't think the primality test is too much of an issue in real life. $\endgroup$ – Maarten Bodewes Mar 9 '16 at 10:51
2
$\begingroup$

For Coppersmith's method to work on $n = p\cdot q$, you need to know $\frac{1}{4}\log n$ bits of $p$. It would take an amazingly badly botched random number generator in your key generation procedure to reveal that to an adversary. There have been two high-profile cases of this: low-quality hardware RNGs Taiwan's national identity smart cards in 2013 (summary), and the ROCA vulnerability in Infineon's RSALib library for smart cards in 2017.

Unless you are trying to use the cheapest possible hardware RNG (as seems to be the case with Taiwan's national identity cards), or trying to be clever about generating keys as efficiently as possible (as seems to be the case with ROCA), you don't have to worry about Coppersmith's attack. There are various ways to generate RSA moduli, and they're all basically fine except insofar as they are distinguishable from one another and enable fingerprinting of RSA key generation procedures.

Safe primes, i.e. primes of the form $p = 2q + 1$ for prime $q$, are not really relevant to RSA. Strong primes, which are similar but with a few more criteria, were once suggested to be relevant but no longer—the costs of the attacks that they thwarted are much higher than the costs of the best modern attacks on >=1024-bit moduli. None of these attacks—from the old Pollard's $p - 1$ or William's $p + 1$ to the modern elliptic curve method or general number field sieve—are related to Coppersmith's method, which is about known fixed bits in the factors.

$\endgroup$
0
$\begingroup$

According to research done primarily in the early 2010s, these authors found that in their "collection of 11.4 million RSA moduli 26965 are vulnerable, including ten 2048-bit ones." Continually, "over the data [they] collected 1024-bit RSA provides 99.8% security at best."

To counter the use of potentially insecure RSA keys, researchers suggest to use 2048-bit keys.

$\endgroup$
  • 2
    $\begingroup$ The two papers you cited are unrelated to the question. They are mostly about primes shared between moduli, which can be recovered from batch GCD computations, and to a lesser extent about low-entropy seeds for key generation procedures. Using 2048-bit keys doesn't help with either of these disastrous failures of key generation. It also doesn't address the case that Coppersmith's attack using lattice reduction addresses, when a small fraction of the bits of one of the factors are known, no matter what the size of the modulus is. $\endgroup$ – Squeamish Ossifrage May 3 '18 at 2:20

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.