### 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 huge variety of encryption methods and analysis tools including many illustrated examples.

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

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:

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

Go To Top