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.

## Installation

Download the folder linked below and then install dependencies.

1 | virtualenv venv |

## Usage

`run.py`

is the runner program. You can use all the functions in `attack_functions.py`

and `pem_utilities.py`

.

`attack_functions`

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

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

### Online Factorization

1 | from attack_functions import * |

### Working with PEMs

1 | from attack_functions import * |

## Notes

- Small public modulus n - use https://factordb.com/index.php to find p and q.
- Given multiple keys - see if any of the keys have common factors using the Euclidean Algorithm.
1

2import fractions

print(fractions.gcd(a, b)) - p and q are close to each other - use YAFU or https://www.alpertron.com.ar/ECM.HTM
- Two ciphertexts use the same modulus n but different exponents e - use: same_modulus.py
- Small p or q - use YAFU or https://www.alpertron.com.ar/ECM.HTM
- Large e or d - Wiener’s attack. Use attackrsa tool.
- Same m and e for multiple messages - Hastad’s Broadcast Attack. Use attackrsa tool.
- 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.

1 | python rsatool.py -n 13826123222358393307 -d 9793706120266356337 |

Given n and d, print PEM format.

1 | # cd rsatool |

Given p and q, print DER format.

1 | # cd rsatool |

Factorize with YAFU.

1 | ./yafu "factor(0xD8E24C12B7B99EFE0A9BC04A6A3DF58A2A944269B492B7376DF129023F2061B9)" -threads 5 |