CT-Logo

Header - Impressionsbeitrag CT-Portal

Schon gewusst?

Ursprünglich für IT-Sicherheits-Schulungen im Unternehmen entwickelt, hat sich CrypTool inzwischen zu einem bedeutenden Open-Source-Projekt im Bereich Kryptologie entwickelt, an dem über 50 Entwickler weltweit ehrenamtlich mitarbeiten.

 

RSA sanity check: Testing RSA moduli for shared prime factors

E-Mail Drucken
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.

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

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 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 Sage [3].


Requirements:

  • An up-to-date Python version (2.6)
  • The Python script requires an installation of Sage. Sage 4.8 officially 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:

  1. Download and install Sage 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 file.
    Run in the terminal: ./moduli_extract.sh
    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 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>


Future Work

  • Check the list of moduli for duplicates
  • Use a more efficient algorithm

*Note: We also developed a C++ version which performs faster than the above Python version. In case you want to check a large set (>1M) of moduli for shared primes please contact us at:

This e-mail address is being protected from spambots. You need JavaScript enabled to view it.

 

[1] Lenstra, A., et al., "Ron was wrong, Whit is right", Cryptology ePrint Archive Report 2012/064, February 2012, http://eprint.iacr.org/2012/064.

[2] Esslinger, Schneider, Simon: "RSA-Sicherheit in der Praxis", KES -- Zeitschrift für Informationssicherheit, April 2012, S. 18 ff

[3] William A. Stein et al., Sage Mathematics Software (Version 4.8), The Sage Development Team, January 2012, http://www.sagemath.org

Web-Development and Design by imagine orange, powered by joomla