How to Check Strength of RSA Public Private Key

Question

How to measure strength of RSA public private key pair. is it enough to only measure the length of primes used to generate N? how to check that primes p,q used to make N were selected truly randomly from a given RSA public private key pair data? Any reliable method of generating public private key pairs and certificates which uses good randomness to for selecting p and q?

Answer 1

RSA public/private key pairs are no exception: there is no way to assess that a cryptographic key is strong by looking at its value; only ways to assess that it is weak. And lack of signs that it is weak is no good indication that it is strong. Arguments are extensions of:

A key which value leaked is totally weak, and has exactly the same value as before it leaked; hence examining the key's value can not demonstrate that the key is strong, or provide a solid indication about that.

Extension: a key that was generated by a strong method from the output of a public Cryptographically Strong Pseudo Random Number Generator which seed was chosen in an undisclosed way, is weak and indistinguishable (by definition of Cryptographically Strong) from one generated similarly except from a truly random seed, which is strong.

It is even hard to conclude that an RSA key is weak by looking at its value (except in extreme cases, like a short public modulus, or when all but one of its prime factors can be compressed into a very small amount of information); in particular, tests concluding that an RSA key does not meet criteria expected for conventionally generated RSA keys are no proof that it is weak: an RSA key can still be strong if it has regular patterns in half the high-order bit of the public modulus $N=p\,q$, or/and some of the high-order bits of $p$ and $q$; or a private exponent $d$ significantly smaller than $N$.

---

So what can be done? Basically, have the key generation process competently audited. By extension, the audit should also cover how the key is kept secret, including during use.

One common modern referential for RSA key generation is NIST's FIPS 186-4, section 5 and references including Appendix B.3 (with some origins in ANS X9.31:1988); but that has limitations:

• FIPS 186-4 formally allows only for 1024-bit, 2048-bit, or 3072-bit public modulus; the former is obsolete, and 4096-bit or even more is increasingly common, for reasons that are at least understandable.
• FIPs 186-4 requires public exponents $e>2^{16}$ and public moduli with two primes factors, when sometime performance considerations dictate otherwise (the public key function is up to about 8 times faster with $e=3$ than with $e=65537$; for constant modulus size the private key function is up to nearly $k^2/4$ times faster in software when there are $k$ factors, and using available hardware support might require $k\ge3$).
• FIPS 186-4 does not give prescriptions for a random generator complete with entropy source and testing procedures; it is thus perfectly feasible that an intentionally weakened random number generator makes an implementation honestly certified compliant to FIPS 186-4 vulnerable selectively to those in the know.
• FIPS 186-4 has 5 methods (B.3.2 to B.3.6), and choice can be a burden; they vary according to several criteria
  • Use of any RNG (possibly non-deterministic), or of a PRNG with seed of precisely twice as many bits as the conventional security strength of the key prescribed by SP 800-57 Part 1;
  • Use, or not, of auxiliary conditions on the primes generated (being $p$ such that $p-1$ and $p+1$ each have a large auxiliary prime factor); notably, that complication is mandated for 1024-bit moduli, and thus unavoidable for conformant implementations that need backward compatibility. That contributes to the significant difficulty of making a marketable truly FIPS 186-4 implementation for constrained environments such as Smart Cards.
  • Use of probable or provable primes, for the factors of the public moduli or/and the auxiliary primes.
• The precision of FIPS 186-4 is a double-edged sword: that makes it feasible to automatically prove non-conformance without false positives; but that makes it feasible to exploit a conformant FIPS 186-4 implementation using a known rigged RNG without knowing the details of the implementation.
• FIPS 186-4 is totally lacking about protection against side-channel leakage and fault attacks, including during key generation, even thought that conceivably can matter in some cases (e.g. Smart Cards supposed to securely generate a key on the field).

A less common referential is ETSI TS 102 176-1 V2.0.0 (2007-11), which pays its simplicity at the price of vagueness:

To generate the key pair two prime numbers, $p$ and $q$, are generated randomly and independently, satisfying the following requirements:

• the bit length of the modulus $n\;=\;p\,q\;$ must be at least MinModLen; its length is also referred to as ModLen;
  
• $p$ and $q$ should have roughly the same length, e.g. set a range such as $0,1 < | \log_2p - \log_2q | < 30$;
  
• the set of primes from which $p$ and $q$ are (randomly and independently) selected SHALL be sufficiently large and reasonably uniformly distributed.

Notice the use of e.g. in the second bullet; and that the bounds then proposed are extremely different from those of FIPS 186-4, are not met for about 1/3 of keys generated according to FIPS 186-4, and often lead to private keys that can not be moved to many implementations designed for FIPS 186-4.