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 1Parse the PEM with asn1parse to read the partial prime
Observation
openssl rsa rejects the key outright on internal inconsistency, so the corruption is structural. asn1parse skips that validation and reads the raw integer fields out of 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.
What didn't work first
Tried: Run openssl rsa -in private.key -text to inspect the key fields
openssl rsa checks internal consistency before printing anything, so a corrupted key gets an error and no output. asn1parse skips that layer and reads the DER bytes directly, which is what you want when the values do not agree.
Tried: Try to identify which field is corrupted by looking at the PEM base64 visually
Base64 hides the byte structure entirely, so the PEM text says nothing about which integer was zeroed. Decode it and compare the nine integers against what a valid key holds; the corrupted prime stands out by the run of zeros at its end.
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 2Recover the full prime with Coppersmith's small-roots method
Observation
The prime comes back with its lower 256 bits zeroed and only its high half intact. A partial prime like that is exactly the setup for Coppersmith's small-roots theorem, since the unknown portion is small relative to the modulus.
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 < 2^256 = n^(1/4), which is the Coppersmith bound for a 512-bit divisor of a 1024-bit modulus, 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 bounds how the root relates to the modulus, and 0.5 tightens it enough that the unknown portion falls just outside, so the solver returns nothing. Lowering it to 0.4 relaxes the constraint at the cost of a larger lattice. The small outer loop matters too, 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 is 1024 bits, well past what yafu or factordb will finish inside a CTF. Coppersmith works only because you already hold the top half of the prime, which shrinks the search to something small. Without that, factoring is out of reach.
Learn more
Why does this work? Coppersmith's theorem (1996), in the divisor form due to Howgrave-Graham, says: given a monic degree-d polynomial f over Z/nZ and a divisor p of n with p >= n^beta, any root x0 of f modulo p with |x0| < n^(beta^2/d) can be found in polynomial time. Here d = 1, p is a 512-bit prime of a 1024-bit n so beta = 0.5, and the bound is n^(1/4) = 2^256. The unknown lower half of p is exactly 256 bits, so it sits right at the bound, which is why the script relaxes beta slightly and brute-forces a few boundary bits.
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, where the missing bits are split across three non-contiguous chunks instead of one contiguous block, which calls for a multivariate version of the same lattice construction.
Step 3Reconstruct the key and decrypt the ciphertext
Observation
With the full prime recovered, the other components follow by ordinary arithmetic, and decryption is textbook RSA with no cryptanalysis left.
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 method recovers an RSA prime when a contiguous high-order chunk is known and the unknown bits are small against the modulus, by turning find a small root into find a short lattice vector, which LLL solves in polynomial time. One prime falling gives up the rest of the key by ordinary arithmetic, so a partial leak of a single prime is total. Implementations must never expose partial prime material, and no amount of padding compensates for weak key generation.

corrupt-key-1 picoMini by redpwn Solution

Description

Solution

Flag

Key takeaway

Related reading

Useful tools for Cryptography

Where to go next

Mini RSA

b00tl3gRSA3

rsa-pop-quiz

b00tl3gRSA2

SRA

StegoRSA