Oh honey 我脑海里全都是你

Problem: [JQCTF 2024 Final]easyrsa

[[toc]]

思路

• l 小 可（并行）枚举
• 消去 d
• bezout 等式搞出一个近似解
• 然后只需要协调 bezout 等式使成倍数

EXP

pk = 
gift = 
enc = 


nbit = 1024


from Crypto.Util.number import *
N, e = pk
k, xh, c = gift

xh = xh << (nbit // 4)

def my_gao(l):
    PR.<u, v> = PolynomialRing(ZZ)

    f = (xh + u) * e * v - (e * c + k * l * (N - v + 1) + l)
    # A * u * v + B * v + C
    A, B, C = f.coefficients()

    g, a, b = xgcd(A, B)
    a *= -C
    b *= -C

    kk = a // B
    a -= kk * B
    b += kk * A

    F = Zmod(random_prime(2^800-1,False,2^799))
    PR.<x, y> = PolynomialRing(F)
    u_ = a + x * B
    v_ = b - x * A
    g = u_ - y * v_

    import itertools

    def small_roots(f, bounds, m=1, d=None):
        if not d:
            d = f.degree()

        if isinstance(f, Polynomial):
            x, = polygens(f.base_ring(), f.variable_name(), 1)
            f = f(x)

        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))
        t = 0
        for h in filter(None, B*monomials):
            t += 1
            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 []

    bounds = [2^201, 2^256]
    sol = small_roots(g, bounds, m=3, d=4)
    if len(sol) > 0:
        kk, xl = sol[0]
        s_ = ZZ(-C / (A * xl + B))
        t_ = ZZ(sqrt(s_^2 - 4 * N))
        p = (s_ + t_) // 2
        q = (s_ - t_) // 2
        d = inverse_mod(e, (p-1)*(q-1))
        m = pow(enc, d, N)
        print(long_to_bytes(int(m)))
        exit()

l = 0
while True:
    l += 1
    print(f'{l = }')
    my_gao(l)
​

总结

一万次悲伤~

依然会有dream~