• 在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—高位剪枝

  • 先掌握方法，再归纳题型。

方法2—低位剪枝

方法3—首尾剪枝

方法4—特殊剪枝

题型1_已知n和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_已知n和(p^q>>bits)

  • 这种题型基本上就是像题型一一样进行剪枝，剪枝得到大部分p大部分的bit位，这样再使用Coppersmith攻击即可。

  • 题目附件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = bytes_to_long(flag.encode())

p = getPrime(1024)
q = getPrime(1024)

e = 65537
gift = (p ^ q) >> 400
n = p * q
print(gift)
print(n)
c = pow(m, e, n)
print(c)
"""
gift= 31958645886829465663742610069283430399728839850513083246386448538197604487936046499520648726337487741518220398603291803472699224153248758152580060648773650158416844012882499079656290683984
n= 15619505127163351990488112863141770563681865299685335225044672449726679222174346048307947030511199439211424719776067281155135078932581011042086945379010517674964386503132937564666399232773753915118399621574185937509903051039065814343973923020001058435075609186940135177566113588279789880050765917976777441097617047571689871730580173453909325715236673431821153879912252168063435406632373091016998302026085400209541600123918721359539043369121055076362039338053031901425283160162332806529991986251686578951231643999424466225561068669799631709183429733152004160441220955561218225125773530257724062784558011621107619960331
c= 5265044898684398200513906083356703459876884038316945972785773883929874451990761745669452129171819134620745907830964766040424898002648481947297293242536080478374906513529238083909508902829410210784413646328197032379795305874547377474243240849178748210770629567973487901163276011693717054581720387087565368827406564018666754977477364832065988106365591859733598683183313263133882321735804828207940650807293882383692341076382872724971004960700289433466846333180494480231222493734477317628426618535134595262632520744157878280876244576396437437202332728155506177243283113630607686326730151811058616601645253399574984429323

"""
  • 题目已知如下条件：

gift=(p⊕q)>>400n=p∗qe=65537\begin{array}{l} gift = (p\oplus q)>>400\\ n = p*q\\ e = 65537 \end{array}

  • 首先我们需要查看一下gitf的位数是不是1024-400=624，如果不是那么gitf需要补0，这是因为在最高位异或的时候，一般是两个1异或，此时得到的结果就会为0，此时最高位就会变小。
1
2
3
4
5
6
7
8
9
10
11
from tqdm import tqdm
gift= 31958645886829465663742610069283430399728839850513083246386448538197604487936046499520648726337487741518220398603291803472699224153248758152580060648773650158416844012882499079656290683984
print(int(gift).bit_length())
xor_p_q = bin(gift)[2:].zfill(624)
print(len(xor_p_q))
print(xor_p_q)
"""
623
624
011101011000010100010001100011101111011001001111010101011010111010001011011011111011111111001111111000011110101100011010110110111111001110100111000011101010001001100100111010000101001100011111000000111110101111110110011111101100001101100101011110110010000110111010111100011100100110001001101000011110101101100001100100111011101101010100000001000111011010100010010100110011101111100101001111001001101011101010011010101001001100111111001100100110001111101100001010101000100110100110011101110100000111010111100000011111011010110111101001010111001100010010001101111010010100110100111000100011101000001101110111001000110001010000
"""
  • 接下来就是类似于题型一，从高位搜索。

