附件链接：https://wwapq.lanzoub.com/b01bjtm29a|密码:6gpp
crypto-Off the Curve
题目描述：
The Roadrunner team uses Northstar Docs to distribute encrypted reports. Tomorrow's quarterly review depends on rpt-042, but the original copy cannot be opened. Northstar marks the delivery complete, and every fresh download returns the same locked file. As a member of the project review workspace, recover the contents of the original delivery.
Credentials: analyst@northstar.test / Curve-Review-2026
No attachments are provided for this challenge.
附件：无
文件名 rpt-042.envelope.json。本次信封中和解密有关的字段是：
{
"aad": {
"classification": "internal-test",
"content_type": "text/plain; charset=utf-8",
"created_at": "2026-09-16T22:40:00Z"
},
"ciphertext": "fHZEj+LBRPb6ib/sQxSWSxCm7g1+Gdy5a9MaqdP90BQ0ViUpNnEgNoum3qVdiGgGL7bJryYdURX40k8TJ5KLLM53cCzdh5LKUYMQ3KLQA6hzSpnGm3AoMgtpyaKJ0UZcUQ3GVXy8m5DJad1Srta3eT50QiRHUmcXwMxRphSq2uwxPWazHdwSj18Iz7cSYPw4axkVAzWvh8tJeXe7on0IW3E+Fl0JUrtU28An4n2DTZntra0lPHb514bEyYK5+brc53RmCmjk2rhCDc5u5MQ+0jCo6VmFZlgIHRqJgxMOeGmoUBjZhoEA",
"info": {
"key_version": "doc-kek-2026.09-v3",
"project_id": "prj-northstar",
"report_id": "rpt-042"
},
"nonce": "62415854be17e5c755fa6ae7",
"recipient_public_key": "02315f",
"tag": "bbfc9923ab97b4e9d7c3c46dcd25335b"
}
页面上的记录 公钥 版本 WP 里怎么用
Rotated browser key / legacy-rotated-05 022308 doc-kek-2026.09-v4，Active 轮换后的新私钥，不参加 CRT
Rotated mobile key / legacy-rotated-06 024c87 doc-kek-2026.09-v4，Active 同上
Android 8 field client / legacy-android-01 025c5d doc-kek-2026.09-v3，Archived 用了，余数 2044
Browser fallback A / legacy-browser-02 02c535 doc-kek-2026.09-v3，Archived 用了，余数 149
/sdk.js 的点加和点乘都不检查点是否在基曲线上。四个 v3 客户端公钥解压后落在四条不同的弱曲线上，点的阶都是三四千的素数。诊断回包给出
SHA256("DOCSHARE-DIAG\0" || key_id || nonce || 共享点编码) 的前 16 字节
/sdk.js 公开的基曲线是
y^2 = x^3 + x + 7 (mod 65519) G = (4, 17054) n = 65444
收件人 02315f 的 x = 0x315f = 12639，解压得到 (12639, 7624)，它在基曲线上。四个 v3 公钥的 Legendre 符号都是 -1，不在基曲线上。各自的 b' 和点阶是：
公钥 b' 点阶
025c5d 46333 3257
02c535 10369 4079
022b09 53552 3863
025d04 9527 2843
sealReport 的派生是：
infoHash = SHA256(canonical(info))
binding = SHA256("northstar-report-scalar-binding\0" || u32be(s) || infoHash)
master = scrypt(encode(shared) || binding,
"northstar-report-v3\0" || nonce || infoHash,
N=32768, r=8, p=1, dkLen=32)
aesKey = HMAC-SHA256(master, "northstar-aes256-gcm-key\0" || infoHash)
用空 HMAC 密钥伪造管理员
{
"role": "admin",
"permissions": {
"audit": true,
"diagnostics": true,
"register_keys": true,
"read": true
}
}
在四条弱曲线上恢复服务器私钥
legacy-android-01 nonce=fb7f739f5d0c3df5 tag=1d11fc5bc92f4de314e57279ab9377f4
legacy-browser-02 nonce=878d82e617d5d542 tag=0f7762f43d46febbc3c3d94b29eeabb1
legacy-rn-03 nonce=82b96ac4930eeb9d tag=6298235f87fe98317e1ed02028bd6127
legacy-browser-04 nonce=e8059d84281d312e tag=644b8dfac811fcf0aad60230cfc1e375
payload:
import base64
import hashlib
import hmac
import json
import sys
import time
from urllib.error import HTTPError, URLError
from urllib.request import ProxyHandler, Request, build_opener
from Crypto.Cipher import AES
BASE = "http://oncgp8fs.nestctf.cyberpeace.cn:58080"
USERNAME = "analyst@northstar.test"
PASSWORD = "Curve-Review-2026"
P = 65519
A = 1
B = 7
V3_KEYS = (
"legacy-android-01",
"legacy-browser-02",
"legacy-rn-03",
"legacy-browser-04",
)
OPENER = build_opener(ProxyHandler({}))
def request(path, token=None, method="GET", body=None):
headers = {"User-Agent": "Mozilla/5.0", "Accept": "application/json"}
data = None
if body is not None:
data = json.dumps(body).encode()
headers["Content-Type"] = "application/json"
if token:
headers["Authorization"] = "Bearer " + token
last_error = None
for attempt in range(4):
req = Request(BASE + path, data=data, headers=headers, method=method)
try:
with OPENER.open(req, timeout=30) as response:
return response.status, response.read()
except HTTPError as error:
raise SystemExit(f"{method} {path} -> HTTP {error.code}: {error.read()[:300]!r}") from error
except (URLError, ConnectionError, TimeoutError) as error:
last_error = error
time.sleep(0.4 * (attempt + 1))
raise SystemExit(f"{method} {path} failed: {last_error}")
def b64url(raw):
return base64.urlsafe_b64encode(raw).rstrip(b"=").decode()
def mint(header, payload, key=b""):
signing_input = b".".join((
b64url(json.dumps(header, separators=(",", ":")).encode()).encode(),
b64url(json.dumps(payload, separators=(",", ":")).encode()).encode(),
))
signature = hmac.new(key, signing_input, hashlib.sha256).digest()
return signing_input.decode() + "." + b64url(signature)
def add(point, other):
if point is None:
return other
if other is None:
return point
x1, y1 = point
x2, y2 = other
if x1 == x2 and (y1 + y2) % P == 0:
return None
if x1 == x2:
slope = ((3 * x1 * x1 + A) * pow((2 * y1) % P, P - 2, P)) % P
else:
slope = ((y2 - y1) * pow((x2 - x1) % P, P - 2, P)) % P
x3 = (slope * slope - x1 - x2) % P
y3 = (slope * (x1 - x3) - y1) % P
return (x3, y3)
def mul(scalar, point):
result = None
while scalar:
if scalar & 1:
result = add(result, point)
point = add(point, point)
scalar >>= 1
return result
def decompress(hex_key):
raw = bytes.fromhex(hex_key)
x = (raw[1] << 8) | raw[2]
rhs = (x * x * x + A * x + B) % P
y = pow(rhs, (P + 1) // 4, P)
if (y & 1) != (raw[0] & 1):
y = (-y) % P
return (x, y)
def on_base_curve(point):
x, y = point
return (y * y - (x * x * x + A * x + B)) % P == 0
def curve_order(b_value):
total = 1
for x in range(P):
rhs = (x * x * x + A * x + b_value) % P
legendre = pow(rhs, (P - 1) // 2, P)
if legendre == 0:
total += 1
elif legendre == 1:
total += 2
return total
def point_order(point):
x, y = point
b_value = (y * y - (x * x * x + A * x)) % P
order = curve_order(b_value)
remainder = order
divisor = 2
primes = []
while divisor * divisor <= remainder:
while remainder % divisor == 0:
primes.append(divisor)
remainder //= divisor
divisor += 1 if divisor == 2 else 2
if remainder > 1:
primes.append(remainder)
for prime in sorted(set(primes)):
while order % prime == 0 and mul(order // prime, point) is None:
order //= prime
return b_value, order
def encode_full(point):
if point is None:
return bytes([0])
x, y = point
return bytes([4, (x >> 8) & 255, x & 255, (y >> 8) & 255, y & 255])
def recover_residue(key_id, point, order, nonce_hex, tag_hex):
prefix = b"DOCSHARE-DIAG\x00" + key_id.encode() + bytes.fromhex(nonce_hex)
target = bytes.fromhex(tag_hex)
current = None
for scalar in range(order):
digest = hashlib.sha256(prefix + encode_full(current)).digest()[:16]
if digest == target:
return scalar
current = add(current, point)
raise SystemExit(f"no residue for {key_id}")
def crt(pairs):
modulus = 1
for _, factor in pairs:
modulus *= factor
value = 0
for remainder, factor in pairs:
partial = modulus // factor
value += remainder * partial * pow(partial, -1, factor)
return value % modulus, modulus
def canonical(value):
return json.dumps(value, sort_keys=True, separators=(",", ":"), ensure_ascii=True).encode()
def decrypt_report(envelope, scalar, shared):
info = envelope["info"]
aad = envelope["aad"]
info_hash = hashlib.sha256(canonical(info)).digest()
binding = hashlib.sha256(
b"northstar-report-scalar-binding\x00" + int(scalar).to_bytes(4, "big") + info_hash
).digest()
master = hashlib.scrypt(
encode_full(shared) + binding,
salt=b"northstar-report-v3\x00" + bytes.fromhex(envelope["nonce"]) + info_hash,
n=32768,
r=8,
p=1,
dklen=32,
maxmem=128 * 1024 * 1024,
)
aes_key = hmac.new(master, b"northstar-aes256-gcm-key\x00" + info_hash, hashlib.sha256).digest()
cipher = AES.new(aes_key, AES.MODE_GCM, nonce=bytes.fromhex(envelope["nonce"]))
cipher.update(canonical({"aad": aad, "info": info}))
return cipher.decrypt_and_verify(
base64.b64decode(envelope["ciphertext"]),
bytes.fromhex(envelope["tag"]),
)
def main():
_, login_raw = request("/api/v1/login", method="POST", body={
"username": USERNAME,
"password": PASSWORD,
})
analyst = json.loads(login_raw)["token"]
header_b64, payload_b64, _signature = analyst.split(".")
payload = json.loads(base64.urlsafe_b64decode(payload_b64 + "=="))
print("analyst role:", payload["role"])
_, report_raw = request("/api/v1/reports/rpt-042/download", analyst)
envelope = json.loads(report_raw)
_, keys_raw = request("/api/v1/projects/prj-northstar/keys", analyst)
public_keys = {item["id"]: item["public_key"] for item in json.loads(keys_raw)["keys"]}
recipient = decompress(envelope["recipient_public_key"])
print("recipient:", envelope["recipient_public_key"], recipient, "on_base_curve:", on_base_curve(recipient))
payload["role"] = "admin"
# kid 读到密钥目录外的文件时，HMAC 密钥是空字节串。
admin = mint({"alg": "HS256", "kid": "../sdk.js", "typ": "JWT"}, payload, b"")
_, me_raw = request("/api/v1/me", admin)
me = json.loads(me_raw)
print("forged role:", me["role"], "diagnostics:", me["permissions"]["diagnostics"])
# 报告绑定 doc-kek-2026.09-v3，v4 轮换后的公钥对应另一把私钥。
residues = []
for key_id in V3_KEYS:
point = decompress(public_keys[key_id])
b_value, order = point_order(point)
_, receipt_raw = request("/api/v1/diagnostics/compat", admin, "POST", {"key_id": key_id})
receipt = json.loads(receipt_raw)
residue = recover_residue(key_id, point, order, receipt["nonce"], receipt["tag"])
residues.append((residue, order))
print(
f"{key_id} pub={public_keys[key_id]} b={b_value} order={order} "
f"nonce={receipt['nonce']} residue={residue}"
)
scalar, modulus = crt(residues)
if not 0 < scalar < 2**32:
raise SystemExit(f"scalar {scalar} mod {modulus} is outside uint32")
# 信封没有临时公钥，共享点就是服务器私钥乘以收件人公钥。
shared = mul(scalar, recipient)
plaintext = decrypt_report(envelope, scalar, shared)
print("scalar:", scalar)
print("shared:", shared)
print(plaintext.decode())
if __name__ == "__main__":
print("python:", sys.version.split()[0])
main()
Immobilizer ECDSA
核心思路：40 条 secp256k1 ECDSA 签名的 nonce 最高 8 位恒为 0，构成隐藏数问题（HNP），用 LLL 格规约恢复私钥
d，再以SHA256(d)作为密钥流异或解密sealed得到 flag。
1. 题目说明
题目只给出一个 data.json，内容为汽车防盗器（immobilizer）的签名记录：
{
"curve": "secp256k1",
"n": "115792089237316195423570985008687907852837564279074904382605163141518161494337",
"G": {
"x": "55066263022277343669578718895168534326250603453777594175500187360389116729240",
"y": "32670510020758816978083085130507043184471273380659243275938904335757337482424"
},
"public_key": {
"x": "23627227489180312529102653625669019920806999775537304645922978739257665571310",
"y": "100753196227827319451259216774802632812381464299694707681682452911610216430556"
},
"signatures": [
{"msg": "immobilizer|vin=LDC613P23A0000001|ctr=0",
"r": "91322417266516705459309644889473281836638529456978360519484264246470515462402",
"s": "74230450154863550368806295818323115017851826111799325299082883080293361476385"},
{"msg": "immobilizer|vin=LDC613P23A0000001|ctr=1",
"r": "103257334126702286333674855231439453735917167735015786437067084411297866188326",
"s": "107744251849317616725436238316208679457009219068941567640123002212877900210964"},
"... 共 40 条，ctr = 0..39，完整 (r, s) 见第 4 节脚本中的 RS 列表 ..."
],
"sealed": "50bbc6a269fd17bb9f2f057da88ee2ce80504261010d80ebddcd27"
}
已知条件与约束：
曲线为 secp256k1：，素域 ，基点 G的阶为n（256 位素数）。40 条签名的消息格式完全固定，只有计数器不同： immobilizer|vin=LDC613P23A0000001|ctr=i，i = 0..39。40 个 r两两不同，所以不存在 nonce 直接复用。sealed为 27 字节的十六进制串，没有说明加密方式。
目标：恢复签名私钥，解开 sealed。
2. 解题思路
40 条签名、r 互不相同，但共用一个私钥
→ 每条签名都把 nonce k_i 写成私钥 d 的线性函数：k_i = A_i + B_i·d (mod n)
→ 猜测 nonce 生成存在偏置（高位为 0），即 k_i 远小于 n
→ 构成 HNP，用格 + LLL 找出短向量 (k_1, ..., k_N)，同时得到 d
→ 用 d·G == Q 校验私钥
→ 用 d 派生密钥流解密 sealed
3. 解题过程
3.1 把每条签名改写成关于私钥的线性方程
关键观察： 签名量很大（40 条），又全部出自同一私钥，消息几乎相同。没有重复 r，只能从 nonce 的统计结构入手。
原理与操作： ECDSA 签名满足（在 中）：
s_i = k_i^{-1} · (z_i + r_i · d) (mod n)
移项得：
k_i = s_i^{-1}·z_i + s_i^{-1}·r_i · d = A_i + B_i·d (mod n)
A_i = z_i · s_i^{-1} mod n, B_i = r_i · s_i^{-1} mod n
其中 z_i 为消息摘要。题目没有说明哈希算法，这里取 ECDSA/secp256k1 最常用的 SHA-256：z_i = int.from_bytes(SHA256(msg_i), "big")。（这一选择属于假设，最终靠 d·G == Q 来确认。）
本步结果： 得到 40 个关于未知数 d 的线性同余式，A_i、B_i 均可从公开数据算出。若 k_i 是 [1, n) 上的均匀随机数，这些方程不泄露任何信息；只要 k_i 有界，就能转化为格问题。
3.2 建立 HNP 格并估计所需签名数
关键观察： 嵌入式 nonce 生成器经常把较短的随机数当作 256 位标量使用，导致高位恒为 0。假设 ，其中 。
原理与操作： 存在整数 使 。构造如下格（为保持整数，整体乘以 n），行向量：
row_i (0 ≤ i < N) : (0, …, n·n (第 i 列), …, 0, 0, 0 )
row_N : (B_1·n, …, B_N·n, K, 0 )
row_{N+1} : (A_1·n, …, A_N·n, 0, K·n)
整数组合 d·row_N + row_{N+1} − Σ l_i·row_i 等于：
v = (k_1·n, …, k_N·n, d·K, K·n)
由于 且 ，v 的每个分量都不超过 K·n，因此 。格的行列式为 ，维数为 ，Gaussian heuristic 给出的典型最短长度约为
要让 v 明显短于这个值，大致需要满足 ，即所有 nonce 一共泄露的位数超过私钥的位数。若每条 nonce 高 8 位为 0（），则需要 条签名，而题目正好给了 40 条，满足条件。
LLL 规约后，找出最后一列等于 ±K·n 的行，即可读出倒数第二列 ±d·K，从而得到 d。
本步结果： 偏置位数未知，脚本从 b = 248 开始逐字节向下尝试。实际在第一个取值 b = 248 就得到了能通过公钥校验的私钥：
[+] nonce bound : k < 2^248
[+] private key d : 65062337734878525051969737001582398336729906718165769482557093642791334506647
[+] d*G == Q : True
3.3 校验私钥与偏置假设
关键观察： 只有找到了正确的私钥，d·G 才会等于公开的公钥 Q。这一步同时确认了 SHA-256 摘要假设和 nonce 上界假设。
原理与操作： 在 secp256k1 上计算 d·G 并与 Q 比较；再用 k_i = A_i + B_i·d mod n 反算全部 40 个 nonce，统计它们的位长。
本步结果：
[+] max k bitlen : 248
[+] k bitlens : [241, 243, 245, 245, 245, 245, 245, 246, 246, 246, 246, 246, 246, 246, 247, 247, 247, 247, 247, 247, 247, 247, 247, 247, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248]
40 个 nonce 全部小于 ，最大位长正好是 248，位长分布与 248 位均匀随机数一致（约一半为满 248 位）。由此可以确认 nonce 的最高字节恒为 0，这也和 flag 的内容相互印证。
3.4 用私钥派生密钥流解密 sealed
关键观察：sealed 只有 27 字节，不是 16 的倍数，也没有附带 IV 或 tag，最可能是长度与明文相同的异或流加密；32 字节的哈希输出足够覆盖 27 字节。
原理与操作： 以私钥为种子生成候选密钥流，依次尝试 SHA256 / SHA512 / MD5 / SHA1 / SHA3 / BLAKE2 作用于 d 的不同编码（32 字节大端、小端、十进制串、十六进制串），把异或结果全部为可打印字符作为筛选标准。只有一个组合满足条件：
keystream = SHA256(d.to_bytes(32, "big"))[:27]
plaintext = sealed XOR keystream
本步结果：
[+] keystream : 36d7a7c5128978cbc04d7c09cdd18da8df242a045e63ef85bea85a
[+] flag : flag{top_byte_of_the_nonce}
27 字节解密后全部是可打印字符，符合 flag{...} 格式，内容也直接点明了漏洞（nonce 的最高字节）。
4. 完整解题脚本
脚本内嵌了全部题目数据，不依赖 data.json，需要在 SageMath 环境中运行（使用 Sage 的椭圆曲线和 LLL）。
# 运行方式: sage -python solve.py
# 流程: ECDSA nonce 高位为 0 -> HNP 格规约恢复私钥 d -> SHA256(d) 异或解密 sealed
import hashlib
from sage.all import EllipticCurve, GF, Matrix, ZZ, inverse_mod
# ---------------- 题目数据（data.json 原样内嵌） ----------------
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F# secp256k1 素域
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
Qx = 23627227489180312529102653625669019920806999775537304645922978739257665571310
Qy = 100753196227827319451259216774802632812381464299694707681682452911610216430556
SEALED = "50bbc6a269fd17bb9f2f057da88ee2ce80504261010d80ebddcd27"
# 第 i 条签名的消息为 "immobilizer|vin=LDC613P23A0000001|ctr=i"，按 i = 0..39 给出 (r, s)
RS = [
(91322417266516705459309644889473281836638529456978360519484264246470515462402,
74230450154863550368806295818323115017851826111799325299082883080293361476385),
(103257334126702286333674855231439453735917167735015786437067084411297866188326,
107744251849317616725436238316208679457009219068941567640123002212877900210964),
(111921579415467239343630252792752981674256232668276147344997845922981734624272,
4465739024795485622525511256112512891165302626460991727012889071473189740134),
(19760154632518205810452223845788919876636879268134733560462131575661960107077,
18954707186767945306957129156974936413620986888245138081593340841252273933916),
(59900847935449140639681020624192883758556828680468938213092324661380308600140,
739814014335417465582541295106362177359722574185228244748325990910949032683),
(86896333256490135745535661310383599481683962310959642026052500303041385103241,
13493672043009196320820017062023781624855449401602395800191423445145595215313),
(26438423975169760929931944760375789902299378270550685303275126811104525919658,
88925662851971342041983962922333967417725749611546603319229621757320212977217),
(35319192334648160740570389894272059452089101708879677493810366846190039028673,
62362102525904922669784176482019076640549401380929306937770096646629967284911),
(49187482715507835518390114696436316349701087638390469522494756009225852397469,
29855157089744994271623929303330718764529955032290152045071436736213519795010),
(68099922010578218379510017308364056843842845022877078410722340870611304760661,
97926516414411479977483363740921360174792736951126322543589404122761023722430),
(88982720681186841201018384792567448088652883916296206564966468529665708526944,
113357221877532074154325416603901430266175592429377519724522020286826432295276),
(35983819891195969296869251304730870656621632886031032824045373506391997338953,
74822873412975629486112867749199622258288346120848278417272591306135834921153),
(106486034599354775517053033813191598461007949169409991368076692335915827709230,
83663550953175141078078543258537874141920607603776621682960227347198110236848),
(44593063361131484901035716995410318235772520097067362752746211614349323927140,
34835439189462574316499014416823866697184221971826561255796251348638797038705),
(25809287748339132488809626799922985467020448703720756151787538779087132391840,
64135007087091921106274422689019350404830759124187625843765798573357597228433),
(114660847037821190585996036846862833049156328974482870886827501878906608521059,
58021959558008521203088580582358965384353775883605613252684094169802391887414),
(31472887143722690798288343243725539871190046926292129521560053199068164727182,
108840279983118147408917234515042357277312350175928288031220468731023559931071),
(7748216005278180396229885008338700420352362191678163795150979851381885815710,
110878367871223346875488223702631837449596695102077986040279242661991579436389),
(102493272842989613217358374645742000017156990862823086068641581881757639495765,
41509958933241709073203799276875800462452046014662483213737454892317499110460),
(27705516223885099222816142353875588017978122857174560413072674163528565339047,
43703270983506427596079706160293621073079596637355291776307934092992047951706),
(75930752581287648338002323670665970586918998501486837906928287598988597424659,
56607719413285013766080628077299830906733395496637902812419568858110650522076),
(64531233869013340927564164484717355226051135791938192459232626473080330043121,
111679362882760520299721853979360878830653866814117834171220093172003994314270),
(97950779372995901281991153726961507266378936935495919272717802397261847557775,
50086464542034420861434291072383030423831339273616064186971633432316262565324),
(109176894727901159733743815434880401858818148832151269781497062967689430528188,
76759997172428018982220500236361900863723449598512288145487629868840432678998),
(49715392084937070526523294121725112558419665956279875324939448566616037468013,
66525212753082011188774574787610439674267899677802024051539103362901203348128),
(64689645862582274399626097725136594545918374646118169678586319579461170400367,
73144643053847465284108769858476883089819545585752469122631492053442990283597),
(63925661970767719838943702591771041140427426933235246313192571602904238506180,
88619660904621821732945375141518815279389111451624531397776778762090735788629),
(68636669376057650460794266041669351259298765958338238284746408411280892762350,
86125511678846604144365927869274299654367804517501394466422249384300336373670),
(107027162123916974424713790975590722165455131198475359961910385474631206324580,
53339469505227315712215017277426033184379700060616290708425386809181616666284),
(110494940453981367397571536729292986885677948445511340263299547246888296610237,
24417732527395478000410451516222791481950022276976553914391344795094245269519),
(66064239010490749303647553620109443793718029215509571175204674453202193003713,
250196222186447551656550267348046979152981595246031063280269846104030847661),
(81903308809013316738774535283101219733263437452942821548274662489719373502355,
111910968894078087273789826302148643529077000915845731872202327644542881060261),
(95006762650493592664452748116163084436498638646442998815684749670527080332748,
70791141494549737059672988712638785664734339633514949525718667871191393404891),
(39250492879172449768135561183981734940554989734861731923206475148960940217810,
26184729599920340018168096789952539260177321766825400893757460943264642542044),
(98741771031626979367022255942062461502697074112863130289796787129681996607238,
66449486728421444778807881004840356041769763535127071767069316731612279165579),
(76403910179182783071243496978692286313257003423062784990869086097689595013970,
86822653072856388727402475555699712588678433416084285429637123104893209918011),
(81388297455582111084803529612994646615684597584733840384596641251731154563949,
61594487362873641385907652236268426967756165209163301630487636916729437352293),
(23010660791018856266187136959328777217667090703210713904655343540416830494871,
11418297390873498136060696424791034786058296918437085536466375091739104139484),
(9301217604506122956560056718852051999582907179434991632145190707870261506428,
70831192311916953428062191521593938196239361435853570821640664457286355000497),
(47763002376375770930941956421456059251823248203373249255237064946670312447403,
101737881744302500031113427248190823581071995601430648843088222854308624542656)
]
MSGS = ["immobilizer|vin=LDC613P23A0000001|ctr=%d" % i for i in range(len(RS))]
E = EllipticCurve(GF(p), [0, 7])
G = E(Gx, Gy)
Q = E(Qx, Qy)
def z_of(msg):
# 消息摘要 z = SHA-256(msg)，大端整数
return int.from_bytes(hashlib.sha256(msg.encode()).digest(), "big") % n
# 由 s = k^-1 (z + r d) 得 k_i = A_i + B_i d (mod n)
A = [int(z_of(m) * inverse_mod(s, n) % n) for m, (r, s) in zip(MSGS, RS)]
B = [int(r * inverse_mod(s, n) % n) for (r, s) in RS]
def hnp(bits):
# 假设 0 <= k_i < K = 2^bits。整体乘 n 保持整数格：
# 第 i 行 (i < N) : 第 i 列为 n*n （对应 mod n 的约简）
# 第 N 行 : (B_1*n, ..., B_N*n, K, 0)
# 第 N+1 行 : (A_1*n, ..., A_N*n, 0, K*n)
# 目标短向量 = (k_1*n, ..., k_N*n, d*K, K*n)，各分量量级都约为 K*n
N, K = len(A), 2 ** bits
M = Matrix(ZZ, N + 2, N + 2)
for i in range(N):
M[i, i] = n * n
M[N, i] = B[i] * n
M[N + 1, i] = A[i] * n
M[N, N] = K
M[N + 1, N + 1] = K * n
for row in M.LLL():
if abs(row[N + 1]) != K * n:
continue
sign = 1if row[N + 1] > 0else-1
d = int(sign * row[N] // K) % n
if d and d * G == Q: # 用公钥校验
return d
returnNone
# 从 248 位开始向下逐字节尝试 nonce 上界
d = None
for bits in range(248, 127, -8):
d = hnp(bits)
if d:
print("[+] nonce bound : k < 2^%d" % bits)
break
assert d, "lattice attack failed"
print("[+] private key d :", d)
print("[+] d*G == Q :", d * G == Q)
# 用恢复出的 d 反算全部 nonce，检验偏置假设
ks = [(a + b * d) % n for a, b in zip(A, B)]
print("[+] max k bitlen :", max(k.bit_length() for k in ks))
print("[+] k bitlens :", sorted(k.bit_length() for k in ks))
# 解密 sealed：密钥流 = SHA256(d 的 32 字节大端表示)
ks_stream = hashlib.sha256(d.to_bytes(32, "big")).digest()
ct = bytes.fromhex(SEALED)
flag = bytes(c ^ k for c, k in zip(ct, ks_stream))
print("[+] keystream :", ks_stream[:len(ct)].hex())
print("[+] flag :", flag.decode())
samples
核心思路：利用 Kannan 嵌入将 32 维秘密、64 样本的模 7681 带误差学习（LWE）问题转化为 97 维格上的最短向量问题（SVP），通过 LLL 格基约减直接恢复二元秘密向量
s，再计算SHA-256(bytes(s))作为掩码密钥流异或解密masked_update得到 Flag。
1. 题目说明
题目提供单文件挑战数据 samples.json，要求从给定的公开矩阵与观测向量中恢复隐藏的秘密参数，并解密 masked_update 字段获取 Flag。
原始数据包含以下 6 个字段：
q = 7681：有限域模数（素数）。n = 32：秘密向量s的维度。m = 64：采样方程组数量。A：64 × 32的模q整数矩阵。b：长度为64的模q整数向量。masked_update：长度为 56 个十六进制字符（28 字节）的密文数据。
完整的题目原始数据如下：
{
"q": 7681,
"n": 32,
"m": 64,
"A": [
[2395, 6050, 1036, 3320, 2631, 4663, 4329, 1258, 3363, 3828, 5797, 7380, 609, 2407, 6810, 4109, 330, 7238, 3281, 4261, 2091, 5694, 641, 1845, 2593, 1584, 6754, 6468, 497, 871, 2968, 3533],
[4337, 334, 5766, 3916, 1515, 2814, 7114, 7349, 3376, 1380, 5932, 3966, 3956, 6806, 1563, 4951, 664, 3148, 711, 4742, 4178, 743, 224, 2630, 7026, 1347, 1890, 1157, 2169, 3858, 3716, 2097],
[194, 6116, 1249, 1821, 6681, 3478, 255, 3784, 4745, 103, 1888, 6175, 5978, 6399, 941, 6547, 479, 1363, 132, 1117, 1629, 6178, 6710, 6289, 3335, 7379, 1474, 4070, 67, 7502, 1629, 5051],
[4505, 4853, 2543, 1416, 6020, 5442, 1857, 4968, 5843, 6707, 6856, 4301, 3494, 2068, 3008, 7250, 3675, 1215, 4595, 2815, 10, 796, 1634, 6486, 129, 4737, 1709, 6542, 3578, 5592, 4456, 6315],
[3688, 6657, 1319, 2658, 4686, 6127, 3353, 7406, 3761, 7365, 3689, 5508, 4742, 7028, 2596, 3272, 301, 2815, 7042, 1061, 5553, 808, 7411, 3544, 1394, 6951, 1903, 6957, 3834, 161, 6094, 953],
[4113, 3282, 683, 6191, 3281, 1594, 806, 758, 2023, 4929, 38, 1392, 7615, 552, 4764, 1058, 6909, 4947, 3753, 2849, 5085, 4036, 6772, 279, 4100, 4623, 7392, 2961, 5256, 1738, 4827, 5654],
[117, 3044, 3367, 4579, 134, 2277, 5999, 4197, 3630, 5733, 457, 2763, 4403, 1340, 6157, 2752, 4702, 1034, 6888, 6086, 7228, 4562, 6738, 4323, 1014, 1939, 5530, 6979, 170, 5292, 2988, 1280],
[2329, 3504, 1759, 6698, 1919, 655, 4194, 4955, 6681, 4967, 6332, 2511, 5138, 2769, 2851, 1008, 6099, 6839, 2066, 2188, 920, 5993, 1404, 564, 6312, 1013, 1004, 3685, 5503, 5817, 4537, 1164],
[2870, 4406, 5602, 3390, 4750, 4097, 5968, 4131, 2102, 6086, 4133, 2183, 6619, 608, 4943, 6695, 3892, 2678, 7668, 6665, 3680, 3299, 7197, 4002, 6475, 4743, 6350, 1092, 7479, 2519, 4708, 5251],
[3399, 2582, 3816, 3767, 1440, 7029, 1425, 7080, 5874, 3923, 4679, 4600, 3595, 3304, 6503, 2320, 4732, 2629, 1210, 4224, 4501, 1397, 3854, 1910, 988, 7340, 6810, 793, 3026, 5309, 1956, 3230],
[5720, 872, 5274, 508, 4891, 6078, 2704, 2698, 1227, 2974, 6919, 703, 5402, 4315, 7314, 6863, 6191, 1044, 53, 5266, 2209, 4968, 3882, 5480, 5453, 7486, 5759, 1736, 5888, 4981, 667, 2343],
[4472, 7050, 5017, 4990, 3584, 5857, 4912, 6189, 4165, 4481, 710, 6889, 1332, 2894, 1095, 999, 4980, 6337, 4921, 3686, 7193, 6208, 6198, 5300, 5512, 6674, 3150, 734, 5509, 5619, 4987, 5753],
[4459, 276, 5645, 1988, 3071, 4102, 5347, 1102, 1789, 73, 4603, 4275, 4941, 6, 1334, 3576, 4415, 5481, 7633, 1397, 3601, 4097, 4524, 433, 2467, 7248, 7549, 1423, 1784, 4860, 830, 412],
[1710, 4751, 6398, 15, 153, 5457, 6836, 5363, 2185, 4161, 6870, 5279, 6698, 7449, 1299, 791, 488, 6114, 6379, 7489, 7395, 4297, 1322, 7479, 6362, 5962, 6081, 2781, 1821, 4870, 1906, 258],
[7575, 552, 5768, 1636, 3737, 2073, 5198, 7315, 1867, 5876, 676, 629, 1610, 5843, 5335, 5374, 3258, 4399, 3918, 926, 3382, 80, 5826, 4543, 2467, 4259, 4644, 360, 2060, 4856, 7219, 2967],
[425, 1397, 5950, 6621, 7524, 4911, 678, 5858, 2944, 886, 6381, 552, 2688, 5485, 553, 2998, 6547, 932, 3160, 510, 2925, 7389, 562, 503, 3681, 6763, 6893, 176, 7150, 5997, 7473, 7591],
[499, 1829, 1298, 1131, 7267, 3640, 4899, 7626, 2301, 4876, 2694, 2755, 6132, 4471, 2052, 6271, 5255, 4863, 7672, 1170, 7073, 98, 6937, 5880, 4068, 4462, 1980, 6797, 1556, 4811, 2189, 1665],
[4443, 4812, 6271, 572, 1927, 3795, 2227, 415, 4627, 5801, 6479, 1143, 267, 6951, 2307, 6256, 2128, 4352, 2179, 4398, 2407, 7654, 4604, 1108, 1947, 3392, 6818, 5111, 2241, 2830, 1794, 3699],
[4465, 1294, 3263, 1718, 172, 7246, 5923, 4438, 1730, 939, 3153, 2768, 1880, 3879, 4972, 7623, 7182, 65, 348, 5206, 2737, 2897, 3983, 3008, 3293, 6836, 251, 6291, 4171, 1060, 5784, 5241],
[657, 3405, 5622, 2550, 5780, 3534, 3477, 6628, 3549, 2590, 7424, 5883, 6759, 3042, 4408, 6124, 1398, 3940, 6119, 2139, 6398, 107, 5094, 1171, 1103, 319, 6771, 1073, 802, 5226, 1132, 2243],
[4226, 4577, 1482, 6461, 6026, 6648, 7325, 2431, 1211, 3295, 28, 359, 3205, 5682, 5477, 5383, 6569, 4986, 5639, 5302, 5858, 2163, 4497, 6008, 763, 2117, 1602, 4895, 4549, 5949, 4845, 896],
[3899, 3004, 5714, 6214, 6511, 7349, 3094, 4092, 4552, 5648, 5760, 925, 1781, 3119, 7427, 5066, 4919, 6562, 4034, 1847, 2171, 6871, 6733, 409, 5477, 3193, 3597, 5730, 6112, 3047, 7574, 3057],
[3086, 3901, 471, 6298, 1473, 7531, 2321, 2024, 7471, 3373, 4274, 4390, 1319, 6215, 3086, 7392, 3688, 3193, 5351, 1185, 4924, 2042, 27, 4584, 2375, 2341, 612, 538, 4109, 1101, 2937, 6647],
[3491, 5193, 3273, 5402, 1182, 2439, 2182, 6704, 7019, 105, 490, 3815, 2170, 961, 6254, 7111, 5934, 5962, 4582, 4585, 7050, 5784, 863, 3329, 5767, 4352, 6947, 2437, 6046, 104, 4311, 5251],
[7626, 1677, 3781, 4295, 6484, 1149, 853, 3386, 6213, 1984, 2786, 2096, 6487, 3354, 1366, 606, 7334, 3779, 1206, 2235, 2439, 212, 6141, 6899, 6091, 4920, 2387, 3335, 7296, 1984, 2600, 844],
[2480, 5903, 3271, 2241, 5863, 195, 5840, 7467, 1266, 1456, 1360, 3126, 1939, 7409, 5391, 1945, 1557, 7177, 3788, 902, 4696, 787, 259, 1528, 3007, 1383, 1656, 5299, 1538, 236, 6176, 1811],
[6242, 4758, 3003, 4663, 2447, 3699, 1729, 1366, 189, 173, 2127, 1711, 567, 3509, 4813, 7016, 7328, 7345, 550, 2177, 5503, 6588, 2277, 3926, 6841, 7299, 2415, 5269, 2599, 390, 1258, 7076],
[1782, 3512, 4569, 4760, 6442, 2355, 2908, 3742, 6776, 2508, 913, 6242, 2798, 3996, 400, 7433, 6127, 1969, 864, 5144, 2702, 4957, 5070, 115, 7510, 1982, 6818, 865, 522, 1807, 3302, 3414],
[4488, 2865, 2492, 7066, 6084, 4061, 3651, 4393, 5419, 2893, 974, 360, 47, 4193, 6130, 4863, 653, 5524, 1728, 3219, 6253, 6400, 1528, 1564, 491, 3662, 4906, 4617, 4493, 461, 2590, 4712],
[5850, 6141, 4538, 7511, 5578, 7161, 1104, 7215, 7205, 5267, 4447, 6498, 4577, 7293, 86, 6095, 1529, 5557, 3766, 3347, 665, 4222, 5842, 4143, 7325, 4226, 1777, 4221, 7480, 3604, 6354, 2732],
[4796, 4354, 7320, 2710, 475, 5289, 2414, 4861, 6543, 2590, 4888, 2631, 3407, 525, 2813, 5251, 5075, 1091, 6215, 3790, 7460, 2383, 2573, 4160, 4103, 1343, 1629, 1270, 3811, 713, 984, 1841],
[6646, 2070, 2342, 5521, 3643, 6009, 1011, 7368, 5566, 7254, 350, 6019, 3049, 3314, 1859, 5328, 2874, 3311, 1212, 876, 116, 4500, 740, 7041, 730, 6825, 4718, 3601, 3963, 3319, 4008, 6145],
[3018, 4968, 4315, 1012, 362, 6804, 2302, 3786, 3584, 575, 1821, 5077, 7381, 3754, 365, 5484, 431, 2245, 1532, 3570, 3351, 3512, 740, 4665, 5768, 4873, 6396, 5581, 2182, 3108, 2614, 3222],
[3549, 3471, 1783, 617, 7520, 4974, 2919, 6957, 2629, 1288, 3226, 872, 358, 1015, 2281, 1234, 3028, 569, 2170, 2194, 6566, 440, 3926, 2351, 1543, 6915, 4229, 1409, 5995, 9, 977, 4761],
[6341, 7424, 5006, 1053, 7431, 4739, 1240, 4123, 2423, 1268, 3842, 7152, 3814, 1551, 1048, 2322, 2514, 1205, 5300, 3401, 42, 7241, 4962, 5384, 3760, 1181, 3747, 373, 1003, 6883, 5071, 3489],
[2237, 2835, 6531, 5228, 2741, 5202, 1126, 1450, 3066, 4793, 4726, 2764, 1627, 5710, 3247, 1434, 2927, 3908, 1591, 6455, 1375, 4059, 4741, 5792, 6436, 7102, 5590, 4336, 2992, 5088, 2327, 4069],
[1595, 958, 4879, 2838, 562, 6287, 3121, 1191, 1467, 1550, 170, 5160, 2939, 124, 3953, 3218, 2555, 2305, 1160, 3575, 5993, 6579, 5296, 772, 4010, 3496, 2074, 5506, 5982, 1214, 1155, 158],
[2748, 1820, 6654, 6094, 7285, 557, 159, 2699, 2134, 6226, 1340, 5183, 3919, 443, 3418, 4866, 6665, 3000, 1842, 5190, 2582, 5478, 769, 652, 4849, 2161, 1961, 6231, 7348, 2965, 2983, 6079],
[6400, 3366, 4311, 6523, 47, 6957, 1913, 4260, 6206, 6361, 4902, 148, 2450, 6449, 4090, 5165, 4950, 2105, 1896, 7013, 3699, 1312, 4767, 5252, 1221, 7431, 7277, 143, 2634, 3604, 843, 5575],
[1962, 6838, 1974, 1077, 5563, 1221, 4481, 6290, 5710, 3541, 3586, 3992, 3477, 7385, 5320, 204, 1015, 2615, 2224, 1490, 4633, 6932, 1752, 4181, 1581, 5882, 82, 589, 4629, 6594, 5427, 4612],
[5328, 1151, 4123, 6380, 1261, 5609, 4498, 5515, 6649, 4369, 5354, 6611, 4296, 336, 5952, 3036, 530, 3524, 6730, 6447, 6596, 417, 6014, 3382, 3284, 755, 616, 4398, 7505, 2405, 7414, 2745],
[1672, 7360, 6569, 2744, 3725, 3605, 4426, 6303, 7482, 256, 4197, 6643, 6139, 1445, 4812, 6677, 6168, 4577, 5000, 2294, 1836, 7266, 464, 2690, 4152, 7154, 7173, 1034, 2730, 3874, 6632, 2160],
[5175, 5481, 1129, 7020, 7473, 5795, 7192, 4295, 3047, 1956, 2834, 2108, 1183, 885, 566, 6564, 7659, 1861, 6146, 3198, 6260, 3546, 1, 1314, 1886, 332, 3206, 6971, 4422, 4301, 7589, 5319],
[7623, 253, 5651, 593, 4597, 5124, 1303, 46, 5352, 3588, 6, 3408, 7512, 1368, 4471, 3551, 2681, 5326, 4669, 5646, 5864, 3901, 7655, 3628, 5046, 5968, 7126, 5376, 272, 101, 6278, 4503],
[5562, 3250, 2938, 3614, 3129, 6689, 798, 1660, 3415, 3532, 4218, 7353, 4753, 3711, 2735, 2741, 4766, 3875, 222, 2082, 4695, 1926, 3033, 4842, 1524, 2006, 6075, 5865, 4265, 5032, 688, 1771],
[883, 5846, 3127, 800, 5437, 6119, 2394, 2404, 2014, 902, 2272, 6269, 1057, 2733, 1160, 6893, 4576, 3611, 4246, 6019, 5520, 5131, 1979, 1898, 5840, 2, 2285, 3700, 6215, 4359, 6171, 3837],
[4578, 2478, 224, 1644, 2949, 2592, 6564, 2000, 6368, 409, 5485, 2307, 7636, 3522, 1219, 4853, 3961, 561, 3713, 7039, 5723, 5039, 5675, 6723, 7474, 1984, 2135, 4681, 7545, 6133, 2632, 5408],
[4392, 3094, 7507, 1619, 793, 2605, 6457, 5177, 5105, 5267, 1705, 5625, 5199, 3728, 3075, 6103, 6307, 6515, 3201, 7451, 4086, 5157, 43, 5344, 6677, 2016, 629, 4172, 5818, 3475, 7487, 4806],
[992, 7627, 185, 4068, 3326, 6855, 6161, 7522, 3642, 7368, 74, 5711, 7310, 7653, 5329, 3742, 2869, 1390, 5107, 818, 2401, 7009, 4737, 4049, 6969, 5908, 5802, 6738, 5102, 7595, 2383, 2133],
[1067, 6690, 1456, 6371, 7527, 3662, 4415, 2104, 3432, 6031, 5278, 2971, 2933, 2585, 4331, 5010, 996, 1017, 1103, 3450, 1797, 4112, 1528, 2230, 596, 6886, 679, 1380, 3526, 6045, 5488, 7179],
[7009, 2613, 4346, 2289, 5072, 5657, 7320, 4487, 444, 7242, 4055, 57, 432, 2760, 7672, 1921, 4349, 3534, 4080, 3567, 4841, 1067, 6569, 1440, 1264, 4010, 5984, 3346, 2342, 39, 2109, 7506],
[5533, 4872, 3287, 4380, 2071, 2173, 1406, 839, 3634, 3390, 2209, 6402, 952, 4296, 5170, 1957, 4307, 6704, 2800, 3391, 7151, 5739, 4234, 2707, 3794, 5603, 1882, 7516, 6504, 5862, 1126, 5968],
[2925, 5941, 6586, 3756, 6391, 6201, 4422, 1725, 6903, 439, 2032, 2313, 2275, 2986, 6987, 3848, 3897, 2713, 1641, 4614, 1765, 2037, 2637, 1882, 1058, 1899, 3361, 6644, 4686, 4470, 3935, 5000],
[1147, 2935, 7332, 2828, 1497, 1736, 298, 4701, 6633, 205, 930, 3924, 2632, 1298, 6514, 2618, 985, 7550, 424, 5206, 5060, 6213, 6052, 6762, 5476, 1406, 4949, 6306, 278, 4653, 5114, 6769],
[3508, 7679, 752, 3515, 990, 3901, 5599, 5574, 935, 3022, 243, 664, 5375, 1731, 1777, 2154, 5689, 1044, 2496, 2537, 4885, 5529, 3097, 5678, 5730, 4278, 2861, 2024, 6537, 442, 5288, 7569],
[65, 6344, 3835, 2824, 6670, 3749, 251, 6700, 2698, 791, 1349, 2626, 2811, 5838, 5782, 3124, 2654, 4886, 5295, 3801, 3052, 7309, 2306, 6663, 4781, 2322, 6610, 1594, 4054, 59, 2966, 7308],
[5870, 1308, 3584, 5643, 6446, 7672, 993, 3211, 7173, 4540, 1013, 5777, 6581, 335, 4665, 6676, 5931, 3533, 38, 50, 1063, 3178, 5069, 2063, 5884, 4966, 7098, 4475, 7333, 4792, 4858, 5187],
[2161, 1504, 1833, 2888, 4673, 3958, 398, 5548, 3381, 5931, 1690, 5467, 1219, 1485, 5376, 4628, 4497, 6165, 2523, 4992, 1162, 5830, 816, 7023, 5161, 2746, 2549, 1174, 4832, 2578, 6425, 5427],
[2030, 5338, 2844, 5805, 3915, 2953, 2640, 6522, 3160, 7078, 3115, 5967, 153, 1960, 282, 5488, 5540, 6538, 5821, 981, 3709, 1928, 4684, 6513, 4440, 1895, 713, 2101, 3895, 6250, 2298, 7138],
[2064, 3963, 1445, 2044, 7429, 614, 5571, 2579, 5168, 2715, 2637, 2679, 5349, 3172, 268, 770, 1804, 7140, 6265, 6715, 3242, 300, 3901, 4853, 6596, 6430, 5659, 6033, 1088, 1589, 6713, 2588],
[3216, 7, 6066, 6353, 6521, 3360, 4965, 6928, 3052, 1996, 5536, 3222, 4373, 6723, 569, 2668, 532, 5104, 2945, 254, 1686, 2236, 5418, 1697, 2614, 7245, 5825, 6169, 6571, 5165, 858, 1982],
[4198, 7431, 4888, 5990, 1734, 4970, 5194, 1272, 234, 4881, 5377, 5707, 3735, 4902, 7528, 4515, 3362, 6320, 2358, 129, 2794, 2085, 5991, 3679, 3755, 151, 1803, 2714, 1421, 1232, 5866, 2933],
[5853, 5213, 4107, 7082, 6336, 1633, 190, 4882, 5700, 3259, 7398, 900, 5169, 6157, 2815, 3667, 5785, 1364, 5763, 839, 4242, 6171, 6811, 2475, 7103, 6144, 4162, 2676, 4505, 3692, 5047, 3371],
[4543, 3660, 2208, 5901, 6076, 4539, 4807, 1223, 6407, 3520, 5829, 2258, 493, 2561, 1136, 2199, 6826, 7052, 5223, 5480, 6451, 1765, 5627, 5877, 3902, 4385, 2571, 3716, 3632, 7250, 3382, 6900]
],
"b": [415, 7439, 2926, 3777, 3990, 6956, 4725, 277, 6379, 559, 5332, 6740, 6731, 4334, 473, 903, 1782, 7451, 6060, 1788, 7590, 2804, 7446, 2244, 1973, 2562, 3406, 4449, 7173, 1807, 7263, 2188, 1669, 2814, 548, 2836, 4453, 2284, 3262, 5799, 5006, 4657, 2932, 2145, 4273, 4567, 2316, 3040, 6835, 2231, 596, 510, 3249, 1629, 4485, 5018, 3228, 2387, 6223, 1831, 6057, 4349, 270, 4080],
"masked_update": "7c53ddbd82faf811c0397982909a9498644d63fb50a6e697d7cf97f6"
}
2. 解题思路
观察参数结构（ q = 7681、n = 32、m = 64、矩阵A和向量b），判定其为标准 LWE 样本集b ≡ A * s + e (mod q)。由于秘密维度 n = 32很小且模数q = 7681较大，构造m + n + 1 = 97维的 Kannan 嵌入格基，将求解小误差e与小秘密s的问题转化为格上的最短向量问题（SVP）。对 97 维格基运行 LLL 约减，直接从约减基首行提取出二元秘密向量 s ∈ {0, 1}^32和三元误差向量e ∈ {-1, 0, 1}^64，并代回原方程校验全部 64 个样本同余关系成立。将 32 维向量 s按单字节序列bytes(s)计算SHA-256摘要，取前 28 字节与masked_update逐字节异或，解出明文 Flag。
3. 解题过程
3.1 识别 LWE 样本参数与 Kannan 嵌入建模
关键观察：输入数据给出了模数 q = 7681（NTT 友好素数，7681 = 30 * 256 + 1）、维度 n = 32、样本数 m = 64、矩阵 A（64 行 32 列）和向量 b（64 维）。在有限域 Z_q 上直接对前 32 行高斯消元得不到有意义的短向量，说明方程含有小噪声项 e，满足 LWE 关系：
b ≡ A * s + e (mod q)
原理与操作：将同余式展开为整数线性关系，存在整数向量 k ∈ Z^m 使得：
A * s - b + q * k = -e
当 s 和 e 的分量绝对值远小于 q = 7681 时，可通过 Kannan 嵌入构造 (m + n + 1) × (m + n + 1) = 97 × 97 的行格基矩阵 B（取嵌入权重 W = 1）：
B = [ q * I_m 0 0 ]
[ A^T I_n 0 ]
[ -b^T 0 1 ]
对于整数行系数向量 (k, s, 1)，其与格基矩阵 B 相乘生成的格向量为：
v = (k, s, 1) * B = (q * k + A * s - b, s, 1) = (-e, s, 1)
该格包含的格点体积为 det(B) = q^m = 7681^64。根据高斯启发式，97 维格中最短非零向量的期望欧氏范数约为：
GH(B) ≈ sqrt(97 / (2 * pi * e)) * 7681^(64 / 97) ≈ 2.382 * 365.45 ≈ 870.5
而目标短向量 v = (-e, s, 1) 在小秘密和小误差条件下的欧氏范数上限低于 sqrt(64 + 32 + 1) ≈ 9.85，远小于高斯启发式下界 870.5，因此 LLL 格基约减可直接分离出唯一目标短向量。
本步结果：完成 97×97 维整数格基矩阵 B 的建模，目标向量形式确定为 v = (-e_0, ..., -e_63, s_0, ..., s_31, ±1)。
3.2 执行 LLL 格基约减恢复秘密向量与误差向量
关键观察：对 97×97 格基矩阵 B 执行标准 LLL 约减后，检查末位坐标绝对值为 1 的行向量。
原理与操作：使用 fpylll 构造 IntegerMatrix(97, 97) 并调用 LLL.reduction(B)。约减完成后，第 0 行（最短基向量）的末位分量 B[0, 96] 恰好为 ±1。设 sign = B[0, 96]，则可按如下关系提取 e 与 s：
e[i] = -sign * B[0, i] (0 <= i < 64)
s[j] = sign * B[0, 64 + j] (0 <= j < 32)
将提取出的 s 和 e 代回全部 64 个样本方程检验 (sum(A[i][j] * s[j]) + e[i]) % 7681 == b[i]。
本步结果：LLL 约减直接给出真实中间值（欧氏范数为 sqrt(39 + 14 + 1) = sqrt(54) ≈ 7.35），且 64 个方程校验全部通过：
s = [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
e = [-1, 1, 0, -1, 0, 1, 1, 0, -1, -1, -1, 1, 0, 1, 1, 1, -1, 1, -1, 0, 1, 1, -1, 0, -1, 1, 1, 1, 0, 1, -1, -1, 0, -1, 1, 0, 0, -1, 0, 1, 0, 1, 1, -1, 0, 1, 0, 0, 0, 0, -1, 0, 0, -1, -1, -1, 1, 1, -1, 0, 0, 1, 1, 0]
其中秘密向量 s 为严格二元向量（元素属于 {0, 1}，汉明重量为 14），误差向量 e 为严格三元小误差向量（元素属于 {-1, 0, 1}）。
3.3 派生 SHA-256 掩码密钥流还原明文 Flag
关键观察：masked_update 的长度为 28 字节（7c53ddbd82faf811c0397982909a9498644d63fb50a6e697d7cf97f6），小于等于 SHA-256 的 32 字节输出长度；同时恢复出的 s 为 32 个取值在 {0, 1} 的整数组成的列表，恰可直接转换为 32 字节序列 bytes(s)。
原理与操作：将 32 维二元向量 s 转换为 32 字节流 bytes(s)（即每个分量作为单字节 \x00 或 \x01），计算其 SHA-256 二进制摘要作为掩码密钥流 keystream，再与 28 字节的 masked_update 逐字节异或：
keystream = SHA256(bytes(s))
plaintext = masked_update XOR keystream[0:28]
本步结果：计算得到的关键字节流与异或结果如下：
bytes(s).hex() | 0100000000000001000000000001010000000101010001000001010100010000 |
SHA256(bytes(s))[:28].hex() | 1a3fbcdaf9979962ab660ae7f5fecbfe16220ea434d489e7b8bae38b |
masked_update | 7c53ddbd82faf811c0397982909a9498644d63fb50a6e697d7cf97f6 |
flag{mask_seed_from_dropout} |
解密出的明文同时解释了题目背景：联邦学习安全聚合场景下，客户端使用二元 dropout mask s 作为种子派生 SHA-256 掩码隐藏模型梯度更新 masked_update。
4. 完整解题脚本
将以下脚本保存为 solve.py 即可独立运行（已内嵌全部题目数据，无需外部文件依赖）：
import hashlib
from fpylll import IntegerMatrix, LLL
q = 7681
n = 32
m = 64
A = [
[2395, 6050, 1036, 3320, 2631, 4663, 4329, 1258, 3363, 3828, 5797, 7380, 609, 2407, 6810, 4109, 330, 7238, 3281, 4261, 2091, 5694, 641, 1845, 2593, 1584, 6754, 6468, 497, 871, 2968, 3533],
[4337, 334, 5766, 3916, 1515, 2814, 7114, 7349, 3376, 1380, 5932, 3966, 3956, 6806, 1563, 4951, 664, 3148, 711, 4742, 4178, 743, 224, 2630, 7026, 1347, 1890, 1157, 2169, 3858, 3716, 2097],
[194, 6116, 1249, 1821, 6681, 3478, 255, 3784, 4745, 103, 1888, 6175, 5978, 6399, 941, 6547, 479, 1363, 132, 1117, 1629, 6178, 6710, 6289, 3335, 7379, 1474, 4070, 67, 7502, 1629, 5051],
[4505, 4853, 2543, 1416, 6020, 5442, 1857, 4968, 5843, 6707, 6856, 4301, 3494, 2068, 3008, 7250, 3675, 1215, 4595, 2815, 10, 796, 1634, 6486, 129, 4737, 1709, 6542, 3578, 5592, 4456, 6315],
[3688, 6657, 1319, 2658, 4686, 6127, 3353, 7406, 3761, 7365, 3689, 5508, 4742, 7028, 2596, 3272, 301, 2815, 7042, 1061, 5553, 808, 7411, 3544, 1394, 6951, 1903, 6957, 3834, 161, 6094, 953],
[4113, 3282, 683, 6191, 3281, 1594, 806, 758, 2023, 4929, 38, 1392, 7615, 552, 4764, 1058, 6909, 4947, 3753, 2849, 5085, 4036, 6772, 279, 4100, 4623, 7392, 2961, 5256, 1738, 4827, 5654],
[117, 3044, 3367, 4579, 134, 2277, 5999, 4197, 3630, 5733, 457, 2763, 4403, 1340, 6157, 2752, 4702, 1034, 6888, 6086, 7228, 4562, 6738, 4323, 1014, 1939, 5530, 6979, 170, 5292, 2988, 1280],
[2329, 3504, 1759, 6698, 1919, 655, 4194, 4955, 6681, 4967, 6332, 2511, 5138, 2769, 2851, 1008, 6099, 6839, 2066, 2188, 920, 5993, 1404, 564, 6312, 1013, 1004, 3685, 5503, 5817, 4537, 1164],
[2870, 4406, 5602, 3390, 4750, 4097, 5968, 4131, 2102, 6086, 4133, 2183, 6619, 608, 4943, 6695, 3892, 2678, 7668, 6665, 3680, 3299, 7197, 4002, 6475, 4743, 6350, 1092, 7479, 2519, 4708, 5251],
[3399, 2582, 3816, 3767, 1440, 7029, 1425, 7080, 5874, 3923, 4679, 4600, 3595, 3304, 6503, 2320, 4732, 2629, 1210, 4224, 4501, 1397, 3854, 1910, 988, 7340, 6810, 793, 3026, 5309, 1956, 3230],
[5720, 872, 5274, 508, 4891, 6078, 2704, 2698, 1227, 2974, 6919, 703, 5402, 4315, 7314, 6863, 6191, 1044, 53, 5266, 2209, 4968, 3882, 5480, 5453, 7486, 5759, 1736, 5888, 4981, 667, 2343],
[4472, 7050, 5017, 4990, 3584, 5857, 4912, 6189, 4165, 4481, 710, 6889, 1332, 2894, 1095, 999, 4980, 6337, 4921, 3686, 7193, 6208, 6198, 5300, 5512, 6674, 3150, 734, 5509, 5619, 4987, 5753],
[4459, 276, 5645, 1988, 3071, 4102, 5347, 1102, 1789, 73, 4603, 4275, 4941, 6, 1334, 3576, 4415, 5481, 7633, 1397, 3601, 4097, 4524, 433, 2467, 7248, 7549, 1423, 1784, 4860, 830, 412],
[1710, 4751, 6398, 15, 153, 5457, 6836, 5363, 2185, 4161, 6870, 5279, 6698, 7449, 1299, 791, 488, 6114, 6379, 7489, 7395, 4297, 1322, 7479, 6362, 5962, 6081, 2781, 1821, 4870, 1906, 258],
[7575, 552, 5768, 1636, 3737, 2073, 5198, 7315, 1867, 5876, 676, 629, 1610, 5843, 5335, 5374, 3258, 4399, 3918, 926, 3382, 80, 5826, 4543, 2467, 4259, 4644, 360, 2060, 4856, 7219, 2967],
[425, 1397, 5950, 6621, 7524, 4911, 678, 5858, 2944, 886, 6381, 552, 2688, 5485, 553, 2998, 6547, 932, 3160, 510, 2925, 7389, 562, 503, 3681, 6763, 6893, 176, 7150, 5997, 7473, 7591],
[499, 1829, 1298, 1131, 7267, 3640, 4899, 7626, 2301, 4876, 2694, 2755, 6132, 4471, 2052, 6271, 5255, 4863, 7672, 1170, 7073, 98, 6937, 5880, 4068, 4462, 1980, 6797, 1556, 4811, 2189, 1665],
[4443, 4812, 6271, 572, 1927, 3795, 2227, 415, 4627, 5801, 6479, 1143, 267, 6951, 2307, 6256, 2128, 4352, 2179, 4398, 2407, 7654, 4604, 1108, 1947, 3392, 6818, 5111, 2241, 2830, 1794, 3699],
[4465, 1294, 3263, 1718, 172, 7246, 5923, 4438, 1730, 939, 3153, 2768, 1880, 3879, 4972, 7623, 7182, 65, 348, 5206, 2737, 2897, 3983, 3008, 3293, 6836, 251, 6291, 4171, 1060, 5784, 5241],
[657, 3405, 5622, 2550, 5780, 3534, 3477, 6628, 3549, 2590, 7424, 5883, 6759, 3042, 4408, 6124, 1398, 3940, 6119, 2139, 6398, 107, 5094, 1171, 1103, 319, 6771, 1073, 802, 5226, 1132, 2243],
[4226, 4577, 1482, 6461, 6026, 6648, 7325, 2431, 1211, 3295, 28, 359, 3205, 5682, 5477, 5383, 6569, 4986, 5639, 5302, 5858, 2163, 4497, 6008, 763, 2117, 1602, 4895, 4549, 5949, 4845, 896],
[3899, 3004, 5714, 6214, 6511, 7349, 3094, 4092, 4552, 5648, 5760, 925, 1781, 3119, 7427, 5066, 4919, 6562, 4034, 1847, 2171, 6871, 6733, 409, 5477, 3193, 3597, 5730, 6112, 3047, 7574, 3057],
[3086, 3901, 471, 6298, 1473, 7531, 2321, 2024, 7471, 3373, 4274, 4390, 1319, 6215, 3086, 7392, 3688, 3193, 5351, 1185, 4924, 2042, 27, 4584, 2375, 2341, 612, 538, 4109, 1101, 2937, 6647],
[3491, 5193, 3273, 5402, 1182, 2439, 2182, 6704, 7019, 105, 490, 3815, 2170, 961, 6254, 7111, 5934, 5962, 4582, 4585, 7050, 5784, 863, 3329, 5767, 4352, 6947, 2437, 6046, 104, 4311, 5251],
[7626, 1677, 3781, 4295, 6484, 1149, 853, 3386, 6213, 1984, 2786, 2096, 6487, 3354, 1366, 606, 7334, 3779, 1206, 2235, 2439, 212, 6141, 6899, 6091, 4920, 2387, 3335, 7296, 1984, 2600, 844],
[2480, 5903, 3271, 2241, 5863, 195, 5840, 7467, 1266, 1456, 1360, 3126, 1939, 7409, 5391, 1945, 1557, 7177, 3788, 902, 4696, 787, 259, 1528, 3007, 1383, 1656, 5299, 1538, 236, 6176, 1811],
[6242, 4758, 3003, 4663, 2447, 3699, 1729, 1366, 189, 173, 2127, 1711, 567, 3509, 4813, 7016, 7328, 7345, 550, 2177, 5503, 6588, 2277, 3926, 6841, 7299, 2415, 5269, 2599, 390, 1258, 7076],
[1782, 3512, 4569, 4760, 6442, 2355, 2908, 3742, 6776, 2508, 913, 6242, 2798, 3996, 400, 7433, 6127, 1969, 864, 5144, 2702, 4957, 5070, 115, 7510, 1982, 6818, 865, 522, 1807, 3302, 3414],
[4488, 2865, 2492, 7066, 6084, 4061, 3651, 4393, 5419, 2893, 974, 360, 47, 4193, 6130, 4863, 653, 5524, 1728, 3219, 6253, 6400, 1528, 1564, 491, 3662, 4906, 4617, 4493, 461, 2590, 4712],
[5850, 6141, 4538, 7511, 5578, 7161, 1104, 7215, 7205, 5267, 4447, 6498, 4577, 7293, 86, 6095, 1529, 5557, 3766, 3347, 665, 4222, 5842, 4143, 7325, 4226, 1777, 4221, 7480, 3604, 6354, 2732],
[4796, 4354, 7320, 2710, 475, 5289, 2414, 4861, 6543, 2590, 4888, 2631, 3407, 525, 2813, 5251, 5075, 1091, 6215, 3790, 7460, 2383, 2573, 4160, 4103, 1343, 1629, 1270, 3811, 713, 984, 1841],
[6646, 2070, 2342, 5521, 3643, 6009, 1011, 7368, 5566, 7254, 350, 6019, 3049, 3314, 1859, 5328, 2874, 3311, 1212, 876, 116, 4500, 740, 7041, 730, 6825, 4718, 3601, 3963, 3319, 4008, 6145],
[3018, 4968, 4315, 1012, 362, 6804, 2302, 3786, 3584, 575, 1821, 5077, 7381, 3754, 365, 5484, 431, 2245, 1532, 3570, 3351, 3512, 740, 4665, 5768, 4873, 6396, 5581, 2182, 3108, 2614, 3222],
[3549, 3471, 1783, 617, 7520, 4974, 2919, 6957, 2629, 1288, 3226, 872, 358, 1015, 2281, 1234, 3028, 569, 2170, 2194, 6566, 440, 3926, 2351, 1543, 6915, 4229, 1409, 5995, 9, 977, 4761],
[6341, 7424, 5006, 1053, 7431, 4739, 1240, 4123, 2423, 1268, 3842, 7152, 3814, 1551, 1048, 2322, 2514, 1205, 5300, 3401, 42, 7241, 4962, 5384, 3760, 1181, 3747, 373, 1003, 6883, 5071, 3489],
[2237, 2835, 6531, 5228, 2741, 5202, 1126, 1450, 3066, 4793, 4726, 2764, 1627, 5710, 3247, 1434, 2927, 3908, 1591, 6455, 1375, 4059, 4741, 5792, 6436, 7102, 5590, 4336, 2992, 5088, 2327, 4069],
[1595, 958, 4879, 2838, 562, 6287, 3121, 1191, 1467, 1550, 170, 5160, 2939, 124, 3953, 3218, 2555, 2305, 1160, 3575, 5993, 6579, 5296, 772, 4010, 3496, 2074, 5506, 5982, 1214, 1155, 158],
[2748, 1820, 6654, 6094, 7285, 557, 159, 2699, 2134, 6226, 1340, 5183, 3919, 443, 3418, 4866, 6665, 3000, 1842, 5190, 2582, 5478, 769, 652, 4849, 2161, 1961, 6231, 7348, 2965, 2983, 6079],
[6400, 3366, 4311, 6523, 47, 6957, 1913, 4260, 6206, 6361, 4902, 148, 2450, 6449, 4090, 5165, 4950, 2105, 1896, 7013, 3699, 1312, 4767, 5252, 1221, 7431, 7277, 143, 2634, 3604, 843, 5575],
[1962, 6838, 1974, 1077, 5563, 1221, 4481, 6290, 5710, 3541, 3586, 3992, 3477, 7385, 5320, 204, 1015, 2615, 2224, 1490, 4633, 6932, 1752, 4181, 1581, 5882, 82, 589, 4629, 6594, 5427, 4612],
[5328, 1151, 4123, 6380, 1261, 5609, 4498, 5515, 6649, 4369, 5354, 6611, 4296, 336, 5952, 3036, 530, 3524, 6730, 6447, 6596, 417, 6014, 3382, 3284, 755, 616, 4398, 7505, 2405, 7414, 2745],
[1672, 7360, 6569, 2744, 3725, 3605, 4426, 6303, 7482, 256, 4197, 6643, 6139, 1445, 4812, 6677, 6168, 4577, 5000, 2294, 1836, 7266, 464, 2690, 4152, 7154, 7173, 1034, 2730, 3874, 6632, 2160],
[5175, 5481, 1129, 7020, 7473, 5795, 7192, 4295, 3047, 1956, 2834, 2108, 1183, 885, 566, 6564, 7659, 1861, 6146, 3198, 6260, 3546, 1, 1314, 1886, 332, 3206, 6971, 4422, 4301, 7589, 5319],
[7623, 253, 5651, 593, 4597, 5124, 1303, 46, 5352, 3588, 6, 3408, 7512, 1368, 4471, 3551, 2681, 5326, 4669, 5646, 5864, 3901, 7655, 3628, 5046, 5968, 7126, 5376, 272, 101, 6278, 4503],
[5562, 3250, 2938, 3614, 3129, 6689, 798, 1660, 3415, 3532, 4218, 7353, 4753, 3711, 2735, 2741, 4766, 3875, 222, 2082, 4695, 1926, 3033, 4842, 1524, 2006, 6075, 5865, 4265, 5032, 688, 1771],
[883, 5846, 3127, 800, 5437, 6119, 2394, 2404, 2014, 902, 2272, 6269, 1057, 2733, 1160, 6893, 4576, 3611, 4246, 6019, 5520, 5131, 1979, 1898, 5840, 2, 2285, 3700, 6215, 4359, 6171, 3837],
[4578, 2478, 224, 1644, 2949, 2592, 6564, 2000, 6368, 409, 5485, 2307, 7636, 3522, 1219, 4853, 3961, 561, 3713, 7039, 5723, 5039, 5675, 6723, 7474, 1984, 2135, 4681, 7545, 6133, 2632, 5408],
[4392, 3094, 7507, 1619, 793, 2605, 6457, 5177, 5105, 5267, 1705, 5625, 5199, 3728, 3075, 6103, 6307, 6515, 3201, 7451, 4086, 5157, 43, 5344, 6677, 2016, 629, 4172, 5818, 3475, 7487, 4806],
[992, 7627, 185, 4068, 3326, 6855, 6161, 7522, 3642, 7368, 74, 5711, 7310, 7653, 5329, 3742, 2869, 1390, 5107, 818, 2401, 7009, 4737, 4049, 6969, 5908, 5802, 6738, 5102, 7595, 2383, 2133],
[1067, 6690, 1456, 6371, 7527, 3662, 4415, 2104, 3432, 6031, 5278, 2971, 2933, 2585, 4331, 5010, 996, 1017, 1103, 3450, 1797, 4112, 1528, 2230, 596, 6886, 679, 1380, 3526, 6045, 5488, 7179],
[7009, 2613, 4346, 2289, 5072, 5657, 7320, 4487, 444, 7242, 4055, 57, 432, 2760, 7672, 1921, 4349, 3534, 4080, 3567, 4841, 1067, 6569, 1440, 1264, 4010, 5984, 3346, 2342, 39, 2109, 7506],
[5533, 4872, 3287, 4380, 2071, 2173, 1406, 839, 3634, 3390, 2209, 6402, 952, 4296, 5170, 1957, 4307, 6704, 2800, 3391, 7151, 5739, 4234, 2707, 3794, 5603, 1882, 7516, 6504, 5862, 1126, 5968],
[2925, 5941, 6586, 3756, 6391, 6201, 4422, 1725, 6903, 439, 2032, 2313, 2275, 2986, 6987, 3848, 3897, 2713, 1641, 4614, 1765, 2037, 2637, 1882, 1058, 1899, 3361, 6644, 4686, 4470, 3935, 5000],
[1147, 2935, 7332, 2828, 1497, 1736, 298, 4701, 6633, 205, 930, 3924, 2632, 1298, 6514, 2618, 985, 7550, 424, 5206, 5060, 6213, 6052, 6762, 5476, 1406, 4949, 6306, 278, 4653, 5114, 6769],
[3508, 7679, 752, 3515, 990, 3901, 5599, 5574, 935, 3022, 243, 664, 5375, 1731, 1777, 2154, 5689, 1044, 2496, 2537, 4885, 5529, 3097, 5678, 5730, 4278, 2861, 2024, 6537, 442, 5288, 7569],
[65, 6344, 3835, 2824, 6670, 3749, 251, 6700, 2698, 791, 1349, 2626, 2811, 5838, 5782, 3124, 2654, 4886, 5295, 3801, 3052, 7309, 2306, 6663, 4781, 2322, 6610, 1594, 4054, 59, 2966, 7308],
[5870, 1308, 3584, 5643, 6446, 7672, 993, 3211, 7173, 4540, 1013, 5777, 6581, 335, 4665, 6676, 5931, 3533, 38, 50, 1063, 3178, 5069, 2063, 5884, 4966, 7098, 4475, 7333, 4792, 4858, 5187],
[2161, 1504, 1833, 2888, 4673, 3958, 398, 5548, 3381, 5931, 1690, 5467, 1219, 1485, 5376, 4628, 4497, 6165, 2523, 4992, 1162, 5830, 816, 7023, 5161, 2746, 2549, 1174, 4832, 2578, 6425, 5427],
[2030, 5338, 2844, 5805, 3915, 2953, 2640, 6522, 3160, 7078, 3115, 5967, 153, 1960, 282, 5488, 5540, 6538, 5821, 981, 3709, 1928, 4684, 6513, 4440, 1895, 713, 2101, 3895, 6250, 2298, 7138],
[2064, 3963, 1445, 2044, 7429, 614, 5571, 2579, 5168, 2715, 2637, 2679, 5349, 3172, 268, 770, 1804, 7140, 6265, 6715, 3242, 300, 3901, 4853, 6596, 6430, 5659, 6033, 1088, 1589, 6713, 2588],
[3216, 7, 6066, 6353, 6521, 3360, 4965, 6928, 3052, 1996, 5536, 3222, 4373, 6723, 569, 2668, 532, 5104, 2945, 254, 1686, 2236, 5418, 1697, 2614, 7245, 5825, 6169, 6571, 5165, 858, 1982],
[4198, 7431, 4888, 5990, 1734, 4970, 5194, 1272, 234, 4881, 5377, 5707, 3735, 4902, 7528, 4515, 3362, 6320, 2358, 129, 2794, 2085, 5991, 3679, 3755, 151, 1803, 2714, 1421, 1232, 5866, 2933],
[5853, 5213, 4107, 7082, 6336, 1633, 190, 4882, 5700, 3259, 7398, 900, 5169, 6157, 2815, 3667, 5785, 1364, 5763, 839, 4242, 6171, 6811, 2475, 7103, 6144, 4162, 2676, 4505, 3692, 5047, 3371],
[4543, 3660, 2208, 5901, 6076, 4539, 4807, 1223, 6407, 3520, 5829, 2258, 493, 2561, 1136, 2199, 6826, 7052, 5223, 5480, 6451, 1765, 5627, 5877, 3902, 4385, 2571, 3716, 3632, 7250, 3382, 6900]
]
b = [415, 7439, 2926, 3777, 3990, 6956, 4725, 277, 6379, 559, 5332, 6740, 6731, 4334, 473, 903, 1782, 7451, 6060, 1788, 7590, 2804, 7446, 2244, 1973, 2562, 3406, 4449, 7173, 1807, 7263, 2188, 1669, 2814, 548, 2836, 4453, 2284, 3262, 5799, 5006, 4657, 2932, 2145, 4273, 4567, 2316, 3040, 6835, 2231, 596, 510, 3249, 1629, 4485, 5018, 3228, 2387, 6223, 1831, 6057, 4349, 270, 4080]
masked_update = "7c53ddbd82faf811c0397982909a9498644d63fb50a6e697d7cf97f6"
def solve():
# 构造 (m + n + 1) = 97 维 Kannan 嵌入格基矩阵 B
dim = m + n + 1
B = IntegerMatrix(dim, dim)
for i in range(m):
B[i, i] = q
for j in range(n):
for i in range(m):
B[m + j, i] = A[i][j]
B[m + j, m + j] = 1
for i in range(m):
B[m + n, i] = -b[i] % q
B[m + n, m + n] = 1
# 执行 LLL 格基约减
LLL.reduction(B)
# 提取满足末位嵌入分量为 ±1 的短向量
for row_idx in range(dim):
row = [B[row_idx, col] for col in range(dim)]
if abs(row[-1]) == 1:
sign = 1if row[-1] == 1else-1
e_vec = [-sign * row[i] for i in range(m)]
s_vec = [sign * row[m + j] for j in range(n)]
# 验证 b == A*s + e (mod q)
if all((sum(A[i][j] * s_vec[j] for j in range(n)) + e_vec[i]) % q == b[i] % q for i in range(m)):
print(f"[+] Short vector found at row {row_idx}")
print(f"[+] s = {s_vec}")
print(f"[+] e = {e_vec}")
keystream = hashlib.sha256(bytes(s_vec)).digest()
ct = bytes.fromhex(masked_update)
print(f"[+] keystream[:28] = {keystream[:len(ct)].hex()}")
flag = bytes(x ^ y for x, y in zip(ct, keystream))
print(f"[+] Flag: {flag.decode()}")
return
if __name__ == "__main__":
solve()
Restore the Plaintext
题目描述：
Please restore the plaintext in the current session and obtain the flag.
test:ncat --ssl addr port
附件：attachments.zip
核心思路：服务端是 PKCS#1 v1.5 填充预言机，并且把第一个合法乘数一并下发；用 Bleichenbacher 攻击按这个乘数收窄明文区间，直到会话明文唯一。
1. 题目说明
题目要求恢复当前会话的明文并取出 flag。附件是 server.py 和 pubkey.json。访问方式写的是 ncat --ssl addr port，本次实例为：
ncat --ssl qocp6ack.nestctf.cyberpeace.cn 58999
明文 TCP 连上去没有数据。必须先做 TLS，再按行交互。实验室证书不是公共 CA，客户端需要关闭证书校验。
pubkey.json 只给出公钥：
e = 65537
n = 26053711197494345044781792077684912715021496527090136170200684647867265472090211834710019839499107995669155152828437896116662002233291085930822051870305763730149854492858590504378536095737328118664985736152084079800882198391309368647378331467360788476262812209190311267210497136432749618866195431576788245257578944400642543842611237033327500755489384635255355477488050218362690346216157317101091056613531444602254303947713075065315141018050424970114665608081069231050100673543130979972703432232664846464287183328555447235439966638024174265363366180280032770503317829739744455034691040984563526167517235779809547052041
n 是 2048 bit，字节长度 k = (2048 + 7) // 8 = 256。私钥在服务端的 secret.json，附件里没有。
一条连接对应一次会话。服务端把 flag 编成 PKCS#1 v1.5 type 2 块，加密后先发一行，再进入预言机循环。server.py 里的发送和判定如下：
c, s = new_session(dec, message)
conn.sendall(f"session {c:x} {s}\n".encode())
while True:
line = reader.readline(8192)
...
c = int(text, 16)
m = dec.decrypt(c)
if is_pkcs1_v15(m, dec.k):
conn.sendall(b"ok\n")
else:
conn.sendall(b"bad\n")
客户端每行提交一个十六进制密文，只可能收到 ok 或 bad。填充、密文和乘数由 pad_message、new_session、first_conforming_multiplier 生成：
def pad_message(message, k):
ps_len = k - 3 - len(message)
ps = bytearray(secrets.token_bytes(ps_len))
for i, byte in enumerate(ps):
if byte == 0:
ps[i] = 1 + secrets.randbelow(255)
return int.from_bytes(bytes((0x00, 0x02)) + bytes(ps) + b"\x00" + message, "big")
def new_session(dec, message):
m = pad_message(message, dec.k)
c = pow(m, dec.e, dec.n)
s = first_conforming_multiplier(m, dec.n, dec.k)
return c, s
def first_conforming_multiplier(m, n, k):
B = 1 << (8 * (k - 2))
s = (n + 3 * B - 1) // (3 * B)
acc = (m * s) % n
whilenot is_pkcs1_v15(acc, k):
s += 1
acc += m
if acc >= n:
acc -= n
return s
因此首行 session <c_hex> <s> 的含义是：
c = m^e mod nm是本连接的填充块，flag 原文不变，PS每次重抽s是从ceil(n / (3B))往上找到的第一个整数，使(m * s mod n)也通过填充检查
填充检查是完整的 type 2，不只看前两个字节：
def is_pkcs1_v15(m, k):
em = m.to_bytes(k, "big")
if em[0] != 0x00 or em[1] != 0x02:
return False
i = 2
while i < k and em[i] != 0:
i += 1
return 10 <= i < k
em[0:2] == 00 02，从下标 2 起至少 8 个非零字节，并且在块结束前出现分隔 00。断开连接后 PS 会变，必须在同一条连接里做完所有查询。
2. 解题思路
这是 Bleichenbacher 的 PKCS#1 v1.5 选择密文攻击。私钥不需要。预言机回答“解密结果是否像一条合法 type 2 块”。
记 B = 2^{8(k-2)} = 2^{2032}。以 00 02 开头的 k 字节整数正好落在 [2B, 3B)。对已知密文 c = m^e mod n，提交
c' = c * s^e mod n
服务端解密得到的是 m * s mod n。若回答 ok，则这个值落在 [2B, 3B)，并且还满足 PS 条件。所有仍可能的 m 因此被切成若干整数区间。反复寻找新的合法乘数，区间宽度大约每次减少 1 bit，直到只剩一个整数。
服务端已经把第一步乘数 s1 算好并下发，本地不必从 ceil(n / (3B)) 开始盲搜。对这份模数，这个起点是 17612，随机乘数落入 [2B, 3B) 的概率约为 B/n ≈ 1/52835。跳过这一段，后面大约两千次成功收窄就能定出明文。
最后检查 m^e ≡ c (mod n)，再按 00 02 || PS || 00 || flag 去掉填充。
3. 解题过程
3.1 把 ok 翻译成区间 [2B, 3B)
k = 256 字节的块如果以 00 02 开头，写成整数就是
m = 2 * 256^{254} + t = 2B + t, 0 <= t < B
所以 2B <= m <= 3B - 1。反过来，落在这个范围内的整数，其 256 字节大端表示一定以 00 02 开头。
is_pkcs1_v15 还要求前 8 个填充字节非零，并且后面某个位置有 00。因此：
回答 ok可以推出m' ∈ [2B, 3B)回答 bad不能推出m'不在这个范围内；大约四成区间内的整数会因为 PS 内部的零字节被拒绝
区间更新只在 ok 时进行，用 [2B, 3B) 做上界是可靠的。被 PS 规则拒绝的乘数直接跳过，换下一个候选。
对本次公钥：
B = 2^2032
s_start = ceil(n / (3B)) = 17612
第 4 节脚本连上后打印的 s_start=17612 就是这个值。它只和 n 有关，每条连接都一样。
3.2 用下发的 s1 做第一次收窄
设当前仍可能的明文属于若干区间。对乘数 s 和整数 r >= 0，条件
2B <= m*s - r*n <= 3B - 1
等价于
ceil((2B + r*n) / s) <= m <= floor((3B - 1 + r*n) / s)
旧区间 [a, b] 上需要考虑的 r 是
r_min = ceil((a*s - 3B + 1) / n)
r_max = floor((b*s - 2B) / n)
每个 r 和 [a, b] 求交，再把相邻区间合并。真实的 m 只要确实让 m*s mod n 落在 [2B, 3B)，就一定留在新集合里。
首行给出的 s1 已经保证 (m * s1 mod n) 通过完整填充检查，所以它必然落在 [2B, 3B)。本地用 c * s1^e mod n 再问一次预言机，只是确认这条连接和公钥匹配。确认之后直接对初始区间 [2B, 3B - 1] 做上面的交。
本次复现连接的首行给出 s1 = 44949，密文 2047 bit。确认查询返回 ok 后，区间集合收成 1 段，宽度的比特数是 2017：
k=256 s_start=17612 s1=44949 c_bits=2047
after_s1 intervals=1 width_bits=2017 queries=1
宽度和乘数的大小相符。一次成功乘法把长度约 B 的区间缩成约 B/s：
log2(44949) ≈ 15.46
log2(B / s1) = 2032 - 15.46 = 2016.54
2^2016.54 的比特长度是 2017，与输出一致。
s1 更大时，同一次交可能留下多段。另一条连接上服务端给出 s1 = 131612，首次收窄后是 3 个区间、宽度 2015 bit；脚本里的 find_s_multi 负责这种情形。它不从 s+1 逐个去问（命中率只有约 1/52835），而是对每个区间生成下一个有可能映入 [2B, 3B) 的乘数，只问这些候选里最小的一个。那条连接最终也得到了同一个 flag，共用 8070 次查询。下面的复现输出是 s1 = 44949 这一次，第一步之后已经只剩单区间。
3.3 单区间时让乘数大约翻倍
只剩 [a, b] 时，按 Bleichenbacher 的 step 2c 选下一组候选，而不是继续取最小的 s。最小乘子往往只把区间削掉一点，查询次数会从线性变成按比特线性。
取
r >= ceil(2 * (b*s_prev - 2B) / n)
再在
s ∈ [ceil((2B + r*n) / b), floor((3B - 1 + r*n) / a)]
里向预言机询问。这样得到的 s 大约至少是 2 * s_prev，新区间长度大约减半，未知比特大约减 1。某个 r 的整段候选都被 PS 规则拒绝时，r 加 1 继续。
本次连接的日志和“每次成功大约减 1 bit”一致：
step=1 width_bits=2017 queries=1
step=400 width_bits=1616 queries=1520
step=800 width_bits=1214 queries=3177
step=1200 width_bits=814 queries=4541
step=1600 width_bits=416 queries=5964
step=2000 width_bits=14 queries=7482
从 step 1 到 step 400，宽度从 2017 降到 1616，399 次成功收窄去掉 401 bit。step 2000 时还剩 14 bit，随后区间变成单点。全程 7521 次预言机查询，平均每次成功收窄大约 3.7 次往返；多出来的查询就是落进 [2B, 3B) 但没通过 8 字节 PS 检查的乘数。
区间上下界相等时，该整数就是候选明文。RSA 加密是双射，再用原始密文核对：
pow(m, e, n) == c
脚本打印 reencrypt_ok，说明这个块不是“某个看起来合法的填充块”，而是本连接密文的唯一原像。
3.4 去掉 type 2 填充
256 字节大端编码后，布局是
00 02 || PS || 00 || flag
PS 的每个字节都非零，所以从下标 2 起遇到的第一个 00 就是分隔符。分隔符后面的字节就是 flag。本次解出的 ASCII 字符串是
flag{DTAW6tuCFbAKt1FiUIYOqSO9V4U71f9EOOQuNlJu}
4. 完整解题脚本
把下面的代码保存为 solve_pkcs.py。模数和指数已经写在脚本里，不读取本地 pubkey.json。主机和端口是本次实例；换实例时只改 HOST 和 PORT。
#!/usr/bin/env python3
"""Recover the PKCS#1 v1.5 session plaintext via Bleichenbacher's oracle attack."""
import socket
import ssl
import time
HOST = "qocp6ack.nestctf.cyberpeace.cn"
PORT = 58999
E = 65537
N = int(
"26053711197494345044781792077684912715021496527090136170200684647867265472090211834710019839499107995669155152828437896116662002233291085930822051870305763730149854492858590504378536095737328118664985736152084079800882198391309368647378331467360788476262812209190311267210497136432749618866195431576788245257578944400642543842611237033327500755489384635255355477488050218362690346216157317101091056613531444602254303947713075065315141018050424970114665608081069231050100673543130979972703432232664846464287183328555447235439966638024174265363366180280032770503317829739744455034691040984563526167517235779809547052041"
)
def ceildiv(a, b):
return (a + b - 1) // b
def merge_intervals(intervals):
ifnot intervals:
return []
intervals = sorted(intervals)
merged = [list(intervals[0])]
for a, b in intervals[1:]:
if a <= merged[-1][1] + 1:
merged[-1][1] = max(merged[-1][1], b)
else:
merged.append([a, b])
return [(a, b) for a, b in merged]
def narrow(intervals, s, n, B):
"""Keep every m still inside some interval with (m*s mod n) in [2B, 3B)."""
out = []
for a, b in intervals:
rmin = ceildiv(a * s - 3 * B + 1, n)
rmax = (b * s - 2 * B) // n
if rmax < 0:
continue
if rmin < 0:
rmin = 0
for r in range(rmin, rmax + 1):
na = max(a, ceildiv(2 * B + r * n, s))
nb = min(b, (3 * B - 1 + r * n) // s)
if na <= nb:
out.append((na, nb))
return merge_intervals(out)
class Scanner:
"""Next multipliers that can send [a, b] into [2B, 3B)."""
def __init__(self, a, b, s_min, n, B):
self.a, self.b, self.n, self.B = a, b, n, B
self.s_min = s_min
self.r = max(0, ceildiv(a * s_min - 3 * B + 1, n))
self.cur = None
self.high = None
self._advance()
def _advance(self):
a, b, n, B = self.a, self.b, self.n, self.B
for _ in range(2_000_000):
low = ceildiv(2 * B + self.r * n, b)
high = (3 * B - 1 + self.r * n) // a
if high < self.s_min:
new_r = ceildiv(a * self.s_min - 3 * B + 1, n)
self.r = self.r + 1if new_r <= self.r else max(new_r, 0)
continue
start = max(low, self.s_min)
if start <= high:
self.cur, self.high = start, high
return
self.r += 1
raise RuntimeError("no candidate multiplier")
def pop(self):
s = self.cur
self.s_min = s + 1
if s < self.high:
self.cur = s + 1
else:
self.r += 1
self._advance()
return s
def find_s_multi(intervals, s_prev, n, B, oracle):
scanners = [Scanner(a, b, s_prev + 1, n, B) for a, b in intervals]
whileTrue:
s_try = min(sc.cur for sc in scanners)
if oracle(s_try):
return s_try
for sc in scanners:
if sc.cur == s_try:
sc.pop()
def find_s_single(a, b, s_prev, n, B, oracle):
"""Bleichenbacher step 2c: choose r so s roughly doubles."""
r = max(0, ceildiv(2 * (b * s_prev - 2 * B), n))
whileTrue:
low = max(s_prev + 1, ceildiv(2 * B + r * n, b))
high = (3 * B - 1 + r * n) // a
if low <= high:
for s in range(low, high + 1):
if oracle(s):
return s
r += 1
class CountingOracle:
def __init__(self, fn):
self.fn = fn
self.queries = 0
def __call__(self, s):
self.queries += 1
return self.fn(s)
def attack(n, e, c, s1, oracle, k):
B = 1 << (8 * (k - 2))
intervals = narrow([(2 * B, 3 * B - 1)], s1, n, B)
ifnot intervals:
raise RuntimeError("s1 produced an empty interval set")
width = max(b - a for a, b in intervals).bit_length()
print(f"after_s1 intervals={len(intervals)} width_bits={width} queries={oracle.queries}", flush=True)
s = s1
step = 0
t0 = time.time()
whileTrue:
step += 1
if len(intervals) == 1and intervals[0][0] == intervals[0][1]:
m = intervals[0][0]
if pow(m, e, n) != c:
raise RuntimeError("recovered block does not re-encrypt to c")
print("reencrypt_ok", flush=True)
return m
if step == 1or step % 400 == 0or len(intervals) != 1:
width = max(b - a for a, b in intervals).bit_length()
print(
f"step={step} intervals={len(intervals)} width_bits={width} "
f"queries={oracle.queries} elapsed={time.time() - t0:.1f}s",
flush=True,
)
if len(intervals) == 1:
a, b = intervals[0]
s = find_s_single(a, b, s, n, B, oracle)
else:
s = find_s_multi(intervals, s, n, B, oracle)
intervals = narrow(intervals, s, n, B)
ifnot intervals:
raise RuntimeError("interval set became empty")
class Remote:
def __init__(self, host, port):
ctx = ssl.create_default_context()
ctx.check_hostname = False
ctx.verify_mode = ssl.CERT_NONE
raw = socket.create_connection((host, port), timeout=20)
raw.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)
raw.setsockopt(socket.SOL_SOCKET, socket.SO_KEEPALIVE, 1)
self.s = ctx.wrap_socket(raw, server_hostname=host)
self.s.settimeout(60)
self.buf = b""
def readline(self):
whileb"\n"notin self.buf:
chunk = self.s.recv(8192)
ifnot chunk:
raise EOFError("connection closed")
self.buf += chunk
line, self.buf = self.buf.split(b"\n", 1)
return line
def query(self, c):
self.s.sendall(b"%x\n" % c)
line = self.readline()
if line == b"ok":
returnTrue
if line == b"bad":
returnFalse
raise RuntimeError(f"unexpected reply {line!r}")
def close(self):
self.s.close()
def unpad(m, k):
em = m.to_bytes(k, "big")
if em[:2] != b"\x00\x02":
raise RuntimeError("missing 00 02 prefix")
sep = em.index(b"\x00", 2)
if sep < 10:
raise RuntimeError("PS shorter than 8 bytes")
return em[sep + 1 :]
def main():
n, e = N, E
k = (n.bit_length() + 7) // 8
B = 1 << (8 * (k - 2))
s_start = ceildiv(n, 3 * B)
conn = Remote(HOST, PORT)
try:
parts = conn.readline().split()
if len(parts) != 3or parts[0] != b"session":
raise RuntimeError(f"bad banner {parts!r}")
c = int(parts[1], 16)
s1 = int(parts[2])
ifnot0 < c < n:
raise RuntimeError("ciphertext is outside the published modulus")
print(f"k={k} s_start={s_start} s1={s1} c_bits={c.bit_length()}", flush=True)
def raw(s):
return conn.query((c * pow(s, e, n)) % n)
oracle = CountingOracle(raw)
ifnot oracle(s1):
raise RuntimeError("published s1 was rejected")
m = attack(n, e, c, s1, oracle, k)
msg = unpad(m, k)
print(f"queries={oracle.queries}", flush=True)
print(f"FLAG {msg.decode('ascii')}", flush=True)
finally:
conn.close()
if __name__ == "__main__":
main()
