1.引言

可以毫不夸张地说，学习Coppersmith’s Attack的师傅们90%+是刷题刷到了强网杯2019的Copperstudy，本小师傅也不例外，借此机会好好study（研究）下Coppersmith叭~

2.原理分析

Coppersmith攻击，如wiki所指，大致有以下方式：低指数攻击；Coppersmith方法；Håstad 的广播攻击；Franklin-Reiter相关消息攻击 ；Coppersmith 的短填充攻击。

低公共指数攻击(Low public exponent attack)：为减少签名验证时间会选取很小的e，容易恢复d（非完全破解）。如果公共指数很小并且明文 m很短，那么 RSA 函数可能很容易反转，这使得某些攻击成为可能。

Coppersmith方法(Coppersmith method)：有整数N且 f ∈ Z[x] 是一个度数为d的单项多项式。对某些k ≥ 0，令 X = N 1/d −k ，那么 给定 （N,f）, Marvin（攻击者） 可以很容易找出所有证书 |x0| < X 满足f (x0) = 0 （mod N)。运行时间由在维度为O(w)的网格上运行LLL算法所需的时间主导，w=min(1/k, log2> N)。

Håstad 的广播攻击(Håstad’s broadcast attack)：在加密前对M进行线性填充并不能防止这种攻击。假设攻击者得知对于1<=i<=k和一些线性函数fi，i.e.,即Bob在加密前对信息M进行了一个填充，这样收件人就会收到略有不同的信息。例如，如果M是m比特长，Bob可能会加密并将其发送给第i个收件人。

Franklin–Reiter相关消息攻击(Franklin–Reiter related-message attack)：如果两个信息之间只存在已知的固定差异，并且在相同的RSA模数N下进行RSA加密，那么就有可能恢复这两个信息。这种攻击最初是在公共指数e=3的情况下描述的，但它更普遍地起作用（随着e的增长，成本增加）。

Coppersmith 的短填充攻击(Coppersmith’s short-pad attack):与Håstad和Franklin-Reiter的攻击一样，这种攻击利用了公共指数e=3的RSA的一个弱点。Coppersmith表明，如果Håstad建议的随机填充被不当使用，那么RSA加密是不安全的。

需要看具体更深层原理的大佬可以移步文末：二十年以来对 RSA 密码系统攻击综述，原文Twenty Years of Attacks on the RSA Cryptosystem。再给一个介绍 LLL（Lenstra–Lenstra–Lovász 格基约简）算法的传送门。

3.例题

言归正传，出来吧强网杯2019 Copperstudy!

原题可以上github拉一下强网杯2019 Copperstudy;buu稍作改动后，本题有7关：level0-6，打通level 6会给出flag。

3.1 level 0

3.1.1 题目

[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=235b85c0695a9d824064d887285b462c6e5bf11eb1521b24fcb72b320aa13ed1
[+]skr[0:5].encode('hex')=88d6b371c4
[-]skr.encode('hex')=

3.1.2 解析

对hashdump即可

from Crypto.Util.number import *
import hashlib

for i in range(10000,20000000):
    tar = 0x88d6b371c4
    payload = long_to_bytes(i)
    payload = long_to_bytes(tar) + payload
    if hashlib.sha256(payload).hexdigest() == '235b85c0695a9d824064d887285b462c6e5bf11eb1521b24fcb72b320aa13ed1' :
        print(str(hex(tar))+str(hex(i))[2:])
        break

3.2 level 1

3.2.1题目

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

3.2.2 解析

直接求三次方的根：

from Crypto.Util.number import *
import gmpy2
c=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
m = gmpy2.iroot(c,3)[0]
#print(long_to_bytes(m))
print (hex(m))

3.3 level 2

3.3.1题目

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

3.3.2 解析

知道了n，e，c以及p高位，还原p进而求出q、d、m即可。核心是SageMath求小根x0可解。

#Sagemath

n = 
p4 = 
#全位p的pbits与缺省p的kbits
pbits = 1024      
kbits = pbits - p4.nbits()
print (“the bits of p4 is:", p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
#求一个小根x0
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]

3.4 level 3

3.4.1题目

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

3.4.2 解析

已知：n、m为512位、c、d的低位512位。

知道d的低位可以通过简单推导（从e∗d=kϕ(n)+1消元q得到p关于d、e、k的表达式，且k<e）求出p的低位，进而用level 2求出p，之后便是有手就能做啦.

#Sagemath
def recover_p(p0, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    p0bits = p0.nbits()
    d0bits = d0.nbits()
    f = 2^p0bits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-p0bits), beta=0.4)  
    if roots:
        x0 = roots[0]
        p = gcd(2^d0bits*x0 + p0, n)
        return ZZ(p)

    
