CR4 Poor RSA

Crypto - 200 Points

This time Fady decided to go for modern cryptography implementations, He is fascinated with choosing his own prime numbers, so he picked up RSA once more. Yet he was unlucky again!

flag.b64 file

Ni45iH4UnXSttNuf0Oy80+G5J7tm8sBJuDNN7qfTIdEKJow4siF2cpSbP/qIWDjSi+w=

key.pub file

-----BEGIN PUBLIC KEY-----
ME0wDQYJKoZIhvcNAQEBBQADPAAwOQIyUqmeJJ7nzzwMv5Y6AJZhdyvJzfbh4/v8
bkSgel4PiURXqfgcOuEyrFaD01soulwyQkMCAwEAAQ==
-----END PUBLIC KEY-----

Writeup

Just like CR3, this challenge was based on RSA.
Looking with OpenSSL at the public key we can see the public exponent e and the modulus n.

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)

The modulus n wasn’t very big so we searched on factordb.

Bingo. factordb entry for our modulus.

At this moment, some other teams already solved this challenge before us, so thank you if you posted the factored modulus on factordb!

The same magic as with CR3

#!/usr/bin/env python2

import base64
import gmpy
from Crypto.PublicKey import RSA

content = ""
with open("key.pub") as f:
    content = f.read()

pub = RSA.importKey(content)
n = long(pub.n)
# http://factordb.com/index.php?query=833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019

p=863653476616376575308866344984576466644942572246900013156919
q=965445304326998194798282228842484732438457170595999523426901
assert(n == p*q)

e = long(pub.e)
d = long(gmpy.invert(e,(p-1)*(q-1)))

key = RSA.construct((n,e,d))

with open("flag.b64") as f:
    content = f.read()
    c = base64.b64decode(content)
    print key.decrypt(c)

'''
�&�d��#H�u6Lۮ��:ALEXCTF{SMALL_PRIMES_ARE_BAD}
'''

The flag is ALEXCTF{SMALL_PRIMES_ARE_BAD}