该文章主要记录一些深搜剪枝相关的趣题
首尾剪枝
题目来源：暂不明确
题目：
1 | from Crypto.Util.number import * |
已知条件：
- p 与 q 的反方向二进制的异或值，共256bit，记为pxorq
搜索方式：
从两端向中间搜索
每一次搜索，需利用当前 pxorq 两端的bit位。这是因为，pxorq 的当前最高位对应p的最高位及q的最低位，pxorq 的当前最低位对应p的最低位及q的最高位 (其中最高、最低均是对于当前搜索而言)
- 如果当前需搜索的最高位为”1”，则对应两种可能：p该位为1，q对应低位为0；p该位为0，q对应低位为1。剩下依此类推
剪枝条件：
- 将p、q未搜索到的位全填0，乘积应小于n
- 将p、q未搜索到的位全填1，乘积应大于n
- p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同
如此进行剪枝即可：
exp.py：
1 | from Crypto.Util.number import * |
特殊剪枝
题目来源：暂不明确
题目：
1 | import sympy |
题目txt：
1 | a1=67739512154277162085770157687437441198363095490607019903179640765859289435128844487312739643781929328039885340492248268381181927215444058044731882600621443249379470235583032722854561171610662253187419453432598163528304052508578209017561499836803166110456130462444164049945234353225230736363194196935115979960 |
可以明显看出，题目分为两部分，均是利用剪枝：
第一部分：
已知条件：
- p1 与 q1 的异或值，共1024bit，记为a1
搜索方式：
从高位向低位搜索
每一次搜索，需利用当前 a1 的最高位
- 若当前 a1 的最高位为”1”，则对应两种可能：p该位为1，q该位为0；p该位为0，q该位为1。剩下依此类推
剪枝条件：
- 将p1、q1未搜索到的位全填0，乘积应小于n
- 将p1、q1未搜索到的位全填1，乘积应大于n
- p1 > q1（这是因为，p1和q1肯定一个比另一个大，因此可以减少一半复杂度）
第二部分：
已知条件：
- (p2 * q2)与(p2 + q2)的异或值，记为a2
- (p2 * q2)与(p2 - q2)的异或值，记为b2
搜索方式：
从低位向高位搜索
每一次搜索，需利用当前 a2、b2 的最低位
- 硬搜索当前位的所有四种可能：00、01、10、11
剪枝条件：
- 若当前已搜索了 k 位，则需满足：
1 | t1 = (int(p,2)*int(q,2)) |
按照此方式就可以递归深搜出p2、q2
exp.py：
1 | from Crypto.Util.number import * |
大概需要十几秒。
Bruce Lee
题目来源：ASISCTF 2023
题目：
1 | #!/usr/bin/env python3 |
本题基于RSA，甚至加密指数也与p、q有关，因此要解密必须得到n的分解，要分解n就要找到p、q生成方式的漏洞。
p、q基于如下方式生成：
- 随机生成密度density，是一个63-114之间的值
- density的作用就是，在素数的1024个比特位中，随机选择density个位置填上1，剩下的均为0
- 最后，在最高两位填上1，保证p、q均为1024比特
那么很明显的一点是，p、q中只有很少的比特为1，绝大部分均为0。我们可以利用这一特点进行搜索得到n的分解。
搜索思路如下：
已知条件：
- p、q的乘积n
搜索方式：
广度优先搜索，注意这个是重点，前些题目都是深搜的
从低位向高位搜索
每一次搜索，硬搜索当前位的所有四种可能：00、01、10、11
剪枝条件：
- 若当前已搜索了 k 位，则需满足：p、q乘积的低 k 位应与 n 的低 k 位相同
显然，只利用上面这些条件是不足以让我们在有限时间内搜索出结果的，因为我们还没有利用上p、q绝大部分比特为0这一特点。而这也是我们为什么这道题要使用广搜而不是深搜。利用广搜，我们可以每一次获得p、q低k位的全部可能结果，然后将结果按照0的总数量降序排列，这样就可以舍弃后面的1的数量较多的结果。
当然，到底舍弃多少，才能既不舍弃掉正确结果，又能尽可能的减少时间，就是个比较复杂的问题了。这里经我测试取30000个比较合适。分解出p、q后爆破e就好。
exp：
1 | from Crypto.Util.number import * |
nextprime剪枝
题目来源：暂不明确
题目：
1 | from sympy import * |
本题重点在于由gen函数获得n的分解：
1 | def gen(): |
注意到p和q具有如下关系：
- q是p的十进制逆序的nextprime
同时，题目还给了两个额外信息a、b，分别是：
1 | a = p&(10**6) |
而这一题的p、q生成方式其实和本篇第一题首尾剪枝有异曲同工之妙，区别在于两点：一是由二进制逆序换成十进制逆序；二是q在取逆序后还作了一次nextprime操作。
那么首先，因为p、q乘积的低六位一定与n的低六位相等。因此我们可以爆破出p的低六位，相应的，我们也就有了q的高六位。
而由于给出的额外信息b暴露了q的低六位，并且我们知道，nextprime一般最多也就产生不超过两千的偏移，因此我们可以对偏移量进行爆破，从而得到正确的p的高六位的逆序。爆破的依据为：
- 对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n
- 对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n
这一步解决后，问题就变成了：已知p、q的高六位和低六位以及p、q的乘积n，要求还原p、q，并且他们之间存在逆序关系，因此用与第一题相似的方法进行深搜，具体如下：
已知条件：
- p、q的高六位与低六位(十进制位)
搜索方式：
从两端向中间搜索
每一次搜索10x10种可能，分别对应高位部分的一个十进制位和低位部分的一个十进制位
剪枝条件：
- 将p、q未搜索到的位全填0，乘积应小于n
- 将p、q未搜索到的位全填9，乘积应大于n
- p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同
当然要注意一些细节，比如本题中自己生成几组数据会发现，p、q可能为154或155位，因此返回条件在位数不同时会有差别。不过到底是154位还是155位在爆破p高六位时就可以确定了。
exp：
1 | from Crypto.Util.number import * |
做完了其实还可以思考一个问题，我们真的需要q的低六位这个信息吗？其实并不用，因为可以发现深搜速度很快，那么我们不用q的低六位这个信息，而直接爆破q的低四位，做法也是一样的(之所以爆破低四位是因为偏移量最多也就几千，低四位完全足够)
然后脚本需要注意两个细节问题：
- 要填充至4个字符
- b-i可能会小于0，这种情况需要对应加上10000变成四位正数
不用信息b的exp如下：
1 | from Crypto.Util.number import * |
hackmd5
题目来源：暂不明确
题目：
1 | from Crypto.Util.number import * |
题目保证flag串为长度14的串，然后计算出他的md5值当作pad，并赋hack初值0。之后利用flag的每一个字符ci，对hack进行如下操作：
给出hack的最终值，要求还原flag。
首先hack并不大，因此可以factordb分解出所有素因子。并且有一点很显然：hack是pad的整数倍。并且由于md5值为128bit数量级的数值，因此我们可以遍历所有可能的乘积组合，找到所有128bit附近的值当作可能的pad。
有了多组可能的pad以后，我们对每一个pad进行深搜尝试，深搜方式由hack的计算过程确定如下：
已知条件：
- hack值与pad值，flag长度为14，应该均为可见字符
搜索方式：
- 从flag末尾向前方逐字符搜索
剪枝条件：
- 每一次爆破可见字符范围，如果字符正确的话，会满足：1、hack当前值模该字符的ASCII码为0；2、hack当前值除以该字符ASCII码之后依然是pad的倍数。
- 满足上述两个条件，就可以继续向前深搜
- 当搜索到的字符长度为14时，就可以核验md5值是否等于pad，等于则搜索成功。
exp：
1 | from Crypto.Util.number import * |
SuperPrime
题目来源：HITCON CTF 2022
题目描述：
1 | Yet another cool prime generation method. |
题目：
1 | from Crypto.Util.number import getPrime, isPrime, bytes_to_long |
output：
1 | n1 = 132240475872174910020944408159013384770525986234801028624784519134365862704105251340824787510945183963356820885920367304711310957365047441178683686926111455575911962257698539064559510444855775549001648292058855493337857073693460061212792795075263084221929517773754699732129582794061997056827998985829666251060653380798686353779510948629280009197715644814616657550158740378670095210797455828266323922570838468050733341304227070902756780052159113811360169205531739117518635829837403006788948761106892086004133969899267757339921 |
题目生成素数的方式为：
1 | def getSuperPrime(nbits): |
可以看到p是随机生成的素数，而q是依赖p对应的字符串生成的，假设p的字符串共有k+1个十进制字符记为ai，如下：
则p和q的数值可以分别记作：
其中，加48代表加上”0”的ASCII码值，而乘2^8i则是bytes_to_long的计算方式，也就是逐字节累加计算出对应大整数。
而既然存在依赖关系，那么我们就可以通过这个关系对p的每个字符进行搜索剪枝，从而还原p获得每个n的分解。以此为基础，题目分成了三类剪枝。
1
1 | n1 = p1 * q1 |
首先我们可以把：bytes_to_long(str(p).encode())记作一个关于p的函数f(p)，那么n1就可以写成如下形式：
而之所以写成这样，是因为通过观察可以知道，f(p)是一个关于p的单调递增函数，因此把n1也看做关于p的函数g(p)的话，那么容易发现g(p)也是一个关于p的单调递增函数。而我们拥有函数值n1 = g(p1)以及p1的上界2^512，因此可以直接二分查找p。
exp：
1 | #task1 |
2
第二部分中，n的生成方式为：
1 | n2 = p2*p3 |
这个时候就可以利用我们刚才分析的点进行逐字符搜索：
可以看到，既然n2和n3分别是p和q相乘，那么我们就可以分别从模10和模2^8下，从末尾向前逐字符剪枝，从而搜索出p2和p3。
exp：
1 | #task2 |
3
第三部分对p4、p5、q4、q5做了个交叉，n的生成方式为：
1 | n4 = p4 * q5 |
爆破的思路也很直白，我们直接从高位向低位爆破，剪枝条件就是后面全部填0乘积小于n；全部填9乘积大于n。而有一点需要注意。512比特的素数十进制可能是154位或155位，p4和p5长度可能不等，因此需要都尝试一下。最后爆破出来发现分别是154位和155位。
exp：
1 | #task3 |
Final
全部分解完毕后，逐次解密RSA就可以恢复flag。
完整exp：
1 | from Crypto.Util.number import * |
middlersa
题目来源：暂不明确
题目：
1 | from Crypto.Util.number import * |
题目基于RSA，给出公钥n、e及密文的同时，还泄露了dp、dq的部分比特位，泄露的比特满足：
- 对于相同位置的比特，dp、dq有且仅有一个泄露该bit的值
同时我们知道dp、dq具有如下关系：
题目还将k1、k2的取值范围从(1,e)限定在了一个更小的范围内，此举显然是为了减少爆破时间。
到这里就是题目提供的所有信息了，要解出flag就要从泄露的dp、dq部分比特去还原出p、q来解密。
而由于dp、dq是按比特泄露的，对于每个位置，由于dp或dq一定有一个泄露了该bit，所以每个位置都只需要爆破两种可能性，这就自然联想到了剪枝。那么剪枝的思路如下：
已知条件：
- dp、dq泄露的部分比特(每个位置有且仅有其中一个泄露)
搜索方式：
由于有关于dp、dq的式子：
因为要逐bit搜索，所以要想办法往n上靠，因此移项整理一下有：
这就给从低位剪枝提供了方法。因为对于当前搜索到的dp、dq低i位，应该满足：
剪枝条件：
- 令：
- temp低 i 位应与 k1k2n 的低 i 位相同
如此进行剪枝即可。
exp：
1 | from Crypto.Util.number import * |
运气最差的话要花一个多小时，但是题目数据实际跑起来只需要20min。
leak_rsa
题目来源：祥云杯 2022
题目：
1 | from Crypto.Util.number import getPrime, inverse, bytes_to_long |
数据：
1 | n = 73380160475470842653695210816683702314062827937540324056880543809752271506601290265975543542548117392788987830919581511428492717214125296973338501980504384307279414528799452106399062576988406269897425829853390463840834798274139351938197666753546672052277640048588091137812362810008344723302886421059831149393 |
简单来说，题目给了以下数据：
- RSA公钥n、e的值，n由两个512bit的素数组成，e为32bit的素数
- 密文c的值
- d、p、q的部分随机比特泄露，泄露的比特位占比约为各自比特数的42%
这种题是有成熟的求解步骤的，具体是：
- 先根据e、n以及d的高位泄露部分找到k
- 结合d、q、p的泄露部分从低位开始剪枝
那么下面就分成两个步骤来讲。
找k
找k的依据是如下等式：
由于有：
所以有：
这样做得到的d’和真实的d的前半部分高位会完全一样，因此d的高位泄露部分就可以成为判断依据。而由于k一定小于e(因为d < phi(n))，所以可以在1-e的范围爆破k，并用这个判断依据去判断k是否正确。由于e本身有32bit之多，所以综合考虑正确性和时间花销，就以d的前两百位高位来判断就比较合适，用python即使不加多进程也只需要2h左右。这样做就可以找到k的准确值：
1 | k = 1972411342 |
结合d、q、p的泄露部分开始剪枝
这一部分的剪枝思路是利用以下两个等式：
这两个等式显然在任意模2^h下均成立：
所以把d、p、q一起深搜，每次搜一位并用上述两个式子剪枝即可恢复d、p、q，大概需要20min左右。
exp：
1 | from Crypto.Util.number import * |