Primetools

By Kryc

Introduction

Primetools is a set of utilities for manipulating prime numbers and, more specifically, factorising the product of two primes. The latter is extremely useful for attacking weak RSA keys.

The main use of this project is in the building and solving of capture the flag (CTF) competitions.

Factorisation Strategies

• Small prime factorisation (against the first 100K primes)
• Fermat's factorisation method
• Pollard's Rho
• Brent-Pollards Rho
• Shank's Square Forms Factorisation (SQUFOF)
• Random Trial Division

Note that although the original Pollard's Rho is implemented and working, Brent's improvements provide a roughly 24% speed improvement so this version is used as the default.

Building

Building the project is straightforward on *nix systems.

mkdir build;
cd build;
cmake -DCMAKE_BUILD_TYPE=Release ..
make

Running

There are a couple of command line switches, but the main one to use would be:

./primetools factorise <N>

Where N is the number whose prime factors you wish to find.