Leaky RSA - RTACTF upsolve

問題

from Crypto.Util.number import getPrime, isPrime, inverse
import os

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p = getPrime(600)
    q = getPrime(500)
    n = p*p*q*q
    e = 65537
    s = ((p**3 - 20211219*q) * inverse(p*p+q*q,n)) % n # tekitou (ha?)

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"c = 0x{c:x}")
    print(f"s = 0x{s:x}")

RSAのようですが、であることと、が与えられていることが特徴的です。

解法

が成り立つのでCoppersmith Methodで解けます。

with open("output.txt") as f:
    n = int(f.readline().strip().split(" = ")[1], 16)
    e = int(f.readline().strip().split(" = ")[1], 16)
    c = int(f.readline().strip().split(" = ")[1], 16)
    s = int(f.readline().strip().split(" = ")[1], 16)


PR.<q> = PolynomialRing(Zmod(n))
f = q^2*s + 20211219*q
f = f.monic()

for r in f.small_roots(X=2**500, beta=0.25, epsilon=0.01):
    if r == 0:
        continue
    q = int(r)
    p = Integer(n // q^2).nth_root(2, 1)[0]

    n = p^2*q^2
    phi = (p^2 - p)*(q^2 - q)

    d = int(pow(e, -1, phi))
    m = (pow(c, d, n))

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