Thursday, May 24, 2012

Testing RSA moduli for shared prime factors

General News

Last updated on Friday, August 21, 2020

The RSA algorithm for public-key cryptography is based on the presumed difficulty of factoring large bi-prime integers, the factoring problem. However, as pointed out in Lenstra et al 1 it is possible, given a set of moduli, to factor some of them by finding shared primes. This way the factoring problem is bypassed using a simple greatest common divisor (gcd) operation. A fast example implementation can be found below.

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 2.

Below you can download an application in Python 3 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 application was improved in 2020 and has now the name 'sanitychecker_v2.py'.

The zipped source code together with some test cases can be downloaded here.

 

Key points

  • 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 the Python script can check up to 1 million moduli in about 4 hours. For larger sets of moduli please see the note* below.

  • The Python script needs as input only the list of moduli without any additional information. This input file must have one modulus (in HEX encoding) per line. You may find the auxiliary shell script moduli_extract.sh useful, which is also in the zipped source code file. This shell script extracts the moduli from your certificates (in PEM format) using openssl and keeps track of their corresponding original files.

  • The Python script can be used in all operating systems which support a Python interpreter and the computer-algebra system SageMath 3.

 

Requirements

  • Python version 3.6 or higher
  • SageMath version 9.0 or higher (required by the Python script)

 

Installation and usage

  1. Download and install SageMath if it is not already installed on your system.

  2. (Optional step) Using the shell script given above, extract the moduli from your certificates and save them to a 'moduli' file.

    To do so, run in a terminal: ./moduli_extract.sh <path to the directory with the pem files>

    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.

  3. Run in a terminal: sage -python3 sanitychecker_v2.py -i <moduli file>

    The Python script loads all moduli from the file, performs computations and in the end it prints all moduli which were successfully factored. For testing you can use the sample set of 10000 moduli also contained in the zipped source code file.

    Optionally, you can also save the results in a report file, just by giving the report file name as another argument:

    sage -python3 sanitychecker_v2.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 -python3 sanitychecker_v2.py -i <moduli file> -f <filenames file>

  4. Further hints using this Python script to find weak moduli with shared primes:

    • The list of moduli is checked for duplicates.
    • With the option -d the moduli can also be delivered as decimal values.
    • Compared to version 1 a more efficient algorithm utilizes several cores in parallel.
    • The shell and the Python script were developed under Linux, but they also run under Windows (in a bash shell and with SageMath for Windows).

 

Note: Besides the Python code, we also developed a C++ version which performs even faster than the above Python version. This C++ code was developed as the code from 4 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.

 

Sources and References

Footnotes

  1. 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. ↩

  2. [2] Esslinger, Schneider, Simon: "RSA-Sicherheit in der Praxis", KES & Zeitschrift für Informationssicherheit, April 2012, pp. 18 ff. This article explains the attack on shared primes, how the sanity check above was developed, and what organizations can do against this risk. This article is in German. ↩

  3. SageMath – free and open-source mathematics software system, v9.1 (2020-05-21), August 2020, https://www.sagemath.org ↩

  4. 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 ↩

Posted by:

Volker Simon