# HackingWeek 2015 - Crypto 2

Breaking a weak 1024-bit RSA key by recovering primes through the Fermat's factorization method.

## 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`.