zzZxby's blog

关联爆破问题

发表于
本文字数： 2.2k 阅读时长 ≈ 8 分钟
比赛上遇到了不少次，这里也算是学习记录一下

关联爆破

比赛也遇到不少形式了，知道要用剪枝操作，但是代码有时候总是操作不好，这里特记录一下，也算是一种脚本的总结

已知p*q和p^q

方法一

github有一个开源的工具，别人写好的sliedes/xor_factor: Given p xor q and n=p*q for two unknown primes p and q, factor n and output p and q. (github.com)

终端直接运行就行

方法二

逐位爆破，从低位开始爆破

1
2
3
4
5
假设p的第一个低位为1（可以通过给出的n和p^q的值判断）
那么q的的第一个低位为p^q^(p_low)
如何得到低位：初始爆破p的长度为l，对爆破的p的长度取模2的l次方，就能得到当前爆破的低位
随着l的增加，就能一位一位的爆破p的值
如何缩短代码时间：剪枝，我们在爆破的时候，需要利用p*q=n这个条件进行判断，当然这个判断也是在当前已爆破的条件上进行爆破的，也需要模操作

题目

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

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

p = getPrime(512)
q = getPrime(512)

e = 65537
gift = p ^ q
n = p * q
print(gift)
print(n)
c = pow(m, e, n)
print(c)

代码

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
from Crypto.Util.number import *
import gmpy2

gift = 5520334853495597921735282792166474758537682627339127498954775990336701482531773669053625647418049894056334409075702944146409439712371560727802612587423576
n = 90953945774792756402916737109273975426357572658472176129183499734542261231983536804533066141420383787137958313774094775411685770452817100792494381703646324445395313669011509397270148851177163554009707972993229758769302747845721871354197178531162476854683289202160901890815940019978013477363717912092956560017
c = 31570336967305212810337242412988841595290143627570694567917834395186087584933155229160817706741004691313049985541057824934010303831623853556679763568764200542586524525825411267374231726119739885331942334870376589607884116048533774547927311974187637817762430069769951277133378621019494159949051340681289187672


def findp(p, rp):
    l = len(p)
    if l == 512:
        rp.append(int(p, 2))
    else:
        pp = int(p, 2)
        qq = (gift ^ pp) % 2 ** l
        if pp * qq % 2 ** l == n % 2 ** l:
            findp('1' + p, rp)
            findp('0' + p, rp)


rp = []
findp('1', rp)
for i in rp:
    if isPrime(int(i)) and n % int(i) == 0:
        print(i)

p = 7518983858891685120046966723075954148773111773672072879887196103108934947677867057681541156965806462970842762209541610909751267864510748749931185542870859
q = n // p
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

已知p*q和(p^q>>bits)

这个题目和上面不一样就是p^q的值进行了移位操作，那么我们就不知道低位的值，也就不能从低位爆破了

那么能不能从高位爆破，问题就在于如何提取高位，我们在上面通过取模得到低位，那么高位只能通过移位获取

这里有个问题就是我们没办法爆破得到所有的位数，因为移位后的数据被抹掉了

但是我们可以爆破到已知的位数，然后利用coppersmith定理求取未知的部分

总结就是第一个情况需要从低位开始爆破，第二个情况就是从高位开始

下面总结两个脚本方法，原理都是从高位开始

题目一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

代码

爆破思路：当p,q相同位相同时为0，不同时为1，爆破的时候只需要逐位判断两种情况，当为0时p,q都置0或者都置1，当为1时p,q分别置1

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
N = 18706855965472342624057939763424482872214329403736588022670810823830284968210885370388661001166733799554843541458754316300002655734547865499832294251476719959685339472505232553318035696334043294583493018799085665100973395464171935497665253854897019585848130524402110067723380001729487763295805724049305195847415832438554371670757918022485495294646131894414072289025724167436635324722072486662116496042680216887523471775800611333173420803326625619428964822316053642973227668518358385684985208861639528026293678346064873875113765964212781464014313025439732581964381711834800618756897046018036356342152039250047100962433
gift = 31804842194481800642289237939366333950938402156162359676516215207202180995245509557106597907613130513998342782732102690555165790483400730844362691314157824965589453046147635163730354622709
gift <<=400
 
PR.<x> = PolynomialRing(Zmod(N))
ok = False
def pq_xor(tp,tq,idx):
    global ok 
    
    if ok:
        return 
    if tp*tq>N:
        return 
    if (tp+(2<<idx))*(tq+(2<<idx))<N:
        return 
        
    if idx<=400:
        try:
            f = tp + x 
            rr = f.monic().small_roots(X=2^400, beta=0.4)
            if rr != []:
                print(rr)
                print(tp)
                print('p = ',f(rr[0]))
                ok = True
                return
        except:
            pass
        
        return
    
    idx -=1
    b = (gift >>idx)&1
    one = 1<<idx 
    if b==0:
        pq_xor(tp,tq,idx)    
        pq_xor(tp+one,tq+one,idx)    
    else:   #1
        pq_xor(tp+one,tq,idx)
        pq_xor(tp,tq+one,idx)

