# Tính

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

def gen(nbit, m):
    kbit = int(nbit * 0.4512)
    key = getPrime(kbit)
    
    while True:
        p = getPrime(nbit // 2 - 1)
        if isPrime(p * 2 + 1):
            p = p * 2 + 1
            break
    while True:
        q = getPrime(nbit // 2 - 1)
        if isPrime(q * 2 + 1):
            q = q * 2 + 1
            break   
    n = p * q
    phi = (p - 1) * (q - 1)
    
    e, k = [], []
    for i in range(m):
        d = key + 2 * i + 2
        ee = inverse(d, phi)
        kk = (ee * d - 1) // phi
        e.append(ee % 2 ** (nbit - kbit))
        k.append(kk)
    
    return n, e, k

n, e, k = gen(1024, 12)
enc = pow(bytes_to_long(flag), 65537, n)

with open("data.txt","w") as f:
    f.write(f"{n = }\n{enc = }\n{e = }\n{k = }\n")

Ta có:

$$
k_i = \frac{ee_id_i-1}{\phi} = \frac{ee_i(key+2i+2)-1}{\phi} \\
$$
$$
\Rightarrow \phi = \frac{ee_i(key+2i+2)-1}{k_i} \\
$$
$$
\Rightarrow \frac{ee_i(key+2i+2)-1}{k_i} = \frac{ee_j(key+2j+2)-1}
{k_j} \\
$$
$$
\Rightarrow ee_i(key+2i+2)k_j - k_j = ee_j(key+2j+2)k_i - k_i \\
$$
$$
\Rightarrow e_i(key+2i+2)k_j - k_j \equiv e_j(key+2j+2)k_i - k_i \pmod{2^{562}}
$$

vì key chỉ có 462 bit, giải phương trình trên ta được $key \bmod 2^{562} = key$
Quay lại phương trình đầu tiên:
$$
\phi{k_i} = { ee_id_i-1} \\
$$

$$
\Rightarrow \phi{k_i} \equiv -1 \pmod{d_i}
$$
$$
\Rightarrow \phi \equiv -k_i^{-1} \pmod{d_i}
$$

$\phi < 2^{1024}$, $d_i$ khoảng 462 bit
$\Rightarrow$ lọc trong $d$ khoảng 3-4 $d_i$ sao cho từng cặp bất kỳ đều nguyên tố cùng nhau, sau đó dùng thặng dư trung hoa ta sẽ tính được $\phi$
Sau khi có $\phi$, dễ dàng tìm được khóa bí mật và giải mã RSA $enc$ để lấy flag