ECDSA 随机数高位窗口泄露恢复私钥 WP

给出的曲线为 secp256k1每条 ECDSA 签名记录额外泄露了随机数 k 的高位窗口低 44 位未知。利用这些不完整窗口可以建立 Hidden Number Problem之后用 LLL 格规约恢复私钥。## 漏洞原理ECDSA 签名满足texts k^-1 * (H(m) r*d) mod n其中- d 是私钥- n 是 secp256k1 的基点阶- r, s 来自 DER 签名- H(m) 是消息哈希本题签名验证可确认使用 SHA-256- k 是每次签名随机数。变形得到textk s^-1 * (H(m) r*d) mod n又因为高位已知、低位未知textk K xK k_high * 2^440 x 2^44代入后textK x s^-1 * (H(m) r*d) mod n继续整理text(r*s^-1)*d (H(m)*s^-1 - K) x mod n记texta_i r_i * s_i^-1 mod nc_i H(m_i) * s_i^-1 - K_i mod n则每条样本给出一个小误差方程texta_i*d c_i x_i mod n, 其中 0 x_i 2^44这就是典型的 Hidden Number Problem。样本数量足够时可以通过格规约找到共同的 d。## 格构造设 B 2^44样本数为 m。脚本中使用 CVP/LLL embedding并将有理格整数化。构造出的短向量目标形态为text(n*x_1, n*x_2, ..., n*x_m, B*d, B*n)由于所有 x_i 都小于 B这个向量相对较短。对构造矩阵做 LLL 后从短向量倒数第二列恢复 B*d再除以 B 得到候选私钥。最后用附件中的压缩公钥验证候选私钥是否正确。## 解题脚本依赖bashpip install ecdsa sympy运行方式bashpython solve.py data.json完整脚本如下pythonimport jsonimport hashlibimport sysfrom pathlib import Pathfrom ecdsa import SECP256k1, SigningKeyfrom ecdsa.util import sigdecode_derfrom sympy import Matrixdef find_data_path(argv):if len(argv) 1:return Path(argv[1]).resolve()here Path(__file__).resolve().parentcandidates [here / data.json,here.parent / attachment_work / data.json,Path.cwd() / attachment_work / data.json,Path.cwd() / data.json,]for path in candidates:if path.exists():return path.resolve()raise FileNotFoundError(data.json not found; pass it as argv[1])def recover_private_key(data_path):data json.loads(Path(data_path).read_text(encodingutf-8))if data[curve] ! secp256k1:raise ValueError(this solver expects secp256k1)n SECP256k1.orderB 1 int(data[unknown_low_bits])samples data[samples]m len(samples)a_values []c_values []for sample in samples:r, s sigdecode_der(bytes.fromhex(sample[sig_der]), n)h int.from_bytes(hashlib.sha256(bytes.fromhex(sample[msg])).digest(), big)known_k int(sample[k_high]) * Binv_s pow(s, -1, n)a_values.append((r * inv_s) % n)c_values.append((h * inv_s - known_k) % n)rows []for i in range(m):row [0] * (m 2)row[i] n * nrows.append(row)rows.append([a * n for a in a_values] [B, 0])rows.append([c * n for c in c_values] [0, B * n])reduced Matrix(rows).lll(delta0.99)pubkey bytes.fromhex(data[pubkey])for i in range(reduced.rows):row [int(reduced[i, j]) for j in range(reduced.cols)]if abs(row[-1]) ! B * n:continuefor signed_d_part in (row[-2], -row[-2]):if signed_d_part % B:continued (signed_d_part // B) % nif not (1 d n):continuevk SigningKey.from_secret_exponent(d, curveSECP256k1).verifying_keyif vk.to_string(compressed) pubkey:return draise RuntimeError(private key not found)def main():data_path find_data_path(sys.argv)d recover_private_key(data_path)key32 d.to_bytes(32, big)flag_bytes d.to_bytes((d.bit_length() 7) // 8, big)print(data:, data_path)print(private_key_hex:, key32.hex())print(flag:, flag_bytes.decode(ascii))if __name__ __main__:main()## 本地验证结果在本地运行powershellpythonsolve.py data.json