数字中国决赛

依旧爆零还是很难受的，不过出人意料的是全场师傅们居然陪我一起爆零哈哈

题目

(pow部分已略过)

from time import time
import random
import os
import sys
import hashlib

import random as py_random

def sample(tau,eta,lens,B,s=None):
    lower = -B + tau * eta
    upper = B - tau * eta
    c_rows = []
    for _ in range(lens):
        row = [0] * 128
        for idx in py_random.sample(range(128), tau):
            row[idx] = py_random.choice((-1, 1))
        c_rows.append(row)
    c = matrix(ZZ, c_rows)

    if s is None:
        s = vector(ZZ, [py_random.randint(-eta, eta) for _ in range(128)])
    cs = c * s

    # If one coordinate can never satisfy the bound for any y in [-B, B],
    # rejection sampling would not terminate.
    count = 0
    while True:
        y = vector(ZZ, [py_random.randint(-B, B) for _ in range(lens)])
        z = cs + y
        if all(lower <= zi <= upper for zi in z):
            return (c_rows, list(z)), (list(s), list(y))
        count+=1
        if count>10000:
            raise Exception("Rejection sampling failed after 10000 attempts. Please check the parameters.")
            exit(0)

tau=39
eta=2
B=2*tau*eta
s= vector(ZZ, [py_random.randint(-eta, eta) for _ in range(128)])

s[0]=eta
print("the first stage")
cs=[]
leaks=[]
count=0
while count<15000:
    print("how many samples do you want to get? (0 to exit)")
    try:
        n=int(input())
    except:
        print("[-] Invalid input!")
        continue

    if n == 0:
        break
    pk,sk=sample(tau,eta,n,B,s)
    cs+=pk[0]
    leaks+=[bin(i&0xffffffff).count('1') for i in sk[1]]
    print(pk[1])
    count+=n
print("the second stage")
count=0
while count<5000:
    print("which samples do you interest in more? (-1 to exit)")
    try:
        indices=input()
        indices = [int(item.strip()) for item in indices.split(',')]
        assert all(-1 <= idx < len(cs) for idx in indices)
    except:
        print("[-] Invalid input!")
        continue
    if -1 in indices:
        break
    ans=[(cs[i],leaks[i]) for i in indices]
    print(ans)
    count+=len(indices)

print("the third stage")
print("plz input the guess secret s:")
try:
    guess_s = [int(item.strip()) for item in input().split(',')]
    assert len(guess_s) == 128
except:
    print("[-] Invalid input!")
    sys.exit(1)
if guess_s == list(s):
    flag=open("./flag.txt").read().strip()
    print(f"[+] Congratulation! Here is your flag: {flag}")
else:
    print("[-] Wrong guess! Better luck next time!")

分析

题目分析

这道题本质上是一个带泄露的稀疏秘密恢复问题，灵感来自 FLIP（Fast Lattice-based Instantiation and Primitive）加密方案。目标是通过服务端给的一些有限信息，把一个 128 维的秘密向量 s 给恢复出来。

参数设置

参数	值	含义
N	128	秘密向量的维度
tau	39	每行 c 的非零元素个数
eta	2	秘密 s 每个分量的范围 [-2, 2]
B	2×39×2 = 156	噪声 y 的范围 [-B, B]

秘密向量 s

1 2	`s = vector(ZZ, [py_random.randint(-eta, eta) for _ in range(128)]) s[0] = eta # s[0] = 2，这是已知条件`

s 是一个 128 维整数向量，每个分量取值于 {-2, -1, 0, 1, 2}，而且 s[0] = 2 是写死的。这个信息后面验证的时候会用到。

稀疏矩阵 c

c_rows = []
for _ in range(lens):
    row = [0] * 128
    for idx in py_random.sample(range(128), tau):  # 随机选 39 个位置
        row[idx] = py_random.choice((-1, 1))        # 每个位置放 ±1
    c_rows.append(row)

c 的每一行是 128 维向量，恰好有 39 个位置是 ±1，剩下 89 个位置全是 0。说白了就是一个稀疏二值矩阵。

