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)
d = 20d87207d0b2adc000a37fd4020af7ede6ab1d587fd42f93d5769457806b4339a0c7c7a3f9e4de7e52b7e3520cb6cdc1d3b672e103a9b09dd40f846dcf7fa74dd5a8a211a875cae39a5cee6862b56db34fd0acd52b48bd95b359c56083fe698f747b8e6f6e71c83fc375b1b5d93749ecd681ea207ae05419aadb9c76cd3d416d
p = 8db72351e42d5e717ed7c317d06c4b3a6166cb1aad0b1407c472e6dc8b34f9488bf0a0cb68fd652d93e54e882a4fb1eca7caf8cd9b014d4f4fae1fc4ee51f023
q = 8db72351e42d5e717ed7c317d06c4b3a6166cb1aad0b1407c472e6dc8b34b9488bf0a0cb68fd652d93e54e882a4fb1eca7caf8cd9b014d4f4fae1fc4ee51ec8b

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
5fbec08ad520bb97a751d49927cce0d6

Flag is “5fbec08ad520bb97a751d49927cce0d6“.