记录一下这次GEEKCTF做出的其中三个赛题(剩下三个我连弄清楚题目要干嘛都做不到)。
babypairing
题目描述：
1 | I believe a larger space is good for security. I am testing my PKE instance with a short paragraph. The flag is of the format |
题目：
1 | import os |
看到题目描述知道这是个基于线性配对的题目，这里先介绍一下双线性配对。简单来说，双线性配对可以理解成一个函数，其输入为椭圆曲线上的两个点，输出为椭圆曲线所在的域上的一个值。如果把这个函数记为e，那么这个概念可以写为：
其中F是椭圆曲线所在域。
而对于一个配对良好的曲线来说，其双线性配对函数满足一个很重要的性质：
同时有如下定义：
以上只是很简单的描述了一下双线性配对以及它的性质，不过对于这个题目来说已经够用了，那么接下来我们回到题目来看看究竟怎么使用。
首先，题目生成一个特定的二次扩域上的特定椭圆曲线E，并取其上一个随机点g，然后题目从Fp中选取一个随机数sk当作私钥，并计算点skg作为公钥pk，并给出我们g和公钥pk的值。
之后就是加密过程，具体来说他的加密方法是：
对于输入的明文串，逐字符取ASCII码作为待加密的明文
建立一个加密字典，如果一个明文已经被加密过，则直接取字典里的值作为待加密项(也就是题目里的cFp2)；如果没有被加密过，则从曲线上随机取一个点作为cFp2
注意这里还没有真正进行加密，相同字符的cF_p2相同并不代表他们的密文相同
记上一步取得的cFp2为P，进行如下操作：
返回c1、c2的压缩点坐标作为本次加密的密文
对于点压缩并不需要关心什么，他已经给出了对应的load函数，所以可以直接从压缩的点坐标还原出完整的点坐标。那么也就是说我们可以获得每次加密得到的c2、c1两个点，要想办法利用其还原明文。
我们的出发点是，对于相同的字符，其每次加密的r虽然不同，但是P会相同。那么两两取密文中的点c11,c12,c21,c22，假设他们是相同字符的密文，那么就有：
由于P点相同，所以将c12与c22进行作差可以消去P得到：
那么此时将T与g作双线性配对就有：
这其实侧面表明双线性配对的一个重要作用：判断配对良好曲线上两个点是否在同一个循环子群中。也就是说，如果我们取的两个密文作差得到的点T与g作线性配对值为1，那么这两个密文对应的明文字符就相同，因为T是g的倍点，所以T在g生成的循环子群里；而如果不是同一个密文，由于无法消去P，因此T和g不在同一个循环群中，线性配对的值自然就不是1。
如此一来，我们可以两两判断出flag的明文字符分布情况，也就是确定flag的明文字符哪些是一样的。之后就是确定下flag框的位置以及flag头，然后去猜测词频就可以得到完整flag了。
exp：
通过线性配对对明文字符分类：
1 | from Crypto.Util.number import * |
猜测+统计词频：
1 | import string |
SpARse
题目描述：
1 | You stole Alice's RSA private key, but it is sparse, can you recover the whole key? |
题目：
1 | -----BEGIN RSA PRIVATE KEY----- |
相当离谱的一个私钥恢复，可以说除了前一部分的n、e以外(其实e也破损了一点)，后面的数据基本都不成人样了。而题目的任务也并不是简单对某个密文进行解密，而是用完整私钥文件的md5值当作flag提交，所以必须要把整个私钥文件完完全全恢复出来才行。
那么首先就要先对私钥进行一个拆分，由Xenny师傅在NSSCTF上的一个密码工坊知道，对于一个PKCS1格式的RSA私钥pem文件，其中数据满足如下排列形式“
1 | 版本 |
简单举一个例子就是：
1 | 标识头 30 |
其中”02”、”80”这样的信息其实代表着数据类型、数据长度等信息。所以我们按照这个格式去对私钥文件做对应拆分后，可以了解到这个私钥文件的破损情况是：
- n是完整的，是一个2048bit的由两个因子组成的大合数
- e缺少了最后6bit，不过其实基本可以猜测他是65537
- d、p、q、dp、dq均有不同形式的损坏，每个值泄露的比特数占比大概只有0.3左右
- invqp这个值完全缺失
那么接下来就要想办法利用这些去还原明文。
这里多说一点，对于这种破损私钥证书的拆分，我比较推荐的做法是先把base64按已知和未知，分别转成6个bit或者6个*之类的未知符号，然后再以字节(8bit)为单位去拆分他，这样拆分比较简单而且能看到直观的比特泄露情况。
然后还有个坑点是dq不知道为啥前面会多出一个填充的00而dp没有:(
虽然d、p、q、dp、dq每个值都有大面积的损毁，但是反过来想，每个值都有小面积的泄露，因此每个值其实都可以利用，那么这个题的核心思路其实就变成了一个非常综合的深搜。简单来说，我们需要从低位开始，反复利用如下几个等式去进行剪枝：
然而一个比较严重的问题是，由于k、kp、kq都不知道，即使他们都肯定在1-e这个区间内，简单爆破的话由于还要剪枝，时间肯定太长了。所以要先想办法把k、kp、kq给求出来。而由于我们拥有d的部分高位，那么求解这三个值是容易的，具体思路如下。
由于有：
所以：
那么就有：
因此我们在1-e爆破k，并计算右侧的值去和d的高位泄露的部分作比较，如果完全相同那么就找到了正确的k。
找到k以后，要继续想办法求解kp和kq，这里我们把上面的几个等式转到模e下来看：
将几个模等式联立，就可以得到在模e下其实有：
转化一下就得到：
把这个式子再代入，得到：
把p、q再用kp、kq分别代掉得到：
然后利用k和kpkq的关系去化为单元方程，这里就以消掉kq为例：
求解这个方程就能得到kp了，显然kq也是该方程的另一个根。
有了kp、kq、k之后就是利用这几个量和上面的四个等式，从低位开始深搜剪枝。不过做到这一步之后还是有点小问题，就是这几个量高位泄露的似乎都比较少，所以剪到高位后深搜会显著的慢很多。不过一个事实是低位肯定是剪对了，因此我在剪到高700位之后化为p低位泄露的问题去copper解掉。
exp：
拆分私钥：
1 | import sys |
求解k、kp、kq：
1 | from Crypto.Util.number import * |
dfs：
1 | ################################################### part3 get k,kp,kq(using sparse_solve_k_kp_kq) |
copper：
1 | from Crypto.Util.number import * |
construct priv.pem：
1 | from Crypto.Util.number import * |
HNP
题目描述：
1 | I am suffering from Herniated Nucleus Pulposus, please help me! |
题目：
1 | from Crypto.Util.number import * |
题目是一个限时challenge，在限定时间内通过三次challenge就可以得到flag，每次challenge的内容完全相同，没有难度递进。
challenge本身的内容是要求解一个HNP问题，具体来说每次challenge会做如下几件事：
生成2048bit的素数作为模数N，并生成待求解的1-N之间的随机数X
生成长度为8的1-N之间的随机数列表Y，并计算其中每个元素与X在模N下的乘积，得到长度为8的列表Z，在这之后会进入一个8轮的数据泄露，这里把题目里的下划线换成轮次对应的值i可能更便于下面说法的理解
每一轮中，Xi会取Z[i]作为本轮的值，也就是：
将Y拆分为256bit的八个块，作为Yi列表
将Xi与Yi列表中每一个值在模N下相乘，并和MASK2做与操作，得到Zi列表
泄露Zi列表
8轮完全泄露之后，要求给出正确的X值，即完成本次挑战
光是描述challenge内容本身就已经感觉到很绕了，最好多理一理题目内容。
特别是注意上面Yi和Y[i]，Zi和Z[i]的区别
由于泄露的是Zi列表，我们要先弄清楚Zi里面是什么，分析MASK2的结构可以知道，Zi其实是对Xi与Yi中每个乘积分三段341位的泄露，记T=2^341，Zij为本次泄露值，那么其中每个值可以写为：
也就是说，每次challenge中的八轮中的每一轮，会提供给我们8个这样的泄露等式，这些等式中Xi都是相等的，都等于XY[i]，那么把符号转化的好理解一些，抽象一下每一轮内的问题就是：
有八组这样的等式：
其中已知zj和N的值，T是常量2^341，yj是256bit的小量，a、b、c分别是341bit的小量，求解出x
注意这里仅仅是求解x，对应求出的也就是Xi，即XY[i]的值，而并不是最终的X。同时要注意，这是一轮内的8个值，而不是8轮。
由于等式中x并不是小量，可以看作是和N数量级相同的大数，所以当务之急是消去他。而消去他的方法和AGCD的处理手段基本一致，也就是两两取出等式：
然后上下凑x的系数：
然后作差：
然后再展开成等式：
此时等式中就仅包含以下几个未知量，其对应的比特数量级大约是：
在模N下都显得比较小，而一共有8组数据，就一共可以取得C(8,2)=28组等式来构造格，妥妥够了。事实上为了节省时间，分段取两次C(4,2)都完全可以，如此一来我们就可以构造格规约出所有的yi，拼接在一起也就得到了初始的Y[i]，如此进行八轮，就得到了全部的初始Y列表。
然而有了Y列表并不足以让我们求解出X，我们仍然需要求解一个下面形式的HNP问题：
有64组这样的等式：
求解X
和上面的区别是，现在Y[i]和Yij的值我们都知道了，并且我们要规约的量变化为了每次的a、b、c。这就是一个标准的分段HNP了，有一篇很好的文章可以做参考：
有一个小细节需要注意，由于每八个等式乘的Y[i]都一样，所以如果仅仅用同一组的式子来求解这个HNP，那么格中会存在线性相关的量，这会导致预期的由a、b、c组成的短向量并不会出现在LLL后的向量中，取而代之的是Yij组成的短向量，这是因为Yij的数量级小于a、b、c。
这也是题目给了八轮数据的意义所在，我们仅需要每轮中取一个值来进行HNP求解即可，这样就可以避免值存在线性相关带来的影响。由于泄露的位数真的很多，所以并不太需要考虑组合，就取2-8轮与第一轮进行消元的七组等式造格即可。
这样处理后时间其实相当宽松，所以并不一定要flatter进行优化。不过奇怪的是我的本地测试完全没有出错过，但是打远程却是概率成功并且没找到原因，所以只能反复重连去碰三次都成功的情况，不过其实也就最多5分钟就能出来flag了。
exp：
1 | from Crypto.Util.number import * |