BUUCTF 强网杯2019 Copperstudy
程序员文章站
2022-05-11 20:29:48
...
强网杯2019 Copperstudy
做之前很爽，做之后更爽
前提说明：百度的wp没看到第0题以为没wp然后饱受摧残做到最后，特写此文纪念下
惨遭社会毒打的我
打开题目：
nc ip port
我做的时候直接用的复现，也就是那个GitHub链接(关键坑比的地方就在这里，等碰到的时候再说
第0题
[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=9987a7715e30a05b29c1fae9c8647fb2a1046589e8fe9b684e75754f86d26c79
[+]skr[0:5].encode('hex')=2127654d44
[-]skr.encode('hex')=
好家伙，第一题直接一波劝退，我当时看到人傻了，先看下代码
import os
os.urandom(i) #基于系统生成长度为i随机byte字节的数据
他给出了m的0-5的数据
[+]skr[0:5].encode('hex')=f708e349be
直接解密，传统艺能导入
from Crypto.Util.number import *
m = long_to_bytes(0xf708e349be)
print(m) #b'\xf7\x08\xe3I\xbe'
一看这怎么不像5长度的样子，开始进入蒙蔽状态，测试
>>>a = os.random(8)#b'\x00p\xaf\xbf\xf6\xc1\x10\xe9'
>>>a[0]
\x00
>>>a[1]
p
>>>a[2]
\xbf
...
测了半天，发现他os.urandom出来的数据就是0-255的chr值，可见字符他就转换，不可见他就变成\xXY的形式，其中XY的范围是00-ff。
发现这个规律之后我立马来了思路，这不就是穷举法嘛，已经给出了5个长度的数据，也就是说剩下的3个数据的组合最多有256^3种可能性，虽然感觉数据量大，但对于现代计算机这点复杂度更本不算什么
然后我这样做了，然后我没做出来…
后来想想这是第0题啊，太丢脸了，然后又莽上去了
测试了下长度为3的数据
from Crypto.Util.number import *
import os
test = []
for i in range(1000):
test.append(bytes_to_long(os.urandom(3)))
print(max(test))
print(min(test))
结果
一看觉得可能会有区间可循，因为想到本来他这个随机性很强，不如试试long_to_bytes的**，我出于小心，选择最低1w，最高2000w的区间，并且十分相信我的电脑
from Crypto.Util.number import *
import hashlib
for i in range(10000,20000000):
tar = 0x48dac257f3
payload = long_to_bytes(i)
payload = long_to_bytes(tar) + payload
if hashlib.sha256(payload).hexdigest() == '0b8debba71632360431d3c0a35395686c0ddfe4142ae4e068b5ec6d36b8dcfd1' :
print(i)
break
还真打出来了
这里跑到511w只花了1分多钟，时间还算合理的趴
然后只要把跑出来的数据hex拼接到前面给出的5个数据后面前面加个0x就行了
注意：每次系统的urandom值不同，每次刷新都要重跑
第1题
总算到了第一题，拿到题目[+]Generating challenge 1
[+]n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
[+]((m>>72)<<72)=2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736
拿到题目我先努力保持冷静
好，开始看题
先测个位数，好家伙，一看2047位，e=3，这波问题很大，m是512位的random数据，测下
懂得都懂,老懂哥了
from Crypto.Util.number import *
import gmpy2
c=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
m = gmpy2.iroot(c,3)[0]
print(long_to_bytes(m))
唯一疑惑的就是最后的m给了不知道一个啥玩意，反正做出来就不管了
第2题
[+]Generating challenge 2
[+]n=12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219
[+]e=65537
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778
[+]((p>>128)<<128)=97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672
[-]long_to_bytes(m).encode('hex')=
第一眼进来就看了e, 65537 …
继续看，n,e,c,还有一个p，看样子是本题的突破口了
有一说一，确实是这样的
((p>>128)<<128)=97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672
也只能来看看这是什么jb玩意，我拿了几个数据测试了一下，发现自己原来进制运算还不是很熟，这里的运算时<< >>位移运算，也就是p右移128位再左移128位，右移直接吞左移不足位补零
也就是说这里给出p的最后128位去除补0并转换为10进制的值
明白的人已经在百度了
已知p的高位攻击，payload:
//sage
//p4已知高位
p4 = 286593827663265980875510954967316219073448170030900062579915534986706486906458307884391633081975974889868808093084141196610789229262338742207816117361927894904776552676541036673244090334164798443162932914355966770450894047111793505063044583029134192122352988382684883337
n = 12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219
//全位数
pbits = 1024
缺省位数
kbits = pbits - p4.nbits()
print (p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print ("x:" ,hex(int(x0)))
p = p4+x0
print ("p: ", hex(int(p)))
assert n % p == 0
q = n/int(p)
print ("q: ", hex(int(q)))
注意：payload里的p是去过位数的值，也就是上面的p要>>128放入payload中
解出来p,q 然后有手就行，就不写了
第3题
[+]Generating challenge 3
[+]n=92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530
[+]d&((1<<512)-1)=787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955
[-]long_to_bytes(m).encode('hex')=
好，那继续
e=3,看下数据
没事了，m还是512位的，pow3一下1.5k位以上了
然后正常的去看最后一个条件d&((1<<512)-1)
刚刚说过位移运算符了，这里
其实就是1的二进制变成1000…512个，根据2-》10进制转化原则可以得到上面的等式
&运算，好，按位与，同1否0，来看下刚刚的二进制值
全是1，按进制计算也可以得到，那么已经很明显了，这里d&((1<<512)-1)后的结果是d最后512位数据
已知d的低位，百度冲！
payload：
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)
def find_p(d0, kbits, e, n):
X = var('X')
for k in range(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p:
return p
if __name__ == '__main__':
n = 92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183
e = 3
d = 787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955
nbits = n.nbits()
kbits = d.nbits()
print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = find_p(d, kbits, e, n)
q = n//p
print ("d0 = %d" % d)
print ("d = %d" % inverse_mod(e, (p-1)*(q-1)))
当时拿到payload改了好长一段时间才出，太难了
d出来了我就不说了，有手就行
第4题
做了这么多才到第四题，丫的题目
[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
[+]c1=pow(m,e,n1)=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
[+]n2==98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
[+]c2=pow(m,e,n2)=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
[+]n3=91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
[+]c3=pow(m,e,n3)=22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616
[-]long_to_bytes(m).encode('hex')=
这种题目一看到这么多组n,c CRT中国剩余定理就可以直接上了
e还等于3
低加密指数广播攻击没跑了
payload：
import gmpy2
from functools import reduce
from Crypto.Util.number import *
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a * b, n)
for n_i, a_i in zip(n, a):
p = prod // n_i
sum += a_i * gmpy2.invert(p, n_i) * p
return int(sum % prod)
n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
c1=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
n2=98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
c2=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
n3=91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
c3=22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616
n=[n1,n2,n3]
c=[c1,c2,c3]
ans=chinese_remainder(n, c)
ans=gmpy2.iroot(ans,3)[0] # e = 3
print(long_to_bytes(ans))
第5题
题目[+]Generating challenge 5
[+]n= 113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061
[+]e=7
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308
[+]x=pow(m+1,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175
[-]long_to_bytes(m).encode('hex')=
好的，审题，e=7,没特征，看下bit位，没有
然后明显的关键点：
c=pow(m,e,n)
x=pow(m+1,e,n)
首先看密文c有没有突破点，虽然明文m^e地下就加了1变成了pow(m+1,e) , 看起来动了一位，但是通过计算可以发现，在高位下两个结果差了很多
然后分析m，第一个m和第二个只差了1，也就是明文高位相同
百度冲
payload：
# coppersmiths_short_pad_attack.sage
def short_pad_attack(c1, c2, e, n):
PRxy.<x,y> = PolynomialRing(Zmod(n))
PRx.<xn> = PolynomialRing(Zmod(n))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+y)^e - c2
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)
h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()
kbits = n.nbits()//(2*e*e)
diff = h.small_roots(X=2^kbits, beta=0.5)[0] # find root < 2^kbits with factor >= n^0.5
return diff
def related_message_attack(c1, c2, diff, e, n):
PRx.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+diff)^e - c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
if __name__ == '__main__':
n = 113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061
e = 7
# nbits = n.nbits()
# kbits = nbits//(2*e*e)
# print ("upper %d bits (of %d bits) is same" % (nbits-kbits, nbits))
# ^^ = bit-wise XOR
# http://doc.sagemath.org/html/en/faq/faq-usage.html#how-do-i-use-the-bitwise-xor-operator-in-sage
# m1 = randrange(2^nbits)
# m2 = m1 ^^ randrange(2^kbits)
# c1 = pow(m1, e, n)
# c2 = pow(m2, e, n)
c1 = 112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308
c2 = 112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175
diff = short_pad_attack(c1, c2, e, n)
print ("difference of two messages is %d" % diff)
print (m1)
m1 = related_message_attack(c1, c2, diff, e, n)
print (m1)
print (m2)
print (m1 + diff)
然后，那个给出的数据是错的，气死我了，估计实机上没问题，反正我很火的，我试了半天，反代数据才发现那玩意是错的数据，他的c 和 x+1其实是这个
c = 16404985139084147094704300764850430964980485772400565266054075398380588297033201409914512724255440373095027298869259036450071617770755361938461322132693877590521575670718076480353565935028734363256919872879837455527948173237810119579078252909879868459848240229599708133153841801633280283847680255816123323196
x = 92463268823628386526871956385934776043432833035349654252757452728405540022093349560058649691620353528569690982904353035470935543182784600771655097406007508218346417446808306197613168219068573563402315939576563452451487014381380516422829248470476887447827532913133023890886210295009811931573875721299817276803
把新数据带进去就对了
第6题
来了，flag！！！
题目
[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL
[-]long_to_bytes(m).encode('hex')=
丫的这玩意好像就没派上过用场
测了下位数…
这次真的只给了n,e,c，然后给了个e和d的生成方式，我在这卡了好久，最后发现真的只有位数信息，方程列了一堆算过来算过去还是一开始的方程，看看生成方式又是最普通的方程生成，d是276位的，e是1021位的
维纳攻击试试
emmmm…
想来想去和平常加密方式唯一的区别就在这了
d=random.getrandbits(1024*0.270) #生成1024*0.270d位数的随机数
这里的0.270和1024肯定有蹊跷
网上疯狂找了一波，最后直接在别人的仓库里找
看到了这个
没中文描述，直接看下源码
import time
############################################
# Config
##########################################
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print( nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print( a)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# level:0
# if no other vectors end up affected
# we remove it
if affected_vectors == 0:
print( "* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
print( "* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB
"""
Returns:
* 0,0 if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever delta < 1 - sqrt(2)/2 ~ 0.292
"""
# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ)
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX*YY + 1
# x-shifts
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()
# x-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()
# y-shifts (selected by Herrman and May)
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# y-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print( "failure")
return 0,0
# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus^mm)
# check if determinant is correctly bounded
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print( "We do not have det < bound. Solutions might not be found.")
print( "Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print( "size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print( "det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)
# LLL
if debug:
print( "optimizing basis of the lattice via LLL, this can take a long time")
BB = BB.LLL()
if debug:
print( "LLL is done!")
# transform vector i & j -> polynomials 1 & 2
if debug:
print( "looking for independent vectors in the lattice")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# resultant
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print( "found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print( "no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print( "Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
#
return solx, soly
def example():
############################################
# How To Use This Script
##########################################
#
# The problem to solve (edit the following values)
#
# the modulus
N = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27
# the public exponent
e = 0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bb
# the cipher
c = 0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866c
# N = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
# e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
# c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = .28 # this means that d < N^delta
#
# Lattice (tweak those values)
#
# you should tweak this (after a first run), (e.g. increment it until a solution is found)
m = 4 # size of the lattice (bigger the better/slower)
# you need to be a lattice master to tweak these
t = int((1-2*delta) * m) # optimization from Herrmann and May
X = 2*floor(N^delta) # this _might_ be too much
Y = floor(N^(1/2)) # correct if p, q are ~ same size
#
# Don't touch anything below
#
# Problem put in equation
P.<x,y> = PolynomialRing(ZZ)
A = int((N+1)/2)
pol = 1 + x * (A + y)
#
# Find the solutions!
#
# Checking bounds
if debug:
print( "=== checking values ===")
print( "* delta:", delta)
print( "* delta < 0.292", delta < 0.292)
print( "* size of e:", int(log(e)/log(2)))
print( "* size of N:", int(log(N)/log(2)))
print( "* m:", m, ", t:", t)
# boneh_durfee
if debug:
print( "=== running algorithm ===")
start_time = time.time()
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
# found a solution?
if solx > 0:
print( "=== solution found ===")
if False:
print( "x:", solx)
print( "y:", soly)
d = int(pol(solx, soly) / e)
m = pow(c,d,N)
print( '[-]d is ' + str(d))
print( '[-]m is: ' + str(m))
print( '[-]hex(m) is: ' + '{:x}'.format(int(m)))
else:
print( "[!]no solution was found!")
print( '[!]All Done!')
if debug:
print(("[!]Timer: %s s" % (time.time() - start_time)))
print( '[!]All Done!')
if __name__ == "__main__":
example()
直接看主函数，回溯上去看example
# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = .28 # this means that d < N^delta
旁边的注释可以看出来 d < n ^ delta ，题目里生成d是1024*0.27位的值 1024是位数，转换一下不也就是N的0.27次方嘛，N通过测试可以发现是1024位的
然后上面标注的上限正好是0.292 ， 0.27在之内，所以改成0.28满足条件
再看一下这里面的N,e,d 测一下size发现也都是高位，那这基本就是payload了
再看一下标题，Bone Durfee 攻击 ，又学到一手
好，到这里整道题目就做完了，其实回过头来可以发现我并没有深入原理分析，知道攻击方式后原理可以自己去网上找教程学习，我希望此文锻炼点在审计和发掘题目考点的能力，其实正真在应用层攻击时往往测试的就是个人平时经验的积累和payload的书写能力，最关键的是fuzz测试能力，能让自己在遇到新题型的时候能灵活处理和应对。
当然基础知识一定要打，不然就是真工具侠了
我的第一篇文章，虽然给人感觉就是在用别人的东西打，但是这一次经历还是挺有价值的