Did you know?

That CrypTool was originally designed as an internal business application for information security training. CrypTool has since developed into an important open-source project in the field of cryptology. Over 50 volunteer developers worldwide contribute to the program.

What is CrypTool 1

CrypTool 1 (CT1) is an open-source Windows program for cryptography and cryptanalysis. It’s the most wide-spreaded e-learning software of its kind.

What is CrypTool 2?

CrypTool 2 (CT2) is an open-source program offering an innovative visual programming GUI to experiment with cryptographic procedures and to animate their cascades.

What is JCrypTool?

JCrypTool (JCT) is an open-source e-learning platform, allowing to experiment comprehensively with cryptography on Linux, MAC OS X, and Windows.

What is CrypTool-Online?

CrypTool-Online (CTO) runs in a browser and provides a variety of encryption and cryptanalysis methods including illustrated examples and tools like password generator and password meter.

What is MysteryTwister C3?

MysteryTwister C3 (MTC3) is an international Crypto Cipher Contest offering a broad variety of challenges, a moderated forum, and an ongoing hall-of-fame.

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


Requirements:

  • 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:

  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 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 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 [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 at:
This email address is being protected from spambots. You need JavaScript enabled to view it.

 


Sources and References

[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] Esslinger, Schneider, Simon: "RSA-Sicherheit in der Praxis", KES -- Zeitschrift für Informationssicherheit, April 2012, pp. 18 ff

[3] William A. Stein et al., Sage Mathematics Software (Version 4.8), The Sage Development Team, January 2012, http://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

[5] Christian Schlipp, Explanations to "Mining Your P’s and Q’s: Detection of Widespread Weak Keys in Network Devices", seminar thesis, February 2013

[6] 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.

Go To Top