Circle City Con CTF 2021 | No Stone Left Unturned

#circle_city_con_2021

from gmpy2 import next_prime, is_prime
import random, os, sys

if __name__ == "__main__":
    random.seed(os.urandom(32))
    p = next_prime(random.randrange((1<<1024), (1<<1024) + (1<<600)))
    pp = (p * 7) // 11
    q = next_prime(random.randrange(pp - (1<<520), pp + (1 << 520)))
    with open(sys.argv[1], "rb") as f:
        flag = int.from_bytes(f.read(), "big")
    assert is_prime(p)
    assert is_prime(q)
    N = p * q
    assert flag < N
    e = 0x10001
    c = pow(flag, e, N)
    with open("out.txt", "w") as f:
        f.write(f"N = {hex(N)}\n")
        f.write(f"e = {hex(e)}\n")
        f.write(f"c = {hex(c)}\n")

$q = \frac{7}{11}p + \alpha$ であるようなSuspicious Prime RSA 。まず思い出すのは CONFidence CTF 2019 Teaser|Really Suspicious AcronymやMidnightsun CTF 2021 Quals | ocat_024 だが、これらの方法ではうまく行かない。なぜ？

そこで $11q = 7p + 11\alpha$ すなわち $11q \simeq 7p$ であることに着目すると

$11 \cdot 7 \cdot n = 7p \cdot 11q = 7p \cdot (7p + 11\alpha) \approx (7p)^2$

よってフェルマー法が有効

$n = x^2 - a^2$ を満たす $x, a$ で、これは $\frac{7p+7p \pm 11\alpha}{2}$ であるが、もっと簡単に表して $\frac{7p \pm 11q}{2}$ である

N = 0xa2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba93f56d1e890d1827d8ae8d40172a2dfafaa73523dd318c608bd4169d702442e6d153ae0637766f635255f4c1ee6bc694589b2708ae9061fb84f9db9da7199996c519635decfb53b4ccfde2bf9e89f70de9172bd370be887e8e1009b278774ee2449ce3ea3b76428506b4a98beda6e3c9aabbf1164e088f27554282d7909ef2ae61fb5316e705e3ea72cba9df06af06e54c3ee898dab8ed245e26290f59feeec9f58e61c4a2051086234fe48b42399a74452b87829da28f3e88a5a4b01b72d045b296297a3da34b9a5c20cb
e = 0x10001
c = 0x2d1f77201435e00d3355246cc4de54b3c98a801f688500ff1e824d985f225f95415019188af01c39c80393e648e5e51bab80e1abfda82a74490fe58ef82afde4bed2999b10ac71f241f20564f5d2461cd57b50033c0fe64319b246ad241846b2ab37328f83d0a77fe5c3564cec18dbc577fdacad417925d208735d8b916779f567ef863dba594d9d035c99e6210db9397797c10e900a1d4a3bce2f87502c23f2e909808c10ac675affb41b3e0769360c959289338ce2877813c723524718d84a75b2209ba4f3560fcbc82da69d6b2f86c32970b325ec034a060fc62f6b3a97ae01cdfc8aeb35df03d92af88a7b60831254095fb66ce73b2c5941440721899dc1

import gmpy2
def fermat(n):
    x = gmpy2.isqrt(n)
    a = x*x - n
    while not gmpy2.is_square(a):
        x += 1
        a = x*x - n
    return x, gmpy2.isqrt(a) # int(x - gmpy2.isqrt(a)), int(x + gmpy2.isqrt(a))

a, b = fermat(11 * 7 * N)
if (a + b) % 7 == 0:
    p = (a + b) // 7
    q = N // p
else:
    p = (a + b) // 11
    q = N // p
assert N % q == 0


d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, N)

print(bytes.fromhex(hex(m)[2:]))