# Given only RSA public key parameters, what security issues might I be able to detect?

I'm attempting to automate some checks against a large list of .NET assemblies, and want to include a test to see if the RSA parameters used to sign the assemblies are sensible. However, since I don't have access to their private keys, I'm wondering how far I can go.

At the moment I'm reporting if:

• The modulus $n$ is smaller than 1024 bits (issue)
• The exponent $e$ is not 65537 (informational)

The latter is reported due to it being unusual, rather than a flaw in the cryptography, as I've never come across a case where a signed .NET binary uses anything other than 65537.

Are there any other checks I can perform, given only this limited data?

• Even though it's strictly not what you are asking for, you might be interested in this paper. – yyyyyyy Mar 16 '15 at 15:35
• @yyyyyyy I was wondering whether somebody might mention shared factors and other such things. I don't know of any that have affected .NET compilers / IDEs, but I'd be interested to know if anyone has heard of such a thing (either in Microsoft .NET, Mono, or another implementation). – Polynomial Mar 16 '15 at 15:48
• @yyyyyyy: the paper you mentionned is related to a batch of RSA parameters that are generated using a poor pseudo-random generator. Here the question is somewhat different as it address how to detect structural flaw on a given key which has been used to sign a given data. I am tempted to answer not much less to check whether if the secret modulus factors aren't close to each other (Dividing by successive integers close to $sqrt{N}$ . – Robert NACIRI Mar 16 '15 at 22:37

The tests you can do depend on how much time you want to spend for checking each certificate and the "stupidity" you assume for the given key-owner.

You already mentioned the basic checks:

• Modulus is too small, only interesting if it's smaller than 1024 bits
• Exponent is unusual, not exactly a vulnerability in most cases

The following attacks may take more or less time but applying each of them will give you high assurances that the parameters are indeed not vulnerable. This can be read as a list of techniques for factoring given moduli.

The following techniques are rather fast and may be applied to each modulus.

• Check for GCD > 1 with a given database. For example get a database of many certificates and apply the GCD algorithm to each pair, if the GCD is larger than 1 you've found a non-trivial factor.
• Check for the Debian RNG vulnerability. Although the vulnerability is quite old you might get "lucky" and find a vulnerable key.
• Check if the modulus is a perfect power. This is highly unlikely but can be verified extremely fast, as proposed by Ricky Demer in the comments.
• Check if the modulus is a prime, for example using the Miller-Rabin test. If it is a prime it's obviously an invalid modulus, making it possible although unlikely.
• Check if $|p-q|$ is small. If so the Fermat factoring (or more advanced version) will quickly factor the modulus. This is highly unlikely as well.

The last few techniques are rather slow and may not be applicable in the given setting due to time constraints.

• If you suspect the modulus to contain a few large (128-bit) primes you can try and apply the elliptic curve method. This is rather unusual for RSA moduli.
• If you suspect that the modulus isn't composed of safe primes you may want to give Pollard's p-1 and Williams p+1 algorithm a try.
• If you suspect the private exponent to be small you can try to apply Wiener's attack.
• One could also run these two algorithms on the modulus. $\;$ – user991 Jul 11 '15 at 19:18
• @RickyDemer, I've added those to the answer (along with Fermat factoring). Thank you for the suggestions. – SEJPM Jul 11 '15 at 19:24