Coppersmith

一、Introduction

Coppersmith定理在RSA中多有应用，最多的就是，

高位攻击一类的

Coppersmith 可以用于求多项式的小根，经常用于 RSA 攻击中“已知某些二进制位，求剩余位”这一类问题。

二、Deduction

Coppersmith干了这么一件事：现有一个阶的多项式，那么可以：

在模意义下,快速求出以内的根
给定，快速求出模某个意义下较小的根，其中，是的因数。

一般采用Sage实现的small_root方法

三、Problem

1. hash爆破

proof: skr=os.urandom(8)
hashlib.sha256(skr).hexdigest()=246bfcbe8c7b0be0a3ee28840a276272ba4416cb650affd846e9f7f2db2820a9
skr[0:5].encode('hex')=c2183d3580
skr.encode('hex')=

　给出了 skr 的前 5 位，需要找到正确的 skr 使得其 sha256 为给定值。显然直接爆破后三位就行。

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('c2183d3580', '246bfcbe8c7b0be0a3ee28840a276272ba4416cb650affd846e9f7f2db2820a9')

# find b'\xc2\x18=5\x80\x14Q9'
# 'c2183d3580145139'

2. 已知明文高位，求低位

n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211

e=3

m=random.getrandbits(512)

c=pow(m,e,n)=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517

((m>>72<<72)=2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

long_to_bytes(m).encode('hex')=

这里给出了的高位440位，我们只需要推断出剩余发低位–72位即可。记真实的为，则

这个方程的根很小，可以直接求解。

def phase2(high_m, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    m = high_m + x
    M = m((m^3 - c).small_roots()[0])
    print(hex(int(M))[2:])

n = 13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211
c = 15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
high_m = 2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

phase2(high_m, n, c)
# 464c41477b325e3872736137353839363933666336383963373763356635323632643635343237323432377d

3. 广播攻击

CRT的应用场景

模数n、密文c不同，明文m、加密指数e相同。一般会是e=k，然后给k组数据
使用不同的模数n，相同的公钥指数e加密相同的信息。就会得到多个(m^e) ==ci (mod ni)，将(m^e)视为一个整体M，这就是典型的中国剩余定理适用情况。按照中国剩余定理容易求得m^e的值，当e较小时直接开e方即可，可使用gmpy2.iroot(M,e)方法。

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，直接通过中国剩余定理得到的确切值，开根号即可。

def phase5(n1, c1, n2, c2, n3, c3):
    r = CRT([c1, c2, c3], [n1, n2, n3])
    m = int(r)^(1/3)
    print(hex(m)[2:])
    
n1 = 78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
c1 = 23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
n2 = 98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
c2 = 72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
n3 = 91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
c3 = 22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616

phase5(n1,c1,n2,c2,n3,c3)
# 464c41477b325e3872736138633566336366663462633039353334396665633635666332323633653837387d

Coppersmith-Study