剪枝

(Updated: )

这段时间遇到很多类似于需要深度剪枝来进行解决的问题，遂从其他师傅的博客浅浅学习一下剪枝的问题

参考

Crypto趣题-剪枝 | 糖醋小鸡块的blog

概括

核心思路就是对p、q逐位进行剪枝爆破，从高到低或者从低到高都可以

如果从高位开始，当定下了p、q的高位，如果低位全部补0，p ⋅ q < n；全部补1，p ⋅ q > n. 如果从低位开始，必须要满足条件$p_{low}q_{low} n ，其中i为低位隐藏的模数（也就是p和q的低i位的乘积的值再模低i位必须与n的低i位相同）一般来说从高位到低位只有唯一解，但是从低位到高位有许多解，所以需要考虑用np$来进行一个判断

1.1 leak=p⊕q

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p * q
leak = p ^ q

print(f"n = {n}")
print(f"leak = {leak}")
...
n = 116680980913985384028173400009713257136954981082402173500716497561249416392181932343196566464785235662358780592150832022035397450356243249590634942283935170262145379306617298692978601294704434377010864627917803882260438084336688858373939615958665695377153841986948630079639091780686630272414593609191252302291
leak = 4981323981354981379128202740094433130063368997160710898675635752316636802002761998706351863504723968176773324731212978686889667271229195343695723977050322
...

这里泄露了n和p⊕q的取值，直接剪枝即可

从高往低的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
def pq_high_xor(p="", q=""):
    lp, lq = len(p), len(q)
    tp0 = int(p + (leak_bits-lp) * "0", 2)#当前高位下p的最小值
    tq0 = int(q + (leak_bits-lq) * "0", 2)#当前高位下q的最小值
    tp1 = int(p + (leak_bits-lp) * "1", 2)#当前高位下p的最大值
    tq1 = int(q + (leak_bits-lq) * "1", 2)#当前高位下q的最大值

    if tp0 * tq0 > n or tp1 * tq1 < n:#是否满足剪枝条件
        return
    if lp == leak_bits:#长度判断
        pq.append(tp0)
        return

    if xor[lp] == "1":#剪枝判断
        pq_high_xor(p + "0", q + "1")
        pq_high_xor(p + "1", q + "0")
    else:
        pq_high_xor(p + "0", q + "0")
        pq_high_xor(p + "1", q + "1")

n = 116680980913985384028173400009713257136954981082402173500716497561249416392181932343196566464785235662358780592150832022035397450356243249590634942283935170262145379306617298692978601294704434377010864627917803882260438084336688858373939615958665695377153841986948630079639091780686630272414593609191252302291
leak=4981323981354981379128202740094433130063368997160710898675635752316636802002761998706351863504723968176773324731212978686889667271229195343695723977050322
leak_bits = 512
xor = bin(leak)[2:].zfill(leak_bits)#为了方便使用脚本，用zfill在前面补0
pq = []

pq_high_xor()
print(pq)

从低往高位的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
def pq_low_xor(p="", q=""):
    lp, lq = len(p), len(q)
    tp = int(p, 2) if p else 0#扩展长度
    tq = int(q, 2) if q else 0#扩展长度

    if tp * tq % 2**lp != n % 2**lp:#剪枝低位条件
        return
    if lp == leak_bits:
        pq.append(tp)
        return

    if xor[-lp-1] == "1":#剪枝判断
        pq_low_xor("0" + p, "1" + q)
        pq_low_xor("1" + p, "0" + q)
    else:
        pq_low_xor("0" + p, "0" + q)
        pq_low_xor("1" + p, "1" + q)
n = 116680980913985384028173400009713257136954981082402173500716497561249416392181932343196566464785235662358780592150832022035397450356243249590634942283935170262145379306617298692978601294704434377010864627917803882260438084336688858373939615958665695377153841986948630079639091780686630272414593609191252302291
leak = 4981323981354981379128202740094433130063368997160710898675635752316636802002761998706351863504723968176773324731212978686889667271229195343695723977050322

