密码学 Coppersmith’s Attack

admin 2023年3月7日10:37:32评论107 views字数 11634阅读38分46秒阅读模式

rsa中的常考

Coppersmith定理指出在一个e阶的mod n多项式f(x)中,如果有一个根小于,就可以运用一个O(log n)的算法求出这些根。

p高位泄露

已知位数 > 0.7p

from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b"flag{}"
 
def enc(m):
    return pow(m, e, N)
 
if __name__ == "__main__":    
    l = 256
    p = getPrime(1024)
    N = p * getPrime(1024)
    e = 65537
    a = (p >> l) << l
    print("N:", N)
    print("Known part of p:", hex(a))
    print("Length of the unknown part:", l)
    print("enc:", enc(bytes_to_long(FLAG)))
 
 

exp

from sage.all import *
n = 13139369168613206469808493070119137888363636548621629780897948879328793540933675072448361493321304924953815474270401406259487525517560528123707016104942485164559271692275987380567766009184969340122208041180122234792566147648471202470677782205185423853314467362074540818483729953544353584322270414479260852672948012862257167187569701381652931473637503302338392147780573148724508117699531886205586281824118899931516823621049590863613262210219765105389989391065557707559113268724368695051264276619633555407916385088611885715568165460641318205321508100969473959719364829756492542217470309748646183210141490634293731384313
p4=0xce2f93251a3a97404a11c1fe88cf15c7aaf26ffd508ff006933bff2e9ea0c6197a98f1188f03b74b16d564e958a84c877fc0e21faf00f0ae42f26bde226ebf7c9732f17d860b81d139799832d510b91001967fc33ff2d9fbd4c4767fa2438e48
e = 0x10001
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:        
    p = p4+int(roots[0])
    print ("n: ", n)   
    print ("p: ", p)
    print ("q: ", n/p)

自写的爆破位数较少的(10bit以内)的exp

import tqdm
n = 118339635751866021565280669234331146291314924611745778946802409595225221719520855255713041472108556128541954342138036763115305132953076410434992832307615179905939072008718458536821260979054625184581509607088465131477587130373615309290521085447957844416682382115910074004563371507680498021010867069751097982169

def high_p(p4):
    kbits = 226
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    roots = f.small_roots(X=2^kbits,  beta=0.4)

    if roots:
        p = p4+int(roots[0])
        print ("n: ", n)
        print ("p: ", p)
        print ("q: ", n/p)

        exit(0)
for ii in tqdm.trange(2**27):
#     缺的位数要算一下,虽然我忘了怎么用了
    p4= int((bin(651765341461649537508951120051394121450462113650811358797688266083913388699042) + "{:027b}".format(ii)),2)
    high_p(p4)

m高位泄露

如果e = 3并且在明文当中只有三分之二的比特是已知的,这种算法可以求出明文中所有的比特。

n=0x2519834a6cc3bf25d078caefc5358e41c726a7a56270e425e21515d1b195b248b82f4189a0b621694586bb254e27010ee4376a849bb373e5e3f2eb622e3e7804d18ddb897463f3516b431e7fc65ec41c42edf736d5940c3139d1e374aed1fc3b70737125e1f540b541a9c671f4bf0ded798d727211116eb8b86cdd6a29aefcc7
e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0x1f6f6a8e61f7b5ad8bef738f4376a96724192d8da1e3689dec7ce5d1df615e0910803317f9bafb6671ffe722e0292ce76cca399f2af1952dd31a61b37019da9cf27f82c3ecd4befc03c557efe1a5a29f9bb73c0239f62ed951955718ac0eaa3f60a4c415ef064ea33bbd61abe127c6fc808c0edb034c52c45bd20a219317fb75
((m>>72)<<72)=0xb11ffc4ce423c77035280f1c575696327901daac8a83c057c453973ee5f4e508455648886441c0f3393fe4c922ef1c3a6249c12d21a000000000000000000

exp

n = 0x2519834a6cc3bf25d078caefc5358e41c726a7a56270e425e21515d1b195b248b82f4189a0b621694586bb254e27010ee4376a849bb373e5e3f2eb622e3e7804d18ddb897463f3516b431e7fc65ec41c42edf736d5940c3139d1e374aed1fc3b70737125e1f540b541a9c671f4bf0ded798d727211116eb8b86cdd6a29aefcc7
e = 3
m = randrange(n)
c = pow(m, e, n)
beta = 1
epsilon = beta^2/7
nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
 
mbar = 0xb11ffc4ce423c77035280f1c575696327901daac8a83c057c453973ee5f4e508455648886441c0f3393fe4c922ef1c3a6249c12d21a000000000000000000
c = 0x1f6f6a8e61f7b5ad8bef738f4376a96724192d8da1e3689dec7ce5d1df615e0910803317f9bafb6671ffe722e0292ce76cca399f2af1952dd31a61b37019da9cf27f82c3ecd4befc03c557efe1a5a29f9bb73c0239f62ed951955718ac0eaa3f60a4c415ef064ea33bbd61abe127c6fc808c0edb034c52c45bd20a219317fb75
print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n1
print (mbar + x0)

