[CISCN 2021华南]small chen_xing的WriteUp

参考博客,二元Coppersmith.

# -*- coding: utf-8 -*-
# @Author  : chen_xing
# @Time    : 2024/12/22 下午8:25
# @File    : small.py
# @Software: PyCharm
from hashlib import *
from itertools import *
p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []
R.<x,y>=Zmod(p)[]
f=(1 + a * x * y ** 2 + b * x ** 2 * y)-c
x,y=small_roots(f,bounds=(2**70,2**71))[0]
m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
flag = "NSSCTF{" + h.hexdigest() + "}"
print(flag)
# NSSCTF{e94e1ea0b945c6573b64ae79f0ebf33d5a585398c183a6752c74c3826bceb74c}