[Crypto] CR4: Poor RSA

CTFtime.org / AlexCTF / CR4: Poor RSACTFtime

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!

Given files:

• flag.b64

• key.pub

flag.b64의 내용은 아래와 같다.

Ni45iH4UnXSttNuf0Oy80+G5J7tm8sBJuDNN7qfTIdEKJow4siF2cpSbP/qIWDjSi+w=

key.pub의 내용은 아래와 같다.

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

아래 명령을 통해 public key의 정보를 얻는다.

$ openssl rsa -pubin -in key.pub -text -noout  
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)

399 비트 암호화임을 알 수 있다.

RSA-512 비트 키도 취약하다고 알려져 있는데, 399 비트는 그에 비해 더 짧아 더 취약하다.

n 값을 hex에서 decimal로 바꾸면 아래와 같다.

$ python -c "print(int('0x52a99e249ee7cf3c0cbf963a009661772bc9cdf6e1e3fbfc6e44a07a5e0f894457a9f81c3ae132ac5683d35b28ba5c324243', 16))"
833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019

decimal로 변환한 n 값을 http://factordb.com에 넣으면 아래와 같이 p와 q 값을 얻을 수 있다.

p: 863653476616376575308866344984576466644942572246900013156919
q: 965445304326998194798282228842484732438457170595999523426901

이를 참고해 파이썬 코드를 짜면 아래와 같다.

from Crypto.PublicKey import RSA
import base64
import gmpy2
import binascii

f = open('key.pub', 'r')
pub = RSA.importKey(f.read())
f.close()

n = pub.n
e = pub.e
p = 863653476616376575308866344984576466644942572246900013156919
q = 965445304326998194798282228842484732438457170595999523426901
assert(n == p * q)

f = open('flag.b64', 'r')
ct = base64.b64decode(f.read())
ct = int.from_bytes(ct, byteorder='big')
f.close()

phi = (p - 1) * (q - 1)
d = int(gmpy2.invert(e, phi))
key = RSA.construct((n, e, d))
pt = key.decrypt(ct)

try:
    print(binascii.unhexlify(hex(pt)[2:]))
except:
    print(binascii.unhexlify('0' + hex(pt)[2:]))

실행 결과는 아래와 같다.

b'\x02\x9e&\xded\xa0\x96#H\x8au6L\xdb\xae\x84\x89:\x00ALEXCTF{SMALL_PRIMES_ARE_BAD}\n'

ALEXCTF{SMALL_PRIMES_ARE_BAD}