Crypto CTF 2021 | Tuti

#cryptoctf2021

#!/usr/bin/env python3

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

l = len(flag)
m_1, m_2 = flag[: l // 2], flag[l // 2:]

x, y = bytes_to_long(m_1), bytes_to_long(m_2)

k = '''
000bfdc32162934ad6a054b4b3db8578674e27a165113f8ed018cbe9112
4fbd63144ab6923d107eee2bc0712fcbdb50d96fdf04dd1ba1b69cb1efe
71af7ca08ddc7cc2d3dfb9080ae56861d952e8d5ec0ba0d3dfdf2d12764
'''.replace('\n', '')

assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(int(k, 16) + x*y))

特殊なディオファントス方程式

sageに突っ込んでfactorする。こういう感じ

sage: x, y = var("x, y")

sage: f = ((x² + 1)*(y² + 1) - 2*(x - y)*(x*y - 1) - 4*x*y) / 4

sage: f.factor()

1/4*(x + 1)²*(y - 1)²

すると簡単そうになるのでを計算して、のfactorをとって、候補を列挙する

s = 992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133612
factors = [2, 2 , 3 , 11, 11 , 19 , 47 , 71 , 3449 , 11953 , 5485619 , 2035395403834744453 , 17258104558019725087 , 1357459302115148222329561139218955500171643099]
from itertools import product
from Crypto.Util.number import long_to_bytes


for pat in product([0,1], repeat=len(factors)):
    x = 1
    for i in range(len(pat)):
        if pat[i] == 1:
            x *= factors[i]

    flag_car = long_to_bytes(x - 1)
    if not flag_car.startswith(b"CCTF"):
        continue

    y = s // x
    flag_cdar = long_to_bytes(y + 1)
    print(flag_car + flag_cdar)
    quit()