tp = 1<<1023
tq = 1<<1023
pq_xor(tp,tq,1023)

求出p后就能解rsa了

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

p = 156312751820343202096817187657750965338488513824160102689481418250930593561890157208297426377931154984541743793038361097646017514839938385390736541319606636813885703108633813056309263784287743708451256148800766745678286950582276290297988042362295244649958953352082941635077301979033537464807142198273440123613
gift = 31804842194481800642289237939366333950938402156162359676516215207202180995245509557106597907613130513998342782732102690555165790483400730844362691314157824965589453046147635163730354622709
n = 18706855965472342624057939763424482872214329403736588022670810823830284968210885370388661001166733799554843541458754316300002655734547865499832294251476719959685339472505232553318035696334043294583493018799085665100973395464171935497665253854897019585848130524402110067723380001729487763295805724049305195847415832438554371670757918022485495294646131894414072289025724167436635324722072486662116496042680216887523471775800611333173420803326625619428964822316053642973227668518358385684985208861639528026293678346064873875113765964212781464014313025439732581964381711834800618756897046018036356342152039250047100962433
c = 12794209312573575749100915624211637292155365912707165305418491442314056699524137698990172074503800252273733761237854112762666157382998208601175150915064715204047907876367016385260965822781044525231089378759441364134208537808855535974753177409801491254478458330987262277165144909736422815482607722757203398963207791454184689820020716763711923377454162849497041563361402795290662590809159204490290459091960419194993377210983171994701178608788724920126553968410593513625304851116511549261271900279711693939689339127996950002029576453531700368097632402268119653383995840345178053336060126043684143615733387687606189824034
e = 65537

q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

题目二

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

nbits=512
p=getPrime(nbits)
q=getPrime(nbits)

leakBits = 262
leak = (p ^ q)  >> (nbits - leakBits)

n=p*q
e=65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(p)
print(q)
print("n=%d" %n)
print("c=%d" %c)
print("leak=%d" %leak)
# n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
# c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
# leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

代码

这里个上一题也有一些不一样，泄露的位数没有那么多，在用coppersmith时需要调小参数

代码来源：2023-鹏城杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

这里还有一个比较不同的，就是上个我们是移位操作，这个就假设未爆破的位数为全0或者全1，原理其实都一样

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
from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

nbits=512
leakBits = 262
leakbits = nbits - leakBits
e = 65537

n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

leak = leak << leakbits


a1 = "0" + str(bin(leak)[2:])
def find(p,q):
    l = len(p)
    tmp0 = p + (512-l)*"0"
    tmp1 = p + (512-l)*"1"
    tmq0 = q + (512-l)*"0"
    tmq1 = q + (512-l)*"1"
    if(int(tmp0,2) < int(tmq0,2)):
        return 
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    elif(int(tmp1,2)*int(tmq1,2) < n):
        return

    if(l == 512 - leakbits):
        pp = int(tmp0,2)
        PR.<x> = PolynomialRing(Zmod(n))
        f = pp + x*2 + 1
        f = f.monic()
        res = f.small_roots(X=2^leakbits-1, beta=0.5, epsilon=0.01)
        if(res):
            try:
                plow = int(res[0])
                p = pp + plow * 2 + 1
                q = n // p
                d = inverse(e,(p-1)*(q-1))
                print(long_to_bytes(int(pow(c,d,n))))
            except:
                pass
                    
    else:
        if(a1[l] == "1"):
            find(p+"1",q+"0")
            find(p+"0",q+"1")
        else:
            find(p+"0",q+"0")
            find(p+"1",q+"1")

tempp = ""
tempq = ""
find(tempp,tempq)

已知p*q和(p+q>>bits)

1
2
3
4
5
6
7
8
9
不同点
只给p+q的话可以解方程求
但是p+q进行移位操作，还是需要对数据逐位爆破求，和一种场景不同的是，这个+运算会产生进位操作
所有情况如下：
当gift当位剩余b
b==0，p,q都不变进行下一步
b==1，三种情况(p+1,q,gift-1)(p,q+1,gift-1)(p,q,gift)
b==2，三种情况(p+1,q,gift-1)(p,q+1,gift-1)(p+1,q+1,gift-2)
b==3，最后一种(p+1,q+1,gift-2)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

