给了 184 个 $\mathbb{F}_2[x]/x^{543} -1$ 上多项式集合 $poly\_set = \{p_1,..,p_{184} \}$ ，一个编码后的多项式 $encoded\_target$ ，一个编码矩阵 $M \in \mathbb{F}_2^{800 \times 543}$ 。需要求一个 184 比特秘密输入 secret 进行选择，使得：

首先注意到后半部分是一个编码问题，给定 $\vec v \in \mathbb{F}_2^{543},M \in \mathbb{F}_2^{800 \times 543}$ ，求一个向量 $\vec x$ 使得 :

$M \cdot \vec x + \vec e = \vec v$

本质上就是 543 个变量，给了 800 个方程，但是这 800 个方程中存在至多 10 个错误的方程（实际上就是 10 个方程是错误的），我们需要找出错误的方程，并且恢复出编码前的向量 $\vec x$ 。大概有两个思路：

多项式环 $\mathbb{F}_2[x]/x^{543} -1$ ，这个模分解开大概是 $x^{543} - 1 = (x+1)(x^2 + x + 1)f_1f_2f_3$，其中 $f_1 , f_2, f_3$ 的都是 180 次的不可约多项式 。 因此这里考虑同态到伽罗瓦域上 ，就形成了三个 Polynomial Subset Product Product (PSPP)，这三个 PSPP 所在的乘法群的阶都是 $2^{180} - 1$ ， 这个阶很光滑，所以可以求解离散对数（其他思路：能否通过 lift 提升到 $(2^{180} -1)^{3}$ ），转换到有限域上经典的子集和问题，估算一下单个背包密度：$184/180 > 1$ ，因此一般的求解子集和的方法在这题是行不通的，不能在多项式时间规约出。

因此考虑三个 PSPP 实例，这是 Multiple Subset Sum Problem，构造一个接近 200 维的格：

用 BKZ 不断调整 block_size 即可，大概需要跑 5 min。

KCTF{666aac797b125dbdcdfdd46ca066ced4ac1cc9f1824275}

1. 用 secret 的 184 比特进行选择，使得 $\prod_{i = 0}^{183} poly\_set[i]^{secret[i]} = target$
2. 上述 target 转换为 $\mathbb{F}_2^{543}$ 上向量 $\vec x$
3. 将 $encoded\_target$ 转换为 $\mathbb{F}_2^{543}$ 上向量 $\vec v$
4. 满足 ：$(M \cdot \vec x) + \vec v = \vec e$
5. 误差向量 $\vec e$ 的汉明重量小于等于 10。

1. 这个形式像 LWE ，可以考虑用格来解，构造格，用 BKZ 规约。
2. Information Set Decode 问题， 这里使用 sage 的 Information Set Decode （ISD）板子来解

1. fplll存在bug，所以在跑exp的时候请如果在 “res = solve_multiple_ssp(subsets, targets, mods, Integer(20), range(Integer(20),Integer(100),Integer(4)))” 出现error，可以调整exp的，启用被注释的“M = M.BKZ(block_size = bs, proof = False, strategies = load_strategies_json(BKZ.DEFAULT_STRATEGY_PATH + BKZ.DEFAULT_STRATEGY))”并且注释上一行代码。
2. 当blocksize = 52 时可以跳出来，循环是为了调整bkz算法的块大小。
3. 推荐使用10.0以上版本的sage
4. exp_opt.sage 是优化版本的exp，这是因为原始的BKZ算法的blocksize决定算法精度，数值越大则精度越高，所以本题目blocksize=56即可立刻跑出flag。同时M.BKZ 的 proof 设置为 False 也能加快BKZ算法的速度。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课