Skip to content

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

License

Notifications You must be signed in to change notification settings

jokker87/RsaCtfTool

This branch is 1 commit ahead of, 979 commits behind RsaCtfTool/RsaCtfTool:master.

Folders and files

NameName
Last commit message
Last commit date
Jun 28, 2018
May 1, 2017
Apr 30, 2017
Nov 20, 2018
Nov 27, 2018
Jan 1, 2019
Mar 20, 2018
Mar 20, 2018
Mar 22, 2018
Aug 11, 2017
Mar 22, 2018
Mar 22, 2018
Apr 20, 2017
Jul 5, 2018
Mar 21, 2018
Jun 10, 2018
Sep 22, 2018
Mar 20, 2018
Apr 5, 2018
Mar 22, 2018
Mar 30, 2016

Repository files navigation

RsaCtfTool

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

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 :

  • 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

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,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
sudo apt-get install libgmp3-dev libmpc-dev
pip install -r "requirements.txt"
python2.7 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`

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?

About

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

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 97.7%
  • Shell 2.3%