picoCTF Solutions
picoMini by redpwnCryptographyHard

corrupt-key-2 picoMini by redpwn Solution

Published: April 2, 2026

Description

Even more corrupted key.

Setup

Download the more heavily corrupted RSA private key PEM from the challenge page.

Parse the ASN.1 and figure out which of the nine fields are still intact this time.

bash
wget <challenge_url>/key.pem  # download the broken key

Solution

Walk me through it
  1. Step 1Dump the ASN.1 and inventory the surviving fields
    Run openssl asn1parse and list which of version, n, e, d, p, q, dp, dq, qinv are intact. In corrupt-key-2 the primes p and q are typically corrupted, but the CRT exponents (dp = d mod (p-1), dq = d mod (q-1)) or the modulus n and exponent d survive. There is still always enough surviving structure to recompute the rest with algebra - no lattice, no Coppersmith, no brute force is needed.
    bash
    openssl asn1parse -in key.pem
    bash
    bash
    # Field order: version, n, e, d, p, q, dp, dq, qinv
    bash
    # Mark which are nonzero and correctly sized. Common surviving
    bash
    # sets for this challenge: {n, e, dp, dq} or {n, e, d}.
    Learn more

    The structure is identical to corrupt-key-1: a PKCS#1 ASN.1 SEQUENCE of nine integers. openssl rsa still refuses the file because the corruption leaves it internally inconsistent, but openssl asn1parse prints whatever integers remain readable.

    The challenge corrupts morefields than part 1, which is intimidating but does not change the technique. RSA's fields are so redundant that even a small surviving subset pins down the whole key. The work is choosing the right relation to rebuild the primes from whatever survived.

  2. Step 2Recover the primes from the surviving CRT fields
    Pick the reconstruction that matches your surviving fields. Case A - n, e, d survive: factor n deterministically from (n, e, d) using the standard k = e*d - 1 / repeated-square-root method, which always recovers p and q in polynomial time. Case B - dp (and/or dq) survive with n and e: since e*dp = 1 + k*(p-1) for some small integer k (1 <= k < e), iterate k over that small range, compute a candidate p = (e*dp - 1)/k + 1, and test whether that p divides n. The correct k yields p; then q = n // p.
    python
    # Case A: factor n from (n, e, d) - deterministic, always works
python3 -c "
import random
n = <n>; e = <e>; d = <d>
k = e*d - 1
t = k
while t % 2 == 0:
    t //= 2
p = None
while p is None:
    a = random.randrange(2, n - 1)
    x = pow(a, t, n)
    if x in (1, n - 1):
        continue
    while x != n - 1:
        y = pow(x, 2, n)
        if y == 1:
            g = __import__('math').gcd(x - 1, n)
            if 1 < g < n:
                p = g
            break
        x = y
q = n // p
print('p', p); print('q', q)
"
    python
    # Case B: recover p from a surviving CRT exponent dp
python3 -c "
n = <n>; e = <e>; dp = <dp>
# e*dp = 1 + k*(p-1) for some 1 <= k < e
for k in range(1, e):
    num = e*dp - 1
    if num % k:
        continue
    p = num // k + 1
    if n % p == 0:
        q = n // p
        print('k', k); print('p', p); print('q', q)
        break
"
    Learn more

    Factoring n from (n, e, d) is a textbook result: because e*d - 1 is a multiple of lcm(p-1, q-1), a Miller-Rabin-style square-root search finds a nontrivial factor of n in polynomial time with overwhelming probability. This is the go-to move whenever the private exponent survived.

    Recovering a prime from a CRT exponent uses dp = d mod (p-1), which means e*dp = 1 mod (p-1), i.e. e*dp - 1 = k*(p-1) for some integer k in the small range 1 ≤ k < e. Trying each k gives a candidate p; the correct one divides n. With e = 65537 this is at most a few tens of thousands of trivial trial divisions.

    Both routes are exact arithmetic. Lattice attacks and Coppersmith are unnecessary because the corrupted key still leaks complete fields, not just partial bits.

  3. Step 3Rebuild the key and decrypt
    Once p and q are recovered (verify p * q == n), recompute d = e^-1 mod (p-1)(q-1), reconstruct the key, and decrypt the ciphertext exactly as in corrupt-key-1.
    python
    python3 -c "
    bash
    from Crypto.Util.number import inverse, long_to_bytes
    bash
    n = <n>; e = <e>; p = <recovered_p>
    bash
    q = n // p
    bash
    assert p * q == n, 'wrong p!'
    bash
    d = inverse(e, (p - 1) * (q - 1))
    bash
    c = <ciphertext_int>
    python
    print(long_to_bytes(pow(c, d, n)))
    bash
    "
    Learn more

    The assert p * q == n check confirms the recovered prime is exact before trusting the decryption. If it fails, you picked the wrong surviving-field case or the wrong k; revisit the asn1parse dump and re-identify which fields are intact.

    This second part reinforces the same point as the first: RSA private keys are heavily over-determined. Even with most fields corrupted, a single surviving exponent or prime is enough to reconstruct the entire key with elementary number theory - which is exactly why partial key leakage is catastrophic in practice.

Flag

picoCTF{...}

More fields corrupted, same idea: read the surviving ASN.1 integers with openssl asn1parse, then reconstruct the primes arithmetically - factor n from (n, e, d) if d survived, or recover p from a surviving CRT exponent via e*dp - 1 = k*(p-1). Then recompute d and decrypt. No lattice or Coppersmith.

Want more picoMini by redpwn writeups?

Browse picoMini by redpwnFull library

Useful tools for Cryptography

Related reading

What to try next