leak_bits = 512
xor = bin(leak)[2:].zfill(512)
pq = []

pq_low_xor()
# print(pq)

for p in pq:#判断是否为正确所需的p和q
    if n % p == 0:
        print(p)
        q=n//p
        print(q)
        break

1.1.2 leak=p⊕(q>>16)

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p * q
leak = p ^ (q >> 16)

print(f"n = {n}")
print(f"leak = {leak}")
...
n = 106472595959213162235218590205522671640635095764089094235614241480470091964235534810444672039862247321409657846920163579915482842628517473654147154947742807544261477289088033183458003496566026695483214132700221832881777942342371749164664372673666878724280250620429973461021872265707611435162822238800043017693
leak = 10368163430890397676569465259278057835096013390185343614735024657852114986662960901138893706721063154883057110872469311245131211162558226705297817498042304
...

与上一题相同，区别在于这里p模了高16位，那么也就是说leak的高16位就是p的高16位，直接传入即可，同时也不需要再补0了

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
def pq_high_xor(p="", q=""):
    lp, lq = len(p), len(q)
    tp0 = int(p + (leak_bits-lp) * "0", 2)#当前高位下p的最小值
    tq0 = int(q + (leak_bits-lq) * "0", 2)#当前高位下q的最小值
    tp1 = int(p + (leak_bits-lp) * "1", 2)#当前高位下p的最大值
    tq1 = int(q + (leak_bits-lq) * "1", 2)#当前高位下q的最大值

    if tp0 * tq0 > n or tp1 * tq1 < n:#是否满足剪枝条件
        return
    if lp == leak_bits:#长度判断
        pq.append(tp0)
        return

    if xor[lp] == "1":#剪枝判断
        pq_high_xor(p + "0", q + "1")
        pq_high_xor(p + "1", q + "0")
    else:
        pq_high_xor(p + "0", q + "0")
        pq_high_xor(p + "1", q + "1")
n = 106472595959213162235218590205522671640635095764089094235614241480470091964235534810444672039862247321409657846920163579915482842628517473654147154947742807544261477289088033183458003496566026695483214132700221832881777942342371749164664372673666878724280250620429973461021872265707611435162822238800043017693
leak = 10368163430890397676569465259278057835096013390185343614735024657852114986662960901138893706721063154883057110872469311245131211162558226705297817498042304
 
leak_bits = 512
xor = bin(leak)[2:]
p_high_16 = xor[:16]
pq = []

pq_high_xor(p_high_16)
print(pq)#得到p的值

1.1.3 leak=(p⊕q)>>100

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p * q
leak = (p ^ q) >> 100

print(f"n = {n}")
print(f"leak = {leak}")
...
n = 68570543759905115486163161468891898017767761227323016094494535223864260309121370302995092612375408968518122446769978081003316692615144617580283649504452494720648413400201354695795142556353815598930007883160961039586103298041637808430561609587525642130978094187011984807433443302099816865339522732169036390481
leak = 1371554776088670105538660546676493995166682627006653295250599729130710418879502543997452743299243061102248607019262123503456
...

还是相同的解法，这里模掉了100位，就用copper攻击解决

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
def pq_high_xor(p="", q=""):
    lp, lq = len(p), len(q)
    tp0 = int(p + (leak_bits-lp) * "0", 2)#当前高位下p的最小值
    tq0 = int(q + (leak_bits-lq) * "0", 2)#当前高位下q的最小值
    tp1 = int(p + (leak_bits-lp) * "1", 2)#当前高位下p的最大值
    tq1 = int(q + (leak_bits-lq) * "1", 2)#当前高位下q的最大值

    if tp0 * tq0 > n or tp1 * tq1 < n:#是否满足剪枝条件
        return
    if lp == leak_bits:#长度判断
        pq.append(tp0)
        return

    if xor[lp] == "1":#剪枝判断
        pq_high_xor(p + "0", q + "1")
        pq_high_xor(p + "1", q + "0")
    else:
        pq_high_xor(p + "0", q + "0")
        pq_high_xor(p + "1", q + "1")
