/RsaCtfTool

RSA attack tool (mainly for ctf) - retreive private key from weak public key and/or uncipher data

Primary LanguagePythonOtherNOASSERTION

RsaCtfTool

lint_python CodeQL GitHub issues GitHub forks GitHub stars Rawsec's CyberSecurity Inventory GitHub license

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

Attacks :

  • 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 (https://github.com/DarkenCode/yafu.git)
  • 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
  • Factordb
  • Londahl
  • Noveltyprimes
  • Partial q
  • Primefac
  • Qicheng
  • Same n, huge e
  • binary polynomial factoring
  • Euler method
  • Pollard Rho
  • Wolfram alpha
  • cm-factor
  • z3 theorem prover
  • Primorial pm1 gcd
  • Mersenne pm1 gcd
  • Fermat Numbers gcd
  • Fibonacci gcd
  • System primes gcd
  • Small crt exponent

Usage

usage: RsaCtfTool.py [-h] [--publickey PUBLICKEY] [--timeout TIMEOUT]
                     [--createpub] [--dumpkey] [--ext] [--sendtofdb]
                     [--uncipherfile UNCIPHERFILE] [--uncipher UNCIPHER]
                     [--verbosity {CRITICAL,ERROR,WARNING,DEBUG,INFO}]
                     [--private] [--ecmdigits ECMDIGITS] [-n N] [-p P] [-q Q]
                     [-e E] [--key KEY] [--isconspicuous] [--convert_idrsa_pub]
                     [--attack {smallfraction,wiener,pastctfprimes,wolframalpha,factordb,fermat,ecm,primorial_pm1_gcd,binary_polinomial_factoring,fibonacci_gcd,londahl,smallq,mersenne_pm1_gcd,noveltyprimes,roca,pollard_p_1,boneh_durfee,ecm2,pollard_rho,z3_solver,cube_root,mersenne_primes,cm_factor,comfact_cn,fermat_numbers_gcd,qicheng,partial_q,siqs,euler,commonfactors,hastads,same_n_huge_e,all} [{smallfraction,wiener,pastctfprimes,wolframalpha,factordb,fermat,ecm,primorial_pm1_gcd,binary_polinomial_factoring,fibonacci_gcd,londahl,smallq,mersenne_pm1_gcd,noveltyprimes,roca,pollard_p_1,boneh_durfee,ecm2,pollard_rho,z3_solver,cube_root,mersenne_primes,cm_factor,comfact_cn,fermat_numbers_gcd,qicheng,partial_q,siqs,euler,commonfactors,hastads,same_n_huge_e,all} ...]]

Mode 1 : Attack RSA (specify --publickey or n and e)

  • 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

Optionaly send the results back to factordb

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

Generate a public key

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

Dump the parameters from a key

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

Check a given private key for conspicuousness

./RsaCtfTool.py --key examples/conspicuous.priv --isconspicuous

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

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

For more examples, look at test.sh file

Convert idrsa.pub to pem format

./RsaCtfTool.py --convert_idrsa_pub --publickey $HOME/.ssh/id_rsa.pub

Requirements

  • GMPY2
  • SymPy
  • PyCrypto
  • Requests
  • Libnum
  • SageMath : optional but advisable
  • Sage binaries

Ubuntu 18.04 and Kali specific Instructions

git clone https://github.com/Ganapati/RsaCtfTool.git
sudo apt-get install libgmp3-dev libmpc-dev
pip3 install -r "requirements.txt"
python3 RsaCtfTool.py

MacOS-specific Instructions

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

easy_install `cat requirements.txt`

Todo (aka. Help wanted !)

  • Implement test method in each attack
  • Assign the correct speed value in each attack