Crypto CTF 2021 | Hamul

cryptoctf2021 rsa msb lsb

#cryptoctf2021

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    P = int(str(p) + str(q))
    Q = int(str(q) + str(p))
    PP = int(str(P) + str(Q))
    QQ = int(str(Q) + str(P))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
    c = pow(m, 65537, n)
    print('n =', n)
    print('c =', c)

RSAで、 p, qを文字列として連結した PP = p|q|q|p, QQ=q|p|p|qが素因数になっている

MSBやLSBは、だいたい p*qになっているはずなのでそれを考えてやればいい。 p*qのMSBをMBSから、LSBをLSBからとって（だいたい20桁 / 20桁ずつ？）つないで素因数分解してみていい感じになれば勝ちという世界観

2^{64} \approx 10^{19}なのでだいたい前後18文字くらいまでは安全で、3〜4文字を全探索する感じになる

digits = "0123456789"
MSB = str(n)[:18]
LSB = str(n)[-19:]
for d in product(digits, repeat=3):
    print(MSB + "".join(d) + LSB)