TokyoWesterns CTF 6th 2020 | sqrt - crypto-writeup-public

from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p


def encrypt(m, k, p):
    return pow(m, 1 << k, p)


assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)

k = 64
pt = bytes_to_long(flag.encode())
ct = encrypt(pt, k, p)

with open("output.txt", "w") as f:
    f.write(str(ct) + "\n")
    f.write(str(p) + "\n")

すごくシンプルな問題。 $m^{2^{64}} \equiv c \mod p$

RSAっぽく解くのは出来なくて、なぜなら $gcd(2^{64}, p-1) \ne 1$ だから。ということはdiscrete_logを解くことになる。愚直にはmodular sqrtを4回やれば良いように見えるが、そうすると $2^{64}$ 個の候補が生じてしまい駄目。