def find_p0(d0, e, n):
    X = var('X')
    for k in range(1, e+1):
        results = solve_mod([e*d0*X == k*n*X + k*X + X-k*X**2 - k*n], 2^d0.nbits())
        for x in results:
            p0 = ZZ(x[0])
            p = recover_p(p0, n)
            if p and p != 1:
                return p

n = 
e = 
c = 
d0 = 
p = int(find_p0(d0, e, n))
q = n//int(p)

3.5 level 4

3.5.1题目

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

3.5.2 解析

有三组n与c，广播攻击即可。

from gmpy2 import *
from functools import reduce


n1=
n2=
n3=

c1=
c2=
c3=

def CRT(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 * invert(p, n_i) * p
    return int(sum % prod)

    
print(hex(iroot(CRT([n1,n2,n3],[c1,c2,c3]),3)[0]))

3.6 level 5

3.6.1题目

[+]Generating challenge 5


  [+]n= 113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061


[+]e=7


[+]m=random.getrandbits(512)


[+]c=pow(m,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308


[+]x=pow(m+1,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175

3.6.2 解析

解法不止一种，可以看成是求多项式下的GCD，（f1(x)=a1x+b1,f2(x)=a2x+b2，其中a1=a2=1,b1=0,b2=1）

#sagemath
def franklinReiter(n,e,b,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X + b)^e - c2
    m_ = GCD(f1,f2).coefficients()[0] 
    # 返回的是首一多项式，coefficients()返回多项式各项式的系数，项式次数递增，所以第0项是常数 
    return Integer(n - m_) 
# 由于tmp其实是 -m % n,所以这里给他转换回去。

def GCD(a, b):
    if(b == 0):
        return a.monic()        
    # 返回首一多项式，即多项式最高次的项式系数为1
    else:
        return GCD(b, a % b)
e = 
n = 
b = 
c1 = 
c2 = 
M = franklinReiter(n,e,b,c1,c2)
print(hex(M))

3.7 level 6

3.7.1题目

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

3.7.2 解析

可以看出:

1)与以往不同的是e足够大（无法求低次根）

2)n为1024位二进制数，而d=random.getrandbits(1024*0.270)，即d<N0.292

3）涉及多元coppersmith’s method，而‘Coppersmith’s algorithm uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to construct the polynomial f with small coefficients’（Coppersmith method使用LLL攻击），github传送门：https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage。将指数改一改带入SageMath

whenever delta < 1 - sqrt(2)/2 ~ 0.292

4.参考链接

https://paper.seebug.org/727/与https://www.ams.org/notices/199902/boneh.pdf（二十年以来对 RSA 密码系统攻击综述中文尽力翻译版/英文原版）

https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage（github boneh_durfee SageMath版）

https://en.wikipedia.org/wiki/Coppersmith%27s_attack与https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm（维基百科Coppersmith’s attack、LLL算法）

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch19.pdf（paper：Coppersmith’s Method和相关应用）

https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf（paper：Coppersmith’s Attack）

https://github.com/851579181/qiangwangbei_2019_crypto_copperstudy（强网杯copperstudy环境）

https://jayxv.github.io/2020/08/13/%E5%AF%86%E7%A0%81%E5%AD%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E4%B9%8Bcoppersmith/（Van1sh师傅Coppersmith学习笔记）

https://blog.csdn.net/walker_feng/article/details/108889696（walker_feng师傅解题笔记）

原文始发于微信公众号（瑞不可当）：Coppersmith’s Attack