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

《rsa 算法的攻擊方法研究-化工》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

2、向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全。1　RSA算法描述RSA算法是由R.Rivest、A.Shamir和L.Adlernan三人于1978年研究提出的，是迄今得到最廣泛應(yīng)用的非對(duì)稱密碼算法。RSA算法理論完善，安全性良好，可用于數(shù)據(jù)加密、數(shù)字簽名與身份認(rèn)證，滿足網(wǎng)絡(luò)安全的多方面需求，同時(shí)算法易于實(shí)現(xiàn)，得到了廣泛的應(yīng)用和深入的研究，其實(shí)現(xiàn)技術(shù)日趨成熟。RSA算法的初始化與應(yīng)用描述如下：1.1　RSA算法的初始化（１）選取兩個(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)

3、,e)=1；（4）計(jì)算d使得de≡1mod?準(zhǔn)(n)；（5）公布（e,n）為公鑰，保密（d,n）為私鑰，銷毀p、q。1.2　RSA算法用于加/解密如需對(duì)明文m（二進(jìn)制表示）加密，須先把m分成等長(zhǎng)s的數(shù)據(jù)塊m1，m2，…，mi，2s=n，加密mi得到密文：ci=mie(modn)。對(duì)密文ci解密得明文：mi=cid(modn)。1.3　RSA算法用于數(shù)字簽名發(fā)送者如需對(duì)信息m進(jìn)行數(shù)字簽名，須使用私鑰d對(duì)m作運(yùn)算：s=md(modn)得到簽名，然后將信息m和簽名s一起發(fā)送給接收方。接收方使用發(fā)送者的公鑰e對(duì)s作運(yùn)算得：m=se(modn)，如果m=m則可證明發(fā)送

4、者的身份。2　RSA算法的攻擊方法RSA算法的安全性依賴于大整數(shù)分解的困難性。最直接的攻擊方法是分解n得到p,q，進(jìn)而基于e計(jì)算d，隨著計(jì)算機(jī)運(yùn)算能力的不斷提高，通過二次篩法已能分解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ù)n的因子分解分解模數(shù)n是最直接的攻擊方法，也是最困難的方法。攻擊者可以獲得公鑰e和模數(shù)n；如果n=pq被成功分解，則攻擊者可以計(jì)算出φ(n)=(p-1)(q-1)

5、，進(jìn)而從ed≡1modφ(n)解得私鑰d。2.2　對(duì)RSA的公共模數(shù)攻擊若一個(gè)多用戶系統(tǒng)中只采用一個(gè)模數(shù)n，不同的用戶擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。在此系統(tǒng)中，若有同一消息用不同的公鑰加密，這些公鑰共模且互質(zhì)，那該信息無需私鑰就可解密。舉例來說，設(shè)P為信息明文，兩個(gè)加密公鑰為e1和e2，公共模數(shù)是n，有：2.3　對(duì)RSA的小指數(shù)攻擊如果RSA系統(tǒng)的公鑰e選取較小的值，可以使加密和驗(yàn)證簽名的速度有所提高。但如果e取得太小，就容易受到小指數(shù)攻擊。例如，有同一系統(tǒng)的三個(gè)用戶，分別使用不同的模數(shù)n1，n2，n3，但都選取e=3；另有一用戶欲將同一明文消息P發(fā)送給

6、以上三人，使用各人的公鑰加密得：C1=P3(modn1)，C2=P3(modn2)和C3=P3(modn3)一般地，n1，n2，n3互素（否則，會(huì)比較容易求出公因子，降低安全性），根據(jù)中國剩余定理，可由C1，C2，C3計(jì)算：C=P3(modn1n2n3)如果Pn1,Pn2,Pn3,有P3n1n2n3，可得2.4　對(duì)RSA的選擇密文攻擊選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對(duì)應(yīng)的明文，由此推出想要的信息。一般攻擊者會(huì)偽裝若干信息，讓擁有私鑰的用戶簽名，由此獲得有用的明文-密文對(duì)，然后推算想要的信息。例2　攻擊者獲得了用戶u使用公鑰e加密的密文y=xe

7、(modn)，想要得到x。他可以先計(jì)算y′=re(modn)（r是小于n的隨機(jī)數(shù)），y″=(yy′)(modn)，然后騙取u對(duì)y″的簽名s=y″d(modn)。則通過計(jì)算(r-1s)(modn)可以恢復(fù)出x，這是因?yàn)椋?r-1s)(modn)=((y′dmodn)-1y″d)(modn)=(y′-dy″d)(modn)=(y′-dydy′d)(modn)=yd(modn)=x。3　對(duì)RSA算法的攻擊的防御建議對(duì)于以上幾種攻擊，防御方案各不相同。攻擊1源于RSA算法的數(shù)學(xué)安全基礎(chǔ)，增加初始化參數(shù)長(zhǎng)度是有效的提高安全度的方法。而攻擊2和攻擊3源于應(yīng)用RSA算法的

8、系統(tǒng)的設(shè)計(jì)缺陷，改進(jìn)方法為：1）在多用戶系統(tǒng)中必須采