给出的曲线为 `secp256k1`，每条 ECDSA 签名记录额外泄露了随机数 `k` 的高位窗口，低 `44` 位未知。利用这些不完整窗口可以建立 Hidden Number Problem，之后用 LLL 格规约恢复私钥。
## 漏洞原理
ECDSA 签名满足：
```text
s = k^-1 * (H(m) + r*d) mod n
```
其中：
- `d` 是私钥；
- `n` 是 secp256k1 的基点阶；
- `r, s` 来自 DER 签名；
- `H(m)` 是消息哈希，本题签名验证可确认使用 SHA-256；
- `k` 是每次签名随机数。
变形得到：
```text
k = s^-1 * (H(m) + r*d) mod n
```
又因为高位已知、低位未知：
```text
k = K + x
K = k_high * 2^44
0 <= x < 2^44
```
代入后：
```text
K + x = s^-1 * (H(m) + r*d) mod n
```
继续整理：
```text
(r*s^-1)*d + (H(m)*s^-1 - K) = x mod n
```
记：
```text
a_i = r_i * s_i^-1 mod n
c_i = H(m_i) * s_i^-1 - K_i mod n
```
则每条样本给出一个小误差方程：
```text
a_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` 得到候选私钥。最后用附件中的压缩公钥验证候选私钥是否正确。
## 解题脚本
依赖：
```bash
pip install ecdsa sympy
```
运行方式：
```bash
python solve.py data.json
```
完整脚本如下：
```python
import json
import hashlib
import sys
from pathlib import Path
from ecdsa import SECP256k1, SigningKey
from ecdsa.util import sigdecode_der
from sympy import Matrix
def find_data_path(argv):
if len(argv) > 1:
return Path(argv[1]).resolve()
here = Path(__file__).resolve().parent
candidates = [
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(encoding="utf-8"))
if data["curve"] != "secp256k1":
raise ValueError("this solver expects secp256k1")
n = SECP256k1.order
B = 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"]) * B
inv_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 * n
rows.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(delta=0.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:
continue
for signed_d_part in (row[-2], -row[-2]):
if signed_d_part % B:
continue
d = (signed_d_part // B) % n
if not (1 <= d < n):
continue
vk = SigningKey.from_secret_exponent(d, curve=SECP256k1).verifying_key
if vk.to_string("compressed") == pubkey:
return d
raise 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()
```
## 本地验证结果
在本地运行：
```powershell
pythonsolve.py data.json
```
```