• 在RSA加密中有这么一类题型，这类题型的特征会给出p异或q的值。大一的时候在比赛中就经常看到，能搜索到博客，但是看到博客时发现需要用上深度搜索。就没去仔细学下去，也不想直接照抄脚本。
  • 到现在发现这类的深度搜索其实不难，现在就来学习一下。
  • 参考博客：Crypto趣题-剪枝 | 糖醋小鸡块的blog

基础知识

  • 这个其实涉及到深度搜索，所以我们需要先了解一下这个算法的基本思想。再从算法到RSA这类题型的剪枝。深度搜索其实就是一个思想，先往其中一种情况深入搜索，当这种情况搜索完发现满足条件，或者搜索的这种情况不满足条件，都会回退一步，往另一种情况搜索。
  • 一般深度搜索都是采用递归的形式。现在给出深度搜索的一个编程模型。如果要详细了解深度搜索，建议还是去看算法。（注意有的时候并不存在for循环）
1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int step)
{
	判断条件条件不满足直接返回;
	判断是否符合可能,符合可能就输出后返回;
	
	尝试每种可能 for(i=1;i<=n;i++)
	{
		继续下一步 dfs(step+1)
	}
	
	返回
}
  • 解决这个编程问题后，现在就回归到了数学问题，也就是我们要寻找题目中的一些条件，我们需要题目的一些条件：
    • 确定搜索的范围和方式
    • 确定判断条件
    • 确定我们想要的可能

题型1_直接给p^q

  • 接下来就直接看题。

  • 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode('utf-8') +b'}'
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)

print("c =",c)
print("e =",e)
print("n =",n)
print("pxorq=",p^q)
"""
c = 66392304950908878492363710070870951531455545751319561148342067457877398782558949718991790201052777075114258165343597322227423312133870924910093734510606640836588043251561979406140627180220409104790289197279651367750150961609680446724982983006836015046568723770416495789041264015005955613063446430704046342541
e = 65537
n = 108441959144783466019949523499775610834720941613924397283976591029507379036773190737681785553451219224390021126115393524892418373642573838193766663870298419018522866484967864033823662130197017420489851681081822197157446811086780203044600471496440854774133957717397970303786868281088943155384798141132782605963
pxorq= 5365823686462750525081057734877193164653044160825672347607373204558980418392160718932907290867433329472424553303252786076257554667653255425933498955296218
"""
  • 接下来查看一下题目给出的关键条件，即pxorq

pxorq=p⊕qpxorq = p \oplus q

  • 确定搜索方式：这时我们就会发现我们不能直接由pxorq恢复p、q，这时我们一位一位的查看，条件如下。这时我们便确定了搜索的方式(条件)

1.对于这512位中的每一位,我们都能挑选出一些可能2.当p⊕q的某一位是1,这表明p、q的那一位为1、0或者0、13.当p⊕q的某一位是0,这表明p、q的那一位为0、0或者1、1\begin{array}{l} 1.对于这512位中的每一位,我们都能挑选出一些可能\\ 2.当p\oplus q的某一位是1,这表明p、q的那一位为1、0或者0、1\\ 3.当p\oplus q的某一位是0,这表明p、q的那一位为0、0或者1、1 \end{array}

  • 确定满足条件的情况：接下来我们还需要确定搜索到什么条件的时候这个值是我们需要寻找的p、q：由于我们搜索是按照一位一位搜索，此时只要我们搜索的位数达到512，这时就很可能是符合题目条件的p、q

  • 确定判断条件：进行搜索的时候我们需要降低时间复杂度，所以就要设立一些条件，使得我们可以在更少的时间能得到正确的结果。

    • 其实我们在搜索的过程中，基本上可以确定搜索的结果有两个，但是我们其实只要搜索一个q即可，因为得到q后，我们可以使用p=n//q计算得到p，此时我们可以默认p>q，也就是当q<p的时候，我们可以认为是不满足条件的，这个时候可以缩短搜索的范围。
    • 上面的判断条件，只是达到一个锦上添花的效果（也就是可以缩短时间）。真正的判断条件，我们需要采取极限思维。
    • 当我们从高位搜索的时候，搜索到某一位时，p、q的前面高位都已知了，现在我们就可以进行极限的判断。我们判断搜索的这一位时，可以将p、q的剩余位都填充0或者1。将他们的相乘的结果与n比较。
      • 最大的情况就是p、q剩余位都填充1，此时如果我们搜索的这一位符合条件，此时应该会有p*q > n，如果此时p*q < n，就说明当前我们搜索到的位不符合结果，直接返回即可
      • 最小的情况就是p、q剩余位都填充0，此时如果搜索的这一位符合条件，此时应该会有p*q < n，如果此时p*q > n，就表明这次搜索就并不满足题目的条件，直接返回即可。

  • 接下来我们就使用这样的剪枝方法，对其进行剪枝。这样就可以解密了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import libnum
import gmpy2
c = 33413207850749511227518404584965321752648197437023083217857527703127099177958468117297469354994985002189524600969289307041505794655427960517170824136053859608423261628244882944505034355584435922708968489131232463522502708804306900444841660801160750466537456598288260419643939235957605370084010443518319880476
e = 65537
n = 69937960689324142377247866549093590080459879074704098933000717642985082246903977856951315583151532583778057166162510030796911163850254255571957322526800143837475133732262049143091225612510157360834204614785780822937994828043052915019016181559335740808052216997021591084236253898991006264268449552394284776071
pxorq= 3582285148305839319026390070977840914669031102024289028546435294136852418894257457449910319953210049437581456372688605696494343886296081252076014395121030
g = bin(pxorq)[2:].zfill(512)
x = []
def find(p,q):
    l = len(p)
    #print(l)
    # 先使用4个临时变量,存储着p未搜位全1、全0,q未搜位全1、全0
    tmp1 = p+(512-l)*'0' # 全0
    tmp2 = p+(512-l)*'1' # 全1
    tmq1 = q+(512-l)*'0' # 全0
    tmq2 = q+(512-l)*'1' # 全1


    # 进行搜索操作默认p>q
    if (int(tmp1,2) < int(tmq1,2)):
        return

    if (int(tmp1,2)*int(tmq1,2)  > n):
        return

    elif(int(tmp2,2)*int(tmq2,2) < n):
        return

    if(l==512):
        x.append(int(q,2))
        return


    else:
        if(g[l] == '1'):
            find(p+'1',q+'0')
            find(p+'0',q+'1')
        else:
            find(p+'1',q+'1')
            find(p+'0',q+'0')
tmp1 = ''
tmp2 = ''
find(tmp1,tmp2)
p = n//x[0]
phi = (p-1)*(x[0]-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))
# b'flag{55529e68-861b-4481-9755-650af1b3ab3e}'

题型2