Problem: [Imaginary CTF 2024]pacap
[[toc]]
思路
手动挡 coppersmith
至于为什么最后一行除以模是一个小整数的那么多次方，我他妈也不知道，试出来的
EXP
from params import *
from Crypto.Util.number import *
import itertools
from tqdm import trange
N, e = pubkey
x, y, z = enc
'''
c * v^3 = (1 - u^3)
* v^6
v^6 * x^3 + c* v^6 * y^3 + c^2*v^6*z^3 - 3*c*x*y*z*v^6 - v^6
v^6 * x^3 + (1-u^3)*v^3*y^3 + (1-u^3)^2 * z^3 - 3*x*y*z*v^3*(1-u^3) - v^6
denote u' = 1 - u^3, v' = v^3
u, v small
u^3, v^3 small
1 - u^3 small
A u^2 + B u v + C v^2
'''
A = z^3
B = y^3 - 3 * x * y * z
C = x^3 - 1
t = 5
l = len(flag)
PR.<u, v> = PolynomialRing(ZZ)
f = A * u^2 + B * u * v + C * v^2
M = N^t
monomials = [u^i *v^(2*t-i) for i in range(2*t+1)]
L = []
for i in range(t + 1):
prod_pow = t - i
for j in range(2 * prod_pow+1):
k = 2 * prod_pow - j
f_ = f^i * u^j * v^k * N^prod_pow
Li = []
for monomial_index in range(2*t+1):
Li.append(f_.coefficient({u: monomial_index, v: 2*t-monomial_index}))
L.append(Li)
def show_lattice(L):
M = []
for i in range(L.nrows()):
Mi = []
for j in range(L.ncols()):
Mi.append('X0'[L[i, j] == 0])
M.append(' '.join(Mi))
M = '\n'.join(M)
print(M)
L = matrix(ZZ, L)
show_lattice(L)
L_ = L.LLL()
coeff_ = L_[0]
print()
show_lattice(L_)
flist = []
for coeff_ in L_[-(2*t+1):]:
# build
f = sum([coeff_[i] * monomials[i] for i in range(2*t+1)])
if f != 0:
flist.append(f.change_ring(QQ))
for i in trange(1, 30):
for si in [-1, 1]:
# Monkey patch
flist_ = [f for f in flist]
flist_[-1] += si * i^(2*t) * M
V = Ideal(flist_).variety()
for sol_ in V:
u_, v_ = sol_[u], sol_[v]
try:
u_ = (1 - u_).nth_root(3)
v_ = v_.nth_root(3)
msg = long_to_bytes(int(u_)) + long_to_bytes(int(v_))
print(msg)
print(len(msg))
except:
pass
总结
一下子就……