RooterCTF 2019 ReallySillyAlgorithmLIBrary

#rooterctf2019

#!/usr/bin/env python3

from Crypto.Util.number import *
import gmpy2, binascii
from sillyLibrary import rsalib_p, rsalib_q
from secret import flag

n = rsalib_p*rsalib_q

e = 0x10001

ciphertext = binascii.hexlify(long_to_bytes(pow(bytes_to_long(flag), e, n)))

file = open('flag.enc', 'w')

file.write("ciphertext: {}\nn: {}\ne: ".format(ciphertext, str(n), str(e)))

ciphertext: 014107b18849e23cc0494a1f32d2176a0c0a497e2ad35d054941716d6a60c5be5656b369e0e4bba72fbcaba4586bc0cd352d4da34023b5a8
n: 11127212863544389237262565582342312793444654886136310133705565382574067475157051952050355000097126157942244686899397157941082263117851
e: 0x10001

問題名や rsalib_p という名前から、かつてRSALibに存在した鍵生成の脆弱性を連想しないといけない。この種の鍵生成に対する攻撃手法としてROCA(Return Of CopperSmith)があり、512bit までのNならnekaというツールで攻撃できる。

めっちゃ速い。

from Crypto.Util.number import *

p = 3851789689222186911734129440311249236982321127122393533115947118361
q = 2888842268486202984677183224410114807785901996516180457699983627091
c = bytes_to_long(
    bytes.fromhex(
        "014107b18849e23cc0494a1f32d2176a0c0a497e2ad35d054941716d6a60c5be5656b369e0e4bba72fbcaba4586bc0cd352d4da34023b5a8"
    )
)
e = 0x10001
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

m = pow(c, d, p * q)
print(long_to_bytes(m))

これは本番で解きたかったなぁ