LINE CTF 2021 - Crypto - babycrypto3

TL;DR

公開鍵（PEMフォーマット）と暗号文が与えられる。

解法

公開鍵を見る。

code:txt

$ openssl rsa -pubin -inform PEM -text -noout < pub.pem

Public-Key: (394 bit)

Modulus:

03:28:b1:41:39:a2:e5:4b:88:a4:66:2f:1a:67:cc:

3a:cd:19:29:c9:b6:27:94:bb:64:91:6a:ff:02:99:

1f:80:45:6e:4d:0e:ed:4d:59:1d:f7:70:8d:5a:f2:

e9:b4:fb:56:89

Exponent: 65537 (0x10001)

n = 31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337

nが394 bit。512 bitの整数はAWSを使うと数時間で解けることは知られているので、それよりも100 bit以上小さい整数であれば簡単に解けると予想できる。

code:txt

minami@factor:~/msieve-1.53$ ./msieve -q -v -t 16 -e

Msieve v. 1.53 (SVN unknown)

Sat Mar 20 10:16:39 2021

random seeds: 341f86e1 eead51a2

factoring 31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337 (119 digits)

searching for 15-digit factors

searching for 20-digit factors

searching for 25-digit factors

200 of 214 curves

completed 214 ECM curves

searching for 30-digit factors

ECM stage 2 factor found

p42 factor: 291664785919250248097148750343149685985101

p78 factor: 109249057662947381148470526527596255527988598887891132224092529799478353198637

elapsed time 00:01:27

求めた素数を使って復号する。

code:a.py

from Crypto.PublicKey import RSA

from Crypto.Util.number import long_to_bytes, bytes_to_long

f = open('pub.pem', 'r')

key = RSA.importKey(f.read())

p = 291664785919250248097148750343149685985101

q = 109249057662947381148470526527596255527988598887891132224092529799478353198637

with open('ciphertext.txt', 'rb') as f:

c = bytes_to_long(f.read())

d = pow(key.e, -1, (p-1)*(q-1))

m = pow(c, d, key.n)

print(long_to_bytes(m))

code:txt

❯ python a.py

b'\x02`g\xff\x85\x1e\xcd\xcba\xe5\x0b\x83\xa5\x15\xe3\x00Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg==\n'

❯ echo -n Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg== | base64 -d

CLOSING THE DISTANCE.

LINECTF{CLOSING THE DISTANCE.}