//Huuge FAN

>Challenge Overview

In this challenge, we're given a custom signature scheme with a critical flaw that allows us to recover the private key. The system uses ECDSA-like signatures with a nonce that leaks partial information.

>Initial Analysis

Understanding the Challenge

We're provided with:

A file out.txt containing multiple signatures
The modulus m = 2^446 - 0x8335DC163BB124B65129C96FDE933D8D723A70AADC873D6D54A7BB0D
The signatures follow the form: s = (z + r*d)/k (mod m)

Where z is the message hash
r is part of the signature
d is the private key we need to recover
k is a nonce with known first 4 decimal digits

Key Observations

Each signature's N value is constructed as A * reverse(A) where A encodes 5 numbers in base B (first 4 digits of m)
The nonce k has its first 4 decimal digits leaked
The signature equation can be rewritten as: k ≡ s^(-1)*z + s^(-1)*r*d (mod m)

>Solution Approach

Step 1: Recovering Nonce Prefixes

For each signature, we need to recover the 5 nonce prefixes from N:

python


def recover_parts(N):

    N = ZZ(N)

    base4 = ZZ(str(m)[:4])

    for a in divisors(N):

        b = N // a

        da = digits_base(int(a), int(base4), num_fans)

        brec = sum(da[i]*(int(base4)**i) for i in range(num_fans))

        if brec == int(b):

            return list(map(ZZ, da))

        db = digits_base(int(b), int(base4), num_fans)

        arec = sum(db[i]*(int(base4)**i) for i in range(num_fans))

        if arec == int(a):

            return list(map(ZZ, db))

    raise ValueError('no parts found')

Step 2: Formulating the Hidden Number Problem

We can rewrite the signature equation as:


a_i * d + b_i ≡ K_i (mod m)

Where:

a_i = r_i * s_i^(-1) mod m
b_i = z_i * s_i^(-1) mod m
K_i is the known prefix of k_i (scaled appropriately)

Step 3: Lattice Construction

We construct a lattice where the solution vector contains our private key d:

python


def hnf_basis_from_a(a_list):

    n = len(a_list)

    G = matrix(ZZ, n+1, n)

    for i in range(n):

        G[i,i] = m

    G[n,:] = vector(ZZ, a_list)

    H = G.hermite_form()

    rows = [r for r in H.rows() if r != 0]

    B = matrix(ZZ, rows)

    assert B.nrows() == n and B.ncols() == n

    return B

Step 4: Solving CVP with fpylll

We use fpylll's efficient CVP solver to find the closest vector:

python


def fpylll_cvp(B, target):

    n = B.nrows()

    A = IntegerMatrix(n, n)

    for i in range(n):

        for j in range(n):

            A[i,j] = int(B[i,j])

    LLL.reduction(A)

    t = tuple(int(x) for x in target)

    v = CVP.closest_vector(A, t, method='fast')

    return vector(ZZ, list(v))

>Final Solver

Here's the complete solver script that puts everything together:

python


from sage.all import *

import ast, hashlib, random, time

from fpylll import IntegerMatrix, LLL, CVP

def solve():

    # Initialize parameters

    m = ZZ(2**446 - 0x8335DC163BB124B65129C96FDE933D8D723A70AADC873D6D54A7BB0D)

    m_len = len(str(m))

    base4 = ZZ(str(m)[:4])

    Bdec = ZZ(10)**ZZ(m_len-4)

    num_fans = 5

    # Load data

    with open('out.txt', 'r') as f:

        recordings = ast.literal_eval(f.read())

    # Process signatures

    vals = []  # (p, a, b, K, r, s, z)

    for N, signs in recordings:

        parts = recover_parts(N)

        for (msghex, r, s), p in zip(signs, parts):

            msg = bytes.fromhex(msghex)

            z = ZZ(int.from_bytes(hashlib.sha256(msg).digest(), 'big')) % m

            r = ZZ(r) % m

            s = ZZ(s) % m

            invs = inverse_mod(s, m)

            a = (r * invs) % m

            b = (z * invs) % m

            K = ZZ(p) * Bdec

            vals.append((ZZ(p), a, b, K, r, s, z))

    # [Rest of the solver code...]

    # Extract flag

    if d is not None:

        L = (m.nbits() + 7) // 8

        b = int(d).to_bytes(L, 'big')

        pos = b.find(b'nite{')

        if pos != -1:

            end = b.find(b'}', pos)

            flag = b[pos:end+1].decode()

            print(f'FLAG: {flag}')

if __name__ == '__main__':

    solve()

>Results

After running the solver, we successfully recover the flag:


FLAG: nite{1m_^_#ug3_f4n_of_8KZ!!_afa5d267f6ae51da6ab8019d1e}

>Key Insights

The nonce prefix leakage allows us to set up a system of equations with small errors
The problem reduces to finding a closest vector in a lattice
Using fpylll's optimized CVP solver is more effective than pure Sage implementations
The solution is robust against minor variations in the input signatures