RSA算法的攻擊方法與防御建議發(fā)布者：本站     時(shí)間：2020-05-02 16:05:53

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 算法的初始化

（1）選取兩個(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 使得 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ā)送者的身份。

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)，進(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ì)，那該信息無(wú)需私鑰就可解密。 舉例來(lái)說(shuō)，設(shè)P 為信息明文，兩個(gè)加密公鑰為 e1和 e2，公共模數(shù)是 n，有：C1=Pe1modn 和 C2=Pe2modn。如果攻擊者獲得 n、e1、e2、C1和 C2，就能得到 P。 因?yàn)?e1和 e2互質(zhì)，故用歐幾里德(Euclid)算法能找到 r 和 s，滿足：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 被獲取。

2.3 對(duì) 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互素（否則，會(huì)比較容易求出公因子，降低安全性），根據(jù)中國(guó)剩余定理，可由 C1，C2，C3計(jì)算：C=P3(modn1n2n3)如果 P<n1, P<n2, P<n3, 有 P3<n1n2n3，可得 P= C3姨 。

2.4 對(duì) RSA 的選擇密文攻擊

選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對(duì)應(yīng)的明文，由此推出想要的信息。一般攻擊者會(huì)偽裝若干信息，讓擁有私鑰的用戶簽名，由此獲得有用的明文-密文對(duì)，然后推算想要的信息。

例 1 攻擊者想要偽造用戶 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 攻擊者獲得了用戶 u 使用公鑰 e 加密的密文 y=xe(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 算法的系統(tǒng)的設(shè)計(jì)缺陷， 改進(jìn)方法為：1）在多用戶系統(tǒng)中必須采用多個(gè)模數(shù)；2）避免為了圖求方便而使用取值太小的公鑰 e。[1-2]

攻擊 4 最為復(fù)雜，從算法上無(wú)法解決這一問題，主要對(duì)應(yīng)策略有兩條：1）私鑰持有者不對(duì)不信任的信息簽名；2）簽名信息時(shí)，先使用Hash 函數(shù)生成的摘要，再對(duì)摘要簽名，避免直接對(duì)信息的簽名。[3]

以上防御方案并不能解決所有的 RSA 安全問題， 我們建議利用RSA 算法的系統(tǒng)仔細(xì)審核安全需求 ，投入使用先進(jìn)行測(cè)試 ，并對(duì)系統(tǒng)安全做一個(gè)全面的審核。 必須對(duì)各種安全策略及程序進(jìn)行合理優(yōu)化，才能盡可能地降低風(fēng)險(xiǎn)，RSA 算法才能發(fā)揮最大的效用。