Fermat's factorization method

A Python and a C implementation of Fermat's factorization method. Example of factoring prime numbers of a weak RSA public key.

Introduction

Prime factorization is known as a way to crack the RSA cryptosystem code. Currently, most of the best modern factoring algorithms are based on the idea behind Fermat's method of factorization.

Fermat's factorization method uses that fact that any number can be expressed as the difference between two squares.
Given a number n, the algorithm consists of finding x and y such that (x2 - y2) = n.

The security of RSA algorithm depends upon the integer N, which is the multiple of two large prime numbers p and q.

Fermat's factorization method factors N into p and q very efficiently if p and q share half of their leading bits. In other words, if the gap between p and q is below the square root of p.

Cracking RSA public keys

If the two prime numbers p and q are too close, specifically if the value of p - q is less than 2n1/4, then Fermat factorization for N will be trivial.

Let's pick two prime number p and q that share half of their leading bits.

p = 7422236843002619998657542152935407597465626963556444983366482781089760760914403641211700959458736191688739694068306773186013683526913015038631710959988771
q = 7422236843002619998657542152935407597465626963556444983366482781089760759017266051147512413638949173306397011800331344424158682304439958652982994939276427

Generate an RSA public key N which is the product of p and q.

N = p * q
N = 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217

To quickly recover the values of p and q from N one can use the Fermat's factorization method.

Python Fermat's factorization method

This Python script uses the gmpy2 library for some large numbers arithmetic operations.

#!/usr/bin/env python
import gmpy2

N = 0x4e733febb94db17ca3e6aa26ec33b4960c150c52300e06c60b3318f0744fef2d687a8f5bf598894a22eec4abdae01b197e4cc5603de67eb670e261eb4e4cc5e26241edcde494cce415bbc5a410abcefdff6199bbcdf62e9d434faa88a1d16012520f80d126208206ff80191e20ed7423cdce5b8a555b4161534e789a74f0a701

def fermat_factor(n):
    assert n % 2 != 0

    a = gmpy2.isqrt(n)
    b2 = gmpy2.square(a) - n

    while not gmpy2.is_square(b2):
        a += 1
        b2 = gmpy2.square(a) - n

    p = a + gmpy2.isqrt(b2)
    q = a - gmpy2.isqrt(b2)

    return int(p), int(q)

if __name__ == "__main__":
    (p, q) = fermat_factor(N)

    print("p = {}".format(p))
    print("q = {}".format(q))

This Python script proved to be useful to get flags during some security CTF competitions. However, it can be interesting to see how it performs in a compiled language.

C Fermat's factorization method

This C implementation of the Fermat's factorization algorithm uses the GMP library for large numbers arithmetic.
This code has great performances and can factorize prime numbers in a very short amount of time.

#include <gmp.h>

void fermat_factor(mpz_t p, mpz_t q, mpz_t N);

int main()
{
    mpz_t N;
    mpz_t p, q;

    mpz_init(N);
    mpz_init(p);
    mpz_init(q);

    mpz_set_str(N, "4E733FEBB94DB17CA3E6AA26EC33B4960C150C52300E06C60B3318F0744FEF2D687A8F5BF598894A22EEC4ABDAE01B197E4CC5603DE67EB670E261EB4E4CC5E26241EDCDE494CCE415BBC5A410ABCEFDFF6199BBCDF62E9D434FAA88A1D16012520F80D126208206FF80191E20ED7423CDCE5B8A555B4161534E789A74F0A701", 16);
    fermat_factor(p, q, N);

    gmp_printf("p = %Zd\n", p);
    gmp_printf("q = %Zd\n", q);

    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(N);

    return 0;
}

void fermat_factor(mpz_t p, mpz_t q, mpz_t N)
{
    mpz_t a, b;

    mpz_init(a);
    mpz_init(b);

    mpz_sub_ui(a, N, 1);
    mpz_sqrt(a, a);
    mpz_add_ui(a, a, 1);

    while (1)
    {
        mpz_mul(b, a, a);
        mpz_sub(b, b, N);

        if (mpz_perfect_square_p(b))
            break;

        mpz_add_ui(a, a, 1);
    }

    mpz_sqrt(p, b);
    mpz_sqrt(q, b);
    mpz_add(p, a, p);
    mpz_sub(q, a, q);

    mpz_clear(a);
    mpz_clear(b);
}

Conclusion

Most of the open source RSA key generators prevents this attack by verifying that the primes are safe and respect some rules. However, there are probably some services with weak keys hanging around the Internet.

Share