piyakcrypt
- •
Attribution
- •
Solved by rn. AI-assisted solve; the original assistance link is preserved below.
- •
- •
What it asked
- •
Recover one secp256k1 private key and submit it. Every private key shares a 40-bit MT19937-generated prefix; each ECDSA nonce exposes a predictable 128-bit upper component and an
os.urandom128-bit lower component.
- •
- •
Approach
- •
Menu 2 reveals the already-shifted shared prefix . Do not shift it a second time. Write the private scalar as , with .
- •
Menu 5 emits invertibly scrambled MT19937 words. Exactly eight panels give words, enough to clone the state. Reading a ninth panel and discarding values would desynchronize later predictions.
- •
Each signature consumes two predicted 64-bit words. Reproduce
make_piecewith the signature’s global position to obtain the known upper nonce component ; write with . - •
ECDSA gives . After multiplying by , define and . Then .
- •
Build a balanced integer lattice with . A target lattice vector has coordinates . LLL only returns a reduced basis, so scan candidate rows instead of assuming row zero is the answer.
- •
Validate every candidate by all nonce-tail bounds and by recomputing its secp256k1 public point. The rare or retry path consumes extra MT output; a robust live client must track that if it occurs.
- •
- •
Solution
- •
from randcrack import RandCrack from sage.all import Matrix, ZZ, inverse_mod N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 MASK32, MASK64 = (1 << 32) - 1, (1 << 64) - 1 X, K, W = 1 << 216, 1 << 128, 1 << 88 def ror(x, n, width): n %= width; mask = (1 << width) - 1 return ((x >> n) | (x << (width - n))) & mask def rol(x, n, width): return ror(x, -n, width) def unpanel(y, pos): salt = (0xA5A5A5A5 + pos * 0x6D2B79F5) & MASK32 bump = (0x9E3779B9 ^ (pos * 0x85EBCA6B)) & MASK32 return ror((y - bump) & MASK32, pos * 7 + 3, 32) ^ salt def fold(x, pos, lane): x ^= ((pos + 1) * 0xD6E8FEB86659FD93 + lane * 0xA0761D6478BD642F) & MASK64 return (rol(x, 17 + pos*9 + lane*23, 64) * 0x9E6C63D0676A9A99 + 0xD1B54A32D192ED03) & MASK64 def predicted_A(rc, pos): a, b = rc.predict_getrandbits(64), rc.predict_getrandbits(64) return (((fold(a, pos, 0) << 64) | fold(b, pos, 1)) << 128) % N def recover_piece(tag_shifted, signatures, public_point, scalar_mul): rows = len(signatures) + 2 B = Matrix(ZZ, rows, rows) B[0, 0], B[-1, 1] = 1, X equations = [] for i, (z, r, s, A) in enumerate(signatures): sinv = inverse_mod(s, N) t = r * sinv % N u = (z * sinv + t * tag_shifted - A) % N equations.append((t, u)) B[0, i+2] = W * t B[i+1, i+2] = W * N B[-1, i+2] = W * u candidates = [] for row in B.LLL(): if abs(row[1]) != X: continue row = row if row[1] > 0 else -row piece = int(row[0]) if 0 <= piece < X and all((t*piece + u) % N < K for t,u in equations): secret = (tag_shifted + piece) % N if scalar_mul(secret) == public_point: candidates.append(secret) assert len(set(candidates)) == 1, candidates return candidates[0] rc = RandCrack() for pos, displayed in eight_panels: # exactly 8*78 = 624 words rc.submit(unpanel(displayed, pos)) signatures = [] for pos, (z, r, s) in enumerate(four_signatures): signatures.append((z, r, s, predicted_A(rc, pos))) secret = recover_piece(tag_shifted, signatures, target_public_point, ec_mul_G) submit_secret(secret)
- •
- •
Verification
- •
A synthetic challenge-sized four-signature instance recovered the exact 216-bit private-key tail and passed all inequalities. The original live service and its signatures were not replayed during this refactor.
- •
- •
Concepts
- •