RsaCtfTool

RSA multi-attack tool that decrypts data from weak public keys and recovers private keys.

Overview

This tool is a utility designed to decrypt data from weak public keys and attempt to recover the corresponding private key. It offers a comprehensive range of attack options for cracking RSA encryption.

RSA security relies on the complexity of integer factorization. This project combines multiple factorization algorithms to enhance decryption capabilities.

Note: This tool is primarily intended for educational purposes. Not every key can be broken in a reasonable timeframe. The tool only supports RSA textbook semiprime composite modulus (not multiprimes).

For advanced factorization, consider msieve, yafu, or cado-nfs.

Usage

RsaCtfTool --publickey key.pub --private                    # Recover private key
RsaCtfTool --publickey key.pub --decryptfile ciphertext    # Decrypt file
RsaCtfTool --publickey key.pub --attack wiener             # Use specific attack

For complete usage, run: RsaCtfTool --help

Installation

Prerequisites

• Python 3.9+
• SageMath (optional but recommended)

Virtual Environment (Recommended)

python3 -m venv venv
source venv/bin/activate
pip install -e .

Docker

docker build -t rsactftool/rsactftool .
docker run -it --rm -v $PWD:/data rsactftool/rsactftool <arguments>

Attacks

Non-Factorization Attacks

• Wiener's attack
• Hastad's attack (small public exponent)
• Boneh-Durfee (small private exponent d < n^0.292)
• Same n, huge e
• Small CRT exponent
• Partial q / Partial d
• Lattice reduction

Integer Factorization Methods

Method	Description
Fermat	Close p and q
Pollard Rho	General factorization
Elliptic Curve (ECM)	Smooth numbers
Pollard p-1	Smooth numbers
Williams p+1	Smooth numbers
ROCA	Vulnerable key generation
SQUFOF	Square forms
Quadratic Sieve	General factorization
Dixon	Random squares
Factordb	Online factorization database
Common factor attacks	Keys sharing factors
GCD attacks	Mersenne, Primorial, Fibonacci, etc.

CTF-Specific Methods

• Noveltyprimes
• Past CTF Primes
• Gimmicky Primes
• Non-RSA (b^x form)
• Z3 Theorem Prover
• Wolfram Alpha

Examples

Recover Private Key

RsaCtfTool --publickey key.pub --private

Decrypt a File

RsaCtfTool --publickey key.pub --decryptfile ciphertext

Attack Multiple Keys

RsaCtfTool --publickey "*.pub" --private

Create Public Key from n and e

RsaCtfTool --createpub -n 7828374823761928712873... -e 65537

Dump Key Parameters

RsaCtfTool --dumpkey --key key.pub
RsaCtfTool --dumpkey --ext --key key.pub  # Include CRT parameters

Factor with ECM

RsaCtfTool --publickey key.pub --ecmdigits 25 --private

Use Specific Attack

RsaCtfTool --publickey key.pub --attack wiener --private
RsaCtfTool --publickey key.pub --attack factordb --private

Send Results to Factordb

RsaCtfTool --publickey "*.pub" --private --sendtofdb

Check for ROCA Vulnerability

RsaCtfTool --isroca --publickey "examples/*.pub"

Convert SSH Key to PEM

RsaCtfTool --convert_idrsa_pub --publickey ~/.ssh/id_rsa.pub

For more examples, run pytest tests/ --collect-only to see available tests.

Testing

Tests use pytest and are located in tests/.

Running Tests

pytest tests/                 # Run all tests
pytest tests/ -m "not slow"   # Skip slow tests
pytest tests/ -v              # Verbose mode
pytest tests/ -k "fermat"     # Run tests matching "fermat"

Test Markers

• @pytest.mark.slow - Slow factorization tests
• @pytest.mark.network - Tests requiring network (Factordb)
• @pytest.mark.attack - Attack integration tests

Test Files

File	Description
test_number_theory.py	Number theory functions (gcd, is_prime, phi, etc.)
test_algos.py	Factorization algorithms (fermat, brent, pollard_rho, etc.)
test_keys_wrapper.py	PublicKey/PrivateKey classes
test_utils.py	Utility functions
test_pubkey_decode.py	RSA public key decoding
test_attacks.py	Attack integration tests
test_regression.py	Bug fix regression tests
test_exceptions.py	Custom exceptions
conftest.py	pytest configuration and fixtures

Contributing

Please read CONTRIBUTING.md for guidelines and CODE_OF_CONDUCT.md before contributing.

License

The original project was released under GPLv3. This code has been relicensed under the MIT License.

Thanks