from Crypto.Util.number import * from secret import flag, x, y def keygen(nbit): p, q = [getPrime(nbit) for _ in range(2)] return (p, q) p, q = keygen(1024) n = p * q t = len(flag)//2 part1 = bytes_to_long(flag[:t]) part2 = bytes_to_long(flag[t:]) D = 1117 x = y = assert x2 - D * y2 == 1 enc1 = pow(233 * n ** 2 + 1, part1, n ** 3) enc2 = pow(y * n + 1, part2, n ** 3) print(f'n = {n}') print(f'enc1 = {enc1}') print(f'enc2 = {enc2}')请解密出flag

这是一个加密脚本，使用了同余式加密（CRT）。

首先，我们需要求出 $p$ 和 $q$，然后计算 $n$。这一部分的代码如下：

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

def keygen(nbit):
    p, q = [getPrime(nbit) for _ in range(2)]
    return (p, q)

p, q = keygen(1024)
n = p * q

接下来，我们需要求出 $y$，满足 $x^2 - Dy^2 = 1$。这可以使用 Sympy 库来求解。

from sympy import *

D = 1117
x = y = symbols('x y')
eq = Eq(x**2 - D*y**2, 1)
sol = solve(eq, (x, y))
x, y = sol[0]

现在，我们已经有了所有的加密参数，可以开始解密了。首先，我们需要求出 $p$ 和 $q$ 的质因数分解。

from sympy import factorint

factors = factorint(n)
p, q = factors.keys()

接下来，我们需要计算 $u_1 = (233n^2+1)^{p-1} \mod p$ 和 $u_2 = (233n^2+1)^{q-1} \mod q$。

u1 = pow(233*n**2+1, p-1, p)
u2 = pow(233*n**2+1, q-1, q)

现在，我们可以使用 CRT 来计算 $v = (u_1 \cdot q \cdot (q^{-1} \mod p) + u_2 \cdot p \cdot (p^{-1} \mod q)) \mod n$。

from Crypto.Util.number import inverse

v = (u1*q*inverse(q, p) + u2*p*inverse(p, q)) % n

最后，我们可以使用 $y$ 来解密第二部分的密文，并将其与第一部分的密文合并得到原始的字节串。

enc1 = ...
enc2 = ...

part1 = pow(enc1, inverse((p-1)*(q-1), n), n)
part2 = pow(enc2, (p+1)//4 * (q+1)//4, n)

flag = long_to_bytes(part1) + long_to_bytes(part2)
print(flag)

完整的解密代码如下：

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

def keygen(nbit):
    p, q = [getPrime(nbit) for _ in range(2)]
    return (p, q)

p, q = keygen(1024)
n = p * q

D = 1117
x = y = symbols('x y')
eq = Eq(x**2 - D*y**2, 1)
sol = solve(eq, (x, y))
x, y = sol[0]

factors = factorint(n)
p, q = factors.keys()

u1 = pow(233*n**2+1, p-1, p)
u2 = pow(233*n**2+1, q-1, q)

v = (u1*q*inverse(q, p) + u2*p*inverse(p, q)) % n

t = len(flag)//2
enc1 = int(input("enc1:"))
enc2 = int(input("enc2:"))

part1 = pow(enc1, inverse((p-1)*(q-1), n), n)
part2 = pow(enc2, (p+1)//4 * (q+1)//4, n)

flag = long_to_bytes(part1) + long_to_bytes(part2)
print(flag)