corrupt-key-2 picoMini by redpwn Solution

Description

1. Step 1Identify the three missing chunks in p

   Observation

   The prime carries three separate runs of zero bytes in the raw DER. Map each region to a bit offset and width before attempting any 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!

   What didn't work first

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

   openssl rsa runs its sanity checks first and errors out before printing anything, because the fields no longer agree. asn1parse reads the DER bytes without validating any mathematical relationship, so it dumps the prime even with holes in it.

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

   An RSA prime has no leading zero bytes in its canonical encoding, so any zero run away from the start is erased data, not padding. Shift the remaining bytes over and you get a value that does not divide the modulus. Locate each region by bit offset and treat it as an unknown.

   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 2Run multivariate Coppersmith (LLL) to recover the missing bits

   Observation

   Three unknown chunks totaling around 112 bits sit inside a 512-bit prime, and that prime divides the modulus. So the unknowns are small roots of a three-variable polynomial, which is what Coppersmith's lattice method is for.

   Coppersmith's theorem, in the divisor form used here, says that if a polynomial f has a root modulo a divisor p of N and that root is small enough relative to p, it can be found in polynomial time via LLL lattice reduction. p is 512 bits and the three unknowns total 112 bits, so the root is far below the bound and the reduction succeeds comfortably. 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

   The single-variable solver handles one unknown, so pinning the other two to zero collapses the problem into a polynomial with no valid root, since the real chunks are nonzero. You get an empty result or a spurious value that fails the divisibility check. Use a multivariate implementation that builds one lattice over all three.

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

   A smaller lattice parameter means fewer shift polynomials. Across three variables and 112 unknown bits, a value of 2 leaves the Howgrave-Graham condition unsatisfied, so LLL returns a short vector that is not the root you want and the check fails on a wrong prime. This needs 6, and reducing it produces garbage without 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) against a 512-bit prime divisor of a 1024-bit N, 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 3Reconstruct the private key and decrypt

   Observation

   The solver returns the three missing chunks, and checking that the reconstructed prime divides the modulus confirms them. From there the private exponent follows from the standard formula.

   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(m.to_bytes((m.bit_length() + 7) // 8, "big").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

   Patching the PEM by hand means recomputing DER length fields, the CRT parameters, and the base64 encoding, and one wrong byte gets the file rejected. Computing the private exponent directly and decrypting the ciphertext as an integer skips openssl entirely.

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

   This one is not actually a failure: d from lcm(p-1, q-1) is congruent to the Euler-derived d modulo the order of every element, so c^d mod N gives the same plaintext. It is simply a smaller exponent. If the decryption still looks like garbage, the fault is upstream, almost always a p that does not divide N.

   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.