RSA tools

This project is a compilation of several tools written in C to attack RSA, mainly to get familier with the mathematical library PARI.

For now, it contains two sets of tools:

• Factorization of a single RSA modulus with or without the public exponent
• Factorization with partial knowledge of one prime or the private exponent

Other attacks might be added in the future.

Content of this repository:

• include/: two headers, one of them is config.h and can be modified to adjust some values
• prgm/: the main file of the binaries
• rsa-coppersmith/: attacks related to Coppersmith's method
• rsa-single/: attacks to factor a single modulus
• utils/: auxiliaries tools
• A makefile and this README

Dependencies and installation

This set of tools relies mainly on the mathematic library PARI (it might already be installed on your system if you are already familiar with Sagemath).

On a Debian system, you can install the following packages:

apt install libpari-dev libpari-gmp-tls7

The installation of is easy: clone the repository and make. That's it.

git clone https://github.com/arusson/rsatools.git
cd rsatools/
make

The programs will be generated into the bin/ folder.

Factorization of a single key

The program is rsa-single and takes as input a modulus (and an optional public exponent).

• -n or --modulus: the modulus
• -e (optional): the public exponent (only useful for the factor_small_d and factor_wiener attack
• --attack (optional): followed by the name of the attack:
  • factor_small
  • factor_square
  • factor_small_d
  • factor_wiener
  • factor_fermat
  • factor_shared_lsb
  • factor_p_pm_1
  • factor_cm

If --attack is not provided, all the attacks will be run. The individual attacks are described below. Some of them have supplementary optional arguments.

There is also the verbose flag -v (or --verbose) for more verbosity, and -h (or --help) for help.

Small modulus

If the modulus is small enough (less than 200 bits), we can factorize the modulus directly with the factor_small attack.

./rsa_single -n 13835591013508601955356617501157248249972987974212552783 --attack factor_small

Square modulus

If $n = p^2$, we can factorize immediately. The name of the attack is factor_square.

Example:

./rsa_single -n 78297508606636734255546527877941659862998377016250455576245379383582442920347363428284313728363073522700726425379782022957275475303153939021034085766104250307515110170603903839197137362974969376662138533915645356136507980050853767364126467841339699197295433089043907534911945250837610122210727857002280456081 --attack factor_square

Small private exponent

It is mandatory to provide the public exponent to run this attack using the -e option.

Two attacks are currently available: factor_small_d and factor_wiener. In both cases, it works if the private exponent size is less than $n^{1/4}$ (in the case of the Wiener, it is $1/3 n^{1/4}$). When the whole set of attacks is applied, factor_small_d is tested first as it is faster.

./rsa_single -n 108925679802284239955001551017681506180164145739691670124361307613981176689733670923774311632395717664402684130443830263937033295748941917653240917714229256396243845478977090813121921418491025509757182629002814915232676429884675193143885477233354472089268619428997934110569939243783923766553598930250989079139 -e 40748325560689123257486527536483510918500840830012157699067275029010630229039582055552209626771400303650355793395740004944852495185054320950198193493963164311430925570877706350889263787470569460632216019425322782108117721415492657825340141267119905429074474964042169876353864031822939977214312487530332981433 --attack factor_small_d

TODO: the Boneh-Durfee attack for private exponents up to $n^{0.292}$.

Close primes attack (Fermat)

A classic attack on RSA, use factor_fermat. We start with $x = \lfloor\sqrt n\rfloor$ and check if $(x + k)^2 - n$ is a square. When that happens, we have $(x + k)^2 - n = y^2$ so $n = (x + k - y)(x + k + y)$.

We try for $k$ with $0 \leq k < B$ (the bound is 50000 by default). This attack has an optional arguments to change this bound: --fermat-bound <VAL>.

./rsa_single -n 17993905914950491436509764609848745889407701208922305196646413621766992846622614476604970908283050717785882685787893383681126527212717999927824594755009072726416107971707905566292701391446727049561208452055259765604283479942581912459438219891123869205353871265616910471441350003239753479583312907703934142271194206788319233033618972618163116022899812760862187551379432607627920372634257141817679924725013054219375317513860159120565072902737014597477023903308248937908414850338991424040608140661465411316830899039534976471493065939613654116614382350055877051913830339187783231007425687358556725613489778331864975405317 --attack factor_fermat

Primes sharing their least significant bits

The previous attack works because $p-q$ is small, in another way the two primes share a lot of their most significant bits. In the case the primes share their least significant bits, it is also possible to factorize with the factor_shared_lsb attack.

This implementation works in a specific case: the primes $p$ and $q$ are such that the number of their least significant bits in common $\ell$ is strictly larger than $\log_2(n)/4$ (the Coppersmith method is not used).

./rsa_single -n 95969061182734167696837319881131542496301619959745607926138388622543497901780880433954730696765466102601701328315194465608056191443195349092158675063024346087987310382654581752734608514531607495470218640233801869376908066505672982563829514015829882243253393598696202962408912036484661274078169360611565256113 --attack factor_shared_lsb

Smooth p-1 and p+1

If $p-1$ or $p+1$ is a product of small primes, the attack factor_p_pm_1 can be used: $$p - 1 = \prod_{i = 1}^m p_i^{\alpha_i},\quad\text{or}\quad p + 1 = \prod_{i=1}^m p_i^{\alpha_i},$$ with $p_i$ prime numbers distinct from each other and $\alpha_i$ their multiplicities.

Several attempts will be made since it will test both cases randomly. The idea is that we construct a group that has either $p-1$ of $p+1$ elements (when the calculations are made modulo the prime $p$), and we know a multiple of this order (the product of small primes).

By default, the attack expects that the prime factors $p_i$ of $p-1$ or $p+1$ are less than $2^{16}$, and such that prime power factors $p_i^{\alpha_i}$ are less than $2^{64}$. This behavior can be changed with optional arguments (it can also be changed at compilation time in the configuration file):

• --p1-prime-bound <val>: bound on the prime factors $p_i$ of $p-1$ or $p+1$
• --p1-nbits-bound <val>: bound on prime power factors $p_i^{\alpha_i}$ of $p-1$ or $p+1$ (the value is given in bits)

Example if the factorization of $p-1$ or $p+1$ has prime factors less than $2^{20}$ (if they appear at most once):

./rsa_single -n 96055084779851008502406592815328861630962527251548171954345046797234192459426797362896924679804346924329938014826957203216360063514093668339656861409919126466853568585981567830912323988597067008449335246177088795611091567898342731168911999529785832299470070731151903234363609895839205834594823341024290244799 --attack factor_p_pm_1 --p1-prime-bound 1048576 --p1-nbits-bound 20

The higher the bounds, the longer it takes to run the attack.

The 4p-1 factorization

This factorization method finds a prime factor $p$ of a composite integer if the non-square part of $4p-1$ is a complex multiplication discriminant, from which an elliptic curve of order $p$ can be constructed (which is called an anomalous elliptic curve).

The idea is the same as the previous factorization method: we construct a group whose order is unknown to the attacker, but a multiple of it is known. In the previous situation, this multiple was a product of many small primes which is easy to calculate. In this case, the order is $p$, and the modulus is a multiple.

Two optional arguments are provided:

• --cm-disc <val>: a CM-discriminant in absolute value (example: 11)
• --cm-disc-bound <val>: discriminants between $-3$ and "-val" will be tested (the default are discriminants $D$ with $|D| < 64$)

Example with --cm-disc 43:

./rsa_single -n 91982984654412298918905100667093043234916389105208833040709639508773652128538386023015487388659716487603461878610876776626504190644167683365520501112611688367330270792623674565452046825518198937965209215150436486498446004121478350269720860943418316052259143174980621393390145101255733850628736444988025154417 --attack factor_cm --cm-disc 43

Prime factor recovery

Not an attack, but a useful tool: if you know the modulus $n$, the public exponent $e$ and the private exponent $d$, then the prime factors $p$ and $q$ can be recovered efficiently.

It is only needed to provide as inputs:

./rsa_single -n <modulus> -e <public exponent> -d <private exponent>

Examples of values:

n = 22696111367870921015552731040448897566507944375931042540652706299121991614888334531171387175658733966997244143173157890392907827477367346607713916863796171326177520101713725914087688865476228551315082805706679478749266289221359032140781888933984489480794719967889033692566354693669616972516160753562320211223639257992396545436008184792442951808306948737032298532772875790800830881955773307644355549794036541111626528788884114173153978251774810938317616181492743832898279751396217437933976006825501587968208924746679998381237046921353037141943546390048021002481176265400867233346941684414591228996327766412084634266611
e = 2793265186105514038606096589933469000435785015878916401650825913905328004065307364873105677118233701712726625957720495309095081