0x2 - Learn CTF: Cryptography

Table of Contents

error-code — Merkle-Hellman implementation bug

Summary

  • Category: Cryptography
  • Challenge: error-code
  • Core scheme: Merkle-Hellman knapsack (subset-sum)
  • Given files: chall.py, output
  • Recovered flag:
CBC{4_cl4ss1c_subs3t_sum_pr0blem_r1ght_9c209955}

Problem statement (practical)

The challenge author says they implemented Merkle-Hellman, but decryption does not work. The job is to identify the implementation error and recover the plaintext.

Root cause

In Merkle-Hellman, the private sequence W must be superincreasing:

$$ W_i > \sum_{j=0}^{i-1} W_j $$

But in chall.py, sequence generation only enforces monotonic growth from the previous term:

def getSequence(size):
    W = []
    w0 = 99999
    for _ in range(size):
        wi = random.randint(w0 + 1, 2 * w0)
        W.append(wi)
        w0 = wi
    return W

This condition is too weak. It creates an increasing sequence, but not necessarily superincreasing. So the classic private-key greedy decryption path is invalid/unreliable.

Why encryption still leaks

Even with that bug, encryption is still linear subset sum over public key coefficients:

$$ c = \sum b_i \cdot pub_i $$

For this instance, each ciphertext block uses 48 coefficients (because len(flag) = 48), and there are 8 blocks in ct_lst. That is directly solvable as subset-sum with meet-in-the-middle.

Solver approach (meet-in-the-middle)

Split public key into two halves of 24 + 24:

  1. Enumerate all subset sums of first half, map sum -> mask.
  2. Enumerate all subset sums of second half, map sum -> mask.
  3. For each ciphertext ct, find s1 + s2 = ct.
  4. Recover 48 bits for that block from masks.
  5. Reconstruct original integer/bytes according to the challenge bit-order.

Repro solver

# solve.py
pub = [399556779992238, 34298225407642, 20642131245786, 65490996326207, 122628372242215, 9829827117171,
       396026745275353, 167294584165304, 296444912760811, 80351792351840, 409914932982222, 85802434589354,
       401591010427922, 187008763237642, 152108391468386, 31583306493979, 25525613569306, 162082080588558,
       126634456980331, 164430139182734, 83701623822886, 402679681495011, 192369423507295, 160258497915791,
       258919777739363, 64531362352673, 306761417690632, 341920025542429, 26318306417850, 4818756642968,
       207127269238936, 200786177672536, 179782888357779, 58758524994661, 278516593354891, 158487072996052,
       291093591620507, 64579822017072, 210651490815487, 217428030502253, 258408901203031, 360703727369716,
       29799816650929, 279304424652560, 34106935830323, 424511985165056, 296198681936242, 429117013029379]

cts = [4732215009804500, 4609442091199342, 5692746616356737, 3525483039088576,
       6333124120174760, 5291548626672528, 4905835028190278, 4783246254953126]

HALF = 24
A, B = pub[:HALF], pub[HALF:]

sa = {0: 0}
for i, w in enumerate(A):
    bit = 1 << i
    for s, m in list(sa.items()):
        ns = s + w
        if ns not in sa:
            sa[ns] = m | bit

sb = {0: 0}
for i, w in enumerate(B):
    bit = 1 << i
    for s, m in list(sb.items()):
        ns = s + w
        if ns not in sb:
            sb[ns] = m | bit

chunks = []
for ct in cts:
    found = None
    for s1, m1 in sa.items():
        need = ct - s1
        m2 = sb.get(need)
        if m2 is not None:
            found = (m1, m2)
            break
    if found is None:
        raise RuntimeError(f"No subset solution for ct={ct}")

    m1, m2 = found
    bits = [((m1 >> i) & 1) for i in range(24)] + [((m2 >> i) & 1) for i in range(24)]
    chunks.append(bits)

