corrupt-key-2 picoMini by redpwn Solution

Description

1. Step 1

   Identify the three missing chunks in p

   Observation

   I noticed that the PEM contained a partially-zeroed prime p with three distinct runs of 00 bytes visible in the raw DER, which suggested mapping each zero region to a bit offset and width before attempting any algebraic recovery.

   Unlike corrupt-key-1 (where whole ASN.1 fields were wiped), here the prime p is present but partially zeroed. Three non-contiguous chunks were erased: one 40-bit gap starting at bit 16, one 32-bit gap at bit 240, and one 40-bit gap at bit 352. Call the zero-filled version _p. The real p equals _p + 2^16 * x0 + 2^240 * x1 + 2^352 * x2, where x0, x1, x2 are the three unknown values bounded by 2^40, 2^32, and 2^40 respectively.

   bash

   openssl asn1parse -in key.pem

   Copied!

   bash

   # Write out p in hex and locate the three zero-filled regions.

   Copied!

   bash

   # Record _p (p with those regions zeroed) and the bit offsets of each gap.

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Run openssl rsa -in key.pem -text to read p instead of asn1parse

   openssl rsa will refuse to parse or will output an error because the PEM fields are corrupted - the RSA key sanity checks fail before printing anything useful. asn1parse reads the raw DER bytes without validating the mathematical relationships, so it successfully dumps p even when it contains zeroed chunks. Always use asn1parse on a corrupted key.

   Tried: Assume the zero bytes in p are just leading zeros and reconstruct p by stripping them

   RSA primes do not have leading zero bytes in their canonical encoding; any zero run that is not at the very start of the integer is genuinely erased data. Treating the zeros as leading padding and shifting the remaining bytes will produce a value that does not divide N. You need to locate each zero region by its bit offset and treat it as an unknown variable, not remove it.

   Learn more

   A PKCS#1 RSA private key stores nine ASN.1 integers including the prime p. In corrupt-key-2 the field is present but three chunks inside it were overwritten with zeros. Knowing most of p but not all of it is the classic setting for a partial-key recovery attack: you have a polynomial over p that you want to evaluate at p mod N.

   Because p divides N, the polynomial f(x0, x1, x2) = _p + 2^16*x0 + 2^240*x1 + 2^352*x2 has a root modulo N at exactly (x0, x1, x2) equal to the missing chunks. The root is "small" relative to N (each unknown is at most 40 bits while Nis 1024 bits), which is precisely the regime where Coppersmith's method applies.

2. Step 2

   Run multivariate Coppersmith (LLL) to recover the missing bits

   Observation

   I noticed that three separate unknown chunks totaling about 112 bits were embedded inside the 512-bit prime p, and since p divides N, the unknowns form small roots of a trivariate polynomial modulo N, which is exactly the setting Coppersmith's lattice method handles.

   Coppersmith's theorem says that if a polynomial f has a root smaller than N^(1/deg) in each variable, that root can be found in polynomial time via LLL lattice reduction. Here each unknown is roughly 2^40 while N is 2^1024, so the bound is comfortably satisfied. You construct a lattice from shifts of f, reduce it with LLL, and extract the unique small root. The m=6 parameter controls how many shift polynomials go into the lattice; larger m increases success probability at the cost of a bigger matrix.

   python

   # Run in Sage (sage solve.sage)
   # You need a multivariate Coppersmith implementation.
   # Well-known reference implementations of multivariate Coppersmith are publicly available.
   
   N = <modulus_from_asn1parse>
   _p = <p_with_gaps_zeroed>
   
   PR.<x0, x1, x2> = PolynomialRing(Zmod(N), 3)
   f = _p + 2**16*x0 + 2**240*x1 + 2**352*x2
   
   x0_sol, x1_sol, x2_sol = coppersmith(f, bounds=(2**40, 2**32, 2**40), m=6)
   p = int(f(x0_sol, x1_sol, x2_sol))
   print("p =", p)
   assert N % p == 0, "Coppersmith returned a wrong root - try larger m"

   Copied!

   What didn't work first

   Tried: Use Sage's built-in univariate small_roots() on a single-variable polynomial after guessing x1 and x2 are zero

   small_roots() only handles one unknown variable, so fixing x1 and x2 to zero collapses the problem but produces a polynomial with no valid root mod N since the real missing chunks are nonzero. The function either returns an empty list or a spurious value that fails the N % p == 0 assert. You must use a multivariate Coppersmith implementation that constructs a joint lattice for all three unknowns simultaneously.

   Tried: Run Coppersmith with m=2 or m=3 to speed things up

   A lower m value produces a smaller lattice with fewer shift polynomials. For a trivariate polynomial with 112 total unknown bits, m=2 is too small for the Howgrave-Graham condition to be satisfied, so LLL finds a short vector that is not the target root. The assert fails and the script prints a wrong p. This challenge requires m=6; reducing it silently produces garbage without throwing an obvious error.

   Learn more

   Why LLL works here: LLL (Lenstra-Lenstra-Lovasz) finds a short vector in a lattice. Coppersmith's technique encodes "find a polynomial root smaller than B" as "find a short vector in a certain lattice." For a trivariate polynomial with bounds (2^40, 2^32, 2^40) and modulus N ~ 2^1024, the Howgrave-Graham condition is well within reach, so LLL reliably finds all three missing chunks in seconds.

   The parameter m=6 controls the lattice dimension: higher values include more shift polynomials, making the lattice bigger but more likely to contain the target short vector. For this specific challenge, m=6 is required.

   This is the key distinction from corrupt-key-1: there only one contiguous block of bits was missing (the lower half of p), so a single-variable Coppersmith polynomial sufficed. Here three non-contiguous chunks were erased, which requires a trivariate polynomial and a multivariate Coppersmith implementation - a strictly harder lattice problem.