短填充攻击 (short-pad attack)

e!=3时 用FranklinReiter

d低位泄露

已知私钥d的512位的低位,Partial Key Exposure Attack

n=0xd463feb999c9292e25acd7f98d49a13413df2c4e74820136e739281bb394a73f2d1e6b53066932f50a73310360e5a5c622507d8662dadaef860b3266222129fd645eb74a0207af9bd79a9794f4bd21f32841ce9e1700b0b049cfadb760993fcfc7c65eca63904aa197df306cad8720b1b228484629cf967d808c13f6caef94a9L
e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0xcaeeb38516d642a19550fa863173f4695c3b44bd5a5554b1e93cfb690d5c1de531b7f1187f7d8c8c11da38af025f19d393033d0ca801e15d6d8441098485f13ab988d09ef1f4f5a735e19780c823cf77415884c33a1f7908cf4229874c082eb7ceb776bafb182b86fdabd29b07bcb8e3f2f50ee4cc0f323e8d9ce320139bcd27L
d=invmod(e,(p-1)*(q-1))
d&((1<<512)-1)=0x603d033f2ef6c759aec839f132a45215fc8a635b757f3951a731fe60bc6729b3bcf819b57abfcaba3a93e9edef766c0d499cad3f7adb306bcf1645cfb63400e3L
long_to_bytes(m).encode('hex')=???

exp