msg = 0
for j, bits in enumerate(chunks):
    val = sum((b << i) for i, b in enumerate(bits))
    msg |= val << (48 * j)

raw = msg.to_bytes(48, 'big')
print(raw.decode())

Expected output:

CBC{4_cl4ss1c_subs3t_sum_pr0blem_r1ght_9c209955}

Correct key-generation fix

To make decryption valid in Merkle-Hellman, generate W as superincreasing:

def getSequence(size):
    W = []
    s = 1
    for _ in range(size):
        wi = random.randint(s + 1, 2 * s)
        W.append(wi)
        s += wi
    return W

Keep:

  • q > sum(W)
  • gcd(r, q) = 1

Then private-key decryption works as intended.

nito — truncated-state recovery with Coppersmith

Summary

  • Category: Cryptography
  • Challenge: nito
  • Given files: challenge.sage, output.txt
  • Core idea: recover unknown 64-bit tails from leaked high bits of modularly-related values
  • Recovered flag:
CBC{cryp70_i5_ju57_AI_5p33drun?}

Given construction

Challenge generates:

  • prime p (256-bit)
  • random a0
  • a1 = a0^2 mod p
  • leaked values:
    • b0 = a0 >> 64
    • b1 = a1 >> 64
  • ciphertext:
c = bytes_to_long(flag) ^^ pow(a1, 42, p)

Let unknown low 64-bit parts be x, y:

$$ a0 = (b0 « 64) + x, \quad a1 = (b1 « 64) + y, \quad 0 \le x,y < 2^{64} $$

From a1 = a0^2 mod p:

$$ ((b0 « 64) + x)^2 - ((b1 « 64) + y) \equiv 0 \pmod p $$

This is a bivariate small-root problem over bounds (2^64, 2^64).

Solve strategy

Use Coppersmith small-roots on the polynomial above to recover (x, y).

I used:

  • Sage (local env at /opt/micromamba/envs/sage)
  • coppersmith.sage from defund/coppersmith (updated to Sage 10.7 API: coefficients_monomials, no deprecation warning)

Found root:

  • x = 8804081745998249949
  • y = 10378144287870099762

Then reconstruct a1, compute pow(a1,42,p), XOR with c, and decode bytes.

Repro script (Sage)

load('coppersmith.sage')

p = 12721492641695199020302023719104846741933769337250722901191654350831830951811
c = 41191888024213095867034353749467947785476609376959645738506308145695929457707
b0 = 505745372664810403157022893345560792860796814985411337944
b1 = 55363083749705718410582971847380097690792442149083200327

kbits = 64
B0 = b0 << kbits
B1 = b1 << kbits

PR.<x,y> = PolynomialRing(Zmod(p))
f = (B0 + x)^2 - (B1 + y)

