Coppersmith例题

  1. part0
  2. part1
  3. part2
  4. part3
  5. part4
  6. part5
  7. part6
  8. 总结

找几道例题加深下印象(当我没说)。

没环境,找了个师傅贴的例子。

part0

[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=b9f5a36134ba3b3b9a41c3ee519899f39fd85f231d9cb2d6c34415fcebe0aa8c
[+]skr[0:5].encode('hex')=13a03f1f32
[-]skr.encode('hex')=

方法解释:os.urandom(i),随机的8bytes长度的数据,每个字节在chr(0-255)之间,是可见的字符就直接打印,不可见就转位\xXY形式,XY范围:00-ff。

a = 0x13a03f1f32
print(long_to_bytes(a))
#b'\x13\xa0?\x1f2'
#a[0] = b'\x13' a[1] = b'\xa0' a[2] = b'?' a[3] = b'\x1f' a[4] = b'2' 
#长度是5

hash解密,随机的8字节skr,给出了前5位,爆破后三位即可。

hashcat还没用过,先记下方法:

hashcat64.exe -a 3 --hex-salt -m 1420 b9f5a36134ba3b3b9a41c3ee519899f39fd85f231d9cb2d6c34415fcebe0aa8c:13a03f1f32 --potfile-disable ?b?b?b  -o res3.txt --outfile-format=2 --force

或者用代码(参考https://www.ruanx.net/coppersmith/):

def phase1(pre, target):
    pre = codecs.decode(pre.encode(), 'hex')
    for x in itertools.product(range(256), repeat=3):
        skr = pre + b''.join([t.to_bytes(1, 'big') for t in x])
        if hashlib.sha256(skr).hexdigest() == target:
            print(f'find {skr}')
            return codecs.encode(skr, 'hex').decode()

phase1('13a03f1f32', 'b9f5a36134ba3b3b9a41c3ee519899f39fd85f231d9cb2d6c34415fcebe0aa8c')

a = b'\x13\xa0?\x1f2\x1b\xdb\x17'
print(hex(bytes_to_long(a)))
#find b'\x13\xa0?\x1f2\x1b\xdb\x17'
#0x13a03f1f321bdb17

part1

[+]Generating challenge 1
[+]n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211 
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
[+]((m>>72)<<72)=2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736
[-]long_to_bytes(m).encode('hex')=

已知m的高440位,直接求解:

#Sage
n = ...
e = ...
c = ...
mbar = ...
kbits = 72
beta = 1
nbits = 2047
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]
print("m:", mbar + x0)

当然e=3,其实也满足了低指数解密攻击,直接开方就能解出来,我这里是为了熟悉下脚本的用法。

part2

[+]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')=

已知p的高位,求低128位,因为n有2047位,所以p大致有1000多位,所满足条件,直接求解:

n = ...

e = 65537
p4 =...

kbits = 128

PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
p = p4+int(roots[0])
print(n)
print(p)
print(n//p)

求出来p、q、n后就是常规求解了,不多bb。

part3

[+]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')=

注意这里d&((1<<512)-1),实质是低位保持不变,高位与0进行与运算。即已知d的低位攻击。知道了d的低512位。直接解:

#sage
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.4)
    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 and p != 1:
                return p

n =...
e = 3
c =...

d0 =...
beta = 0.5
nbits = 1024
kbits = 508
p = int(find_p(d0, kbits, e, n))
q = n//int(p)
print(inverse_mod(e, (p-1)*(q-1)))

d解出来了后就是常规RSA解密了,不多bb。

part4

[+]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')=

三队c、n,一眼广播攻击,用中国剩余定理解即可。

n1 = ...
n2 = ...
n3 = ...
c1 = ...
c2 = ...
c3 = ...
e = 3

n = [n1, n2, n3]
c = [c1, c2, c3]


def CRT(a, n):
    sum = 0
    N = reduce(lambda x, y: x * y, n)

    for n_i, a_i in zip(n, a):
        N_i = N // n_i
        sum += a_i * N_i * invert(N_i, n_i)
    return sum % N


x = CRT(c, n)

m = iroot(x, e)[0]
print(long_to_bytes(m))

part5

[+]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')=

m高位相同,为短填充攻击Coppersmith Shortpad Attack(Franklin-Reiter攻击),需要补充,直接解:

n = ...
c1 = ...
c2 = ...
e = 3

# c1 = m^e
# c2 = (m+1)^e

R.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+1)^e - c2

def myGcd(x, y):
    if y == 0:
        return x.monic()
    return myGcd(y, x%y)

v = myGcd(g2, g1)
m = n - v.coefficients()[0]

assert g1(m) == 0
print(m)

part6

[+]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')=

e很大,d<N的0.292次方,Boneh Durfee 攻击,需要补充,脚本不是一般的长,改来改去我还运行不了。。。累了。贴上佬的博客。

参考:

https://www.ruanx.net/coppersmith/

[强网杯2019 Copperstudy_无名函数的博客-CSDN博客](https://blog.csdn.net/m0_57291352/article/details/119685392?ops_request_misc=%7B%22request%5Fid%22%3A%22168293153416800188536549%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168293153416800188536549&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119685392-null-null.142^v86^control_2,239^v2^insert_chatgpt&utm_term=强网杯2019 Copperstudy&spm=1018.2226.3001.4187)

[BUUCTF 强网杯2019 Copperstudy_walker_feng的博客-CSDN博客](https://blog.csdn.net/walker_feng/article/details/108889696?ops_request_misc=&request_id=&biz_id=102&utm_term=强网杯2019 Copperstudy&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-3-108889696.142^v86^control_2,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)

总结

收获满满(麻了😃😥),本来说找几道coppersmith的题练一下,没想到找的第一道就给我累够呛,所以下次再来。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 1666739907@qq.com
github