1.当p⊕q的某一位是1,这表明p、q的那一位为1、0或者0、12.当p⊕q的某一位是0,这表明p、q的那一位为0、0或者1、13.p、q剩余位补0,如果还大于n则剪去4.p、q剩余位补1,如果还小于n则剪去5.p<q剪去6.最后达到624位的满足条件的p值都放入一个列表中\begin{array}{l} 1.当p\oplus q的某一位是1,这表明p、q的那一位为1、0或者0、1\\ 2.当p\oplus q的某一位是0,这表明p、q的那一位为0、0或者1、1\\ 3.p、q剩余位补0,如果还大于n则剪去\\ 4.p、q剩余位补1,如果还小于n则剪去\\ 5.p<q剪去\\ 6.最后达到624位的满足条件的p值都放入一个列表中 \end{array}

  • 但是这里还存在一个问题，由于gift是p^q的部分位，所以我们剪枝的时候并不是填充到624位，而是p、q剩余位要补充满1024位。

  • 算法如下，首先进行判断判断是否符合条件，判断是否达到624位，然后再进行搜索。

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
from tqdm import tqdm
gift= 31958645886829465663742610069283430399728839850513083246386448538197604487936046499520648726337487741518220398603291803472699224153248758152580060648773650158416844012882499079656290683984
n= 15619505127163351990488112863141770563681865299685335225044672449726679222174346048307947030511199439211424719776067281155135078932581011042086945379010517674964386503132937564666399232773753915118399621574185937509903051039065814343973923020001058435075609186940135177566113588279789880050765917976777441097617047571689871730580173453909325715236673431821153879912252168063435406632373091016998302026085400209541600123918721359539043369121055076362039338053031901425283160162332806529991986251686578951231643999424466225561068669799631709183429733152004160441220955561218225125773530257724062784558011621107619960331
c= 5265044898684398200513906083356703459876884038316945972785773883929874451990761745669452129171819134620745907830964766040424898002648481947297293242536080478374906513529238083909508902829410210784413646328197032379795305874547377474243240849178748210770629567973487901163276011693717054581720387087565368827406564018666754977477364832065988106365591859733598683183313263133882321735804828207940650807293882383692341076382872724971004960700289433466846333180494480231222493734477317628426618535134595262632520744157878280876244576396437437202332728155506177243283113630607686326730151811058616601645253399574984429323
print(int(gift).bit_length())
xor_p_q = bin(gift)[2:].zfill(624)
print(len(xor_p_q))
print(xor_p_q)
p_count = []
bit = 624

print(n_x.bit_length())
def find(p,q):
    length = len(p)
    p_min = p + '0'*(1024-length)
    p_max = p + '1'*(1024-length)
    q_min = q + '0'*(1024-length)
    q_max = q + '1'*(1024-length)
    
    if int(p_min,2) < int(q_min,2):
        return 
    
    if int(p_min,2)*int(q_min,2) > n:
        return
    
    if int(p_max,2)*int(q_max,2) < n:
        return 
    
    if length == 624:
        p_count.append(int(p,2))
        return 
    else:
        if xor_p_q[length]=="0":
            find(p+"0",q+"0")
            find(p+"1",q+"1")
        else:
            find(p+"0",q+"1")
            find(p+"1",q+"0")

p = ""
q = ""
find(p,q)
print(p_count)
  • 接下来就是使用Coppersmith攻击求得p的完整位了。最终的exp如下：
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
50
51
52
53
54
55
56
57
58
59
60
61
62
from tqdm import tqdm
import libnum
gift= 31958645886829465663742610069283430399728839850513083246386448538197604487936046499520648726337487741518220398603291803472699224153248758152580060648773650158416844012882499079656290683984
n= 15619505127163351990488112863141770563681865299685335225044672449726679222174346048307947030511199439211424719776067281155135078932581011042086945379010517674964386503132937564666399232773753915118399621574185937509903051039065814343973923020001058435075609186940135177566113588279789880050765917976777441097617047571689871730580173453909325715236673431821153879912252168063435406632373091016998302026085400209541600123918721359539043369121055076362039338053031901425283160162332806529991986251686578951231643999424466225561068669799631709183429733152004160441220955561218225125773530257724062784558011621107619960331
c= 5265044898684398200513906083356703459876884038316945972785773883929874451990761745669452129171819134620745907830964766040424898002648481947297293242536080478374906513529238083909508902829410210784413646328197032379795305874547377474243240849178748210770629567973487901163276011693717054581720387087565368827406564018666754977477364832065988106365591859733598683183313263133882321735804828207940650807293882383692341076382872724971004960700289433466846333180494480231222493734477317628426618535134595262632520744157878280876244576396437437202332728155506177243283113630607686326730151811058616601645253399574984429323
print(int(gift).bit_length())
xor_p_q = bin(gift)[2:].zfill(624)
print(len(xor_p_q))
print(xor_p_q)
p_count = []
bit = 624
e = 65537
print(n_x.bit_length())
def find(p,q):
    length = len(p)
    p_min = p + '0'*(1024-length)
    p_max = p + '1'*(1024-length)
    q_min = q + '0'*(1024-length)
    q_max = q + '1'*(1024-length)
    
    if int(p_min,2) < int(q_min,2):
        return 
    
    if int(p_min,2)*int(q_min,2) > n:
        return
    
    if int(p_max,2)*int(q_max,2) < n:
        return 
    
    if length == 624:
        p_count.append(int(p,2))
        return 
    else:
        if xor_p_q[length]=="0":
            find(p+"0",q+"0")
            find(p+"1",q+"1")
        else:
            find(p+"0",q+"1")
            find(p+"1",q+"0")