c·s

1	`cs = c * s # 矩阵乘法，得到一个 lens 维向量`

这里有个关键的数学性质：c·s 的每个分量是有界的。

|(\mathbf{c}_i \cdot \mathbf{s})| \leq \sum_{j \in \text{supp}(\mathbf{c}_i)} |c_{ij}| \cdot |s_j| \leq 39 \times 1 \times 2 = 78

原因很简单：c 的每行只有 39 个非零元素（都是 ±1），s 的每个分量绝对值不超过 2，所以内积的绝对值最多就是 78。

噪声 y 与拒绝采样

lower = -B + tau * eta   # = -156 + 78 = -78
upper = B - tau * eta    # = 156 - 78 = 78

y = vector(ZZ, [py_random.randint(-B, B) for _ in range(lens)])  # y ∈ [-156, 156]
z = cs + y
if all(lower <= zi <= upper for zi in z):  # 要求 z ∈ [-78, 78]
    return (c_rows, list(z)), (list(s), list(y))

所以最终每个样本满足：

z_i = \mathbf{c}_i \cdot \mathbf{s} + y_i

其中：

$z_i \in [-78, 78]$ （拒绝采样保证）
$y_i \in [-156, 156]$ （均匀随机生成）
$\mathbf{c}_i \cdot \mathbf{s} \in [-78, 78]$ （稀疏性保证）

这里多说一句，为什么拒绝采样要限制 z ∈ [-78, 78]？

如果 $z \in [-78, 78]$ ，那么 $y = z - \mathbf{c} \cdot \mathbf{s} \in [-78-78, 78+78] = [-156, 156]$ ，自动满足 y 的范围约束。换句话说，这个约束确保了：给定 z 之后，y 的有效范围是 $[z-78, z+78]$ ，宽度只有 156（而不是完整的 313）。当 |z| 比较小的时候，这个范围跟 [-156, 156] 的交集更小，HW 约束就更容易把 y 唯一确定下来。

交互逻辑

第一步：收集 z 值

你可以请求最多 15000 个样本。对于每个样本，服务端返回 z 值（也就是 $\mathbf{c} \cdot \mathbf{s} + y$ ），同时在后台偷偷记录了 HW32(y)（y 当作 32 位整数来看，二进制表示里 1 的个数）。

1	`leaks += [bin(i & 0xffffffff).count('1') for i in sk[1]]`

第二步：查询详细信息

你可以按索引查询最多 5000 个样本，服务端会返回 (c_row, leak)，也就是稀疏行向量 $\mathbf{c}_i$ 和对应的 $HW_{32}(y_i)$ 。

第三步：提交答案

猜出完整的 128 维秘密向量 s，全对就给 flag。

解题思路

我们已知：

$z_i = \mathbf{c}_i \cdot \mathbf{s} + y_i$
$HW_{32}(y_i)$ （y_i 的 32 位 Hamming Weight）
$\mathbf{c}_i \cdot \mathbf{s} \in [-78, 78]$
$y_i \in [-156, 156]$

目标：恢复s

关键洞察：如果对某个样本，我们能唯一确定 $\mathbf{c}_i \cdot \mathbf{s}$ 的值，那就得到了一个关于 s 的精确线性方程。

怎么唯一确定 $\mathbf{c}_i \cdot \mathbf{s}$

已知 $z_i$ 和 $HW_{32}(y_i)$ ，我们可以：

枚举所有满足 $HW_{32}(y) = \text{leak}$ 的 $y$ 值（范围 $[-156, 156]$ ）
对每个候选 $y$ ，计算 $\mathbf{c}_i \cdot \mathbf{s} = z_i - y$
检查 $z_i - y$ 是否在 $[-78, 78]$ 范围内
如果只有一个候选满足条件，那 $\mathbf{c}_i \cdot \mathbf{s} = \text{rhs}$ 就被唯一确定了

HW32(y) 的信息量

