质量很高的题目，记录一下做法，确实不太会对称所以暂时没有做twist这道。赛中完全没有注意到MT所以没有搞定M4sTeriX，有点可惜，还是差了一招。
n0tr5a
题目描述：
1 | It's not RSA! |
题目：
1 | from Crypto.Util.number import * |
data.txt：
1 | n = 82699881935193109791472212259236125591789180928354081401868164018417228277481034922264132029171387301840769422435233519725339633533151517379984801310897094212731380971539763520078187279519479595450340858225632773423726273875857681742976022998251134553236897670416440247498103588885527592983304472279634643957 |
题目先生成一个462bit的素数当作key，之后生成两个512bit的安全素数p、q，然后给出12轮hint，每一轮中：
给出每一轮的ee的低562位以及kk，要求分解n来解最后的RSA密文。
把hint代进等式就有：
可以看出在模$2^{562}$下满足：
记：
那么有：
这是个线性等式，且$p+q$和$key$在模$2^{562}$下都不大，所以可以LLL得到，之后解方程就可以分解n。
exp：
1 | from Crypto.Util.number import * |
seashells
题目描述：
1 | Searching for Seashells🐚 by the seaside🏝️ : ) |
题目：
1 | FLAG = "n1ctf{REDACTED}" |
题目基于CSIDH，连接上靶机后，靶机会生成一个随机数pearls，我们的目的就是求出pearls来。
为了达到这个目的，题目给了我们30轮交互机会（必须要用完），每次交互过程为：
- 靶机随机生成私钥列表，该私钥列表由0-3的元素组成，用这个私钥进行同源得到一条曲线并给出，记为E1
- 我们拿到E1后，可以选择E1上的一个点$Q$发送给靶机
- 靶机之后会将parls的比特串当作私钥列表进行同源，并将我们选择的点经过同源映射后的$\phi(Q)$返回给我们
与一般的CSIDH过程相比，题目不同的点在于工作域放在了二次扩域而不是一次域，这直接影响了CSIDH的工作机理，因为在一次域上，对于一个小素因子来说，其邻居是确定的，而二次扩域上则会有不同的邻居（参考SIDH）。
此外还有一个奇怪的地方就是每次同源靶机选择torsion points的方式，也就是下面的这个pebble函数：
1 | def pebble(self, E, ell): |
可以看出，对于一条确定的曲线来说，由于种子固定，选择的torsion points也就是固定的。
方法一
接下来进入解题，首先，由于我们可以自己构造点$Q$并获得同源后的$\phi(Q)$，这就很类似于imaginaryCTF的coast一题。在coast中，由于同源工作在一次域上，每个素因子q只有q-torsion里独特的一个分支，所以我们发送的点在经历q-isogeny之后，这个点阶的因子q一定会消失，所以可以通过判断返回的点的阶来得到私钥列表。
而这个题不一样，由于torsion在二次域上有多个分支，所以当且仅当我们发送的Q与本次同源的kernel在同一个群中的时候，Q的阶在经历q-isogeny之后，其阶的因子q才会消失。
而由于我们有E1，并且pebble函数生成kernel的时候会固定种子为1337，所以一个很自然的思路就产生了：
从素因子3开始，我们假设其对应的私钥是1，那么由于我们有E1，因此我们同样可以设置种子为1337，并通过pebble求出本次同源的kernel
我们就选这个kernel当作$Q$发送给靶机，那么当靶机返回$\phi(Q)=O$的时候，就说明3对应的私钥的确是1，否则就是0
此时我们就知道了私钥列表中3这个素因子对应的值，这代表着我们能够知道下一次我们拿到的E1经过这个值后到达的曲线，记为$E1_{3}$
那么继续这个过程，我们假设素因子5对应的私钥是1，我们同样可以通过pebble获得这个5-isogeny的kernel，记这个kernel为$Q_5$。而现在我们只要让发送的$Q$满足：
$\phi_3(Q) = Q_5$
其实并不需要相等，其实只需要在同一个torsion分支中即可，这样在$\phi_5$之后就会降阶
为此我们取$\phi_3$的对偶同源$\hat{\phi_3}$，并在$E1_{3}$上随机取一个p+1阶的点$P$，然后取$Q = \hat{\phi_3}(P)$，那么当5对应的私钥的确为1时，我们最后就会收到因为$\phi_5$降过阶的$\phi(Q)$，否则就说明5对应的私钥为0。此时我们就又得到了$E1_{3,5}$
以此类推
这个过程可以反复进行下去，一直到30轮结束的时候，我们总共可以获得前三十个素因子对应的私钥。这引出了一个严峻的问题，素因子列表总共长53，还有23个素因子获得不了，而这23bit靠爆的话，似乎复杂度还是挺高了。
所以这个方法可能可以优化一下，但是我确实没有想到啥优化的好思路。
一个想法是发送的点不直接用kernel，而是取用在乘$\frac{p+1}{q}$之后等于kernel的p+1阶点，这样在最后检查阶的变化时可能会获得其他torsion的自然泄露
此时也许可以加上一些爆破来获得完整的私钥列表
方法二
而突破点依然在于pebble，再仔细看看这个函数：
1 | def pebble(self, E, ell): |
要注意到，最后返回P之前有一个set_random_seed(randint(0,p))的过程，这似乎是为了解除set_random_seed(1337)而设计的，但是由于randint(0,p)也和种子有关，所以这实际上压根没有解除。这代表着在除了第一次pebble之前的随机私钥以外，剩下的一切都是在一个确定的状态下走的！
这甚至会影响wave中的这一行：
1 | if not signal: priv = [randint(0, 3) for _ in range(len(ells))] |
这代表着一旦某两次进入pebble的曲线一样，那么这两次同源将会完全一样，并且这两次同源之后的包括生成0-3的priv列表在内的所有步骤都会完全一样，这就会产生一个循环节。
实际测试一下会发现这种循环节太容易产生了，因此我们很轻松的就可以在30轮交互中收到两次一模一样的曲线E1，之后我们就取E1上的两个阶为p+1且在两个不同分支中的点$Q_1,Q_2$，那么比如对于3-isogeny来说，我们计算：
那么如下点会生成3-torsion的所有分支：
为什么会有这个结果，用配对的角度去想会比较简单，记：
那么显然有：
由weil pairing的性质可以知道几个事实：
- weil pairing的函数值是个3次单位根，因此$e(Q_{1,3}, Q_{2,3})$是个生成元，所以对于不同的i结果不同
- weil pairing本质是对torsion不同分支的配对，因此不同函数值对应torsion的不同分支
所以如果3对应的私钥是1的话，由于$\phi(Q_{1,3}) + i\phi(Q_{2,3})$一定会遍历到所有的3-$torsion$，所以如果经历了3-isogeny，一定有一个分支是对应的kernel，那么就存在一个结果的因子3会消失；这也就是说遍历0-2的值，这个结果一定会有一个是单位元。否则说明3对应的私钥是0。
这种方法就很简单，我们只需要找到两次一模一样的曲线，然后发送两个对任何q-torsion都不在同一个分支的Q1、Q2即可，然后就可以一次性计算出全部的私钥列表了。
而实际脚本编写的角度倒完全不用这样，因为对于后面素因子来说实际上很难在同一个torsion里，主要是前面的3、5、7这种小素因子比较容易出偏差，所以不用全部检查一遍。
exp：
1 | from Crypto.Util.number import * |
方法三
赛后和hashhash和yolbby一起讨论了好一会儿这个题目，发现在方法一的基础上完全可以加一点优化，使得能够达到如下目的：
- 每一次交互都可以找到当前已获得私钥列表的后续的第一个0
这是什么意思呢，比如说题目的pearls是：
1 | [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1] |
那么用这个优化的方法，每一次交互可以获得：
1 | [1, 1, 0] |
思路其实非常简单，假设私钥列表接下来的连续10个值全是1，那么我们能通过pebble获得完整的iso链，也就获得了一个完整的$\phi$，此时我们可以计算他的对偶同源$\hat{\phi}$，而互为dual的同源具有如下性质：
其中d是$\phi$和$\hat{\phi}$的degree。
这里连续多少个值其实不重要，10个值是计算时间和概率做了平衡的结果：
- 连续10个计算时间不算长
- 很难有连续10个1出现
那么我们在$phi$后到达的曲线上随机取一个$p+1$阶的点$P$，并计算$\hat{\phi}(P)$作为我们发送给靶机的点$G$，那么如果接下来连续十个值真的都是1，靶机发送给我们的结果就是：
那么$P$的阶就会降低d这么多。
而如果实际上并不是连续十个1，比如在连续两个1之后就断掉了，那么我们发送的$G$在降低前两个素因子的阶之后，阶将不会再下降，而这停止下降的素因子的位置就为我们指示了下一个0的位置。
而这样一来，30次交互，只要当前私钥是1，那么就至少会往前推进两个，所以运气正常的话恢复完整私钥列表就绰绰有余了。
exp：
1 | from Crypto.Util.number import * |
*M4sTeriX
题目描述：
1 | I know that the matrix master is always performing tedious and error-prone matrix operations day after day : ( |
题目：
1 | from Crypto.Util.Padding import pad |
题目先生成了一个长20的列表s，其中每个元素是$Z_{256}$下的512维向量，这是我们需要求解出的会作为AES密钥的内容。
而对于s的内容，题目给了这样一些信息：
error_work部分，题目对于s中的每一个向量$\textbf{s}_i$，计算：
其中$a_i$是$512\times1024$的矩阵，$P_i$是一个随机置换，$e_i$是误差数量为22的error。在这之后把长1024的向量$t_i$拆成一个$4\times 256$的矩阵放入矩阵$A$中，最终会得到一个$80 \times 256$的矩阵$A$
tedious_work部分，题目在$F_q$计算了一个：
并给出$π,α$
接下来就分三个部分来进入解题。
方法一
tedious_work
对于这个部分，我们有$π,α$，以及如下关系式：
注意到在$F_q$下，全为256以内值的$A$显然算小量，因此这其实是个正交格的问题，具体来说，我们用格找到满足如下条件的小值矩阵$M$：
那么代入上式有：
所以对$M$的左核进行规约就可以找到LLL-reduce过的$A$了，记为$kA$
实际上可以更进一步，用测试数据观察一下，会发现$kA$中的向量基本只涉及原始A中的至多两个向量的约减，并且系数是1或者-1。所以用贪心的思路去搜其实可以找到一个$A$的行向量置换后的结果，也就是可以找到一个$PA$，这是一个更强的条件
exp：
1 | from Crypto.Util.number import * |
*MT
这一步比赛中我完全没有注意到，直接导致了不知道该怎么恢复$A$的顺序，并且由于最后一步是需要求解s中向量的和而不是顺序的s，所以直接导致了我认为也许可以在A顺序错乱的情况下解决error_work部分，因此整个思路就跑偏了。
而现在看来，其实连题目名字都对这个做了暗示，只能说这波考虑的不是很周到TT
而之所以能用MT主要在于tedious_work部分里其实大范围使用了randrange函数：
1 | def tedious_work(A): |
而对于$q=2^{521}-1$这种数字来讲，这样的randrange(0, q)基本完全等价于getrandbits(521)，因此如果我们能求出$ε$，就有60个521bit的数字，就可以利用MT通过预测随机数的方式得到$σ$了。
而求解$ε$并不麻烦，回顾等式：
我们现在有了$kA$，那么我们求$kA$的右核$M$，代入就得到：
然后解矩阵方程就有$ε$，之后就可以通过MT预测随机数得到$σ$。
这里预测随机数的话，我用朴素的建矩阵方法会发现由于比特之间线性相关性很强，至少要用30000多bit的输出才能使矩阵的秩达到预期的19937，而这样内存会直接不够用
问了下hashhash师傅，又得到了一个有力的新工具：
而现在我们有了$σ$，就可以恢复顺序正确的$A$了，粗暴一点直接对下式逐列做LLL即可：
exp：
1 | PA = load("PA.sobj") |
error_work
现在我们有了顺序的$A$，我们也就拥有了20个下面的实例中的$t_i,a_i$：
e的误差数量少，但是误差值是$F_{256}$下的随机值，这显然是一个将$a_i$作为生成矩阵的线性码解码问题。
我对编码了解的并不多，不过很容易注意到两个事实：
1024个方程中只有22个是错误的，所以随机选520个去解方程得到s，这概率也并不低，几百万次就可以
可以这样简单测一下：
1
2t = comb((1024-22),520) / comb(1024,520)
print(int(1/t))1
7523285
$Z_{256}$完全可以转到$Z_2$下做decode，计算量减小的同时，偶数的误差还会消失，相当于误差数量会变小
同样可以测一下，既然一共有22个error，那么预期中放到模2后会减小11个error，所以我们能定位11个error的位置，从而减小选到error的概率，此时期望为：
1
2t = comb(1024-22,520) / comb(1024-11,520)
print(int(1/t))1
2920
可以看出需要的次数就少很多了
所以一个很自然的思路就是：
- 先对每个码字在模2下decode，这样可以把奇数的误差定位，然后从备选列中剔除掉
- 之后在$Z_{256}$下剩余的列中随机选择520列去解方程（这样做是为了增加约束），有解的时候就得到了s
在模2下decode可以直接抄maple在Grey Cat The Flag 2024 Qualifiers中的调用，由于模2下期望会有一半的奇数误差会消失，所以可以把error weight设置的低一些提高解码速度，之后就一直从剩余的方程组里抽一直到找到解就好。
不过实际上手会发现，解512x520规模的$F_{256}$下矩阵方程也要好几秒一次，所以要加点多进程才行。
其实还是相当慢，所以还是按预期解从$Z_2$下decode往上lift最好，但是我真的不太会
应该都不能说相当慢，实际上是巨慢，尤其有一个$F_2$下error只有6个的，预期要roll 20万次，所以我实际上偷懒没跑这组而是直接用了hashhash的数据XD
exp：
1 | A = load("A.sobj") |
1 | cipher = AES.new(md5(str(sum(s)).encode()).digest(), AES.MODE_ECB) |
方法二
有意思的是，sage的random随机数似乎也并不安全，其使用的随机数主要是基于MT的python random和基于gmp的c random。而究竟使用哪一种似乎和以下两者都有关系：
- 是矩阵还是向量
- 使用的环是什么
这一部分可以做如下测试：
1 | import random |
1 | 5944058836160505616155866937005287978210040077123457746556810859056754156581041151236899945171255465561118925474653412955903593045941410134996821295584866556 |
以及：
1 | set_random_seed(SEED) |
1 | [188, 170, 178, 103, 61, 228, 17, 94, 56, 168] |
这两个测试说明，对于题目中的：
1 | s = [random_vector(F, N//2) for _ in range(20)] |
sage均使用的是基于MT19937的python的random，而我们拥有$α$，并且比特完全足够，因此可以恢复$α$前对应的随机数状态，并且往前回滚得到$s$前的随机数状态，然后直接预测$s$就可以了。由于s使用的是randrange(0,256)所以并不好预测究竟需要回滚多少个状态，所以简单爆破一下看能不能解出flag就好了。
而对于：
似乎就没有使用python的random
exp：
1.用$α$的前60个值，和方法一的第二步MT一样恢复出$α$前的MT state：
1 | #https://github.com/icemonster/symbolic_mersenne_cracker |
2.往前回滚，并逐个测试s进行解密：
1 | from Crypto.Util.number import * |
哈哈哈