代码

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
N = 22398699297762429492240463695149209598953191913914250274334959408936466626709767203795928260632633526529986584516612990634853439372145270966645004610843264907486995514891241264900062942677946045045102531217747973015030965015115984831603228162539840321760619025278925339356880648514285731088578156632342855265866008190857967855561352802052119373432686410402584018364224892529791407346844329490691835861851663985544831188244011267819905082223999055440614384023833104923725075939687869221677886604547462159479192421742664500289270937685723384566928149675802958103124877898785273157964165967194692892199269557387215118229
gift = 115949464135543873667356544321114013642432063020632381195983542969535286109623221762809011120770679450341205761868649044031660422145112658119966580941713678634616521251250585930471772508493
gift = gift<<400
 
PR.<x> = PolynomialRing(Zmod(N))
ok = False
def pq_add(tp,tq,tgift,idx):
    global ok 
    if ok:
        return 
    if tp*tq>N:
        #print('>')
        return 
    
    if (tp+(2<<idx))*(tq+(2<<idx))<N:
        #print('<', hex((tp+(1<<(idx+2))))[:20], hex(tq+(2<<idx))[:20], hex(N)[:20])
        return 
        
    if idx<=400:
        try:
            f = tp + x 
            rr = f.monic().small_roots(X=2^400, beta=0.4)
            if rr != []:
                print(rr)
                print(tp)
                print('p = ',f(rr[0]))
                ok = True
                return
        except:
            pass
        
        return
    
    idx -=1
    b = tgift >>idx 
    one = 1<<idx
    
    #print(hex(tp)[:20],hex(tq)[:20],hex(tgift)[:20],idx,b)
    
    if b==0 or b==1:
        pq_add(tp,tq,tgift,idx)    
    if b==1 or b==2:
        pq_add(tp+one,tq,tgift-one,idx)
        pq_add(tp,tq+one,tgift-one,idx)
    if b==2 or b==3:
        pq_add(tp+one,tq+one,tgift-(one<<1),idx)
    
tp = 1<<1023
tq = 1<<1023
tgift = gift -tp -tq 
pq_add(tp,tq,tgift,1023)

然后解rsa

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

n = 22398699297762429492240463695149209598953191913914250274334959408936466626709767203795928260632633526529986584516612990634853439372145270966645004610843264907486995514891241264900062942677946045045102531217747973015030965015115984831603228162539840321760619025278925339356880648514285731088578156632342855265866008190857967855561352802052119373432686410402584018364224892529791407346844329490691835861851663985544831188244011267819905082223999055440614384023833104923725075939687869221677886604547462159479192421742664500289270937685723384566928149675802958103124877898785273157964165967194692892199269557387215118229
c = 19459058015255747979675566411760591387346930072958488102496553309827275614011341119722879974026004366424863422880372837878804781704271505404623120814555506455826259972089765470140479884289985712921947355761601869625995897130103364150827575977235103104847368754689754720329382142627108882164642140768775016478179380366695382520008383095848532521930405358232646114695494383241366145651188440368307287111495552004475154269836050543588580181088681136438760452956902516502218922299785695909716583660334898109530985544093303113936983845962257477613846013387047985121910005480321268621195236709378225161923355920272534358550
p = 153305387463348037357487373035059049858328853159142649103487512945187364968009787569616241281858216580389833745138207790411915561161286910364146345998580015250170791603381228114031585408080948659270513906658361657599207575631357250809353341546820477160639377447173754631313358720551110151520459451675836094943
e = 65537
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

已知p*q和(p^_q)

_q就是把q的二进制逆序

1
2
3
4
5
6
7
8
爆破思路：
1，两端开始，中间结束
2，当前p^q的值代表p的高位和q的低位异或
3，如果但前最高位为1，那么存在两种可能，p的高位为1，q的低位为0；p的高位为0，q的低位为1
如何剪枝：
1，将p，q未搜索的位数全填0，乘积小于n
2，将p，q未搜索的位数全填1，乘积大于n
3，p和q第k位相乘再去低k位，应与n的低k位相同

题目

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

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = bytes_to_long(flag.encode())
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)

代码

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
from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

pxorq = 51287709736576888935481948699419684645077512911004452954544449353000129825666
n = 7549646524692891529379305444522565345198070517965170637491013434396002300135441956108140101868033449923161114018585691925018270576670312096298867739915267
c = 2994980847727693507040660553883783304256037103745623354848049342746834808142159707589916983618996144073142775906508542462612795063698492450131178963281968
e = 65537
pxorq = str(bin(pxorq)[2:]).zfill(256)
 
def find(ph,qh,pl,ql):
    l = len(ph)
    tmp0 = ph + (256-2*l)*"0" + pl
    tmp1 = ph + (256-2*l)*"1" + pl
    tmq0 = qh + (256-2*l)*"0" + ql
    tmq1 = qh + (256-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(int(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")

学习参考

关联爆破-RSA分解-CSDN博客

Crypto趣题-剪枝 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

2023-鹏城杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

鹏城杯Crypto WP - Zhevitz的笔记小站