picoCTF Solutions
picoMini by redpwnCryptographyHard

corrupt-key-1 picoMini by redpwn Solution

Published: April 2, 2026

Description

My RSA key is corrupted. Can you fix it?

Setup

Download the provided RSA private key PEM file from the challenge page.

Notice that openssl rejects it: some fields inside the key are corrupted/zeroed.

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

Solution

Walk me through it
  1. Step 1Parse the PEM as raw ASN.1 to see which fields survived
    An RSA private key stores nine values in order: version, n (modulus), e (public exponent), d (private exponent), p, q, dp = d mod (p-1), dq = d mod (q-1), and qinv = q^-1 mod p. openssl rsa fails on a corrupted key because it cross-checks these fields, but openssl asn1parse decodes the SEQUENCE field by field so you can read the intact integers directly. Identify which fields are correct and which were zeroed or mangled - in corrupt-key-1 only one or two fields are damaged, leaving enough to rebuild everything else.
    bash
    # This usually errors because the fields are inconsistent:
    bash
    openssl rsa -in key.pem -text -noout 2>&1 | head
    bash
    bash
    # Dump the raw ASN.1 integers regardless of consistency:
    bash
    openssl asn1parse -in key.pem
    bash
    bash
    # Each INTEGER line is one of: version, n, e, d, p, q, dp, dq, qinv
    bash
    # Read off the ones that are intact (nonzero, correct length).
    Learn more

    An RSA private key in PKCS#1 format (RFC 8017) is an ASN.1 SEQUENCE of nine INTEGER values in a fixed order: version, n, e, d, p, q, dp, dq, qinv. The PEM file is just that DER structure base64-encoded between -----BEGIN RSA PRIVATE KEY----- markers.

    openssl rsa validates the whole key and refuses to load it if the fields are inconsistent, which is why the corrupted file fails. openssl asn1parse does no such validation - it walks the ASN.1 and prints each integer, so you can recover every field that was not damaged. The corruption in this challenge zeroes or scrambles a small number of the nine fields; the rest are exact.

    This is pure key reconstruction from RSA's internal relationships - no lattices, no Coppersmith, no brute force. Knowing n plus one prime (or n, e, and d) is enough to derive everything.

  2. Step 2Recompute the missing field arithmetically
    Use the intact fields to recompute the corrupted one. If a prime is missing but n and the other prime survive, the missing prime is just n // p. If d is corrupted, recompute d = e^-1 mod (p-1)(q-1). The CRT fields follow: dp = d mod (p-1), dq = d mod (q-1), qinv = q^-1 mod p. Pick whichever relation closes the gap left by the corrupted field.
    python
    python3 -c "
    bash
    from Crypto.Util.number import inverse
    bash
    # Fill in the values you read from openssl asn1parse.
    bash
    n = <n>; e = <e>
    bash
    p = <intact_prime_p>          # one prime survived
    bash
    q = n // p                    # recover the other prime
    bash
    assert p * q == n             # sanity check
    bash
    phi = (p - 1) * (q - 1)
    bash
    d = inverse(e, phi)           # recover the private exponent
    bash
    dp = d % (p - 1)
    bash
    dq = d % (q - 1)
    bash
    qinv = inverse(q, p)
    python
    print('p', p); print('q', q); print('d', d)
    python
    print('dp', dp); print('dq', dq); print('qinv', qinv)
    bash
    "
    Learn more

    The RSA fields are bound together by exact equations, so any one of them is reconstructible from the others:

    • q = n / p (exact integer division - verify with p * q == n)
    • d = e^-1 mod (p-1)(q-1) (modular inverse / extended Euclid)
    • dp = d mod (p-1), dq = d mod (q-1)
    • qinv = q^-1 mod p

    Whichever field the challenge zeroed, one of these formulas regenerates it. There is no search and no approximation: the survivors fully determine the missing value. The inverse() helper from Crypto.Util.number computes the modular inverses with the extended Euclidean algorithm.

  3. Step 3Rebuild the key and decrypt
    With every field recovered, reconstruct a valid RSA key object and decrypt the provided ciphertext (or simply re-export a repaired PEM if that is what the challenge asks for). The flag falls out of the decryption.
    python
    python3 -c "
    bash
    from Crypto.PublicKey import RSA
    bash
    from Crypto.Util.number import inverse, long_to_bytes
    bash
    n = <n>; e = <e>; p = <p>
    bash
    q = n // p
    bash
    assert p * q == n
    bash
    d = inverse(e, (p - 1) * (q - 1))
    bash
    key = RSA.construct((n, e, d, p, q))
    bash
    # Re-export the repaired key, or decrypt the ciphertext:
    bash
    open('fixed.pem','wb').write(key.export_key())
    bash
    c = <ciphertext_int>
    bash
    m = pow(c, d, n)
    python
    print(long_to_bytes(m))
    bash
    "
    Learn more

    RSA.construct((n, e, d, p, q)) from pycryptodome rebuilds a complete, consistent key object (it recomputes the CRT parameters internally), so you can either export a clean PEM or decrypt right away with pow(c, d, n).

    The lesson: RSA private key material is massively redundant. Knowing n and a single prime - or n, e, and d- is enough to reconstruct the entire key, which is exactly why a "partially" leaked private key should be treated as fully compromised.

Flag

picoCTF{...}

Parse the PEM with openssl asn1parse to read the intact ASN.1 integers, then recompute the corrupted field from RSA's internal relations (q = n // p, d = e^-1 mod phi, dp/dq/qinv), rebuild the key, and decrypt. No lattice or Coppersmith needed.

Want more picoMini by redpwn writeups?

Browse picoMini by redpwnFull library

Useful tools for Cryptography

Related reading

What to try next