# How common are weak RSA keys?

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?

• 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)
– SEJPM
Mar 8 '16 at 21:18
• 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. Mar 9 '16 at 10:51

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.
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.