1 RSA算法描述
RSA 算法是由 R.Rivest、A.Shamir 和 L.Adlernan 三人于 1978 年研究提出的，是迄今得到最廣泛應用的非對稱密碼算法。 RSA 算法理論完善，安全性良好，可用于數據加密、數字簽名與身份認證，滿足網絡安全的多方面需求，同時算法易于實現，得到了廣泛的應用和深入的研究，其實現技術日趨成熟。 RSA 算法的初始化與應用描述如下：
1.1 RSA 算法的初始化
（1）選取兩個非常大的、互異的質數 p，q；（2）計算 n=pq 及 準\\(n\\)=\\(p-1\\)\\(q-1\\)；（3）在開區間\\(0,準\\(n\\)\\)上取素數 e，滿足 gcd\\(準\\(n\\),e\\)=1；（4）計算 d 使得 de≡1mod準\\(n\\)；（5）公布（e, n）為公鑰，保密（d, n）為私鑰，銷毀 p、q。
1.2 RSA 算法用于加/解密
如需對明文 m（二進制表示）加密，須先把 m 分成等長 s 的數據塊m1，m2，…，mi，2s<=n，加密 mi得到密文：ci=mie\\(modn\\)。對密文 ci解密得明文：mi=cid\\(modn\\)。
1.3 RSA 算法用于數字簽名發送者如需對信息 m 進行數字簽名，須使用私鑰 d 對 m 作運算：s=md\\(modn\\)得到簽名，然后將信息 m 和簽名 s 一起發送給接收方。接收方使用發送者的公鑰 e 對 s 作運算得：m=se\\(modn\\)，如果 m=m則可證明發送者的身份。
2 RSA算法的攻擊方法
RSA 算法的安全性依賴于大整數分解的困難性。 最直接的攻擊方法是分解 n 得到 p,q，進而基于 e 計算 d，隨著計算機運算能力的不斷提高，通過二次篩法已能分解 180 多位的十進制素數，增加 p,q 的長度已成為許多安全應用系統的加密要求。 另一方面，利用系統設計和實現的缺陷， 人們也提出了一些基于非因子分解方式破解 RSA 算法的方案。 目前，對 RSA 算法的攻擊主要有以下幾種：
2.1 對模數 n 的因子分解
分解模數 n 是最直接的攻擊方法，也是最困難的方法。 攻擊者可以獲得公鑰 e 和模數 n；如果 n=pq 被成功分解，則攻擊者可以計算出φ\\(n\\)=\\(p-1\\)\\(q-1\\)，進而從 ed≡1modφ\\(n\\)解得私鑰 d。
2.2 對 RSA 的公共模數攻擊
若一個多用戶系統中只采用一個模數 n，不同的用戶擁有不同的e 和 d，系統將是危險的。 在此系統中，若有同一消息用不同的公鑰加密，這些公鑰共模且互質，那該信息無需私鑰就可解密。 舉例來說，設P 為信息明文，兩個加密公鑰為 e1和 e2，公共模數是 n，有：C1=Pe1modn 和 C2=Pe2modn。如果攻擊者獲得 n、e1、e2、C1和 C2，就能得到 P。 因為 e1和 e2互質，故用歐幾里德\\(Euclid\\)算法能找到 r 和 s，滿足：r*e1+s*e2=1，設 r 為負數，則\\(C1-1\\)-r*C2s=\\(Pe1modn\\)r*\\(Pe2modn\\)s=\\(Pr*e1+s*e2\\)modn=Pmodn，如果 P 2.3 對 RSA 的小指數攻擊 如果 RSA 系統的公鑰 e 選取較小的值， 可以使加密和驗證簽名的速度有所提高。 但如果 e 取得太小，就容易受到小指數攻擊。 例如，有同一系統的三個用戶，分別使用不同的模數 n1，n2，n3，但都選取 e=3；另有一用戶欲將同一明文消息 P 發送給以上三人，使用各人的公鑰加密得：C1=P3\\(modn1\\)，C2=P3\\(modn2\\)和 C3=P3\\(modn3\\)一般地，n1，n2，n3互素（否則，會比較容易求出公因子，降低安全性），根據中國剩余定理，可由 C1，C2，C3計算：C=P3\\(modn1n2n3\\)如果 P 2.4 對 RSA 的選擇密文攻擊 選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對應的明文，由此推出想要的信息。一般攻擊者會偽裝若干信息，讓擁有私鑰的用戶簽名，由此獲得有用的明文-密文對，然后推算想要的信息。 例 1 攻擊者想要偽造用戶 u 對消息 x 的簽名。 他可以先計算 x1,x2，使得 x≡\\(x1x2\\)\\(modn\\)，并騙取 u 對 x1和 x2的簽名 s1=x1d\\(modn\\)和 s2=x2d\\(modn\\)， 則對 x 的簽名可計算如：s=xd\\(modn\\)=\\(\\(\\(x1x2\\)\\(modn\\)\\)d\\)\\(modn\\)=\\(\\(x1dmodn\\)\\(x2dmodn\\)\\)modn=\\(s1s2\\)\\(modn\\)。 例 2 攻擊者獲得了用戶 u 使用公鑰 e 加密的密文 y=xe\\(modn\\)，想要得到 x。 他可以先計算 y′=re\\(modn\\)（r 是小于 n 的隨機數），y″=\\(yy′\\)\\(modn\\)，然后騙取 u 對 y″的簽名 s=y″d\\(modn\\)。 則通過計算\\(r-1s\\)\\(modn\\)可以恢復出 x，這是因為：\\(r-1s\\)\\(modn\\)=\\(\\(y′dmodn\\)-1y″d\\)\\(modn\\)=\\(y′-dy″d\\)\\(modn\\)=\\(y′-dydy′d\\)\\(modn\\)=yd\\(modn\\)=x。 3對RSA算法的攻擊的防御建議對于以上幾種攻擊，防御方案各不相同。攻擊 1 源于 RSA 算法的數學安全基礎， 增加初始化參數長度是有效的提高安全度的方法。而攻擊 2 和攻擊 3 源于應用 RSA 算法的系統的設計缺陷， 改進方法為：1）在多用戶系統中必須采用多個模數；2）避免為了圖求方便而使用取值太小的公鑰 e。[1-2] 攻擊 4 最為復雜，從算法上無法解決這一問題，主要對應策略有兩條：1）私鑰持有者不對不信任的信息簽名；2）簽名信息時，先使用Hash 函數生成的摘要，再對摘要簽名，避免直接對信息的簽名。[3] 以上防御方案并不能解決所有的 RSA 安全問題， 我們建議利用RSA 算法的系統仔細審核安全需求 ，投入使用先進行測試 ，并對系統安全做一個全面的審核。 必須對各種安全策略及程序進行合理優化，才能盡可能地降低風險，RSA 算法才能發揮最大的效用。 參考文獻：
［1］閆洪亮,牛軍濤.實現 RSA 算法應注意的問題[J].計算機應用與軟件,2008\\(5\\):253-254.
［2］謝建全,陽春華.RSA 算法中幾種可能泄密的參數選擇[J].計算機工程 ,2006\\(16\\):118-119.
［3］李志敏.基于 RSA 密碼體制的選擇密文攻擊的研究[J].網絡安全技術與應用,2009\\(1\\):12-13.
