2025-西湖论剑-New-Year-Ring4-wp

这次西湖论剑出了这道New Year Ring4，个人认为这道题非常有意思。但是由于比赛时间本身很短，并且还是第二批次放的这道题，所以实际上选手只有3个小时来完成这题，思考的时间完全不够，感觉有点可惜。

这里详细记录一下这个题目的预期解法。

题目内容

题目：

from random import randint, choice, shuffle
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

p = getPrime(round(20.25))
a, b, d = randint(0, p), randint(0, p), 14
A, B, seed, secret = [], [], [randint(0, p) for _ in range(4)], [randint(0, p) for _ in range(d)]

PR.<x> = PolynomialRing(GF(p))
PRq = PR.quo(PR(list(b"DASCTF_XHLJ2025")))
for i in range(ord("🚩") % sum(list(map(ord, "flag")))):
    A += [PRq.random_element().list()]
    B += [(PRq(A[i]) * PRq(secret) + PRq([choice(seed) for _ in range(d)])).list()]
    seed = [(a * _ + b) % p for _ in seed]

print("A =", [a] + A)
print("B =", ["b"]+B)
print("C =", AES.new(key=md5(str([b]+seed+secret).encode()).digest(), nonce=b"Xenny.fans.club", mode=AES.MODE_CTR).encrypt(flag).hex())

题目描述：

quaternary but unknown :)

题意梳理

1.题目先生成一个20bit的素数p，之后基于如下商环生成加密数据：

$$PRq = \frac{Z_p[x]}{f}$$

其中f = PR(list(b"DASCTF_XHLJ2025"))，记d = f.degree()=14，之后生成如下数据：

• LCG的参数$a,b$
• 一个长为4的秘密列表seed
• 一个长为d的秘密列表secret，并将其转化为$PRq$下的多项式，记为$s$

所有数据均为模p下的随机数，并且p并不知道。

2.之后进行ord("🚩") % sum(list(map(ord, "flag"))) = 351轮加密，每一轮加密为：

• 生成一个$PRq$下的随机多项式$A_i$
• 生成一个长为d的随机列表，其中每个值均来自于seed，并将其转化为$PRq$下的多项式，记为$e_i$
• 计算$B_i = A_is + e_i$
• seed中每个元素均进行LCG迭代

3.给出所有的$A_i, B_i$以及LCG的参数$a$，需要解出：

• LCG的参数$b$
• 迭代到最后的seed
• 秘密列表secret

用这些数据计算[b]+seed+secret的md5值，从而解AES得到flag。

题目分析

题目主要问题在于：

1.作为基域模数的p并不知道

2.每一次加密对应的$A_i, B_i$似乎都是RLWE的样本，然而：

• $s$不是短向量，而是模q下的随机向量
• $e_i$也不是短向量，而是在指定范围内LCG迭代得到的随机向量

这导致用格求解不太可能，需要寻找其他办法。

题目求解

1.首先肯定要恢复p才能进行域运算，而p仅有20bit，所以即使是最朴素的爆破，也仅需要爆破所有20bit的素数即可。

然而，实际上是不需要把所有20bit的素数都看作可能的p，去进行后面的求解步骤的，这是因为我们有A、B列表。由于A、B列表都是模p下的值且有一定的样本数量，所以：

• A、B中的值一定全部小于p
• A、B中的最大值应该很接近p

所以可以取最大值作为基准，向后nextprime即可，一般来说nextprime次数就在10次以内，题目对应的数据为4次。

2.有了p之后需要考虑如何求解这个系统，而这个系统的显著特点在于：

• 每一轮加密中，都是相同的$s$与不同的随机多项式$A_i$做乘法
• 每一轮加密中，$e_i$都是在确定的4个值中选择的，这4个值具体是多少由初始seed以及轮次唯一决定

而既然格解决不了就要考虑解线性方程，因此要先找到题目每一轮次对应的等式究竟是多少。

3.我们可以将seed看作是四个变量，记为$e_1,e_2,e_3,e_4$；同时我们还有秘密多项式$s$不知道，同样把他的各项系数作为变量，记为$s_1,s_2,…,s_{d}$。

此外还有初始LCG的参数$b$也需要设置一个变量，此时我们总共有5+d个变量，我们需要找到有关于这些变量的等式并想办法求解。

4.商环下的乘法是可以用矩阵表示的，因此我们可以将每一轮加密的多项式计算$B_i = A_is + e_i$转换成对应的矩阵-向量乘法形式：

$$\textbf{b}_i = \textbf{s}\textbf{A}_i + \textbf{e}_i$$

展开一下更为直观：

$$(b_1, b_2, ... ,b_{d})_i = (s_1, s_2, ... ,s_{d}) \left(\begin{matrix} a_{11} &a_{12}& \cdots &a_{1d}\\ a_{21} &a_{22}& \cdots &a_{2d}\\ && \ddots &\\ a_{d1} &a_{d2}& \cdots &a_{dd}\\ \end{matrix} \right)_i + (e_1, e_2, ... ,e_{d})_i$$

简单移下项：

$$(s_1, s_2, ... ,s_{d}) \left(\begin{matrix} a_{11} &a_{12}& \cdots &a_{1d}\\ a_{21} &a_{22}& \cdots &a_{2d}\\ && \ddots &\\ a_{d1} &a_{d2}& \cdots &a_{dd}\\ \end{matrix} \right)_i + (e_1, e_2, ... ,e_{d})_i -(b_1, b_2, ... ,b_{d})_i = 0$$

