The idea this time is to crack RSA built with small prime numbers. We first needed to find the public modulus *n* and then factorize it, since:
    n = p*q
Our code to do it:
~~~~from Crypto.PublicKey import RSAimport gmpyimport base64import binascii
with open('key.pub','r') as key:    pub = RSA.importKey(key.read())
n = int(pub.n)
print(n)~~~~
[FactorDB](http://factordb.com/) is the best place I know to do it and we got very quickly the results for *p* and *q*:
~~~~# Using factordbp = 863653476616376575308866344984576466644942572246900013156919q = 965445304326998194798282228842484732438457170595999523426901~~~~
Now we can rebuild the private key. Instead of doing the same thing we did with CR3, I tried to explore *gmpy* module:
~~~~# We could also use the same algorithm we did with cr3d = int(gmpy.invert(e,(p-1)\*(q-1)))print(d)
pvt = RSA.construct((n, e, d, p, q))
print(pvt.exportKey().decode())~~~~
And here it is:
~~~~-----BEGIN RSA PRIVATE KEY-----MIH5AgEAAjJSqZ4knufPPAy/ljoAlmF3K8nN9uHj+/xuRKB6Xg+JRFep+Bw64TKsVoPTWyi6XDJCQwIDAQABAjIzrQnKBvUPnpCxrK5x85DWuS8dbTtmFP+HEYHE3wjaTF9QEkV6ZDCUBers1jQeQwJ5MQIaAImWgwYMdrnA3lgaaeDqnZG+0Qcb6x2SSjcCGgCZzedK7e6Hrf/daEy8R451mHC08gaS9lJVAhlmZEB1y+i/LC1L27xXycIhqKPeaoR6qVfZAhlbPhKLmhFavne/AqQbQhwaWT/rqHUL9EMtAhk5pem+TgbW3zCYF8v7j0mjJ31NC+0sLmx5-----END RSA PRIVATE KEY-----~~~~
For some weird reason (which I did not take the time to figure out), python3 was complaining about a charachter when decoding the flag. So instead of struggling with it forever I decided to move on and give OpenSSL a try:
    base64 -d flag.b64 | openssl rsautl -decrypt -inkey key.pvt | cat    ALEXCTF{SMALL_PRIMES_ARE_BAD}
This above simply decodes the base64 flag and uses openssl to decrypt it. And they sure do :)