TSG Live CTF 10 | flag in prime

#tsg_live_ctf_10

#!/usr/bin/python3

from Crypto.Util.number import getPrime
from flag import flag
from sympy import nextprime

dummy = b"GSTDIVE{this is a dummy}"

dm = int.from_bytes(dummy,'little')


assert(len(flag)==61)
import secrets

flag = secrets.token_bytes(3) + flag
flag_p = int.from_bytes(flag,'little')

p = nextprime(flag_p)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)


c = pow(dm, e, N)

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')
print(f'd = {d}')

RSA で 。が渡されているのでhow to factorize N given dで素因数分解すれば良い。

def factorize(N, e, d):
    from math import gcd
    import gmpy2

    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 3
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)

N = 64520526206097404524024211452645852957657084409556148815916386603769166536998975736753692795261222675204121710517188186945869080954167583419070284387863080205316630949575873419149459806301249360206332929794859864056972262453615731343854031268502264887263522429964730707941853636820684818445835405297913159581
e = 65537
c = 50405602561258249457621481698900557458256424040628069593118822621959449536444269183670934689019723246761133694592779464827597609507900890129476767005708848340986527063010425161275694280120584662908496135551811572898509656387262083100584848084699892597348505793637952094147620804746858241409887346156434122126
d = 36283381804564136956725396540690951840249810731559147727399765449775129052612985806156176632579342382084134239301630691516090223515965733660525128265173767745066453071398348349612057022894341970667872937142653296911628076422501528249530803106046348685331064115618316391099491213322810712206266874335390193473

p,  q = factorize(N, e, d)

for d in range(2**24):
    m = (q - d).to_bytes(64, "little").strip(b"\0")
    if len(m) != 64:
        continue

    print(m)