An example implementation can be found here.
The above method is effective only against RSA keys for which the choices made during the generation procedure were not truly random. Taking into consideration the significance of strong cryptographic keys it is important to verify that all keys were generated following the principle of true randomness .
Below you can download an application which finds all shared factors that may exist, given a finite set of moduli. The purpose of this application is to enable system administrators and everyone who needs to test his own RSA keys, to do so. The application computes the gcd to determine which moduli pairs share primes and then, based on the known primes, factors these moduli completely.
The source code can be downloaded here.
- The implementation is written in Python. As a result, the source code is in an easy to read and modify form and at the same time, the program performs well in terms of speed.
- Depending on the setup it can check up to 1 million moduli in about 4 hours. For larger sets of moduli please see the note* below.
- It can be used in all operating systems which support a Python interpreter and the computer-algebra system SageMath .
- An up-to-date Python version (2.6)
- The Python script requires an installation of SageMath. SageMath 4.8 e.g. uses Python 2.6.4.
- Only the moduli are supplied in the input for the Python script without any additional information. The file containing the moduli should have only one modulus (in HEX encoding) per line. You may find this shell script useful in order to extract the moduli from your certificates (in PEM format) and keep track of their corresponding origin files.
Installation and usage:
- Download and install SageMath if it is not already installed on your system.
- (Optional step) Using the shell script given above, extract the moduli from your certificates and save them to a file.
Run in the terminal:
Make sure that you have set permission (via chmod) for executing the shell script. The shell script will create two files in the local directory:
- The 'moduli' file which contains one modulus per line in HEX encoding.
- The 'filenames' file which contains the filename of a PEM file on each line. It can be used to backtrack the PEM files whose moduli share primes.
- Run in terminal:
sage –python sanitycheck.py -i <moduli file>
The Python script will load all moduli from the file, perform computations and in the end it will print all moduli which were successfully factored. For testing you can use this set of 10000 moduli. Optionally, you can also save the results in a report file, just by giving the report file name as a second argument:
sage –python sanitycheck.py -i <moduli file> -r <report file>
Additionally, the Python script can be given the 'filenames' file generated by the shell script in
step 2 and backtrack the PEM files corresponding to the moduli which share primes.
sage -python sanitycheck.py -i <moduli file> -f <filenames file>
- Check the list of moduli for duplicates
- Use an even more efficient algorithm
*Note: Besides the Python code, we also developed a C++ version which performs faster than the above Python version. This C++ code was developed as the code from  was not available in 2012 to the public. In case you want to check a large set (>1M) of moduli for shared primes and want to get this C++ code please contact us at:
Sources and References
 Arjen K. Lenstra et al., "Ron was wrong, Whit is right", Cryptology ePrint Archive Report 2012/064, February 2012, http://eprint.iacr.org/2012/064.
 Esslinger, Schneider, Simon: "RSA-Sicherheit in der Praxis", KES -- Zeitschrift für Informationssicherheit, April 2012, pp. 18 ff
 William A. Stein et al., Sage Mathematics Software (Version 4.8), The Sage Development Team, January 2012, http://www.sagemath.org
 Nadia Heninger et al., "Mining your P’s and Q’s: Detection of Widespread Weak Keys in Network Devices", in proceedings of the 21st USENIC Security Symposium, August 2012, https://factorable.net/weakkeys12.extended.pdf
 Christian Schlipp, Explanations to "Mining Your P’s and Q’s: Detection of Widespread Weak Keys in Network Devices", seminar thesis, February 2013
 Daniel J. Bernstein, Nadia Heninger, and Tanja Lange, "FactHacks: RSA factorization in the real world", slides to their talk at 29C3, December 2012, https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf. This explains attacks on RSA very well using SageMath in practice.