roots = small_roots(f, bounds=(2^64,2^64), m=3, d=3)
for xv, yv in roots:
    a1 = B1 + int(yv)
    m = c ^^ power_mod(a1, 42, p)
    print(Integer(m).to_bytes((Integer(m).nbits()+7)//8, 'big'))

Expected output:

CBC{cryp70_i5_ju57_AI_5p33drun?}

Lack of Entropy — deterministic RSA prime relation

Summary

  • Category: Cryptography
  • Challenge: firebird2022 - lack-of-entropy (CryptoHack archive)
  • Given files: chall.py, output.txt
  • Recovered flag:
firebird{b1n4ry_s34rch_f0r_th3_w1n!}

Vulnerability

The challenge generates RSA values with:

p = random.getrandbits(256)
q = int(gmpy2.digits(p, 3))
n = p * q

So q is not independent. It is a deterministic function of p:

$$ q = f(p) = \text{int}(\text{base3}(p)) $$

Hence modulus has special form:

$$ n = p \cdot f(p) $$

f(p) is monotonic increasing for positive integers, therefore $g(p) = p\cdot f(p)$ is also monotonic. We can recover p by binary search on 256-bit range.

Solver approach

  1. Parse n, e, c from output.txt.
  2. Define f(p)=int(base3(p)).
  3. Binary search p in [2^255, 2^256-1] with target p*f(p)=n.
  4. Recover q=f(p), compute RSA private exponent d, decrypt c.

Repro solver

#!/usr/bin/env python3
import re
from Crypto.Util.number import long_to_bytes

with open('output.txt','r') as f:
    txt = f.read()

n = int(re.search(r"n\\s*=\\s*(\\d+)", txt).group(1))
e = int(re.search(r"e\\s*=\\s*(\\d+)", txt).group(1))
c = int(re.search(r"c\\s*=\\s*(\\d+)", txt).group(1))


def base3_str(x: int) -> str:
    if x == 0:
        return '0'
    ds = []
    while x:
        x, r = divmod(x, 3)
        ds.append(str(r))
    return ''.join(reversed(ds))


def f(p: int) -> int:
    return int(base3_str(p))


lo = 1 << 255
hi = (1 << 256) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    g = mid * f(mid)
    if g == n:
        p = mid
        break
    if g < n:
        lo = mid + 1
    else:
        hi = mid - 1
else:
    raise RuntimeError('p not found')

q = f(p)
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())

Verification

Output:

firebird{b1n4ry_s34rch_f0r_th3_w1n!}

Lesson

Never derive one RSA prime from the other. Independent prime generation is mandatory; structure leaks can collapse factoring to search.

a-joke-cipher — broken key exchange leaks plaintext multiplier

Summary

  • Category: Cryptography
  • Challenge: HKCERT 2021 - a-joke-cipher
  • Given files: chall.py, output.txt
  • Recovered flag:
hkcert21{th1s_i5_wh4t_w3_c4ll3d_sn4k3o1l_crypt0sy5t3m}

Vulnerability

The custom key-exchange design publishes:

  • p
  • y_A = S_A mod p
  • y_B = S_B mod p

And computes Alice’s shared key as:

$$ S_{AB} = (y_A \cdot y_B \cdot y_B) \cdot S_A \mod p $$

Since y_A = S_A mod p, we can substitute directly:

$$ S_{AB} \equiv y_A^2 \cdot y_B^2 \pmod p $$

So the shared multiplier is fully recoverable from public values.

Encryption then does plain integer multiplication:

$$ c = m \cdot S_{AB} $$

No modular reduction is applied at encryption stage, so plaintext is recovered exactly by integer division.

Solver approach

  1. Parse p, y_A, y_B, c from output.txt.
  2. Compute sk = ((y_A * y_B) mod p)^2 mod p.
  3. Recover m = c // sk.
  4. Convert m to bytes and decode.

Repro solver

#!/usr/bin/env python3
import re
from pathlib import Path

text = Path('output.txt').read_text()

def hx(name):
    m = re.search(rf"{name}\s*=\s*(0x[0-9a-f]+)", text)
    if not m:
        raise ValueError(f"missing {name}")
    return int(m.group(1), 16)

p = hx('p')
y_A = hx('y_A')
y_B = hx('y_B')
c = hx('c')

sk = pow((y_A * y_B) % p, 2, p)
m = c // sk
print(m.to_bytes((m.bit_length() + 7) // 8, 'big').decode())

Verification

Running the solver prints:

hkcert21{th1s_i5_wh4t_w3_c4ll3d_sn4k3o1l_crypt0sy5t3m}

Lesson

Publishing linear key material plus using non-modular ciphertext multiplication collapses confidentiality. Custom cryptosystems without formal security proofs are usually breakable in exactly this way.

d-phi-enc — recovering RSA factors from encrypted φ and d

Summary

  • Category: Cryptography
  • Challenge: HackTM CTF 2023 - d-phi-enc
  • Given files: chall.py, output.txt
  • Recovered flag:
HackTM{Have you warmed up? If not, I suggest you consider the case where e=65537, although I don't know if it's solvable. Why did I say that? Because I have to make this flag much longer to avoid solving it just by calculating the cubic root of enc_flag.}

Given construction

The challenge does:

  • RSA with e = 3 and 1024-bit strong primes p, q
  • n = p*q, phi = (p-1)(q-1), d = e^{-1} mod phi
  • publishes:
    • enc_phi = phi^3 mod n
    • enc_d = d^3 mod n
    • enc_flag = m^3 mod n

At first glance this looks like “encrypted internals”, but with e=3 the algebra is highly constrained.

Core derivation

Let:

$$ s = p + q - 1, \quad \phi = n - s $$

Then:

$$ enc_\phi \equiv (n-s)^3 \pmod n $$

Also from RSA relation (e=3):

$$ 3d \equiv 1 \pmod \phi $$

Since phi is even and gcd(3,phi)=1, d is odd, and concretely for this instance:

$$ 3d = 1 + 2\phi $$

So modulo n:

$$ 27,enc_d \equiv (1+2\phi)^3 \equiv (2(n-s)+1)^3 \pmod n $$

Eliminating cubic terms between this and 8*enc_phi yields a quadratic in s up to an integer lift m:

$$ 12s^2 - 6s + \left(1 + 8,enc_\phi - 27,enc_d - m n\right) = 0 $$

Scan small integer m, require discriminant perfect square, and verify candidate with:

$$ (n-s)^3 \equiv enc_\phi \pmod n $$

Once s is found:

  • p+q = s+1
  • solve quadratic X^2 - (p+q)X + n = 0 to recover p, q
  • compute d, decrypt enc_flag.

Repro solver

#!/usr/bin/env python3
from math import isqrt
import re


def parse_output(path: str):
    txt = open(path, "r", encoding="utf-8").read()
    def grab(name: str) -> int:
        m = re.search(rf"{name}\s*=\s*(\d+)", txt)
        if not m:
            raise ValueError(f"missing {name}")
        return int(m.group(1))
    return grab("n"), grab("enc_d"), grab("enc_phi"), grab("enc_flag")


def recover_sum_pq_minus_1(n: int, enc_d: int, enc_phi: int) -> int:
    C = 1 + 8 * enc_phi - 27 * enc_d
    a, b = 12, -6
    for m in range(-200, 400):
        c = C - m * n
        D = b * b - 4 * a * c
        if D < 0:
            continue
        r = isqrt(D)
        if r * r != D:
            continue
        for num in (-b + r, -b - r):
            den = 2 * a
            if num % den:
                continue
            s = num // den
            if s <= 0:
                continue
            if pow((n - s) % n, 3, n) == enc_phi:
                return s
    raise RuntimeError("failed to recover s")


def factor_from_sum(n: int, s: int):
    S = s + 1
    D = S * S - 4 * n
    r = isqrt(D)
    if r * r != D:
        raise RuntimeError("non-square discriminant")
    p = (S + r) // 2
    q = (S - r) // 2
    if p * q != n:
        raise RuntimeError("factorization mismatch")
    return p, q


def i2b(x: int) -> bytes:
    if x == 0:
        return b"\x00"
    return x.to_bytes((x.bit_length() + 7) // 8, "big")


def main():
    n, enc_d, enc_phi, enc_flag = parse_output("output.txt")
    s = recover_sum_pq_minus_1(n, enc_d, enc_phi)
    p, q = factor_from_sum(n, s)

    e = 3
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)

    m = pow(enc_flag, d, n)
    print(i2b(m).decode())


if __name__ == "__main__":
    main()

Verification

Running the solver prints the full HackTM{...} flag above.

Lesson

“Encrypting sensitive RSA internals” is not a protection when algebraic relations remain intact. With low exponent and correlated values (phi, d), structure leaks can be enough to recover factors directly.

 

Zero

CTF notes by Zero

Challenge writeups for crypto problems, from mathematical modeling to solver implementation.

By Zero, 2026-02-23

Tags

#ctf #learn #cry