13
$\begingroup$

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.

$\endgroup$
2
  • 10
    $\begingroup$ What is the statement you want to precisely prove/verify? Put differently, what is the definition of a valid key in your context? Do you want to check that the modulus is a semiprime? Or you just want to check that the modulus is absent of known vulnerabilities? I believe there are many vulnerabilities that you can check just by given the public modulus, for instance you can check whether a modulus is susceptible to the ROCA attack, see it here: github.com/crocs-muni/roca $\endgroup$ Sep 21, 2022 at 13:37
  • $\begingroup$ In principle I would consider any key that performs as it should in the RSA cryptosystem a valid key. That said, you make an interesting point: any tests that can be performed that indicate a vulnerable system could be considered as well. $\endgroup$
    – Maarten Bodewes
    Sep 21, 2022 at 15:13

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is there a CLI tool to do this? I feel tempted to write one if not… $\endgroup$
    – l0b0
    Sep 29, 2022 at 10:46
  • $\begingroup$ @l0b0: no, I know no public domain tool for this. I do have a Mathematica script along these lines that I once made to filter invalid entries in a database of public keys. It does all that I described, with a larger $a$, some Pollard's rho and Fermat factoring on top of that. [update: and IIRC, tests 1 to 6 was all that triggered rejection in practice]. $\endgroup$
    – fgrieu
    Sep 30, 2022 at 5:50
  • $\begingroup$ I'm no Mathematica expert, but if you make that code public I'm sure someone will be interested in making a FLOSS tool for it. $\endgroup$
    – l0b0
    Sep 30, 2022 at 7:48
6
$\begingroup$

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'

$\endgroup$

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.