solver of coooppersmith from DEFCON CTF 2020 Quals

solver.py

from pwn import *
from ctypes import *
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes as l2b, inverse, GCD as gcd
import gmpy2

s = remote("coooppersmith.challenges.ooo", 5000)

s.recvuntil(":")
s.sendline("1" + "0" * 119)

s.recvuntil('Your public key:\n')

key = s.recvuntil("-----END RSA PUBLIC KEY-----\n")
with open("key.pem", "wb") as f:
    f.write(key)
print(key)

with open("key.pem", "r") as f:
    key = RSA.import_key(f.read())

s.recvuntil("Question:")
question = s.recvuntil("\n")
print(question)

c = CDLL("/lib/x86_64-linux-gnu/libc.so.6")
c.srand(c.time(0))

rand1 = c.rand()
rand2 = c.rand()

rand_sum = rand1 + rand2

s.sendline(str(rand_sum))

s.recvuntil('Your flag message:\n')
flag = s.recvline()
s.close()

p = 1 << (119 * 4 + 32)
t = key.n - 1
while True:
    if gcd(p, t) == p:
        break
    p += 1

t //= 2 * p

for i in range(2):
    a = t % p + i * p
    if (t - a) % (2 * p) != 0:
        continue
    b = (t - a) // (2 * p)

    d = a * a - 4 * b
    dsq = gmpy2.isqrt(d)
    if dsq ** 2 != d:
        continue

    k1 = (a + dsq) // 2
    k2 = (a - dsq) // 2

    assert a == k1 + k2 and b == k1 * k2

q1 = 2 * k1 * p + 1
q2 = 2 * k2 * p + 1
assert q1 * q2 == key.n

e = 0x10001
d = inverse(e, (q1 - 1) * (q2 - 1))

flag = int(flag, 16)

flag = pow(flag, d, q1 * q2)
print(l2b(flag))