给出的曲线为 `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
```
```