Corrupt-Key-2 — Multivariate Coppersmith Attack

Files: private.key (corrupted prime p), msg.enc (128 bytes)

Analysis

The corrupted prime p has 3 blocks of zeroed bytes — 114 unknown bits total (~23% unknown, ~77% known). With >50% bits known, this is a candidate for a multivariate Coppersmith attack based on May & Ritzenhofen (2008).

Block	Position	Unknown Bits
1	bits 16-57	41 bits
2	bits 239-272	33 bits
3	bits 352-392	40 bits

Attack Methodology

Polynomial Construction: f_bar(x1,x2,x3) = p0 + 2^16·x1 + 2^239·x2 + 2^352·x3
Lattice Generation: Build helper polynomials, construct lattice (m=7, t=1)
LLL Reduction: Find short lattice vectors → polynomials with small roots
Newton Iteration: Converge to integer values of x1, x2, x3
Prime Recovery: Reconstruct p, verify N mod p = 0

Performance

Metric	Value
LLL Runtime	~313 seconds
Newton Iterations	11
Matrix Size	120 × 120
Total Time	~5.5 minutes

Flag

picoCTF{1d68da1447328c3f11541d076c9c613957d86566}