A paper I found (http://eprint.iacr.org/2012/064.pdf, which was submitted to a cryptography conference about two years ago), is based on the analysis of some 7.1 million 1024-bit RSA keys published online. By subjecting the modulus of each public key to an algorithm first postulated more than 2,000 years ago by the Greek mathematician Euclid, the researchers looked for underlying factors that were used more than once. Almost 27,000 of the keys they examined were cryptographically worthless because one of the factors used to generate them was used by at least one other key.

As these findings were related to 1024-bit RSA keys (and even those show some points of weakness), does it make sense to generally block all RSA keys under 1024 bits to enforce/strengthen used crypto?

  • $\begingroup$ Yes, but not for a reason completely unrelated to your first paragraph. $\;$ $\endgroup$
    – user991
    Commented Dec 11, 2013 at 5:22
  • 1
    $\begingroup$ @RickyDemer Meanwhile, I realized that too. ;) $\endgroup$
    – e-sushi
    Commented Dec 11, 2013 at 20:18

3 Answers 3


Yes, it does make sense to block them.

Seeing you've asked this question in July, it's funny to think you might have had some kind of unintentional foresight of what meanwhile has become reality.

Some hard facts:

  1. As raw computing power increases over time it becomes possible to factor or crack smaller sized RSA keys. Key sizes smaller than 1024 bits were voluntarily discontinued by Microsoft on 12 December, 2012.
  2. As a proactive measure, effective 31 December, 2013, the NATIONAL INSTITUTE OF STANDARDS and TECHNOLOGY [NIST] has recommended that 1024-bit RSA certificates be eliminated and replaced with 2048-bit or stronger keys.
  3. As a result of the NIST recommendation, the Certification Authority/ Browser (CA/B) Forum, created to develop best practices within the SSL/TLS industry, created a mandate to bring the 1024-bit RSA key size to end of life by December 31st, 2013.
  • 2
    $\begingroup$ 1024 bit key sizes have been known to be in the danger zone for much longer than last Juli. What's happening now is the enforcement instead of the recommendation to switch to larger key sizes (and to better hash algorithms as well) $\endgroup$
    – Maarten Bodewes
    Commented Dec 11, 2013 at 17:42

Those findings were based on a broken PRNG. A broken PRNG affects all keys generated on such a device, no matter the size or the algorithm.

Common primes were how the problem was detected, but the problem itself is unrelated to primes or RSA. If RSA keys of a specific size where affected, that's only incidental because that's what the broken devices generated.

Blocking keys smaller than 1024 bits can be a good idea, because their security margin against factoring attacks has grown pretty thin, even when they're correctly generated. But that threat isn't related to the paper you link.

  • $\begingroup$ Distinct keys with duplicate primes are a FAR FAR worse problem than mere duplicate keys. Duplicate keys mean that someone stealing the key from one device can use it to impersonate another, not good but they still have to work on stealing the key in the first place. Distinct keys that share one (but not both) primes can be trivially factored by gcd. $\endgroup$ Commented Jan 6, 2020 at 13:38

Hard to answer impartially, expect opinion-colored answers here.

The paper you are mentioning has essentially nothing to do with keysizes. Instead they show that bad use of randomness during RSA key generation may have major security impact. If so, why did they essentially find problems with 1024-bit key ? Well, mostly because they could collect much more 1024-bit keys and also to a certain extend because implementations that take the pain to use 2048-bit keys are probably written with more care.

Does this imply that blocking 1024-bit key would be a good idea ? May be not, but this would give some forward momentum to move away from 1024-bit keys (see How big an RSA key is considered secure today? for more about when they are expected to be really not enough).

We could even dream that people would move away from RSA and go for elliptic-curve.


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.