# Introduction

```Bob uses a RSA public key with the public exponent e = 65537 and modulus:

N = 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217

The challenge validation key is given by the md5sum of the value of its private key d.
```

# Resolution

As said in the statement, it’s a simple RSA challenge.

N is characterized by N = p * q (with p and q being primes factors, cf. key generation). So let’s try to factorize N to derive these numbers. Several methods exists, like the Fermat’s one.

Let’s run this little python script that will calculate it for us:

```#from math import ceil

def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x

def fermat(n, verbose=True):
a = isqrt(n) # int(ceil(n**0.5))
b2 = a*a - n
b = isqrt(n) # int(b2**0.5)
count = 0
while b*b != b2:
if verbose:
print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
a = a + 1
b2 = a*a - n
b = isqrt(b2) # int(b2**0.5)
count += 1
p=a+b
q=a-b
assert n == p * q
print('a=',a)
print('b=',b)
print('p=',p)
print('q=',q)
print('pq=',p*q)
return p, q

n_long=55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217
fermat(n_long, verbose=False)
```

Source

A few hours later of calculation we get:

```('a=', 7422236843002619998657542152935407597465626963556444983366482781089760759965834846179606686548842682497568352934319058805086182915676486845807352949632599L)
('b=', 948568795032094272909893509191171341133987714380927500611236528192824358010356172L)
('p=', 7422236843002619998657542152935407597465626963556444983366482781089760760914403641211700959458736191688739694068306773186013683526913015038631710959988771L)
('q=', 7422236843002619998657542152935407597465626963556444983366482781089760759017266051147512413638949173306397011800331344424158682304439958652982994939276427L)
('pq=', 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217L)
```

We have now all the elements to calculate d, it will be easier by using the python script named rsatool.

```\$ python rsatool.py -p 7422236843002619998657542152935407597465626963556444983366482781089760760914403641211700959458736191688739694068306773186013683526913015038631710959988771 -q 7422236843002619998657542152935407597465626963556444983366482781089760759017266051147512413638949173306397011800331344424158682304439958652982994939276427 -n 55089599753625499150129246679078411260946554356961748980861372828434789664694269460953507615455541204658984798121874916511031276020889949113155608279765385693784204971246654484161179832345357692487854383961212865469152326807704510472371156179457167612793412416133943976901478047318514990960333355366785001217 -e 65537
Using (p, q) to initialise RSA instance
n = 4e733febb94db17ca3e6aa26ec33b4960c150c52300e06c60b3318f0744fef2d687a8f5bf598894a22eec4abdae01b197e4cc5603de67eb670e261eb4e4cc5e26241edcde494cce415bbc5a410abcefdff6199bbcdf62e9d434faa88a1d16012520f80d126208206ff80191e20ed7423cdce5b8a555b4161534e789a74f0a701
e = 65537 (0x10001)
```

We need to convert it to a decimal value:

```\$ python -c "print int('20d87207d0b2adc000a37fd4020af7ede6ab1d587fd42f93d5769457806b4339a0c7c7a3f9e4de7e52b7e3520cb6cdc1d3b672e103a9b09dd40f846dcf7fa74dd5a8a211a875cae39a5cee6862b56db34fd0acd52b48bd95b359c56083fe698f747b8e6f6e71c83fc375b1b5d93749ecd681ea207ae05419aadb9c76cd3d416d', 16)"
23064887432133452418944968485393480424632078139076757103405026306352475603240094293896627789805523522813645480807271096237944782073289886838211647399003341787604426963520708394682398410522699177647706339791627975491188337143684005336934914780236824919338821455517142365700147254540590602906990901658514178413
```

And convert it into a md5sum. (-n argument means no \n for the echo)

```\$ echo -n '23064887432133452418944968485393480424632078139076757103405026306352475603240094293896627789805523522813645480807271096237944782073289886838211647399003341787604426963520708394682398410522699177647706339791627975491188337143684005336934914780236824919338821455517142365700147254540590602906990901658514178413' | md5sum