six seven again — LA CTF 2026 Crypto Writeup

Category: Crypto Difficulty: Medium Points: 164 Solves: 114 Flag: lactf{n_h4s_1337_b1ts_b3c4us3_667+670=1337} Solved by: Smothy @ 0xN1umb

"Six of one, seven of another... but Coppersmith don't care about the difference."

Challenge Description

six seven again — AVDestroyer LA CTF will take place on February 6 and February 7, 2026. nc chall.lac.tf 31181

We're given chall.py — a textbook RSA setup, except p is generated in a very specific way. Each connection gives fresh n and c, so we need to solve it programmatically. Let's gooo.

TL;DR

RSA where p is a 201-digit prime made of 67 sixes, 67 random {6,7} digits, and 67 sevens. The unknown middle part is only ~220 bits — well within Coppersmith's N^(1/4) ≈ 334 bit bound. One small_roots() call and it's GG. Lattice go brrr.

Initial Recon

Download the source and take a look:

def generate_super_67_prime() -> int:
    while True:
        digits = ["6"] * 67
        digits += [secrets.choice("67") for _ in range(67)]
        digits += ["7"] * 67
        test = int("".join(digits))
        if isPrime(test, false_positive_prob=1e-12):
            return test

p = generate_super_67_prime()
q = getPrime(670)
n = p * q
e = 65537
c = pow(m, e, n)

So p is a 201-digit prime with a very constrained structure:

• First 67 digits: all 6s
• Middle 67 digits: each randomly 6 or 7
• Last 67 digits: all 7s

And q is a standard 670-bit random prime. Classic RSA otherwise.

The first thing that jumps out: we know 2/3 of p's digits exactly. The only unknown is the middle 67 digits, and each of those can only be one of two values. That's only 2^67 possibilities — way too many to brute force, but suspiciously little entropy for a prime this size.

Step 1: Understanding the Prime Structure

Let's decompose p mathematically:

Where δ is the unknown middle part. Each digit of δ (offset by 6) is either 0 or 1:

So δ_max = 111...1 (67 ones) = (10^67 - 1)/9 ≈ 10^66 ≈ 2^220

We can write: p = p₀ + δ × 10^67 where p₀ is completely known.

Step 2: The Coppersmith Insight

Here's where the magic happens. We have a linear polynomial modulo a factor of n:

with a small root x = δ where |δ| < X ≈ 2^220.

Coppersmith's theorem says: for a monic polynomial f(x) of degree d with a root modulo a factor b ≥ N^β of N, we can find roots bounded by |x| < N^(β²/d).

For our case:

• d = 1 (linear polynomial)
• β ≈ 0.5 (since p ≈ q ≈ √n)
• Bound: X < N^(0.25) ≈ 2^(1337/4) ≈ 2^334

Our unknown: δ < 2^220. Since 220 < 334, the bound is comfortably satisfied!

Step 3: Why 1337 Bits?

The flag basically spoils the joke, but it's still satisfying to verify:

667 + 670 = 1337. The whole challenge is a leet speak joke. Respect.

Step 4: The Solve

The actual solve is clean. Connect to the server, grab n and c, then run Coppersmith:

# Make the polynomial monic (required by SageMath)
P.<x> = PolynomialRing(Zmod(n))
mult_inv = pow(10**67, -1, n)
c_const = (p0 * mult_inv) % n
f = x + c_const

# Coppersmith magic — finds δ instantly
roots = f.small_roots(X=X, beta=0.499, epsilon=0.1)

Under the hood, SageMath constructs a lattice from shift polynomials of f, runs LLL reduction, and extracts a short vector that encodes the small root. For a linear polynomial, the lattice is as small as 2×2 with the right parameters.

And just like that — p drops, q = n/p, standard RSA decryption, flag.

The Flag

Breaking it down:

• n_h4s_1337_b1ts → n has 1337 bits
• b3c4us3_667+670=1337 → because 667 + 670 = 1337

The Solve Script

#!/usr/bin/env sage
"""six seven again — LA CTF 2026
Coppersmith small roots on structured RSA prime
Smothy @ 0xN1umb"""

def long_to_bytes(n):
    return n.to_bytes((n.bit_length() + 7) // 8, 'big')

n = <from server>
c = <from server>
e = 65537

# Known structure of p
sixes_67 = int("6" * 67)
sevens_67 = int("7" * 67)
p0 = sixes_67 * 10^134 + sixes_67 * 10^67 + sevens_67
mult = 10^67
X = (10^67 - 1) // 9 + 1  # ~2^220

# Monic polynomial: f(x) = x + p0/mult mod n
P.<x> = PolynomialRing(Zmod(n))
mult_inv = int(pow(int(mult), -1, int(n)))
c_const = (p0 * mult_inv) % n
f = x + c_const

# Coppersmith — finds the unknown middle digits
roots = f.small_roots(X=X, beta=0.499, epsilon=0.1)

for root in roots:
    x0 = int(root)
    p_cand = int(p0 + x0 * mult)
    from math import gcd
    g = gcd(p_cand, n)
    if 1 < g < n:
        p = g
        q = n // p
        phi = (p-1)*(q-1)
        d = int(pow(e, -1, phi))
        m_val = int(pow(c, d, n))
        flag = long_to_bytes(m_val)
        print(f"Flag: {flag}")

The Graveyard of Failed Attempts

Attempt 1: fpylll without SageMath

Tried implementing Coppersmith manually using fpylll's LLL. Built the 2×2 lattice [[n, 0], [p0, mult*X]], ran LLL, tried extracting the root as x0 = -v0 * X / v1... got non-exact divisions every time. The lattice was finding short vectors, but root extraction from raw LLL output is finicky without SageMath's small_roots() doing the heavy lifting.

Attempt 2: Larger fpylll Lattices (Howgrave-Graham shifts)

Scaled up to 7×7, 9×9, 11×11 lattices with shift polynomials N^{m-i} * f(x)^i. LLL ran fine, but extracting polynomial roots from the reduced basis without a proper polynomial GCD implementation was painful. The polynomial root-finding over integers for degree > 1 needs either SymPy or SageMath.

Attempt 3: Neighborhood Search

After getting approximate roots from LLL, tried searching ±1000 around the approximation. Didn't find anything — the approximation wasn't close enough without proper Howgrave-Graham bounds checking.

The Fix: Docker SageMath

Realized the SageMath Docker image was already pulled. One docker run later, small_roots() found the root in under a second with beta=0.499, epsilon=0.1. Sometimes you just gotta use the right tool.

Key Takeaways

1. Structured primes = Coppersmith. If you know parts of a prime factor and the unknown is less than N^(1/4), Coppersmith's method is your best friend.

2. The monic polynomial requirement in SageMath's small_roots() is a common gotcha. Divide by the leading coefficient mod n before calling it.

3. Start with large epsilon. epsilon=0.1 creates a tiny lattice and runs fast. Only decrease it if you need to push closer to the theoretical bound.

4. Don't fight without SageMath. For lattice-based crypto attacks, SageMath's small_roots() saves hours of manual lattice construction. Keep a Docker image ready.

5. Count the bits. 667 + 670 = 1337. The challenge author knew exactly what they were doing.

Tools Used

• SageMath (Docker: sagemath/sagemath) — Coppersmith small_roots()
• Python 3 + pwntools — Server interaction, PoW solving
• fpylll — Failed attempt at manual LLL (educational though)
• matplotlib — Screenshot generation
• Way too much caffeine

Writeup by Smothy from 0xN1umb team. Six of one, seven of another, but Coppersmith takes them all. GG.