CTF_Crypto_剪枝-先知社区

剪枝

简单的剪枝比较容易看出来，看过类似的套个脚本就出了

p^q

就像这种类型的，给出了p*q和p^q，对于每一位p^q的结果来说，该位的组合情况有 4 种1^0,0^1,1^1,0^0

搜索方式是从低位开始搜索,根据条件限定，并且需要满足

非法 TeX 公式

将p和q剩下位全部填充为1，需要满足 p*q > n

将p和q剩下位全部填充为0，需要满足 p*q < n

脚本：

例题

帕鲁杯江枫渔火对愁眠

看起来非常简单，结果卡住了，我印象里|和^都是按位异或，但试了一下才发现实际上是

| 按位或：对应位有一个为1则为1。

^按位异或：对应位不同则为1，相同则为0。（我是笨蛋，这都会记错

所以leak1^leak2=p^q，常规剪枝

首尾剪枝(p^q_rev)

已知p与反方向二进制的q异或的值和p*q

从两端向中间搜索，每次搜索利用p^q_rev当前位数（与p^q_rev当前最高位有关的是当前p的最高位和q的最低位，p^q_rev当前最低位有关的是当前p的最低位和q的最高位）

如果当前搜索的最高位为”1”，则可能是：p该位为1，q对应低位为0；p该位为0，q对应低位为1。

如果当前搜索的最高位为”0”，则可能是：p该位为0，q对应低位为0；p该位为1，q对应低位为1。

搜索最低位也一样

从以下几个限定剪枝：

将p、q未搜索到的位全填0，乘积应该小于n;

将p、q未搜索到的位全填1，乘积应该大于n;

p、q低k位乘积再取低k位应该和n的低k位相同

脚本：

p ^ (q >> kbits)

思路一

已知n=p*q和p^(q>>kbits)

从高位向低位搜索，p的高kbits位已知（与给出的p^(q>>kbits)值的高kbits位相同），那搜索就从p^(q>>kbits)的kbits位后开始，即p的第kbits位，q的第1位。

若p^(q>>kbits)搜索的当前位值为1，则可能为：p为1，q为0 或者 p为0，q为1；反之若p^(q>>kbits)当前位为0，则p为1，q为1 或者 p为0，q为0。（p,q指的都是对应位的）

剪枝条件：

将p和q剩下位全部填充为1，需要满足 p*q > n

将p和q剩下位全部填充为0，需要满足 p*q < n

要注意把p的已知的高kbits位加上

结束条件是

非法 TeX 公式

脚本：

思路二

因为异或后的高 kbits 位就是 P 的高 kbits 位。用 N 除以 P 后得到的就是 Q 的高位，再次利用 Q 的高位和 gift，可以求出 P 的 kbits ～ 2*kbits 位，以此类推来恢复 P、Q。

例如下面这个：

来源：

一些关于p^q问题剪枝算法 _

我一开始不明白右移6位这个6是怎么来的，下面那个左移的位数和上面那个右移的联系是啥

后面貌似想明白了

直接说结论吧：上面那个6取别的值也是可以的，不能大于kbits，下面那个值则是最后的pbits-kbits-qbar.bit_length()

也就是说这个脚本也可以写成这样：

（更好套一点，原博客的别的题不能直接套）

例题

DASCTF 2023 & 0X401七月暑期挑战赛 ezRSA

P,Q的获取可用剪枝获得，得到之后可得n

结果一看，发现求出的n结尾居然是2，并且长度只有1020位，所以可以想到是因为n>N导致结果-N，所以真实的n应该再加上N,验算位数正好是1024位，然后是Franklin-Reiter攻击解flag

nextprime剪枝

可以看出来关键就在于gen函数

与普通首尾剪枝的区别在于这边逆序是十进制而普通的是二进制，且取逆序之后还进行了一次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的高六位与低六位(十进制位)

因此当我们爆破出p的低六位，相应的，我们也就有了q的高六位。而由于给出的额外信息b暴露了q的低六位（自行计算位数），因此我们可以对偏移量进行爆破，从而得到正确的p的高六位的逆序。爆破的依据为：

●

对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n

●

对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n

这一步解决后，问题就变成了：已知p、q的高六位和低六位以及p、q的乘积n，要求还原p、q，并且他们之间存在逆序关系。

搜索方式：

●

从两端向中间搜索

●

每一次搜索10x10种可能，分别对应高位部分的一个十进制位和低位部分的一个十进制位

剪枝条件：

●

将p、q未搜索到的位全填0，乘积应小于n

●

将p、q未搜索到的位全填9，乘积应大于n

●

p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同

与普通首尾剪枝的区别在于这边逆序是十进制而普通的是二进制，且这题取逆序之后还进行了一次nextprime

如果能爆破出p的低6位，也就有了q的高6位，因为给的b泄露了q的低6位，n的低6位一定等于p*q的低6位，所以可以爆破得到p的低6位从而得到q的高6位。

因为nextprime偏移很小一般不会超过2000，且q的低6位泄露，q是p十进制逆序的下一个值，所以q的低6位偏移不超过2000再倒序就是p的高6位，可以爆破得到。

爆破的依据是：

对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n

对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n

至此已知条件就成了已知p、q的高六位与低六位(十进制位)和p*q,并且p,q互为逆序，要还原p,q

搜索方式：从两端向中间搜索，每次搜索有10×10种可能

剪枝条件：

p,q未搜索到的位全填0，乘积应该小于n

p,q未搜索到的位全填9，乘积应该大于n

p,q低k位的乘积取低k位，应该和n的低k位相同

好难想到

到这步接下来就能得到flag了

部分参照：

Crypto趣题-剪枝

Crypto-剪枝