Recover RSA factors from a leaked CRT exponent

The visible fraction of a private key is a poor measure of exposure. A structured encoding repeats algebraically related values, so a complete small-looking field may reveal more than a large contiguous slice of apparently random bytes.

Research anchor and scope

CryptoHack’s PEM recovery article identifies a complete prime q, a complete reduced exponent dp, low bits of p, and partial modulus and dq information. It assumes the common public exponent 65537 and validates the recovered fields. The result does not establish that any arbitrary half-redacted PEM is recoverable; field boundaries and which integers survive are decisive.

Identify fields before doing algebra

PEM is an armor around encoded binary data. Base64 characters span six-bit boundaries, while DER integers have tags, lengths, and sometimes a leading sign byte. Annotate reliable fragments by byte offset and keep uncertain transcription separately. Do not concatenate surviving lines across a redacted gap and treat the resulting bytes as a valid DER stream.

For a PKCS#1 RSA private key, determine which values are complete, which have known high or low bits, and which are absent. A full reduced exponent can be more immediately useful than a similarly sized fragment of the full private exponent. Preserve leading-zero and signed-integer rules while interpreting lengths.

Use the reduced exponent equation

For dp = d mod (p-1), RSA’s inverse relation gives e*dp - 1 = k*(p-1). With 0 < dp < p-1, the integer multiplier satisfies 1 <= k < e. If e is small and known, enumerate this multiplier rather than factor a large unrelated integer.

As a toy example, take e = 7, dp = 3. Then e*dp-1 = 20. The candidate k = 2 gives p = 20/2 + 1 = 11. If an independently known q = 13 is available, the modulus is 143 and the private inverse modulo 120 is 103; indeed 103 mod 10 = 3. Other divisors may give prime-looking candidates, so this equation alone needs external validation.

Validate and state the remaining uncertainty

Require exact divisibility, primality, plausible bit length, and consistency with every reliable surviving fragment. If the modulus is known, p*q = n is decisive. With a partial modulus, compare only the bits whose offsets are established. Recompute CRT exponents and coefficient, then test a public/private round trip on a harmless integer.

Unknown e, an incomplete dp, mislabeled fields, or OCR errors change the attack substantially. Avoid claiming a generic Coppersmith result when the actual recovery comes from a complete CRT field and a bounded multiplier search. The reusable lesson is to reason about algebraic redundancy after identifying the encoding.