Fword CTF 2020 | One Part

RSA だけどRSA-CRTのが与えられている。dpがわかっているときの素因数分解

from ptrlib import Socket
from Crypto.Util.number import GCD, inverse, long_to_bytes


sock = Socket("onepart.fword.wtf", 4445)
n, e = map(int, sock.recvregex(r"\((.+), (.+)\)"))
dp = int(sock.recvregex("dp : (.+)")[0])
c = int(sock.recvregex("Cipher : (.+)")[0])


a = 2
while True:
    print(a)
    x = pow(a, e * dp - 1, n) - 1
    p = GCD(x, n)
    if p != n and p != 1 and n % p == 0:
        break
    a += 1

q = n // p
if p > q:
    p, q = q, p
qp = q % p

d = inverse(e, (p-1)*(q-1))
dp = d % (p-1)
dq = d % (q-1)

m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
h = (m1 - m2) * qp % p
m = m2 + q * h

print(long_to_bytes(m))