Description

My RSA key is corrupted. Can you fix it?

Setup

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

Notice that openssl rejects the key: the lower bits of p are zeroed out, so the key is internally inconsistent.

bash

# Download the broken key and ciphertext from the challenge page.

Solution

Want to try it yourself first?

The guided walkthrough reveals hints one step at a time.

Walk me through it

The corrupted PEM holds the upper 256 bits of one RSA prime p, but the lower bits are zeroed. Because the lower bits are unknown, plain division cannot reconstruct p. Instead the challenge calls for Coppersmith's small-roots method: express p as a polynomial whose unknown piece is small relative to n, then use LLL lattice reduction to find that unknown piece exactly.

Step 1
Parse the PEM with asn1parse to read the partial prime
Observation
I noticed that openssl rsa rejected the key entirely due to internal inconsistency, which suggested the corruption was structural and that a lower-level tool bypassing validation, specifically openssl asn1parse, was needed to read the raw integer fields directly from the DER encoding.
Run openssl asn1parse on the corrupted PEM. The nine integers in order are: version, n, e, d, p, q, dp, dq, qinv. In this challenge p is present but its lower 256 bits are all zero - you will see a very large integer whose binary representation ends with a long run of zeros. Record n, e, and the partial p_high.
bash
# Dump the raw ASN.1 integers:
bash
openssl asn1parse -in private.key
bash
bash
# The printed integers map to: version, n, e, d, p, q, dp, dq, qinv
bash
# p will appear as a large number ending in many zero bits.
Expected output
```
picoCTF{d741543f...}
```
What didn't work first
Tried: Run openssl rsa -in private.key -text to inspect the key fields
openssl rsa validates internal consistency before printing anything, so it exits with an error like 'no start line' or 'bad end line' when the key is corrupted. asn1parse skips that validation layer and reads raw DER bytes directly, which is exactly what you need when the key values are inconsistent.
Tried: Try to identify which field is corrupted by looking at the PEM base64 visually
Base64 obscures the byte-level structure completely - you cannot tell from the PEM text which ASN.1 integer is zeroed. You must decode it with asn1parse and compare the nine integers against what a valid PKCS#1 key should contain; the corrupted p will stand out as an unusually large number whose value ends in a suspicious number of zeros.
Learn more
A PKCS#1 RSA private key (RFC 8017) is an ASN.1 SEQUENCE of nine INTEGER values: version, n, e, d, p, q, dp, dq, qinv. The PEM file is that DER structure base64-encoded between -----BEGIN RSA PRIVATE KEY----- markers.
openssl rsa cross-checks all nine fields and refuses to load the file if they are inconsistent. openssl asn1parse does no such validation - it walks the raw ASN.1 and prints each integer as-is, letting you read whatever bytes survived the corruption.
In corrupt-key-1 the corrupted field is p: the upper 256 bits are intact, but the lower bits are zeroed. This gives you p_high, the high-order portion, and leaves an unknown remainder x such that p = p_high + x where x is small compared to n.
Step 2
Recover the full prime with Coppersmith's small-roots method
Observation
I noticed that asn1parse revealed p with its lower 256 bits zeroed, meaning only the high-order portion was intact; this partial prime disclosure is exactly the setup for Coppersmith's small-roots theorem, which can recover the unknown lower bits because they are small relative to n.
Write f(x) = p_high * 2^(p_bits - p_high_bits) + x in SageMath's polynomial ring over Zmod(n). The unknown x equals the lower bits of p. Because x < n^(1/2) approximately, the Coppersmith bound is satisfied and small_roots finds x in seconds. A complication: the exact boundary between the known and unknown bits depends on how many trailing zeros you count, so the solve function brute-forces the last 7 uncertain bits before calling small_roots, checking each candidate against n with gcd.
bash
# Run in SageMath (sage script.sage or sage -python if adapted):
bash
python
from tqdm import tqdm
bash
python
def small_roots(f, X, beta=1.0, m=None):
bash
N = f.parent().characteristic()
bash
delta = f.degree()
bash
if m is None:
bash
epsilon = RR(beta^2/f.degree() - log(2*X, N))
bash
m = max(beta**2/(delta * epsilon), 7*beta/delta).ceil()
python
t = int((delta*m*(1/beta - 1)).floor())
bash
f = f.monic().change_ring(ZZ)
bash
P,(x,) = f.parent().objgens()
bash
g = [x**j * N**(m-i) * f**i for i in range(m) for j in range(delta)]
bash
g.extend([x**i * f**m for i in range(t)])
bash
B = Matrix(ZZ, len(g), delta*m + max(delta,t))
bash
for i in range(B.nrows()):
bash
for j in range(g[i].degree()+1):
bash
B[i,j] = g[i][j]*X**j
bash
B = B.LLL()
bash
f = sum([ZZ(B[0,i]//X**i)*x**i for i in range(B.ncols())])
bash
roots = set([f.base_ring()(r) for r,m in f.roots() if abs(r) <= X])
bash
return [root for root in roots if N.gcd(ZZ(f(root))) >= N**beta]
bash
python
def recover(p_high, n, m):
bash
p_bits = (len(bin(n))-2)//2
bash
p_high_bits = len(bin(p_high)) - 2
bash
PR.<x> = PolynomialRing(Zmod(n))
bash
f = p_high * 2**(p_bits-p_high_bits) + x
bash
x = small_roots(f, X=2**(p_bits-p_high_bits), beta=0.4, m=m)
bash
if x == []:
bash
return None
python
p = int(f(x[0]))
bash
return p
bash
bash
# Fill in n and _p_high from openssl asn1parse:
bash
n = <n_from_asn1parse>
bash
_p_high = <partial_p_from_asn1parse>
bash
python
def solve(bits, m):
bash
for x in tqdm(range(2**bits, -1, -1)):
bash
_p = _p_high + x * 2**(256-bits)
python
p_high = int(bin(_p)[:256+bits+2], 2)
bash
p = recover(p_high, n, m)
bash
if p is not None:
bash
return p
bash
bash
p = solve(bits=7, m=18)
When small_roots returns a nonempty list, plug x back into f to get the full prime p. Verify with assert n % p == 0.
What didn't work first
Tried: Call small_roots with beta=0.5 instead of beta=0.4 and skip the outer brute-force loop
The beta parameter sets the lower bound on the root's relationship to n - using 0.5 tightens the Coppersmith bound and causes small_roots to return an empty list for this challenge because the unknown portion of p sits just outside that bound. Lowering beta to 0.4 relaxes the constraint enough to recover the root, at the cost of requiring a larger m lattice dimension. Skipping the 7-bit outer loop also fails because the boundary between intact and zeroed bits is ambiguous by a few positions.
Tried: Use factordb or yafu to factor n directly instead of applying Coppersmith
The modulus n in this challenge is 1024 bits, which is far beyond what general-purpose integer factoring tools like yafu or factordb can handle in a CTF timeframe. Coppersmith works because you already have the high-order half of p, reducing the search to a small unknown; without that partial knowledge, factoring n would be computationally infeasible.
Learn more
Why does this work? Coppersmith's theorem (1996) says: given a monic degree-d polynomial f over Z/nZ, any root x0 with |x0| < n^(1/d - epsilon) can be found in polynomial time. Here d = 1 and x is roughly n^(1/2) in size (the unknown lower half of a 512-bit prime), so the bound is satisfied.
The algorithm builds a lattice from scaled shifts of f. By the LLL algorithm, the shortest vector in that lattice corresponds to a polynomial with integer coefficients that is divisible by a high power of p, and whose root can be read off directly without factoring n. This is fundamentally different from brute force: LLL runs in polynomial time regardless of how many bits are unknown.
The outer solve loop brute-forces only 7 bits (128 candidates) because the exact bit boundary between the intact high part and the zeroed low part is ambiguous by a few bits. For each candidate high part, recover calls small_roots; the first call that returns a nonzero p wins.
This technique is also used in the related challenge corrupt-key-2, which has more bits unknown and requires tuning the m parameter higher.
Step 3
Reconstruct the key and decrypt the ciphertext
Observation
I noticed that once small_roots returned the full prime p, the remaining RSA components (q, phi, d) are derivable through standard arithmetic, which meant decryption of msg.enc was a straightforward application of textbook RSA with no further cryptanalysis needed.
With p in hand, everything else follows from plain RSA arithmetic. Compute q = n // p (exact integer division), verify p * q == n, then derive d and decrypt.
bash
from Crypto.Util.number import long_to_bytes
bash
bash
e = 0x10001
bash
q = n // p
bash
assert p * q == n
bash
d = pow(e, -1, (p-1)*(q-1))
bash
python
c = open('msg.enc', 'rb').read()
bash
from Crypto.Util.number import bytes_to_long
bash
c = bytes_to_long(c)
bash
m = pow(c, d, n)
python
print(long_to_bytes(m))
Learn more
Once p is known, recovering q is a single integer division because n = p * q by definition. With both primes in hand, phi = (p-1)*(q-1) and d = e^-1 mod phi follow immediately. Decryption is then textbook RSA: m = c^d mod n.
The broader lesson: even a partial leak of one RSA prime - here only the high-order half - is enough to completely break the key via lattice methods. This is why implementations must never expose partial prime material, and why random padding (OAEP) alone does not compensate for a weak key generation process.

Interactive tools

RSA CalculatorDecrypt RSA ciphertexts, factor n from the sum of primes, or generate key parameters. Handles arbitrarily large BigInt values.

Flag

Reveal flag

picoCTF{d741543f...}

Parse the PEM with openssl asn1parse to extract n, e, and the upper 256 bits of p. Define f(x) = p_high * 2^(unknown_bits) + x over Z/nZ, then use Coppersmith small_roots (LLL) in SageMath - bruting 7 boundary bits and calling small_roots for each candidate - to recover the full prime p. Standard RSA arithmetic then yields q, d, and the flag.

Key takeaway

Coppersmith's small-roots method recovers an RSA prime when a contiguous high-order chunk is known and the unknown bits are small relative to the modulus, by recasting 'find a small root' as 'find a short lattice vector' that LLL solves in polynomial time. Once one prime falls, the rest of the key follows from textbook arithmetic, so even a partial leak of a single prime is catastrophic. This is why implementations must never expose partial prime material and why OAEP padding cannot compensate for a weak key-generation process.

corrupt-key-1 picoMini by redpwn Solution

Description

Solution

Flag

Key takeaway

Related reading

Useful tools for Cryptography

What to try next

Mini RSA

EVEN RSA CAN BE BROKEN???

Scrambled: RSA

b00tl3gRSA3

rsa-pop-quiz

b00tl3gRSA2