Crypto-RSA-公鑰攻擊小結
前言
本篇文章對一些常見的公鑰RSA攻擊進行小結,歡迎補充
e=1
當e只有1的時候,我們有
當c小於N的時候,c即m
題目如下
N=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd e=0x1 c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
此時只要
print libnum.n2s(c)
即可
Rabin演算法
滿足條件
e=2,且n可以被分解
(既然n可以被分解,為什麼不直接算d?因為不互素,沒法求逆元)
通解方法
我們有
此時計算兩個值
又因為 gcd(p,q)=1
那麼有
可以求出兩個y,然後再計算下列4值
小性質
計算指令碼
import gmpy2 import string from Crypto.PublicKey import RSA with open('pubkey.pem', 'r') as f: key = RSA.importKey(f) N = key.n e = key.e with open('flag.enc', 'r') as f: cipher = f.read().encode('hex') cipher = string.atoi(cipher, base=16) q = ...... p = ...... inv_p = gmpy2.invert(p, q) inv_q = gmpy2.invert(q, p) mp = pow(cipher, (p + 1) / 4, p) mq = pow(cipher, (q + 1) / 4, q) a = (inv_p * p * mq + inv_q * q * mp) % N b = N - int(a) c = (inv_p * p * mq - inv_q * q * mp) % N d = N - int(c) for i in (a, b, c, d): s = '%x' % i if len(s) % 2 != 0: s = '0' + s print s.decode('hex')
低指數攻擊
滿足條件
e很小,通常為3
通解方法
當e很小的時候,我們爆破k,開e次方即可得到m
計算指令碼
import gmpy import libnum from Crypto.Util import number import gmpy2 def getd(e,p,q): phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) % phi return d def getm(m): return int(m.encode('hex'), 16) c=.... n=.... e=3 i = 0 while 1: if (gmpy.root(c + i * n, 3)[1] == 1): m = gmpy.root(c + i * n, 3)[0] print libnum.n2s(m) break i = i + 1
低指數廣播攻擊
滿足條件
當有如下條件
我們有多組(c,n),但是他們都是用同樣的公鑰加密同樣的訊息,且這裡的公鑰是一個低指數
通解方法
此時就可以使用中國剩餘定理計算通解
其中
詳細連結
http://skysec.top/2018/09/13/Crypto-RSA多等式攻擊總結/#多等式之低加密指數廣播攻擊
計算指令碼
指令碼如下
import gmpy2 import gmpy import libnum question = [c1,c2,c3....n1,n2,n3...] N = 1 e=10 for i in range(len(question)): N*=question[i]['n'] N_list = [] for i in range(len(question)): N_list.append(N/question[i]['n']) t_list = [] for i in range(len(question)): t_list.append(int(gmpy2.invert(N_list[i],question[i]['n']))) sum = 0 for i in range(len(question)): sum = (sum+question[i]['c']*t_list[i]*N_list[i])%N sum = gmpy.root(sum,e)[0] print libnum.n2s(sum)
Related Message Attack
滿足條件
當e=3時,我們有如下條件
此時,我們有(c1,c2,n,padding)的值
通解方法
那麼就可以使用此攻擊,得到通解
詳細推導過程見
http://skysec.top/2018/09/15/淺析RSA-Padding-Attack/
計算指令碼
指令碼如下
def getM2(a,b,c1,c2,n): a3 = pow(a,3,n) b3 = pow(b,3,n) first = c1-a3*c2+2*b3 first = first % n second = 3*b*(a3*c2-b3) second = second % n third = second*gmpy2.invert(first,n) third = third % n fourth = (third+b)*gmpy2.invert(a,n) return fourth % n m = getM2(a,b,c1,c2,n)-padding2 print libnum.n2s(m)
Winner's Attack
滿足條件
當題目中
那麼即可使用Winner's Attack
更簡單的判斷方式為:e很大
計算指令碼
https://github.com/pablocelayes/rsa-wiener-attack
Boneh and Durfee attack
滿足條件
當題目中
那麼即可使用Boneh and Durfee attack
更簡單的判斷方式為:e很大,且Winner's Attack無法使用
計算指令碼
https://github.com/mimoo/RSA-and-LLL-attacks
與Winner's Attack對比
Boneh and Durfee attack的條件需求比Winner's Attack的需求低的多
所以一般情況下,在e很大的情況下,Winner's Attack無法使用可以使用Boneh and Durfee attack