Problem: [H&NCTF 2024]Is this Iso
思路
曾经让我陶醉的碎片
EXP
from Crypto.Util.number import *
from random import *
import itertools
from tqdm import tqdm
def nextPrime(p):
while(not isPrime(p)):
p += 1
return p
p =
deg1 = 2
deg2 = 5
leak1 =
leak2 =
leak3 =
leak4 =
n =
cipher =
F.<i> = GF(p^2, modulus = x^2 + 1)
E = EllipticCurve(j=F(1728))
assert E.is_supersingular()
# Begin solving
Fp = GF(p)
a1, b1, a2, b2 = F["a1,b1,a2,b2"].gens()
PR_Fp = Fp["a1,b1,a2,b2"]
j1 = a1 + b1 * i
j2 = a2 + b2 * i
f = classical_modular_polynomial(deg1)
f0 = f(j1, j2)
res_real = PR_Fp(f0.map_coefficients(lambda c: c.polynomial()[0]))
res_imag = PR_Fp(f0.map_coefficients(lambda c: c.polynomial()[1]))
a1, b1, a2, b2 = PR_Fp.gens()
PR.<u> = Fp[]
for b1l, a2l in tqdm(itertools.product(range(2^5), repeat=2), total=int(2^10)):
b1_ = leak2+b1l
a2_ = leak3+a2l
res_real_ = res_real(a1, b1_, a2_, b2)
res_imag_ = res_imag(a1, b1_, a2_, b2)
res_1 = res_real_.sylvester_matrix(res_imag_, b2).det()
res_u = res_1(u, 0, 0, 0)
sol = res_u.roots()
for x_, alpha in sol:
if ZZ(x_) >> 400 << 400 == leak1:
print("AOLIGEI!!!")
a1_ = x_
print(f"{a1_ = }, {b1_ = }, {a2_ = }")
res_real_ = res_real(a1_, b1_, a2_, u)
res_imag_ = res_imag(a1_, b1_, a2_, u)
sol_real_ = res_real_.roots()
sol_imag_ = res_imag_.roots()
sol_real_ = [x_ for x_, alpha in sol_real_]
sol_imag_ = [x_ for x_, alpha in sol_imag_]
sol = list(set(sol_real_) & set(sol_imag_))
assert len(sol) == 1
b2_ = sol[0]
print(f'{b2_ = }')
break
else:
continue
break
j2_ = a2_ + b2_ * i
f = classical_modular_polynomial(deg2)
PR.<u> = Fp[]
f0 = f(j2_, u)
sol = f0.roots()
for j3, alpha in sol:
p = nextPrime(int(j3[0]))
if n % p == 0:
break
else:
raise Exception("GG")
q = n // p
e = 65537
d = inverse_mod(e, (p-1)*(q-1))
m = pow(cipher, d, n)
print(f'{long_to_bytes(int(m)) = }')
总结
全都散落在街边