crypto_tools

A collection of cryptographic attacks and tools for CTFs and other purposes.

This is a work in progress, and its purpose is to complement other tools such as RsaCtfTool.

Tools

RSA / Prime Factorization

• factorize_base.py: Tries to factorize a number using a base where it has a high ratio of 0's, by writing it as a polynomial which can be easily factorized (inspired by this writeup). The script checks bases from 2 to 64 (by default) to find a good candidate.

Elliptic Curve Cryptography

• ecc_attacks.py: Tries various attacks on elliptic curves to break the discrete logarithm problem. Automatically calculates the curve parameters $a$ and $b$ from the given points if not provided.

  Implemented attacks:

  • ecc_mov.py: Implements the MOV attack that works on supersingular elliptic curves (whose embedding degree is small), by pairing the curve group with a finite field where the DLP is easier to solve.

  • ecc_smart.py: Implements Smart's attack that works on anomalous elliptic curves ($#E(F_p) = p$).

  • ecc_pohlig_hellman.py: Implements the Pohlig-Hellman algorithm to solve the ECDLP on curves of relatively smooth order, by reducing the problem to smaller subgroups. It solves the DLP iteratively for each prime factor of the curve order and stops once their CRT is the right solution, or if all remaining factors are too large (configurable via --max-bits).