Crown Sterling: Semi Prime Factorization

Code samples to support the white paper "Novel Geometric Methods for Semiprime Factorization"

Get started with this example as used in the public demonstration:

./RsaCtfTool.py --publickey ./examples/siqs.pub --private

Details

RSA tool for ctf - uncipher data from weak public key and try to recover private key Automatic selection of best attack for the given public key

Attacks :

• Prime N detection
• Weak public key factorization
• Wiener's attack
• Hastad's attack (Small public exponent attack)
• Small q (q < 100,000)
• Common factor between ciphertext and modulus attack
• Fermat's factorisation for close p and q
• Gimmicky Primes method
• Past CTF Primes method
• Self-Initializing Quadratic Sieve (SIQS) using Yafu
• Common factor attacks across multiple keys
• Small fractions method when p/q is close to a small fraction
• Boneh Durfee Method when the private exponent d is too small compared to the modulus (i.e d < n^0.292)
• Elliptic Curve Method
• Pollards p-1 for relatively smooth numbers
• Mersenne primes factorization
• Londahl's factorisation for close p and q
• Qi Cheng's unsafe primes factorization

Usage:

usage: RsaCtfTool.py [-h] [--publickey PUBLICKEY] [--createpub] [--dumpkey] [--ext]
                     [--uncipherfile UNCIPHERFILE] [--uncipher UNCIPHER]
                     [--verbose] [--private] [--ecmdigits ECMDIGITS] [-n N]
                     [-p P] [-q Q] [-e E] [--key KEY]
                     [--attack {hastads,factordb,pastctfprimes,mersenne_primes,noveltyprimes,smallq,wiener,comfact_cn,primefac,fermat,siqs,Pollard_p_1,londahl,prime_n,all}]

Mode 1 - Attack RSA (specify --publickey)

• publickey : public rsa key to crack. You can import multiple public keys with wildcards.
• uncipher : cipher message to decrypt
• private : display private rsa key if recovered

Mode 2 - Create a Public Key File Given n and e (specify --createpub)

• n - modulus
• e - public exponent

Mode 3 - Dump the public and/or private numbers (optionally including CRT parameters in extended mode) from a PEM/DER format public or private key (specify --dumpkey)

• key - the public or private key in PEM or DER format

Uncipher file :

./RsaCtfTool.py --publickey ./key.pub --uncipherfile ./ciphered\_file

Print private key :

./RsaCtfTool.py --publickey ./key.pub --private

Attempt to break multiple public keys with common factor attacks or individually - use quotes around wildcards to stop bash expansion

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

Generate a public key :

./RsaCtfTool.py --createpub -n 7828374823761928712873129873981723...12837182 -e 65537

Dump the parameters from a key:

./RsaCtfTool.py --dumpkey --key ./key.pub

Factor with ECM when you know the approximate length in digits of a prime:

./RsaCtfTool.py --publickey key.pub --ecmdigits 25 --verbose --private

Examples :

• weak_public.pub, weak_public.cipher : weak public key
• wiener.pub, wiener.cipher : key vulnerable to Wiener's attack
• small_exponent.pub, small_exponent.cipher : key with e=3, vulnerable to Hastad's attack
• small_q.pub, small_q.cipher : public key with a small prime
• close_primes.pub, close_primes.cipher : public key with primes suceptible to fermat factorization
• elite_primes.pub : public key with a gimmick prime
• fermat.pub : public key with another vulnerability to fermat factorization
• pastctfprimes.pub : public key with a prime from a past CTF
• siqs.pub: 256bit public key that is factored in 30 seconds with SIQS
• factordb_parsing.pub: a public key with a prime that is described as an expression on factordb.com
• smallfraction.pub: a public key where p/q is close to a small fraction
• boneh_durfee.pub: a public key factorable using boneh_durfee method
• multikey-0.pub and multikey-1.pub: Public keys that share a common factor
• ecm_method.pub: Public key with a 25 digit prime factorable with ECM method in around 2 minutes (use --ecmdigits 25 to test)

Requirements:

• GMPY2
• SymPy
• PyCrypto
• Requests
• SageMath - optional but advisable

Ubuntu 18.04 and Kali specific Instructions

git clone https://github.com/Ganapati/RsaCtfTool.git
cd RsaCtfTool
sudo apt-get install libgmp3-dev libmpc-dev
python3 -m venv .
. bin/activate
pip install -r "requirements.txt"
./RsaCtfTool.py

MacOS-specific Instructions

If pip install -r "requirements.txt" fails to install requirements accessible within environment, the following command may work.

easy_install `cat requirements.txt`

If you get the error "ImportError: No module named Crypto.PublicKey" even with pycrypto installed, then, switch to a python virtual environment and should be ok.

Todo

• Implement multiple ciphertext handling for more attacks (Common modulus attack)
• Implement support for MultiPrime RSA (see 0ctf 2016)
• Possibly implement Msieve support...
• Some kind of polynomial search...
• Brainstorm moar attack types!
• Saw a CTF where the supplied N was a 2048 bit prime. Detect this and solve using phi = (n - 1) * (n - 1) which seemed to work for that CTF
• Replicate all functionality of rsatool.py
• Support more types of expression based primes from factordb.com?