#【AIS3 Pre-Exam 2026 Writeup】Crypto - EasyFAULT

Reading chal.py first.

c, n, d = gen()
rows = [randbits(BITS) for _ in range(ROUNDS)]
base = randbits(WIDTH - 1) | (1 << (WIDTH - 1))

print(f"c = {c}")
print("blob = [")
for item in bundle(base):
    print(f"    {item},")
print("]")
print("data = [")
for i, row in enumerate(rows):
    print(f"    ({row ^ f(base, i)}, {pow(c, d ^ row, n)}),")
print("]")

The RSA part is a bit special. d is only 448 bits, but n is around 2688 bits. The output gives many values:

y_i = c^(d xor row_i) mod n

The row_i values are masked:

x_i = row_i xor f(base, i)

The first target is base.

bundle(base) looked strange at first:

total = -base * bias[j]
for i in range(NBITS):
    total += coeffs[i] * cols[i][j]
vals.append(total % mod)

There are 72 rows, but only 32 hidden bit columns. That means many short integer relations should kill the 32 column terms. I first thought maybe Z3 could solve the 0/1 columns directly, but the constraints were not nice enough. It kept timing out or only found the zero solution. No progress there.

Sympy also had Matrix.lll(), but it failed on the scaled lattices I wanted. I installed fpylll and used that instead:

python3 -m pip install --target /tmp/fpylll fpylll cysignals

For the first lattice, I used both moduli at the same time:

[ e_j | vals1[j] * Q | vals2[j] * Q ]
[  0  | mod1 * Q    | 0            ]
[  0  | 0           | mod2 * Q     ]

LLL gave short exact relations where:

sum(w[j] * vals1[j]) = 0 mod mod1
sum(w[j] * vals2[j]) = 0 mod mod2

The shortest ones also had:

sum(w[j] * bias1[j]) = 0
sum(w[j] * bias2[j]) = 0

Those relations are the common left kernel of the hidden columns and the two bias vectors. Another kernel lattice from them gave 32 short vectors after LLL. That matched the 32 hidden column directions.

After that, I took the left kernel of those 32 short vectors. This gives a relation w that kills the hidden columns, but not necessarily the bias. For such a relation:

sum(w[j] * vals[j]) = -base * sum(w[j] * bias[j]) mod mod

So:

base = -sum(w[j] * vals[j]) * inverse(sum(w[j] * bias[j]), mod) mod mod

Both moduli gave the same 192-bit value:

base = 6226901257745988517400304262260068971526607509066332027399

Now the masks are gone:

row_i = x_i ^ f(base, i)

The next part was recovering n. Since:

y_i = c^(d xor row_i) mod n

The next object is integer coefficients lambda_i that make the exponent sum zero:

sum(lambda_i * (d xor row_i)) = 0

For every bit, d xor row_i is linear if the coefficient sum and every row-bit sum are balanced:

sum(lambda_i) = 0
sum(lambda_i * bit(row_i, k)) = 0

Then:

prod(y_i^positive) - prod(y_i^negative) = 0 mod n

Taking gcd of several such differences gives a multiple of n.

The matrix here is 449 by 896:

448 bit rows from row_i
1 all-one row

A direct scaled LLL lattice for this kernel was my first try. It was slow and did not give clean zero-constraint vectors fast enough. HNF with transformation matrix worked better. python-flint made this easy:

python3 -m pip install --target /tmp/flint python-flint

HNF of M^T gave the next useful object. The zero rows in the transformed matrix were a saturated integer kernel basis. The basis was huge, so it needed several rounds of fplll.

apt-get download fplll-tools libfplll9 libfplll9-data
mkdir -p /tmp/fplll_tools
dpkg-deb -x fplll-tools_*.deb /tmp/fplll_tools
dpkg-deb -x libfplll9_*.deb /tmp/fplll_tools
dpkg-deb -x libfplll9-data_*.deb /tmp/fplll_tools
export FPLLL=/tmp/fplll_tools/usr/bin/fplll
export LD_LIBRARY_PATH=/tmp/fplll_tools/usr/lib/x86_64-linux-gnu:$LD_LIBRARY_PATH

After LLL, the relation coefficients were around a few thousand. Large, but usable. Big integer products were still slow in Python, so gmpy2 helped.

python3 -m pip install --target /tmp/gmpy2 gmpy2

The first few gcds still had a huge common cofactor. Most of it was just small prime powers. Trial division by small primes left the 2687-bit RSA modulus.

One more relation is needed for the flag. This time I want:

sum(lambda_i) = 1
sum(lambda_i * bit(row_i, k)) = 0

Then:

sum(lambda_i * (d xor row_i)) = d

So:

c^d = prod(y_i^positive) * inverse(prod(y_i^negative), n) mod n

That value is the plaintext flag.

Full solve script:

#!/usr/bin/env python3
import ast
import os
import re
import subprocess
import sys
from hashlib import shake_256
from pathlib import Path

sys.set_int_max_str_digits(0)

