听说maple出了道MLFSR，作为老粉之一当然就来了，然后发现其他题质量也都不错，就写篇wp记录下。
univariate
题目
题目描述：
1 | I love univariate polynomials... |
题目：
1 | from Crypto.Util.number import getPrime, bytes_to_long |
题目生成一个单变量随机多项式$f(x)$，并计算：
其中$n=pq$，给出$n,f,w$，要分解掉$n$从而解RSA得到flag。
思路
由费马小定理知道：
所以如果把指数关于$p$的多项式$f(p)$分解成：
那么有：
而$k$只需要将$f(x)$模掉$x-1$就能得到，所以求$gcd(w-2^k, n)$就能得到$p$了。
exp
1 | from Crypto.Util.number import * |
bivariate
题目
题目描述：
1 | I love bivariate polynomials... |
题目：
1 | from Crypto.Util.number import getPrime, bytes_to_long |
题目生成一个双变量随机多项式$f(x, y)$，并计算：
其中$n=pq$，给出$n,f,w$，要分解掉$n$从而解RSA得到flag。
思路
相比于上一道题，这道题的变化就是把单变量变成了双变量。
由于还拥有等式$n=pq$，所以可以把$f(p,q)$消去一元，变成单变量多项式，然后就和上一题一样了。
exp
1 | from Crypto.Util.number import * |
Prime Cuts
题目
题目描述：
1 | You can keep the primes, I'll keep the rest... |
题目：
1 | from Crypto.Hash import SHA256 |
题目在$GF(2)$下生成了一个64阶的随机方阵$M$以及一个长64的初始向量$\textbf{v}$，并用如下值的序列当作AES的key：
并给出其中当$i$为素数时的序列值，同时额外给出$M$的特征多项式$f$，要求还原flag。
思路
我们知道$f$以$M$的特征值为根，再取$f$的伴随矩阵$X$，$X$的特征值和$M$完全相等，因此两个矩阵相似，所以存在：
取$i$次幂则是：
同时右乘$\textbf{v}$：
此时可以把$P^{-1}\textbf{v}$看做一个整体，记为$\textbf{t}$，因此得到：
$P,X$虽然是不可交换的，但由于整个式子取的是得到结果的最后一个分量，所以我们看看等式右边究竟做了什么。
把他写开成两个方阵乘一个向量的形式：(这里没管$i$次幂，因为只是要看看怎么乘的而已)
因为是取最后一个分量，因此只需要关注：
记最后得到的分量是$y$，则：
这样可能不够直观，我们记$P$的最后一行为向量$\textbf{p}_{64}$，然后$X$的第$i$个列向量是$\textbf{x}_{i}$，那么就是：
而$t_i$仅仅是个数字，所以可以交换上面的运算顺序，让$t_i$先和$\textbf{p}_{64}$做运算：
不仅如此，$t_i$和$\textbf{p}_{64}$还都是固定值，而$\textbf{x}_{i}$的具体值我们是知道的。
所以实际上这是关于$t_i$以及$\textbf{p}_{64}$这128个未知数的方程，而方程数有172个，因为是在$GF(2)$下，所以即使是二次方程，groebner基可能也有机会解掉。
但实际上这也等价于对$X^i$的列空间做了个固定的线性组合，因此实际上只有64个未知数，所以直接用$X$的幂次来搜集线性方程也可以做，这也是我的做法。
exp
1 | from Crypto.Util.number import * |
1 | R = vector(F2, prime_cuts) |
1 | from Crypto.Hash import SHA256 |
1 | temp = [] |
1 | def bits_to_bytes(bits): |
MLFSR
题目
题目描述：
1 | Following the steps of @moai_man, I made another masked linear feedback shift register challenge! Except the register is a bit bigger than what you might expect 😛 |
题目：
1 | from sage.all import * |
和上一道题目类似，题目在$GF(2^{127}-1)$下生成16阶的随机方阵$M$以及长16的初始向量$\textbf{v}$，并取$M^{i}\textbf{v}$的第一个分量的高64bit作为第$i$个随机数。
给出连续256个随机数，要求能向前还原两个随机数，从而解AES得到flag。
思路
这个题目的主要问题在于不仅没有$\textbf{v}$，我们甚至没有$M$的任何有关信息，只有256个随机数而已。
我的思路是利用特征多项式。由于$M$阶为16，所以存在度为16的特征多项式$f$满足：
不妨就假设$f$为：
也就是说满足：
而虽然我们系数$a_i$和矩阵$M$都不知道，但是我们可以在上式右边同时乘上$\textbf{v}$得到：
为什么要这样做？假如最终取随机数不去掉低63位的状态为$s_i$，那么对于上式来说，我们取其第一个分量就能得到：
而又因为对任意的自然数$k$，下式也成立：
所以就得到了一个关系：
这个关系很强，如果简单移项一下会发现，新状态是由前16个状态共同决定的：
所以这本质上是个MRG，而取高位生成随机数的操作其实也就是truncated MRG，因此可以搜到论文，然后照着实现一下就好了。
exp
1 | from Crypto.Cipher import AES |
1 | #https://eprint.iacr.org/2022/1134.pdf |
1 | PR.<x> = PolynomialRing(F) |
1 | from re import findall |
1 | coef = gcd(μs[0], μs[1]).list() |
1 | from Crypto.Util.number import * |
Wrong ssh
题目
题目描述：
1 | I've heard MD4 is insecure so I made this new super secure hash to replace it, guess my 1 in a 100 million password to win big 🎰🎰🎰🎰 🤑 nc 155.248.210.243 42191 |
题目：
1 | from Crypto.Hash import MD4 |
连接上靶机后，题目随机生成一个长度为4并由printable组成的4位password，如果猜对该password就可以拿到flag，否则会返回’Nope!’。
思路
问题出在他对password猜测成功与否的check上，他不直接判断字符串是否完全相等，而是：
- 逐步判断前1个字符，前2个字符，前3个字符，前4个字符
- 每次判断也不直接判断相等，而是判断一个复杂的hash过程后的值是否相等
所以这很明显是个时间侧信道，相等的时候会进入下一步判断，从而显著增长时间。
exp
1 | from pwn import * |
Long Rods
题目
题目描述：
1 | Don't you hate it when your favorite cipher needs padding to encrypt, me, I just make my messages longer... Anyways go decrypt this code for the flag, shouldn't be too hard, even Plutarch knew how to do it |
思路
题目输出有点长，但简单来说就是个密码棒，只是密文很长，所以是个很长的密码棒XD。
而解决思路也很简单，factor一下密文发现正好是$1009\times 1013$，所以合理猜测密码棒的长度和宽度就是这两个值，因此解码即可。
exp
1 | M = Matrix(ZZ, 1009, 1013, list(enc.encode())).T |
bitD2cision
题目
题目描述：
1 | Make your decision bit by bit, again! |
题目：
1 | from Crypto.Util.number import * |
题目基于$BLS12-381$曲线，取曲线阶的因子$sn$，之后根据flag每一bit进行decision：
- 当前bit为0，则给出一个$GF(p)$下的随机数
- 当前bit为1，则给出$e(sQ_1, sQ_2)$，其中$e$为weil配对函数，$Q_1,Q_2$是曲线上的随机点
思路
这个套路很熟了，当前bit为1的weil配对值显然是个$sn$次单位根。
exp
1 | from Crypto.Util.number import * |