HTB - Fractured Seal

Sypnosis

I was handed a corrupted RSA private key file, `fractured_seal.pem`, riddled with wildcard characters where data should have been. The task in front of me was to figure out how much of the key I could actually trust, and whether that was enough to rebuild the rest and recover the flag.

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.

Skills Required

Basic understanding of RSA key structure (PKCS#1 / ASN.1 DER encoding)
Familiarity with Base64 encoding and byte-level parsing
Basic Python scripting

Skills Learned

Parsing and reconstructing ASN.1 DER structures from partially corrupted Base64 data
Understanding Coppersmith's theorem and partial key exposure attacks
Applying Howgrave-Graham's lattice-based formulation in SageMath to recover unknown bits of an RSA prime
Using small_roots() to solve for bounded unknowns modulo N

Enumeration

Code Analysis

The first thing I did was pull apart encrypt.py to understand exactly how the key and ciphertext were generated.

python

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
d = pow(e, -1, (p-1)*(q-1))

m = bytes_to_long(open('flag.txt', 'rb').read())

open('seal.pem', 'wb').write(RSA.construct((n, e, d)).export_key())
open('flag.enc', 'wb').write(long_to_bytes(pow(m, e, n)))

So this was standard textbook RSA: two 1024-bit primes $p$ and $q$ multiplied into a 2048-bit modulus $N$ , public exponent $e = 65537$ , and the flag encrypted as $c = m^e \pmod N$ . The private key was exported in standard PKCS#1 DER format — nothing exotic there. The real puzzle was in the damaged key I'd actually been given.

I knew a PKCS#1 v1.5 RSA private key is just an ASN.1 SEQUENCE holding nine integers:

text

RSAPrivateKey ::= SEQUENCE {
    version           INTEGER,  -- 0
    modulus           INTEGER,  -- n (2048 bits)
    publicExponent    INTEGER,  -- e (65537)
    privateExponent   INTEGER,  -- d (2048 bits)
    prime1            INTEGER,  -- p (1024 bits)
    prime2            INTEGER,  -- q (1024 bits)
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER   -- q^(-1) mod p
}

So I went through fractured_seal.pem byte by byte to figure out what had survived.

Header Block (Bytes 0 to 267): The first 356 Base64 characters were completely intact, decoding cleanly into the first 267 bytes of the DER structure:

text

30 82 04 a3 02 01 00 02 82 01 01 00 ...

I recognized 30 82 04 a3 as the SEQUENCE tag plus length, 02 01 00 as the version integer, and 02 82 01 01 as the tag and length for the modulus $N$ — followed by a leading 00 sign byte and then 255 bytes of $N$ itself.

The one gap was the 256th and final byte of $N$ , which straddled the boundary between the last intact Base64 character ('d') and the wildcard corruption that followed. But since I knew $N$ had to be odd, and $e = 65537$ (02 03 01 00 01) immediately followed it in the DER structure, I could narrow that final byte down to just two candidates: 0x75 or 0x77.

Prime Block (Base64 indices 884–990): A surviving chunk here, 2msCgYEAwLGxcJ7/YCgq..., decoded to the tail end of the private exponent $d$ , followed by:

text

02 81 81 00

— the ASN.1 header for a 128-byte prime factor — and then 72 bytes of real data. That gave me the most significant 576 bits of prime $q$ .

Putting it together: I had the complete 2048-bit modulus $N$ (modulo one byte with two candidates), and the top 576 bits of a 1024-bit prime $q$ , leaving 448 unknown bits at the bottom. That ratio was the detail that mattered most.

Solution

Finding the vulnerability

More than half the bits of $q$ were sitting right in front of me, and that rang a bell: Coppersmith's theorem, specifically the partial key exposure variant using Howgrave-Graham's lattice reduction technique.

I modeled $q$ as:

$q = q_0 + x_0$

where $q_0 = \text{MSB}(q) \ll 448$ was my known 576-bit prefix, shifted into position, and $x_0 \in [0, X)$ was the unknown 448-bit suffix, bounded by $X = 2^{448}$ .

From there I built the polynomial:

$f(x) = x + q_0 \pmod N$

Since $f(x_0) = q_0 + x_0 = q \equiv 0 \pmod q$ , I had exactly the kind of small-root problem Coppersmith's method is built for.

Howgrave-Graham's formulation told me that for a monic polynomial $f(x)$ of degree $d$ , any root $x_0$ with $f(x_0) \equiv 0 \pmod q$ where $q \ge N^\beta$ can be recovered efficiently if:

$X < N^\bgroup\beta^2 / d\egroup$

Plugging in my numbers:

Degree $d = 1$
$\beta = 0.5$ (since $q \approx N^{0.5}$ )
Bound: $X < N^{0.25} = 2^{512}$

My actual unknown was $X = 2^{448} = N^{0.21875}$ , comfortably under $2^{512}$ . The condition held with room to spare, which meant LLL lattice reduction on the Howgrave-Graham matrix should be able to construct a polynomial $h(x)$ over $\mathbb{Z}$ sharing the root $x_0$ . I had my path forward.

Exploitation

I wrote solve_sage.py to walk through the recovery step by step:

Parse the Base64 key to pull out the 255-byte prefix of $N$ and the 72-byte prefix of $q$ .
Formulate $f(x) = x + q_0 \pmod N$ .
Run SageMath's f.small_roots(X=2^448, beta=0.45) to solve for $x_0$ .
Reconstruct $q = q_0 + x_0$ , then recover $p = N // q$ .
Compute the private exponent $d = e^{-1} \pmod{(p-1)(q-1)}$ and decrypt flag.enc.

python

import base64
import os
from sage.all import Zmod, PolynomialRing

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

DIR = os.path.dirname(os.path.abspath(__file__))

# 1. Parse damaged key
raw = open(os.path.join(DIR, "crypto_fractured_seal/fractured_seal.pem")).read()
lines = [l.strip() for l in raw.splitlines() if l.strip() and not l.startswith("-----")]
b64_str = "".join("".join(c for c in l if c in "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=*") for l in lines)

prefix_356 = b64_str[:356]
raw_267 = base64.b64decode(prefix_356)
n_bytes_255 = raw_267[12:]

part2 = b64_str[884:990]
part2_cut = part2[:104]
der2 = base64.b64decode(part2_cut)
pos = der2.find(bytes([0x02, 0x81, 0x81, 0x00]))
q_known_bytes = der2[pos+4:]
q_top_val = int.from_bytes(q_known_bytes, "big")

shift_bits = (128 - len(q_known_bytes)) * 8
q_0 = q_top_val << shift_bits
X = 1 << shift_bits

c = int.from_bytes(open(os.path.join(DIR, "crypto_fractured_seal/flag.enc"), "rb").read(), "big")
e = 65537

# 2. Test modulus candidate and run Coppersmith
for last_byte in [0x75, 0x77]:
    N = int.from_bytes(n_bytes_255 + bytes([last_byte]), "big")
    
    R = Zmod(N)['x']
    x = R.gen()
    f = x + q_0
    roots = f.small_roots(X=X, beta=0.45, epsilon=0.03)
    
    for r in roots:
        q_cand = q_0 + int(r)
        if N % q_cand == 0:
            q = q_cand
            p = N // q
            
            phi = (p - 1) * (q - 1)
            d = pow(e, -1, phi)
            m = pow(c, d, N)
            print("FLAG:", long_to_bytes(m).decode())
            exit(0)

Since I only had two candidates for that final ambiguous byte of $N$ , I just looped over both and let the lattice reduction sort out which one was correct.

Getting the flag

I ran the solver inside a SageMath container:

bash

docker run --rm -v $(pwd):/work sagemath/sagemath sage /work/solve_sage.py

And it landed almost immediately:

text

q_0 bits: 1024, shift_bits: 448

--- Testing N with last_byte = 0x75 ---
Roots found: [494533564276282312327644746782974681166630268929025105049519624303197509347145019462993146399659035259691482718467703635222459734427551]

============================================================
🎉🎉🎉 SUCCESS! RSA FACTORED! 🎉🎉🎉
p = 131245497686548195467002565571865142560301544570020751232142961289012921376593159901052103730440250925007836457109179886547836486011666467584064970241380093385446276958000532368427648668071765509981171770398020329521298809677306252117144794197756373244812597628909948298104892770922899165466399775874596133483
q = 135314408378842790751605878050931209066067635249717498350882274491410611188834198512433542860977980915267615830180088553515126808474341043736459805810824761780913391116795622398843468715298669440308270490800437972694168370812052926427757058006436117836843232703533488083597801200757836873180405061962240493471
FLAG: HTB{{REDACTED}}
============================================================

Caldrin was right — the seal didn't need to be whole. 576 known bits out of 1024 was more than enough for Coppersmith's method to hand me back the rest.