Fractured Seal

Platform: CACTF2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: position_preserving_base64_recovery, der_offset_parsing, known_high_bits_factoring, coppersmith_method, howgrave_graham, lll_lattice_reduction, modulus_low_byte_bruteforce

Summary

Task: an RSA-2048 PKCS#1 private-key PEM is heavily redacted with '*' but keeps position-preserving base64 alignment, plus a ciphertext. Solution: decode each intact 4-char base64 group at its fixed DER offset to recover 576 high bits of a prime factor and all but the low byte of n, then factor n via Coppersmith known-high-bits (LLL) while brute-forcing the 128 odd candidate low bytes of n.

Fractured Seal — CACTF2026

Description

One of the Registry's oldest key-scrolls survived the fall of Crownspire, though time and fire spared only fragments of its writing, and most in the vault dismissed it as useless. Caldrin didn't. She always said a seal doesn't have to be whole to still remember the door it once opened.

We are given:

• encrypt.py — standard RSA-2048 (p,q = getPrime(1024), n = p*q, e = 0x10001, d = inverse(e, phi)); the flag is encrypted as c = pow(m, e, n) into flag.enc, and the private key is exported to a PEM.
• fractured_seal.pem — the RSA PRIVATE KEY PEM with large portions of its base64 body replaced by '*', and a decorative ASCII-art cat inserted mid-line.
• flag.enc — the 256-byte RSA ciphertext. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Goal: recover the private key from its surviving fragments and decrypt the flag.

Analysis

The flavor text is a direct hint: "a seal doesn't have to be whole to still remember the door it once opened" — a partial/fractured RSA private key still holds enough information to be fully reconstructed.

Key observation about the redaction: the PEM base64 body is position-preserving. Every body line is 64 characters, and the '*' redaction keeps original column alignment. Base64 encodes in independent 4-character groups (3 bytes each), so any fully-intact 4-char group can be decoded on its own and dropped at its fixed byte offset in the underlying DER structure. The ASCII-art cat is decorative noise to be stripped before column reconstruction. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

A PKCS#1 RSAPrivateKey is a DER SEQUENCE of: version, INTEGER n, INTEGER e, INTEGER d, INTEGER p, INTEGER q, then dp, dq, qinv. Decoding all surviving 4-char groups at their offsets recovers two useful things:

• n: 256 of its 257 DER content bytes are known (the leading 0x00 sign byte plus 256 magnitude bytes). Only the least-significant byte of n is unknown. Because n = p*q of two odd primes, n is odd, leaving only 128 odd candidate low bytes.
• A prime factor: the INTEGER header 02 81 81 00 (at the q INTEGER, DER offset 665) is followed by the top 72 bytes = 576 known high bits of a 1024-bit factor. Whether it is labelled p or q is irrelevant — it is a factor of n. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

With 576 of 1024 bits of a factor known (> 50%), n can be factored. The unknown low part is 448 bits < N^0.25 = 512 bits, within Coppersmith's bound for a monic linear polynomial modulo an unknown factor.

Solution

1. Recover fragments from the redacted PEM

Strip the ASCII-art cat, split the body into fixed 64-char lines, and for each aligned 4-character base64 group with no '*', decode it and place its 3 bytes at the known byte offset. This yields the 256 high bytes of n (low byte unknown) and the 72 high bytes (576 bits) of a factor. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. Known-high-bits factoring (Coppersmith / Howgrave-Graham)

Let a = known_high_bits << 448 be the known high part of the factor and search for the small root x0 (the 448 unknown low bits, |x0| < X = 2^448) of f(x) = x + a modulo the unknown factor of n.

