HackingWeek 2015 - Crypto 2

Introduction

The goal of the second cryptography challenge was to factorize a 1024 bits RSA modulus and to reconstruct the private key d.

Bob utilise une clef publique RSA avec l'exposant public e = 65537 et le module:

N = 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217

La clef de validation de l'épreuve est donnée par le md5sum de la valeur de sa clef privée d.

Factoring 1024-bit RSA

We know the modulus N is 308 digits long, FactorDB does not have any records for this number.
The first thing that came to my mind was to use Fermat's factorization method.

Fermat's factorization

This method factors N into p and q very quickly if p and q share half of their higher level bits. In other words if the gap between p and q is below the square root of p.

To speed up the algorithm below, it's recommended to use the gmpy2 Python library.

Prime Factorization script

#!/usr/bin/env python
import gmpy2
import hashlib

N = 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217
e = 65537

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

    factor1 = a + gmpy2.isqrt(b2)
    factor2 = a - gmpy2.isqrt(b2)
    return int(factor1), int(factor2)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("modular inverse does not exist")
    else:
        return x % m

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

    phi_n = (p - 1) * (q - 1)
    d = mod_inv(e, phi_n)

    m = hashlib.md5()
    m.update(str(d))
    solution = m.hexdigest()

    print(solution)

In a matter of seconds this Python script will factorize N and calculate the modular multiplicative inverse d.