Validating an RSA public key

Question

What kind of tests can be performed on a public key to check if it is likely a valid key? The tests should be relatively fast - i.e. not computationally intensive - and not include modular exponentiation.

I'm asking this question as developers generally work (or should work) on the principle of fail fast, in which an error is thrown as soon as it can be detected.

As an example I could indicate that the public key should not include negative integers for the modulus and public exponent. Please assume that the RSA public key consists of two integer values; encoding related problems should be ignored.

Answer 1

Given a pair of integers $(n,e)$, we can quickly decide that it is not a valid RSA key (mathematically, or in the sense of conforming to the de-facto standard PKCS#1, or in the sense of providing practical security) if any of the following holds (and we should stop on the first one):

1. $e$ is even.
2. $n$ is even (technically, textbook RSA works with even $n$, but then the parity of the plaintext trivially is the parity of the ciphertext, and that's so bad it's not considered RSA).
3. $e<3$
4. $n<\ell$, for some limit $\ell$ which depends on the security context:
   • $n<15$ is not worth the name of RSA key.
   • I've never seen any $n<2^{320}$ used in a production context (since 1983, when I started monitoring the field), but $n<2^{321}$ bit was still used in the early 2000s. $n<2^{511}$ was then insecure, and no longer much used in new applications.
   • By 2022: $n<2^{639}$ provides very little security, it's been publicly shown $n<2^{829}$ is insecure, and perhaps $n<2^{1024}$ is insecure w.r.t. state-level attackers. In practice, $n<2^{1023}$ is no longer used even in low-security application AFAIK, and $n<2^{2047}$ is no longer recommended in new applications.
   • In addition, some security standards require $n$ to be in a precise set; e.g. FIPS 186-4, taken to the letter, requires $n\in[2^{1023},2^{1024}]\cup[2^{2047},2^{2048}]\cup[2^{3071},2^{3072}]$.
5. $e\ge n$ (since that's a non-conformance to PKCS#1). If interoperability with old implementations matters, this can be changed to $e\ge2^{32}$ (or $e\ge2^{256}$ for FIPS 186-4). But larger $e$ are mathematically OK ($e=n$ is always mathematically OK, and was proposed by Clifford Cocks even before the publication of RSA, see reference 2s there).
6. It was used $\ell\ge2^{128}$ or so in test 4 (meaning we care even so little about security), and $\gcd(n,a)\ne1$ for the highest convenient fixed constant $a$ member of A070826, like $a=3710369067405<2^{32}$ (product of the first $11$ odd primes) or $a=16294579238595022365<2^{64}$ (product of the first $15$ odd primes). This finds small factors in $n$ with a single scan of the full $n$, to compute $n'=n\bmod a$.
7. $n$ is a square (which makes textbook RSA irreversible for some plaintexts, and makes $n$ easy to factor). A standard method to performs this test is in FIPS 186-4 appendix C.4. But we can use this as a last resort only. Having ascertained by test 2 that $n$ is odd, $n$ can only be a square if $n\bmod8=1$, that is the three low-order bits of $n$ are 001. Now assuming they are: if and when it's found some odd prime $r$ with $\left(\frac rn\right)=-1$ (that's the Jacobi symbol), $n$ can't be a square. Each additional $r$ tested has near 50% chance of demonstrating non-squareness for non-pathological generation of $n$. Further, if we computed $n'=n\bmod a$ in test 6, we can use $n'$ to run this $\left(\frac rn\right)=-1$ test for the primes $r$ dividing $a$ without scanning $n$ again, extremely quickly. This makes the relatively costly full-blown squareness test rarely necessary.

Note: It would be possible to test for divisibility by more small primes than stated in 6; perhaps, test $\gcd(n,e)\ne1$; and/or, depending on the interpretation of "not include modular exponentiation", some level of Pollard's rho or other factoring method might be an option; but for either of these, we are hit by diminishing returns. Also, it would make sense to test that $n$ is not prime (which would make RSA insecure), but that seems to require some form of modular exponentiation.

Answer 2

Well, for $e$, you can certainly test if $e$ is an odd number greater than 1; any such $e$ is a possible public exponent, and and it is infeasible to determine if $\gcd( e, \phi(n)) > 1$, and so that's the best we can do.

As for $n$, you can certainly make sure that it's a large (for your definition of large, say, at least 2048 bits) odd number.

Other than those trivial tests, the tests become more expensive and are less likely to catch bad moduli.

You could further check for small factors, for example, compute $n \bmod (3*5*7*11*13*17*19*23*29)$ (if you have a 32 bit CPU; a few more small primes if you have 64 bit mod instructions), and make sure that's relatively prime to $3*5*7*11*13*17*19*23*29$; that shouldn't be that bad; for a 2048 bit value, that can be done with 64 $64 \times 32 \rightarrow 32$ bit mod operations (and would catch it about half the time if someone just sent you a random odd number).

You could do some further tests (say, a few hundred iterations of Monte Carlo factorization to search for somewhat larger small facrors or testing it for primality); however that's starting to get away from the idea of a 'quick test'