Build the Howgrave-Graham lattice: rows g_i(x) = N^(m-i) * (x+a)^i for i = 0..m, plus t extra x-shift rows x^i * (x+a)^m for i = 1..t; scale column k by X^k; reduce with fpylll LLL. Extract integer roots of the shortest reduced polynomials with python-flint fmpz_poly.factor(), taking degree-1 factors (naive/Newton root-finding fails on the huge integer coefficients). Parameters m = 20, t = 10 (lattice dimension 31) suffice, verified with a same-size self-test (two random 1024-bit primes, 448 unknown bits, 2048-bit modulus). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

3. Brute-force the unknown low byte of n

CRUCIAL SUBTLETY: Coppersmith needs the exact modulus. A wrong low byte of n makes LLL fail (confirmed by self-test). So brute-force all 128 odd candidate low bytes; for each, rebuild the lattice (rows depend on N^(m-i)), run LLL, and test the recovered factor for divisibility. At ~2.5 s/byte the correct byte 0x75 (b = 117) is found after ~390 s.

4. Recover the key and decrypt

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import json
from Crypto.Util.number import inverse, long_to_bytes
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

d = json.load(open("pq.json"))          # {"N":..., "p":..., "q":..., "b":117}
N, p, q = d["N"], d["p"], d["q"]
e = 0x10001
c = int.from_bytes(open("flag.enc", "rb").read(), "big")

phi = (p - 1) * (q - 1)
dkey = inverse(e, phi)
m = pow(c, dkey, N)
print(long_to_bytes(m).decode())

The Coppersmith brute-force driver (brute.py) is reproduced faithfully below.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import json, sys, time
from fpylll import IntegerMatrix, LLL
import flint

d = json.load(open("frag.json"))
nb = d["n_bytes"]; ph = d["p_high"]
n_high = 0
for xx in nb[:-1]: n_high = (n_high << 8) | xx
q_high = 0
for xx in ph: q_high = (q_high << 8) | xx
unknown = 1024 - len(ph) * 8
a = q_high << unknown
X = 1 << unknown
m, t = 20, 10
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def pmul(u, v):
    r = [0] * (len(u) + len(v) - 1)
    for i, x in enumerate(u):
        if x == 0: continue
        for j, y in enumerate(v): r[i + j] += x * y
    return r

f = [a, 1]; fpows = [[1]]
for i in range(1, m + 1): fpows.append(pmul(fpows[-1], f))
fm = fpows[m]
deg = m + 1 + t
Xp = [X ** k for k in range(deg)]

def attempt(N):
    Np = [1]
    for i in range(1, m + 1): Np.append(Np[-1] * N)
    rows = []
    for i in range(m + 1): rows.append([c * Np[m - i] for c in fpows[i]])
    for i in range(1, t + 1): rows.append([0] * i + fm[:])
    dim = len(rows)
    B = IntegerMatrix(dim, deg)
    for r, row in enumerate(rows):
        for k, c in enumerate(row): B[r, k] = int(c) * Xp[k]
    LLL.reduction(B)
    for ri in range(dim):
        coeffs = [B[ri, k] // Xp[k] for k in range(deg)]
        while len(coeffs) > 1 and coeffs[-1] == 0: coeffs.pop()
        if len(coeffs) <= 1: continue
        fac = flint.fmpz_poly(coeffs).factor()
        for fp, mm in fac[1]:
            if fp.degree() == 1:
                a0 = int(fp[0]); a1 = int(fp[1])
                if a1 != 0 and a0 % a1 == 0:
                    r = -a0 // a1
                    cand = a + r
                    if cand > 1 and N % cand == 0 and cand.bit_length() == 1024:
                        return cand
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

start = time.time()
for b in range(1, 256, 2):
    N = n_high * 256 + b
    if N.bit_length() != 2048: continue
    p = attempt(N)
    if p:
        q = N // p
        print("FOUND b=", b, "time", round(time.time() - start, 1))
        json.dump({"N": int(N), "p": int(p), "q": int(q), "b": b}, open("pq.json", "w"))
        sys.exit(0)
    if b % 11 == 1:
        print("progress b=", b, "elapsed", round(time.time() - start, 1), flush=True)
print("none found")

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