3. Step 3

   Reconstruct the private key and decrypt

   Observation

   I noticed the Coppersmith solver returned the three missing chunks x0, x1, x2, and verifying that p divides N confirmed the recovery was correct, which meant the standard RSA formula d = e^-1 mod (p-1)(q-1) could now be computed and applied to the encrypted message.

   Once the Coppersmith solver returns x0, x1, x2, reconstruct p = _p + 2^16*x0 + 2^240*x1 + 2^352*x2. Verify p divides N exactly, then compute q = N // p, d = e^-1 mod (p-1)(q-1), and decrypt the ciphertext.

   python

   # In the same Sage script (or in Python after exporting p):
   q = N // p
   assert p * q == N, "sanity check failed"
   e = 65537
   d = int(pow(e, -1, (p - 1) * (q - 1)))
   
   c = int.from_bytes(open("msg.enc", "rb").read(), "big")
   m = pow(c, d, N)
   print(bytes.fromhex(hex(m)[2:]).decode())

   Copied!

   What didn't work first

   Tried: Write the recovered p and q back into the PEM and decrypt with openssl rsautl or openssl pkeyutl

   Manually patching a PKCS#1 PEM with new integer bytes requires recalculating DER length fields, recomputing dp, dq, qInv, and re-encoding in base64 - any single byte off makes openssl reject the file. It is far easier to compute d directly in Python or Sage with pow(e, -1, (p-1)*(q-1)) and decrypt the raw ciphertext as an integer, bypassing openssl entirely.

   Tried: Compute phi as lcm(p-1, q-1) instead of (p-1)*(q-1) when deriving d

   Using the Carmichael totient lambda = lcm(p-1, q-1) instead of Euler's phi = (p-1)(q-1) produces a valid d that decrypts correctly for most ciphertexts, but if the challenge expects a specific padding scheme (e.g. PKCS#1 v1.5) and the d values differ, the decrypted bytes may not strip padding correctly and the output appears as garbage. Use (p-1)*(q-1) to match the standard RSA key derivation assumed by the challenge.

   Learn more

   Once p is exact, the rest is standard RSA: q = N // p (integer division, no remainder), phi = (p-1)(q-1), d = e^-1 mod phi, and decryption is m = c^d mod N. The assert p * q == N check is essential - if it fails, the Coppersmith output is wrong and you should re-run with a larger m.

   The lesson: when a partial prime leaks (even with most bits known), Coppersmith's small-root method can reconstruct the whole prime as long as the unknown bits are small relative to the modulus size. This is why side-channel attacks that leak even a few hundred bits of a 1024-bit prime are catastrophic in practice.

Flag

Parse the PEM with openssl asn1parse to get N and a partially-zeroed p. Define f(x0,x1,x2) = _p + 2^16*x0 + 2^240*x1 + 2^352*x2, then run multivariate Coppersmith (LLL, m=6, bounds 2^40/2^32/2^40) in Sage to recover the three missing chunks. Reconstruct p, compute q = N//p and d = e^-1 mod (p-1)(q-1), then decrypt.