n = 68570543759905115486163161468891898017767761227323016094494535223864260309121370302995092612375408968518122446769978081003316692615144617580283649504452494720648413400201354695795142556353815598930007883160961039586103298041637808430561609587525642130978094187011984807433443302099816865339522732169036390481
leak = 1371554776088670105538660546676493995166682627006653295250599729130710418879502543997452743299243061102248607019262123503456


leak = leak << 100
leak_bits = 412
xor = bin(leak)[2:].zfill(512)
pq = []

pq_high_xor()
# print(pq)

for p_high in pq:
    R.<x> = PolynomialRing(Zmod(n))
    f = p_high + x
    res = f.small_roots(X = 2^100,beta = 0.4)
    if res != []:
    p = p_high + int(res[0])
    print(p)

2.1 p^q_rev

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 *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
_q = int(bin(q)[2:][::-1] , 2)
c = pow(m,e,n)

print(p ^ _q)
print(n)
print(c)

'''
47761879279815109356923025519387920397647575481870870315845640832106405230526
10310021142875344535823132048350287610122830618624222175188882916320750885684668357543070611134424902255744858233485983896082731376191044874283981089774677
999963120986258459742830847940927620860107164857685447047839375819380831715400110131705491405902374029088041611909274341590559275004502111124764419485191
'''

p与q的低位开始剪枝 gift 的当前最高位对应 p 的最高位及 q 的最低位，gift 的当前最低位对应 p 的最低位及 q 的最高位 满足条件

  • 将 p、q 未搜索到的位全填 0，乘积应小于 n
  • 将 p、q 未搜索到的位全填 1，乘积应大于 n
  • p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同
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
from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

pxorq = 47761879279815109356923025519387920397647575481870870315845640832106405230526
n = 10310021142875344535823132048350287610122830618624222175188882916320750885684668357543070611134424902255744858233485983896082731376191044874283981089774677
c = 999963120986258459742830847940927620860107164857685447047839375819380831715400110131705491405902374029088041611909274341590559275004502111124764419485191
e = 65537
leak_bits = 256
pxorq = str(bin(pxorq)[2:]).zfill(leak_bits)

def find(ph,qh,pl,ql):
    l = len(ph)
    tmp0 = ph + (leak_bits-2*l)*"0" + pl
    tmp1 = ph + (leak_bits-2*l)*"1" + pl
    tmq0 = qh + (leak_bits-2*l)*"0" + ql
    tmq1 = qh + (leak_bits-2*l)*"1" + ql
    if(int(tmp0,2)*int(tmq0,2) > n):
        return
    if(int(tmp1,2)*int(tmq1,2) < n):
        return
    if(int(pl,2)*int(ql,2) % (2**(l-1)) != n % (2**(l-1))):
        return

    if(l == 128):
        pp0 = int(tmp0,2)
        if(n % pp0 == 0):
            pf = pp0
            qf = n//pp0
            phi = (pf-1)*(qf-1)
            d = inverse(e,phi)
            m1 = pow(c,d,n)
            print(long_to_bytes(m1))
            exit()

    else:
        if(pxorq[l] == "1" and pxorq[255-l] == "1"):
            find(ph+"1",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "1" and pxorq[255-l] == "0"):
            find(ph+"1",qh+"0","0"+pl,"0"+ql)
            find(ph+"0",qh+"0","0"+pl,"1"+ql)
            find(ph+"1",qh+"1","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","1"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "1"):
            find(ph+"0",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "0"):
            find(ph+"0",qh+"0","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","0"+pl,"1"+ql)
            find(ph+"0",qh+"1","1"+pl,"0"+ql)
            find(ph+"1",qh+"1","1"+pl,"1"+ql)

find("1","1","1","1")