資源描述：
《rsa算法的攻擊方法與防御建議》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、RSA算法的攻擊方法與防御建議 1RSA算法描述 RSA算法是由R.Rivest、A.Shamir和L.Adlernan三人于1978年研究提出的，是迄今得到最廣泛應(yīng)用的非對(duì)稱(chēng)密碼算法。RSA算法理論完善，安全性良好，可用于數(shù)據(jù)加密、數(shù)字簽名與身份認(rèn)證，滿(mǎn)足X絡(luò)安全的多方面需求，同時(shí)算法易于實(shí)現(xiàn)，得到了廣泛的應(yīng)用和深入的研究，其實(shí)現(xiàn)技術(shù)日趨成熟。RSA算法的初始化與應(yīng)用描述如下： 1.1RSA算法的初始化 ?。?）選取兩個(gè)非常大的、互異的質(zhì)數(shù)p，q；（2）計(jì)算n=pq及準(zhǔn)(n)=(p-1)(q-1)；（3）在開(kāi)區(qū)
2、間(0,準(zhǔn)(n))上取素?cái)?shù)e，滿(mǎn)足gcd(準(zhǔn)(n),e)=1；（4）計(jì)算d使得de≡1mod準(zhǔn)(n)；（5）公布（e,n）為公鑰，保密（d,n）為私鑰，銷(xiāo)毀p、q?！ ?.2RSA算法用于加/解密 如需對(duì)明文m（二進(jìn)制表示）加密，須先把m分成等長(zhǎng)s的數(shù)據(jù)塊m1，m2，，mi，2s<=n，加密mi得到密文：ci=mie(modn)。對(duì)密文ci解密得明文：mi=cid(modn)?！ ?.3RSA算法用于數(shù)字簽名發(fā)送者如需對(duì)信息m進(jìn)行數(shù)字簽名，須使用私鑰d對(duì)m作運(yùn)算：s=md(modn)得到簽名，然后將
3、信息m和簽名s一起發(fā)送給接收方。接收方使用發(fā)送者的公鑰e對(duì)s作運(yùn)算得：m=se(modn)，如果m=m則可證明發(fā)送者的身份?！ ?RSA算法的攻擊方法 RSA算法的安全性依賴(lài)于大整數(shù)分解的困難性。最直接的攻擊方法是分解n得到p,q，進(jìn)而基于e計(jì)算d，隨著計(jì)算機(jī)運(yùn)算能力的不斷提高，通過(guò)二次篩法已能分解180多位的十進(jìn)制素?cái)?shù)，增加p,q的長(zhǎng)度已成為許多安全應(yīng)用系統(tǒng)的加密要求。另一方面，利用系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的缺陷，人們也提出了一些基于非因子分解方式破解RSA算法的方案。目前，對(duì)RSA算法的攻擊主要有以下幾種： 2.1對(duì)模數(shù)
4、n的因子分解 分解模數(shù)n是最直接的攻擊方法，也是最困難的方法。攻擊者可以獲得公鑰e和模數(shù)n；如果n=pq被成功分解，則攻擊者可以計(jì)算出φ(n)=(p-1)(q-1)，進(jìn)而從ed≡1modφ(n)解得私鑰d?！ ?.2對(duì)RSA的公共模數(shù)攻擊 若一個(gè)多用戶(hù)系統(tǒng)中只采用一個(gè)模數(shù)n，不同的用戶(hù)擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。在此系統(tǒng)中，若有同一消息用不同的公鑰加密，這些公鑰共模且互質(zhì)，那該信息無(wú)需私鑰就可解密。舉例來(lái)說(shuō)，設(shè)P為信息明文，兩個(gè)加密公鑰為e1和e2，公共模數(shù)是n，有：C1=Pe1m
5、odn和C2=Pe2modn。如果攻擊者獲得n、e1、e2、C1和C2，就能得到P。因?yàn)閑1和e2互質(zhì)，故用歐幾里德(Euclid)算法能找到r和s，滿(mǎn)足：r*e1+s*e2=1，設(shè)r為負(fù)數(shù)，則(C1-1)-r*C2s=(Pe1modn)r*(Pe2modn)s=(Pr*e1+s*e2)modn=Pmodn，如果P<n，則P被獲取?！ ?.3對(duì)RSA的小指數(shù)攻擊 如果RSA系統(tǒng)的公鑰e選取較小的值，可以使加密和驗(yàn)證簽名的速度有所提高。但如果e取得太小，就容易受到小指數(shù)攻擊。例如，有同一系統(tǒng)的三個(gè)用戶(hù)，分別使用不
6、同的模數(shù)n1，n2，n3，但都選取e=3；另有一用戶(hù)欲將同一明文消息P發(fā)送給以上三人，使用各人的公鑰加密得：C1=P3(modn1)，C2=P3(modn2)和C3=P3(modn3)一般地，n1，n2，n3互素（否則，會(huì)比較容易求出公因子，降低安全性），根據(jù)中國(guó)剩余定理，可由C1，C2，C3計(jì)算：C=P3(modn1n2n3)如果P<n1,P<n2,P<n3,有P3<n1n2n3，可得P=C3姨?！ ?.4對(duì)RSA的選擇密文攻擊 選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對(duì)應(yīng)的明文，由
7、此推出想要的信息。一般攻擊者會(huì)偽裝若干信息，讓擁有私鑰的用戶(hù)簽名，由此獲得有用的明文-密文對(duì)，然后推算想要的信息?！ ±?攻擊者想要偽造用戶(hù)u對(duì)消息x的簽名。他可以先計(jì)算x1,x2，使得x≡(x1x2)(modn)，并騙取u對(duì)x1和x2的簽名s1=x1d(modn)和s2=x2d(modn)，則對(duì)x的簽名可計(jì)算如：s=xd(modn)=(((x1x2)(modn))d)(modn)=((x1dmodn)(x2dmodn))modn=(s1s2)(modn)。 例2攻擊者獲得了用戶(hù)u使用公鑰e加密的密文y=
8、xe(modn)，想要得到x。他可以先計(jì)算y′=re(modn)（r是小于n的隨機(jī)數(shù)），y″=(yy′)(modn)，然后騙取u對(duì)y″的簽名s=y″d(modn)。則通過(guò)計(jì)算(r-1s)(modn)可以恢復(fù)出x，這是因?yàn)椋?r-1s)(modn)=((y′dm
