SECCON CTF 2022 Quals | pqpq

#SECCON_CTF_2022_Quals

#kurenaif

from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)

assert m < n

c1p = pow(p, e, n)
c1q = pow(q, e, n)
cm = pow(m, e, n)
c1 = (c1p - c1q) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")

RSA。やが暗号化されているのでとりあえずgcdを取ることでが手に入る。あとはで暗号化されているため、RSAを解いてからRabinCryptosystemを解くような形で解の候補を求めればよい。

nth-rootしてからCRTするかたちでやった

from math import gcd
from random import randint
from itertools import product
from ptrlib import crt


def legendre(a, p):
    return pow(a, (p - 1) // 2, p)


def tonelli(n, p):
    assert legendre(n, p) == 1, "not a square (mod p)"
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r


def all_roots(known_root, e, p):
    proots = set()
    while len(proots) < e:
        proots.add(pow(randint(2, p-1), (p - 1) // e, p))

    roots = set()
    for root in proots:
        roots.add(known_root * root % p)

    return roots


with open("output.txt") as f:
    _ = int(f.readline().strip().split(" = ")[1])
    n = int(f.readline().strip().split(" = ")[1])
    c1 = int(f.readline().strip().split(" = ")[1])
    c2 = int(f.readline().strip().split(" = ")[1])
    cm = int(f.readline().strip().split(" = ")[1])

p = gcd(c1 + c2, n)
q = gcd(c1 - c2, n)
r = n // (p * q)

e = 65537
d = pow(e, -1, (p-1)*(q-1)*(r-1))

c2 = pow(cm, d, n)

mps = all_roots(tonelli(c2, p), 2, p)
mqs = all_roots(tonelli(c2, q), 2, q)
mrs = all_roots(tonelli(c2, r), 2, r)


for mp, mq, mr in product(mps, mqs, mrs):
    m, _ = crt([(mp, p), (mq, q), (mr, r)])
    print(m.to_bytes(200, "big"))