def partial_p(p0, kbits, 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 = 0xd463feb999c9292e25acd7f98d49a13413df2c4e74820136e739281bb394a73f2d1e6b53066932f50a73310360e5a5c622507d8662dadaef860b3266222129fd645eb74a0207af9bd79a9794f4bd21f32841ce9e1700b0b049cfadb760993fcfc7c65eca63904aa197df306cad8720b1b228484629cf967d808c13f6caef94a9
    e = 3
    d = 0x603d033f2ef6c759aec839f132a45215fc8a635b757f3951a731fe60bc6729b3bcf819b57abfcaba3a93e9edef766c0d499cad3f7adb306bcf1645cfb63400e3
    beta = 0.5
    low_p = dbb9478d0b64086091aac64efd51eb37b5067feb380995d39a917c0c927b26902f06dc449b53d80cd59c5d912fb5a5f45b223278919ae1ce449f4db7afbc252f16247129ea68dc6011093da6b11356591a9e8c0e10057e9d733712a6e0caafc462e9b2d07fb2aa3a451403a7f8
    n = 02077c66e48a6fc80ce744f16b87e237ddd9a4efb4ffa2f9f89d09af382dddfc259dbf932728c23757957638f3ec9327fc0eaf3fd5d72b91c714798ca1459dfdf6c7505eb6e39f26624431239b6daa7bbaa6c5aad3dc3bf6b377923781ab5c221c195115d39c477c0561d5c769c175
    T = inverse_mod(2^570,n)
    def phase(low_p, n, T):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = low_p*T + x
    x0 = p.small_roots(X = 2^(1024-570), beta = 0.4)[0]
    P = x0*2^570+low_p
    print P
    phase(low_p, n, T)
    data = data + [(msg, n)]
    print ("Please wait, performing CRT")
    x, n = chinese_remainder_theorem(data)
    e=session['e']
    realnum = gmpy.mpz(x).root(e)[0].digits()
    print (my_parse_number(int(realnum)).encode("UTF-8").hex())

Boneh and Durfee attack

当 d 较小时,满足  时,我们可以利用该攻击,比 Wiener's Attack 要强一些

(Wiener's Attack的应用范围是)

exp

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

特殊玩法

p高位泄露,但是 leak

hgame2023 week3

from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
N = p*q
leak = p >> 253

print("N =",N)
print("leak =",leak)
密码学 Coppersmith’s Attack

所以我们想让这⾥的临界值X变⼤,就需要增⼤格的维度。coppersmith有个参数epsilon可以⽤来调整 格的⼤⼩

密码学 Coppersmith’s Attack

这边的参数试着大概只支持247~253bit

from tqdm import trange

N = 51471058562789669584563923668230049987327557749731419227080649737596352929196876065322449843154647912172897240553256601219377833812105653648319010805903588280374669203130950549551864116334593597406581198865513502191466098466416839551885822431896220657842707834576452321460066523621329965842288825805727487769
leak = 31204473258488385544848241191027314972203372468745266339527331830701679342098249

shift_bits = 247
PR = PolynomialRing(Zmod(N),'x')
x=PR.gen()
for t in trange(2**5):
    f = ((leak*2**5) + t)*2**(shift_bits-5) + x
    roots = f.small_roots(X=2**(shift_bits-5), beta=0.4, epsilon=0.01)
    if len(roots):
        p = int(f(x=roots[0]))
        if not N % int(p):
            q=N//p
            print("p=",p)
            print("q=",q)
            break

p高位泄露,低位有noise

高位如果知道的多,可以直接用上面的方法攻击

NSSCTF Round7 裁雨留虹

这题受到噪声影响的范围比较小,可以用高位攻击直接做

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = next_prime(p ^ (1 << 512) - 1 ^ bytes_to_long(b'Xennymeiyouxiaojiji'))

n = p * q
c = powmod(m, e, n)

print('n =', n)
print('c =', c)

exp


#sage
from Crypto.Util.number import *
from gmpy2 import *

c = 15546188685670270989199906044558574433366484290772391354882078554084743654222571393831055720952863349992616432152309914545326592443467398289132671762720854032834488065822184124339213419923974351212825007090162081761199122047243460841337179292197550846513590989342399182349179744028434042728937799656895558765
n = 24848763781294960312192846136593590839603690645254602686502190289505392664651874312309233278973019021742369830474864145937527929626247195281541664177986962295793555679916810745356107658949311600978190764721093243821973785651000172711701812600677626207685056517809830973646884066946140459319936104649144209423
e=65537
 
#estimate p
px=(gmpy2.iroot(pow(2,1024)-4*n,2)[0]+pow(2,512))//2+ bytes_to_long(b'Xennymeiyouxiaojiji')
print(px)
p=int(px)
 
P.<x>=PolynomialRing(Zmod(n))  
for i in range(100,1000):
    f=x+ZZ(((p>>i)<<i))     
    root=f.small_roots(X=2^i,beta=0.4)
    if root!=[]:
        print(i)
        p=root[0]+ZZ(((p>>i)<<i))
        break
print(p)
 
q=ZZ(n)//ZZ(p)
print(q)


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

print(long_to_bytes(m))

NSSCTF Round7 织诗成锦

https://www.cnblogs.com/App1eTree/#/c/subject/p/17070788.html

这个的noise变得很大

不能用直接攻击低位的方法了

用dfs深搜的方法来算

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)

poem = '''爱得痛了
痛得哭了
哭的累了矛盾心理总是强求'''


q = next_prime(p ^ (1 << 512) - 1 ^ bytes_to_long(poem.encode('utf-8')))
n = p * q
c = powmod(m, e, n)


print('n =', n)
print('c =', c)

from Crypto.Util.number import *
import gmpy2
n=9917194039107056112184040918942991087006948095942990759083653963386347099537872574166056046291870369660144747910297948865119742599237172372299988293988091347394105128159638670279156137176691709760735170161276067729520093855522898374683007605621773716069049053067108582990968946937131419271617984877669716809
e=65537
c=7587789694070748707348883888501708440754567305328311759140303893816709636596826176623331039561461438614968853491941771170730448862622628116994823624292597456598154540152890431881836541630974352792727975698270205577342357896211852053562431611816629189278379946359321494584849773739040563488839129619217040844

p=((1<<512)-1)^^((1<<151)-1)
q=0
for i in range(510,150,-1):
        bit=1<<i
        if (p^^bit)*(q^^bit)<n:
                p^^=bit
                q^^=bit
 
P.<x>=PolynomialRing(Zmod(n))
for i in range(150,230):
    f=x+ZZ(((p>>i)<<i))
    root=f.small_roots(X=2^i,beta=0.4)
    if root!=[]:
        p=root[0]+ZZ(((p>>i)<<i))
        break
 
q=ZZ(n)//ZZ(p)
phi=ZZ((p-1)*(q-1))
d=gmpy2.invert(e,phi)
flag=ZZ(pow(c,d,n))
print(long_to_bytes(flag))
#NSSCTF{e75a2dbf-8581-49bf-a125-383cca7fd377}

参考文章

密码学学习笔记 之 Coppersmith’s Method | Van1sh的小屋 
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/

ctfwiki
Coppersmith 相关攻击 
https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_coppersmith_attack/

知乎专栏 
https://zhuanlan.zhihu.com/p/525677071

GitHub攻击脚本合集 
https://github.com/mimoo/RSA-and-LLL-attacks/

2023冬 密码学趣题——3 
https://www.cnblogs.com/App1eTree/#/c/subject/p/17077107.html

- END -


网络安全社团公众号

微信号 : qlnu_ctf

新浪微博:齐鲁师范学院网络安全社团

密码学 Coppersmith’s Attack

原文始发于微信公众号(齐鲁师院网络安全社团):密码学 Coppersmith’s Attack

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年3月7日10:37:32
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   密码学 Coppersmith’s Attackhttps://cn-sec.com/archives/1590789.html

发表评论

匿名网友 填写信息