$HW_{32}(y)$ 就是 y 的 32 位二进制表示中 1 的个数。对于 $y \in [-156, 156]$ （当作有符号 32 位整数来看），不同的 y 值可能有相同的 HW32，但这个约束已经大大缩小了候选空间。

举个例子，假设 $z = 3$ ， $HW_{32}(y) = 15$ ，那 y 必须同时满足：

$y \in [3-78, 3+78] = [-75, 81]$
$HW_{32}(y) = 15$

同时满足这两个条件的 y 可能就只有 1 个，这时候 $\mathbf{c} \cdot \mathbf{s} = 3 - y$ 就被唯一确定了。

这样一来，问题就变成了：

\mathbf{c}_i \cdot \mathbf{s} = z_i - y_i

进一步选出 128 条线性无关方程做高斯消元解方程就好了

from time import time
import random
import os
import sys
import hashlib
import string
import itertools
import heapq

from pwn import *
io = remote('127.0.0.1', 9999)
#io.interactive()
io.recvuntil("XXXX+")
a = io.recvuntil(") == ")
a = a[:-5]
target = io.recvline().strip().decode()


candidata = itertools.product(string.ascii_letters+string.digits,repeat=4)
for i,item in enumerate(candidata):
    cand = b''
    for j in range(4):
        cand += item[j].encode()
    if target == hashlib.sha256(cand + a).hexdigest():
        print("ok")
        break

io.recv()
io.sendline(cand)

zs = []

for i in range(1500):
    io.recvuntil(b'exit)\n')
    io.sendline(b'10')
    zs += eval(io.recvline().strip().decode())

# zs = sorted(enumerate(zs), key=lambda x: x[1], reverse=True)[:5000]
# print(zs[10])
data = []


qs = sorted(range(len(zs)), key=lambda i: abs(zs[i]))[:5000]

data = []
for off in range(0, 5000, 100):            # 一次问 100 个，省 RTT
    chunk = qs[off:off+100]
    io.recvuntil(b'exit)\n')
    io.sendline(','.join(map(str, chunk)).encode())
    data += eval(io.recvline().strip().decode()) 

hw = {}

for y in range(-156,157):
    hw.setdefault(bin(y & 0xffffffff).count('1') ,[]).append(y)
    
eq = []   # 装方程的系数行（每个是 128 维的 c 向量）
rhs = []

zs_ = []
exact = 0

for i in qs:
    zs_.append(zs[i])


for i in range(len(data)):
    c = data[i][0]
    leak = data[i][1]
    z = zs_[i]

    candidata = []
    for y in range(-156,157):
        if bin(y & 0xffffffff).count('1') != leak:
            continue
        cs = z-y
        if -78 <= cs <= 78:
            candidata.append(cs)

    if len(candidata) == 1:
        eq.append(c)
        rhs.append(candidata[0])
        exact += 1 

print(exact)




import sympy as sp
A = sp.Matrix([row for row in eq])
b = sp.Matrix(rhs)
s = sp.Matrix(A.solve(b))       # 精确求解s
s = [int(x) for x in s]         # 必须是整数解

# 校验再提交
assert s[0] == 2 and all(-2 <= x <= 2 for x in s)
io.sendlineafter(b'guess secret s:', ','.join(map(str, s)).encode())
print(io.recvall().decode())

数字中国决赛

https://ddanggui.top/2026/04/26/数字中国决赛/

作者

ddanggui

发布于

2026年4月26日

许可协议

tutctf wp 上一篇

软件安全区域线下赛后记下一篇

数字中国决赛

题目

分析

题目分析

参数设置

秘密向量 s

稀疏矩阵 c

c·s

噪声 y 与拒绝采样

交互逻辑

第一步：收集 z 值

第二步：查询详细信息

第三步：提交答案

解题思路

怎么唯一确定 ci⋅s\mathbf{c}_i \cdot \mathbf{s}ci​⋅s

HW32(y) 的信息量

怎么唯一确定 $\mathbf{c}_i \cdot \mathbf{s}$