p = ""
q = ""
find(p,q)
#print(p_count)
PR.<x> = PolynomialRing(Zmod(n))
for i in tqdm(p_count,leave="true"):
    f = i*(2^400) + x
    f = f.monic()
    result = f.small_roots(X=2^400,beta=0.4)
    if result:
        p = int(f(result[0]))
        q = n//p
        phi=(p-1)*(q-1)
        d = inverse_mod(e,phi)
        m = pow(c,d,n)
        print(m)
        flag = libnum.n2s(int(m))
        if b'flag' in flag:
            print(flag)
            break
# 56006392793428031098528164046902473735914942472421571736913862629536737626781484473455349368097236605
# b'flag{bf9479c1-d113-4a22-8635-eff7d74aeaff}'

题型3_已知n和p^q的低位

  • 该题型与题型3比较相似，都是泄露部分位，但是该题型需要从低位搜索，因为高位是未知的，所以比较的必须是n的低位，所以在与n比较的时候，我们需要对n进行模操作。
  • 题目如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from uuid import uuid4
flag = b'flag{' + str(uuid4()).encode() + b'}'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p * q
leak = (p ^ q) % 2**412
e = 65537
c = pow(m,e,n)
print(f"n = {n}")
print(f"leak = {leak}")
print("c=",c)
"""
n = 100067171215784436922726116667829636101749904813139264812522764457839791326558303122342640996637017743078254406667808278471432173199869414158634259101208840509206943398696427874670443166642119337187949569578775835261382262934419063527840553058604243362595487934302573649900855427025107244675713231876070288113
leak = 10543832115168186473789693511591064003599011911243189606838628791917775426849764109796961711367962396680258737918389765791736
c= 80814331464810597768737366158891960237333475871335064565579754621450945292918227366788544042379458885165286365172544344865464054423301878576663429241721492502024564913646743967814247446096208328410179346145050571335354785914338284241561040442534786615044961507831039886737797898408428067352230443860691411097
"""
  • exp如下：
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
50
51
52
53
54
55
56
57
58
59
from tqdm import tqdm
from Crypto.Util.number import *
import libnum
n = 100067171215784436922726116667829636101749904813139264812522764457839791326558303122342640996637017743078254406667808278471432173199869414158634259101208840509206943398696427874670443166642119337187949569578775835261382262934419063527840553058604243362595487934302573649900855427025107244675713231876070288113
leak = 10543832115168186473789693511591064003599011911243189606838628791917775426849764109796961711367962396680258737918389765791736
c= 80814331464810597768737366158891960237333475871335064565579754621450945292918227366788544042379458885165286365172544344865464054423301878576663429241721492502024564913646743967814247446096208328410179346145050571335354785914338284241561040442534786615044961507831039886737797898408428067352230443860691411097
e = 65537
print(leak.bit_length())
p_xor_q = bin(leak)[2:].zfill(412)
print(p_xor_q)
x = []
bit = 412
def find(p,q):
    length = len(p)
    tmp1 = int(p,2) if p else 0
    tmp2 = int(q,2) if q else 0
    tmp3 = tmp1*tmp2 % 2^length
    #print(tmp1.bit_length())
    if tmp3 != n % 2^length:
        return
        
    if length == 412:
        x.append(int(p,2))
        return 

    else:
        if p_xor_q[bit-1-length] == '1':
            find("1"+p,"0"+q)
            find("0"+p,"1"+q)
        else:
            find("1"+p,"1"+q)
            find("0"+p,"0"+q)
p = ""
q = ""
find(p,q)
for i in tqdm(x,leave="true"):
    #print(i.bit_length())
    PR.<y> = PolynomialRing(Zmod(n))
    f = y*(2^i.bit_length()) + i
    f = f.monic()
    result = f.small_roots(X=2^(512-i.bit_length()),beta = 0.4)
    if result:
        print(result)
        p = int(result[0]*2^(i.bit_length()) + i)
        print(p.bit_length())
        q = n//p
        print(q)
        phi = (p-1)*(q-1)
        try:
            d = inverse_mod(e,phi)
            m = pow(c,d,n)
            flag = long_to_bytes(m)
            if b'flag' in flag:
                print(flag)
                break
        except:
            continue

# b'flag{f01c75b0-43d8-40c0-a222-944b1f58c837}'