sys.path[:0] = [
    "/tmp/fpylll",
    "/tmp/flint",
    "/tmp/gmpy2",
]

import gmpy2
from Crypto.Util.number import long_to_bytes
from flint import fmpz_mat
from fpylll import IntegerMatrix, LLL
from sympy import primerange


BITS = 448
WIDTH = 192
NBITS = 32
NROWS = 72

ROOT = Path(__file__).resolve().parent
OUT = ROOT / "output.txt"
FPLLL = os.environ.get("FPLLL", "fplll")


def parse_output():
    text = OUT.read_text()
    c = int(re.search(r"c = (\d+)", text).group(1))
    blob = ast.literal_eval(re.search(r"blob = (\[.*?\])\ndata =", text, re.S).group(1))
    data = ast.literal_eval(re.search(r"data = (\[.*\])", text, re.S).group(1))
    return c, blob, data


def f(base, idx):
    buf = shake_256(base.to_bytes(WIDTH // 8, "big") + idx.to_bytes(4, "big")).digest(BITS // 8)
    return int.from_bytes(buf, "big")


def solve_base(blob):
    (p1, b1, v1), (p2, b2, v2) = blob
    n = NROWS
    q = 1 << 160

    mat = IntegerMatrix(n + 2, n + 2)
    for j in range(n):
        mat[j, j] = 1
        mat[j, n] = v1[j] * q
        mat[j, n + 1] = v2[j] * q
    mat[n, n] = p1 * q
    mat[n + 1, n + 1] = p2 * q

    LLL.reduction(mat, delta=0.99)

    rels = []
    for i in range(n + 2):
        row = [int(mat[i, j]) for j in range(n + 2)]
        w = row[:n]
        if not any(w):
            continue
        if row[n] == 0 and row[n + 1] == 0:
            if sum(w[j] * b1[j] for j in range(n)) == 0:
                if sum(w[j] * b2[j] for j in range(n)) == 0:
                    rels.append(w)

    rels = rels[:38]

    scale = 1 << 20
    mat2 = IntegerMatrix(n, n + len(rels))
    for j in range(n):
        mat2[j, j] = 1
        for i, rel in enumerate(rels):
            mat2[j, n + i] = rel[j] * scale

    LLL.reduction(mat2, delta=0.99)

    short = []
    for i in range(n):
        row = [int(mat2[i, j]) for j in range(n + len(rels))]
        if all(row[n + k] == 0 for k in range(len(rels))):
            vec = row[:n]
            if any(vec) and max(abs(x) for x in vec) <= 2:
                short.append(vec)

    short = short[:NBITS]

    mat3 = IntegerMatrix(n, n + len(short))
    for j in range(n):
        mat3[j, j] = 1
        for i, vec in enumerate(short):
            mat3[j, n + i] = vec[j] * scale

    LLL.reduction(mat3, delta=0.99)

    for i in range(n):
        row = [int(mat3[i, j]) for j in range(n + len(short))]
        if not all(row[n + k] == 0 for k in range(len(short))):
            continue
        w = row[:n]
        if not any(w):
            continue

        sb1 = sum(w[j] * b1[j] for j in range(n))
        sb2 = sum(w[j] * b2[j] for j in range(n))
        if sb1 == 0 or sb2 == 0:
            continue

        sv1 = sum(w[j] * v1[j] for j in range(n))
        sv2 = sum(w[j] * v2[j] for j in range(n))
        base1 = (-sv1 * pow(sb1, -1, p1)) % p1
        base2 = (-sv2 * pow(sb2, -1, p2)) % p2

        if base1 == base2 and base1.bit_length() <= WIDTH:
            return base1

    raise RuntimeError("base not found")


def write_fplll_matrix(path, rows):
    with open(path, "w") as fp:
        fp.write("[\n")
        for row in rows:
            fp.write("[" + " ".join(map(str, row)) + "]\n")
        fp.write("]\n")


def read_fplll_matrix(path):
    rows = []
    for line in open(path):
        line = line.strip()
        if not line or line in "[]":
            continue
        rows.append([int(x) for x in line.strip("[]").split()])
    return rows


def run_fplll(src, dst, delta):
    env = os.environ.copy()
    extra_lib = "/tmp/fplll_tools/usr/lib/x86_64-linux-gnu"
    if Path(extra_lib).exists():
        old = env.get("LD_LIBRARY_PATH", "")
        env["LD_LIBRARY_PATH"] = extra_lib + (":" + old if old else "")

    subprocess.run(
        [FPLLL, "-a", "lll", "-m", "wrapper", "-d", str(delta), "-e", "0.501", "-y", src],
        check=True,
        stdout=open(dst, "w"),
        env=env,
    )


def build_relation_lattice(rows):
    n = len(rows)
    m = BITS + 1

    mt = fmpz_mat(n, m)
    for i, row in enumerate(rows):
        x = row
        while x:
            low = x & -x
            bit = low.bit_length() - 1
            mt[i, bit] = 1
            x -= low
        mt[i, BITS] = 1

    hnf, trans = mt.hnf(transform=True)

    kernel = []
    for i in range(n):
        if all(hnf[i, j] == 0 for j in range(m)):
            kernel.append([int(trans[i, j]) for j in range(n)])

    return kernel, hnf, trans


def reduce_kernel(kernel):
    tmp = Path("/tmp/easyfault_kernel.txt")
    r1 = Path("/tmp/easyfault_kernel.r1")
    r2 = Path("/tmp/easyfault_kernel.r2")
    r3 = Path("/tmp/easyfault_kernel.r3")

    write_fplll_matrix(tmp, kernel)
    run_fplll(str(tmp), str(r1), 0.51)
    run_fplll(str(r1), str(r2), 0.75)
    run_fplll(str(r2), str(r3), 0.999)
    return read_fplll_matrix(r3)


def product_mod_relation(ys, rel, mod):
    pos = gmpy2.mpz(1)
    neg = gmpy2.mpz(1)
    for a, y in zip(rel, ys):
        y = gmpy2.mpz(y)
        if a > 0:
            pos = (pos * gmpy2.powmod(y, a, mod)) % mod
        elif a < 0:
            neg = (neg * gmpy2.powmod(y, -a, mod)) % mod
    return (pos * gmpy2.invert(neg, mod)) % mod


def product_difference(ys, rel):
    pos_terms = []
    neg_terms = []
    for a, y in zip(rel, ys):
        y = gmpy2.mpz(y)
        if a > 0:
            pos_terms.append(y ** a)
        elif a < 0:
            neg_terms.append(y ** (-a))

    def tree(values):
        values = list(values)
        if not values:
            return gmpy2.mpz(1)
        while len(values) > 1:
            values = [
                values[i] * values[i + 1] if i + 1 < len(values) else values[i]
                for i in range(0, len(values), 2)
            ]
        return values[0]

    return abs(tree(pos_terms) - tree(neg_terms))


def recover_modulus(ys, reduced_kernel):
    g = gmpy2.mpz(0)
    for rel in reduced_kernel[:120]:
        diff = product_difference(ys, rel)
        g = diff if g == 0 else gmpy2.gcd(g, diff)

    for p in primerange(2, 200000):
        while g % p == 0:
            g //= p
        if 2600 <= g.bit_length() <= 2700:
            return int(g)

    if 2600 <= g.bit_length() <= 2700:
        return int(g)
    raise RuntimeError(f"bad modulus size: {g.bit_length()}")


def target_relation_from_hnf(hnf, trans, rows):
    n = len(rows)
    m = BITS + 1

    nonzero = [i for i in range(n) if any(hnf[i, j] != 0 for j in range(m))]

    basis = fmpz_mat(m, m)
    trans_rows = []
    for out_i, row_i in enumerate(nonzero):
        for j in range(m):
            basis[out_i, j] = hnf[row_i, j]
        trans_rows.append([int(trans[row_i, j]) for j in range(n)])

    target = fmpz_mat(m, 1)
    target[BITS, 0] = 1

    sol = basis.transpose().solve(target)
    coeffs = []
    for i in range(m):
        q = sol[i, 0]
        assert q.denominator == 1
        coeffs.append(int(q.numerator))

    rel = [0] * n
    for c, row in zip(coeffs, trans_rows):
        if c:
            for j, v in enumerate(row):
                rel[j] += c * v

    # Babai reduce this target relation using the already reduced kernel.
    # fpylll CVP enumeration is limited in this build, so use Babai.
    from fpylll import CVP

    reduced = read_fplll_matrix("/tmp/easyfault_kernel.r3")
    mat = IntegerMatrix(len(reduced), n)
    for i, row in enumerate(reduced):
        for j, v in enumerate(row):
            mat[i, j] = v

    close = CVP.babai(mat, tuple(-x for x in rel))
    rel = [rel[i] + int(close[i]) for i in range(n)]

    assert sum(rel) == 1
    for bit in range(BITS):
        assert sum(rel[i] * ((rows[i] >> bit) & 1) for i in range(n)) == 0

    return rel


def main():
    c, blob, data = parse_output()

    base = solve_base(blob)
    print(f"base = {base}")

    rows = [x ^ f(base, i) for i, (x, _) in enumerate(data)]
    ys = [y for _, y in data]

    kernel, hnf, trans = build_relation_lattice(rows)
    reduced_kernel = reduce_kernel(kernel)

    n = recover_modulus(ys, reduced_kernel)
    print(f"n bits = {n.bit_length()}")

    rel = target_relation_from_hnf(hnf, trans, rows)
    m = product_mod_relation(ys, rel, n)
    print(long_to_bytes(int(m)))


if __name__ == "__main__":
    main()

After installing the lattice / integer libraries, the script printed:

b'AIS3{lll_then_lll_then_lll_then_lll_owob}'

Flag:

AIS3{lll_then_lll_then_lll_then_lll_owob}