# RSA Tool

Many CTF competitions come with some kind of RSA cryptography challenge. These challenges vary in difficulty but usually use the same textbook RSA calculations. To speed up my solve times, I’ve created some simple scripts to help solve the most common RSA CTF challenges. Many of them are snippets I’ve found online and adapted to work with my utilities.

## Usage

run.py is the runner program. You can use all the functions in attack_functions.py and pem_utilities.py.

1. attack_functions contains functions that perform numerical attacks against RSA and provides some basic utilities, such as converting integers to ASCII text.

2. pem_utilities contains functions that make it easier to work with PEM files or files that have been encrypted using openssl.

## Notes

1. Small public modulus n - use https://factordb.com/index.php to find p and q.
2. Given multiple keys - see if any of the keys have common factors using the Euclidean Algorithm.
3. p and q are close to each other - use YAFU or https://www.alpertron.com.ar/ECM.HTM
4. Two ciphertexts use the same modulus n but different exponents e - use: same_modulus.py
5. Small p or q - use YAFU or https://www.alpertron.com.ar/ECM.HTM
6. Large e or d - Wiener’s attack. Use attackrsa tool.
7. Same m and e for multiple messages - Hastad’s Broadcast Attack. Use attackrsa tool.
8. If num_ciphertexts >= e then you can use Chinese Remainder Theorem to calculate the message (but gcd of all n’s must be 1 - if the gcd between any two n’s is not 1, then you can just find a common factor between them).

## External Utility Notes

Here are some commands to transform and work with keys.

Given n and d, print e, p, q.

Given n and d, print PEM format.

Given p and q, print DER format.

Factorize with YAFU.