那么对于每一个位置的分量，我们可以写出一个关于向量$\textbf{s}$的线性方程，比如：

$$({\color{red}s_1, s_2, ... ,s_{d}}) \left(\begin{matrix} {\color{red}a_{11}} &a_{12}& \cdots &a_{1d}\\ {\color{red}a_{21}} &a_{22}& \cdots &a_{2d}\\ && \ddots &\\ {\color{red}a_{d1}} &a_{d2}& \cdots &a_{dd}\\ \end{matrix} \right)_i + ({\color{red}e_1}, e_2, ... ,e_{d})_i -({\color{red}b_1}, b_2, ... ,b_{d})_i = 0$$

也就是：

$$b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_1 = 0$$

而我们有d个分量，所以一次交互我们可以得到d个上述方程，他们关于$s$和$e,d$都是线性的。

5.LCG的迭代是好处理的，把seed看做是一个向量$\textbf{e}$，那么每一轮次$e_i$选择范围就是：

$$i=0, \quad \textbf{e}$$ $$i=1, \quad a\textbf{e}+b$$ $$i=2, \quad a(a\textbf{e}+b) + b = a^2\textbf{e} + (a+1)b$$ $$\cdots$$ $$i=k, \quad a^k\textbf{e} + \sum_{j=0}^{k-1}(a^j)b$$

所以在$a$已知的情况下，$e,b$变量的迭代都是线性的，不会引入新的高次项变量。

6.如此一来，351次交互可以拿到351*d个方程，而变量只有5+d个，一切似乎都很明朗。

然而我们需要注意一个问题，每一个线性等式里的e并不真正等于我们最开始设置的变量，这是因为：

• 每一次加密，seed都会做LCG递推，因此本轮的e都是上一轮的e做LCG递推的结果
• 我们并不知道每个分量究竟是多少，我们只知道e会在4个确定的值中随机选择

这是什么意思呢，比如对于第一轮第一个分量的加密，要对应上之前设置的5+d个变量，那么应该是：

$$b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_1 = 0$$ $$or \quad b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_2 = 0$$ $$or \quad b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_3 = 0$$ $$or \quad b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_4 = 0$$

此处的$e_1,e_2,e_3,e_4$是设置的变量名，对应的也就是初始seed里的四个值，而不是向量$(e_1, e_2, … ,e_{d})$的分量，要注意区别。

7.我们只知道，会成立的线性等式会是4个中的一个，但是具体是哪一个似乎无从得知，然而，我们可以舍弃这种线性，而构造出一个恒成立的4次多项式：

$$(b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_1)(b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_2)(b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_3)(b_1 - \sum_{i=1}^{d}s_ia_{i1} - e_4) = 0$$

由于4个中一定“有且仅有一个成立”，所以总会有一个等于0，因此这个4次方程是恒成立的，此时我们就得到了351*d个由我们设置的5+d个变量组成的4次方程。

但是高次多变量多项式求解是不容易的，而简单的想法是做一个线性化，也就是把所有等式展开后，我们能得到如下项：

[s0^4, s0^3*s1, s0^2*s1^2, ... s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, s13, s14, e0, e1, e2, e3, b]

把这些新的项看作是新的变量，那么我们就得到了关于这些新变量的线性等式，此时解这样的线性方程就可以解出所有项来。

8.然后还有最后一个问题，上面的项总共有8020项，然而我们拥有的等式只有351*d=4914个，是不足以让我们解线性方程得到唯一解的。

此时需要注意$e_1,e_2,e_3,e_4$其实内部顺序并不重要，并且只要我们能求解出$s$，那么求解$e$的集合仅需要简单代入即可，而爆破$4!$就可以恢复他的顺序。

因此我们完全可以少设置3个变量，将$e_1,e_2,e_3,e_4$合并为$e$，那么我们构建的线性方程就是：

$$(b_1 - \sum_{i=1}^{d}s_ia_{i1} - e)^4 = 0$$

此时项数减小到了4844，小于等式数量4914，因此就可以求得唯一解了。

取消内部置换，这个举一个简单的例子就很好说明，比如已知$x$是$e_1,e_2$中的其中一个值，并且$x,e_1,e_2$都不知道，那么可以将他们视为三个变量，建一个二次方程为：

$$(x-e_1)(x-e_2) = 0$$

也就是：

$$x^2 - e_1x - e_2x + e_1e_2 = 0$$

此时得到的对应线性方程有4项，需要四个方程来解出$x^2, e_1x, e_2x, e_1e_2$

然而，如果建立：

$$(x-e)^2 = 0$$

也就是：

$$x^2 - 2ex + e^2 = 0$$

此时就只有三项，三个方程就可以解出$x^2, ex, e^2$，已经满足了我们求解$x$的需要。而之所以项变少了是因为：

$$e_1 + e_2 \rightarrow 2e$$ $$e_1e_2 \rightarrow e^2$$

这就是取消内部置换的含义

9.求出$s$和$b$之后，代入最后一轮加密并迭代一次，就可以求出最终用于加密的$seed$的集合。爆破$4!$的顺序其中有一个就可以成功解出flag了。

exp

详细exp可以参考我的repo：

My-CTF-Challenges/2025 西湖论剑/New Year Ring4/exp/exp.ipynb at main · tangcuxiaojikuai/My-CTF-Challenges (github.com)