# AlexCTF: CR4: Poor RSA - 200 pts

Get modulus and exponent from public key

# openssl rsa -pubin -inform PEM -text -noout < key.pub
Public-Key: (399 bit)
Modulus:
    52:a9:9e:24:9e:e7:cf:3c:0c:bf:96:3a:00:96:61:
    77:2b:c9:cd:f6:e1:e3:fb:fc:6e:44:a0:7a:5e:0f:
    89:44:57:a9:f8:1c:3a:e1:32:ac:56:83:d3:5b:28:
    ba:5c:32:42:43
Exponent: 65537 (0x10001)

Factor the modulus with factordb

# python -c 'print 0x52a99e249ee7cf3c0cbf963a009661772bc9cdf6e1e3fbfc6e44a07a5e0f894457a9f81c3ae132ac5683d35b28ba5c324243'
833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019
863653476616376575308866344984576466644942572246900013156919
965445304326998194798282228842484732438457170595999523426901

Generate a private key and decrypt the flag

# ipython

In [1]: import gmpy

In [2]: p = 863653476616376575308866344984576466644942572246900013156919

In [3]: q = 965445304326998194798282228842484732438457170595999523426901

In [4]: e = 65537L

In [5]: d = long(gmpy.invert(e,(p-1)*(q-1)))

In [6]: n = p * q

In [7]: from Crypto.PublicKey import RSA

In [8]: key = RSA.construct((n,e,d))

In [9: f = open('flag.b64')

In [10]: edata = f.read()

In [11]: f.close()

In [12]: import base64

In [13]: key.decrypt(base64.b64decode(edata))
Out[13]: 
'ALEXCTF{SMALL_PRIMES_ARE_BAD}'