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
• dp / dq leak (--dp or --dq)
• Lattice reduction

Coppersmith Attacks

Coppersmith's lattice reduction methods solve for small roots of modular polynomials (requires optional SageMath dependency for lattice LLL reduction).

Attack	Required Flags	Feasibility Limits	Example Command
stereotyped_message	--sm-len and (--sm-prefix or --sm-suffix)	$e \le 17$, $X < N^{1/e}$	RsaCtfTool --publickey key.pub --decryptfile cipher.bin --attack stereotyped_message --sm-prefix "FLAG:" --sm-len 16
short_pad	--decryptfile c1,c2	$e \le 5$, $\Delta < N^{1/e^2}$	RsaCtfTool --publickey key.pub --decryptfile c1.bin,c2.bin --attack short_pad
partial_p	--p-high and --p-unknown-bits	$\text{unknown_bits} \le \lfloor N/4 \rfloor + 2$ ($\approx N^{0.25}$)	RsaCtfTool --publickey key.pub --attack partial_p --p-high 0x1234... --p-unknown-bits 212 --private
partial_d	--key (partial private key), optional --d-known-bits	Low bits of $d$ known	RsaCtfTool --key key.priv --partial --attack partial_d --d-known-bits 20
lattice	--key (partial key with approx of $p$)	Approximation of factor $p$	RsaCtfTool --key key.priv --partial --attack lattice
smallfraction	--publickey	$p/q$ close to small fraction $a/b$	RsaCtfTool --publickey key.pub --attack smallfraction --private

Note for text parameters (--sm-prefix, --sm-suffix): Values starting with 0x or 0X are parsed as hex byte strings, while all other string inputs are parsed as UTF-8 / ASCII text bytes.

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