RSA 算法的攻擊方法研究-化工

1、.RSA 算法的攻擊方法研究-化工RSA 算法的攻擊方法研究 李家蘭（廣東石油化工學(xué)院計(jì)算機(jī)系，廣東 茂名 525000）【摘要】RSA算法是迄今在網(wǎng)絡(luò)安全領(lǐng)域應(yīng)用最為廣泛的非對稱密碼算法，其安全性是基于大整數(shù)的因數(shù)分解難問題的，算法的攻破一般被認(rèn)為等同于大數(shù)分解。另一方面，對RSA算法的攻擊可針對設(shè)計(jì)與應(yīng)用該算法的系統(tǒng)的某些缺陷。本文研究了對RSA算法的攻擊的主要方法，并對攻擊防御提出了建議。關(guān)鍵詞網(wǎng)絡(luò)安全；RSA算法；算法攻擊；攻擊防御基金項(xiàng)目：廣東石油化工學(xué)院科學(xué)研究基金資助項(xiàng)目（200839）。作者簡介：李家蘭（1977），男，廣東茂名人，碩士，講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全。1

2、RSA算法描述RSA算法是由R.Rivest、A.Shamir和L.Adlernan三人于1978年研究提出的，是迄今得到最廣泛應(yīng)用的非對稱密碼算法。RSA算法理論完善，安全性良好，可用于數(shù)據(jù)加密、數(shù)字簽名與身份認(rèn)證，滿足網(wǎng)絡(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）在開區(qū)間(0,?準(zhǔn)(n)上取素?cái)?shù)e，滿足gcd(?準(zhǔn)(n),e)=1；（4）計(jì)算d使得 de1mod?準(zhǔn)(n)；（5）公布（e,

3、n）為公鑰，保密（d, n）為私鑰，銷毀p、q。1.2RSA算法用于加/解密如需對明文m（二進(jìn)制表示）加密，須先把m分成等長s的數(shù)據(jù)塊 m1，m2，mi，2s=n，加密mi得到密文：ci=mie(modn)。對密文ci解密得明文：mi=cid(modn)。1.3RSA算法用于數(shù)字簽名發(fā)送者如需對信息m進(jìn)行數(shù)字簽名，須使用私鑰d對m作運(yùn)算：s=md(modn)得到簽名，然后將信息m和簽名s一起發(fā)送給接收方。接收方使用發(fā)送者的公鑰e對s作運(yùn)算得：m=se(modn)，如果m=m則可證明發(fā)送者的身份。2RSA算法的攻擊方法RSA算法的安全性依賴于大整數(shù)分解的困難性。最直接的攻擊方法是分解n得到p,q

4、，進(jìn)而基于e計(jì)算d，隨著計(jì)算機(jī)運(yùn)算能力的不斷提高，通過二次篩法已能分解180多位的十進(jìn)制素?cái)?shù)，增加p,q的長度已成為許多安全應(yīng)用系統(tǒng)的加密要求。另一方面，利用系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的缺陷，人們也提出了一些基于非因子分解方式破解RSA算法的方案。目前，對RSA算法的攻擊主要有以下幾種：2.1對模數(shù)n的因子分解分解模數(shù)n是最直接的攻擊方法，也是最困難的方法。攻擊者可以獲得公鑰e和模數(shù)n；如果n=pq被成功分解，則攻擊者可以計(jì)算出(n)=(p-1)(q-1)，進(jìn)而從ed1mod(n)解得私鑰d。2.2對RSA的公共模數(shù)攻擊若一個(gè)多用戶系統(tǒng)中只采用一個(gè)模數(shù)n，不同的用戶擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。在此系

5、統(tǒng)中，若有同一消息用不同的公鑰加密，這些公鑰共模且互質(zhì)，那該信息無需私鑰就可解密。舉例來說，設(shè)P為信息明文，兩個(gè)加密公鑰為e1和e2，公共模數(shù)是n，有： 2.3對RSA的小指數(shù)攻擊如果RSA系統(tǒng)的公鑰e選取較小的值，可以使加密和驗(yàn)證簽名的速度有所提高。但如果e取得太小，就容易受到小指數(shù)攻擊。例如，有同一系統(tǒng)的三個(gè)用戶，分別使用不同的模數(shù)n1，n2，n3，但都選取e=3；另有一用戶欲將同一明文消息P發(fā)送給以上三人，使用各人的公鑰加密得：C1=P3(modn1)，C2=P3(modn2)和C3=P3(modn3)一般地，n1，n2，n3互素（否則，會比較容易求出公因子，降低安全性），根據(jù)中國剩余定

6、理，可由C1，C2，C3計(jì)算：C=P3(modn1n2n3)如果Pn1, Pn2, Pn3, 有P3n1 n2 n3，可得2.4對RSA的選擇密文攻擊選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對應(yīng)的明文，由此推出想要的信息。一般攻擊者會偽裝若干信息，讓擁有私鑰的用戶簽名，由此獲得有用的明文-密文對，然后推算想要的信息。 例2攻擊者獲得了用戶u使用公鑰e加密的密文y=xe(modn)，想要得到x。他可以先計(jì)算y=re(modn)（r是小于n的隨機(jī)數(shù)），y=(yy)(modn)，然后騙取u對y的簽名s=yd(modn)。則通過計(jì)算(r-1s)(modn)可以恢復(fù)出x，這是因?yàn)椋?r-1s)(

7、modn)=(ydmodn)-1yd)(modn)=(y-dyd)(modn)=(y-dydyd)(modn)=yd(modn)=x。3對RSA算法的攻擊的防御建議對于以上幾種攻擊，防御方案各不相同。攻擊1源于RSA算法的數(shù)學(xué)安全基礎(chǔ)，增加初始化參數(shù)長度是有效的提高安全度的方法。而攻擊2和攻擊3源于應(yīng)用RSA算法的系統(tǒng)的設(shè)計(jì)缺陷，改進(jìn)方法為：1）在多用戶系統(tǒng)中必須采用多個(gè)模數(shù)；2）避免為了圖求方便而使用取值太小的公鑰e。1-2攻擊4最為復(fù)雜，從算法上無法解決這一問題，主要對應(yīng)策略有兩條：1）私鑰持有者不對不信任的信息簽名；2）簽名信息時(shí)，先使用Hash函數(shù)生成的摘要，再對摘要簽名，避免直接對信息的簽名。3以上防御方案并不能解決所有的RSA安全問題，我們建議利用RSA算法的系統(tǒng)仔細(xì)審核安全需求，投入使用先進(jìn)行測試，并對系統(tǒng)安全做一個(gè)全面的審核。必須對各種安全策略及程序進(jìn)行合理優(yōu)化，才能盡可能地降低風(fēng)險(xiǎn)，RSA算法才能發(fā)揮最大的效用。參考文獻(xiàn)1閆洪亮,牛軍濤.實(shí)現(xiàn)RSA算法應(yīng)注意的問題J.計(jì)算機(jī)應(yīng)用與軟件,2008(5):