【文章內(nèi)容簡介】 大的 Eric Yang 等發(fā)起編寫的。相關 Open SSL 應用 RSA 實現(xiàn)簽名和密鑰交換，已經(jīng)在各種操作系統(tǒng)得到非常廣泛的應用。另外，家喻戶曉的 IE 瀏覽器，自然也實現(xiàn)了 SSL 協(xié)議，集成了使用 RSA技術的加密功能，結合 MD5 和 SHA1，主要用于數(shù)字證書和數(shù)字簽名，對于習慣于使用網(wǎng)上購物和網(wǎng)上銀行的用戶來說，幾乎天天都在使用 RSA 技術。 RSA 更出現(xiàn)在要求高度安全穩(wěn)定的企業(yè)級商務應用中。在當今的企業(yè)級商務應用中，不得不提及使用最廣泛的平臺 j2ee。事實上， 在 j2se 的標準庫中，就為安全和加密服務提供了兩組 API： JCA 和 JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如證書、數(shù)字簽名、報文摘要和密鑰對產(chǎn)生器； JCA 由幾個實現(xiàn)了基本的加密技術功能的類和接口組成，其中最主要的是 包，此軟件包包含的是一組核心的類和接口， Java 中數(shù)字簽名的方法就集中在此軟件包中。 JCE(Java Cryptography Extension) 在 JCA 的基礎上作了擴展， JCE 也是由幾個軟件包組成，其中 最主要的是 包，此軟件包提供了 JCE加密技術操作 API。 中的 Cipher 類用于具體的加密和解密。在上述軟件包的實現(xiàn)中，集成了應用 RSA 算法的各種數(shù)據(jù)加密規(guī)范 ，這些 API 內(nèi)部支持的算法不僅僅只有 RSA，但是 RSA 是數(shù)字簽名和證書中最常用的，用戶程序可以直接使用 java 標準庫中提供的 API 進行數(shù)字簽名和證書的各種操作。單機應用程序使用 RSA 加密尚比較少見，例如使用 RSA 加密任意一個文件。 河南理工大學畢業(yè)設計（論文）說明書 7 RSA 算法的攻擊與安全性的討論 理論上， RSA的安全性取決于因式分解 模數(shù) N的困難性。從嚴格的技術角度上來說這是不正確的，在數(shù)學上至今還未證明分解模數(shù)就是攻擊 RSA的最佳方法，也未證明分解大整數(shù)就是 NP問題 (表示那些能在多項式時間內(nèi)利用“不確定性 圖靈機可以求解的問題 )。事實情況是，大整數(shù)因子分解問題過去數(shù)百年來一直是令數(shù)學家頭疼而未能有效解決的世界性難題。人們設想了一些非因子分解的途徑來攻擊 RSA體制，但這些方法都不比分解 n來得容易。因此，嚴格地說， RSA的安全性基于求解其單向函數(shù)的逆的困難性。RSA單向函數(shù)求逆的安全性沒有真正因式分解模數(shù)的安全性高，而且目前人們也無法證明 這兩者等價。許多研究人員都試圖改進 RSA體制使它的安全性等價于因式分解模數(shù)。 對 RSA算法的攻擊主要有以下幾種： 對 RSA的分解模數(shù) n攻擊 分解模數(shù) n是最直接的攻擊方法，也 是 最困難的方法。攻擊者可以公開密鑰 e 和模數(shù) N；如果模數(shù) N=pq 被因式分解，則攻擊者通過 P和 q便可計算出 ()N? =(p1)(q1)，進而由 ed≡ 1(mod ()N? )而得到解密密鑰 d。大整數(shù)分解研究一直 是 數(shù)論與密碼理論研究的重要課題。 對 RSA 的選擇密文攻擊 選擇密文攻擊 是 攻擊者對 RSA等公鑰算法最常用的攻擊，也 是最有效的攻擊手段之一。選擇密文攻擊通常是由 RSA加密變換的性質(zhì)誘發(fā)的，常見的對 RSA的選擇密文攻擊有三種： （ 1）明文破譯。攻擊者獲得某用戶 A使用公鑰 e加密的密文 Y= ex (modN)，并試圖恢復出消息 X。隨機選取 rn，計算 1 (mod )ey r n? ，這意味 1 (mod )dr y n? 。計算21(mod )y yy n? 。令 1(mod )t r n?? ，則 1 (mod )dt y n?? ，現(xiàn)在攻擊者請 A對消息 2y 進行簽名 ,得到 2(mod )ds y n? 。攻擊者計算 1 1 2 1 1( ) ( m o d ) ( ) ( m o d ) ( m o d )d d d d d dt t s y y n y y y n y n x??? ? ? ? ?，得到了明文。 （ 2）騙取仲裁簽名。在有仲裁情況下，若某用戶 A有一個文件要求仲裁，可先將其送給仲裁 T， T使用 RSA的解密密鑰進行簽名后送給 A。攻擊者有一個消息想要 T簽名，但 T并不想給他簽，因為可能有偽 造的消息，也可能是來自非法使用者的消息。但攻擊者可用下述方法騙取 T的簽名。令攻擊者的消息為 X，他首先任取一個數(shù) N，計算河南理工大學畢業(yè)設計（論文）說明書 8 (mod )ey N n? (e是 T的公鑰 )，然后計算 M=yx，送給 T， T將簽名的結果 (mod )dMn發(fā) 送給攻擊者，則有： 1 1 1 1( ) ) ( ) ( m o d )d d d d d dM N y x N x y N x N N x n? ? ? ?? ? ? ? 攻擊者成功騙取 T對 x的簽名。 （ 3）偽造合法簽名。攻擊者利用自己偽造兩個消息 1x 和 2x 來拼湊出所需要的3 1 2( )(mod )x x x n? 。攻擊者如果得到用戶 A對 1x 和 2x 的簽名 1(mod )dxn和 2(mod )dxn，就可以計算 3x 的簽名 3 1 2( ( m o d ) ) ( ( m o d ) ) ( m o d )d d dx x n x n n? 對 RSA 的小指數(shù)攻擊 這類攻擊專門針對 RSA算法的實現(xiàn)的細節(jié)。采用小的 e、 d可以加快加密和驗證簽名的速度，而且所需的存儲空間 小，但是如果 e、 d太小，則容易受到小指數(shù)攻擊，包括低加密指數(shù)攻擊和低解密指數(shù)攻擊。 通過獨立隨機數(shù)字對明文消息 X進行填充，這樣使得 (mod )eex n x? ，可以有效地抗擊小指數(shù)攻擊。 對 RSA 共模攻擊 在 RSA公鑰密碼的實現(xiàn)中，為簡化問題，可能會采用給每個人相同的值，但不同的指數(shù)值 e和 d。這樣做的問題是，如果同一信息用兩個不同的指數(shù)加密，這兩個指數(shù)是互素的，則不需要任何解密密鑰就能恢復明文。 設 m是明文，兩個加密密鑰分別為 1e 和 2e ，共同的模數(shù)為 n，兩個密文為： 11 modec m n? 22 modec m n? 由于 1e 和 2e 是互素的，由擴展的歐幾里德算法可以找 到 r和 s，使之滿足 121re se?? 假設 r是負數(shù) (其中必有一個為負數(shù) )，再次使用歐幾里德算法可以求得 1c 對模數(shù) n的逆元 11c? ，故可以得到 12112( ) ( m o d ) ( m o d ) ( m o d )r e s ersc c n m m n m n?? ?? 即密碼分析者知道 n,1e ,2e ,1c 和 2c ，則可以恢復出明文 m。 RSA 的安全性討論 加密系統(tǒng)最重要的是它的安全性，再好的加密系統(tǒng)若其安全性不足將會一文不值。河南理工大學畢業(yè)設計（論文）說明書 9 RSA密碼體制的安全性取決于其加密函 數(shù)求逆的困難性。判斷一個密碼系統(tǒng)是否安全，不能從算法設計角度分析，而應該看其能否抵抗各種攻擊。因此，在分析 RSA的安全時，必須討論其攻擊方法，看其是否足夠強勁以抵御這些攻擊。 RSA 公鑰密碼系統(tǒng)就是基于這樣一個事實：給定兩個大素數(shù) p和 q，要獲得他們的乘積 n=p q 很容易，但是如果給定一個剛好是兩個大素數(shù)乘積的合數(shù) n，要找出這個合數(shù)的兩個素因子非常困難。 分解大整數(shù)模 n是最顯而易見的攻擊方法。雖然無法證明， RSA 密碼算法的強度等同于大數(shù)模 n的因子分解，但目前還沒有找到比分解模 n更快的攻擊方法。如果攻擊者分解了模 n，得到其因子 p 和 q，那么結合公開的加密指數(shù) e，找到對應的解密指數(shù) d就輕而易舉，解密密文自然也不成問題。 一般攻擊 RSA 算法的方法就是求合數(shù)的素因子分解。 RSA 公鑰密 碼體制的公開密鑰是目前最難分解的一類合數(shù)，專用的分解方法和數(shù)域篩的方法都不會對這類數(shù)構成危險。對于 100 位至 200 位之間的數(shù)，每增加 3 位，則分解時間將增加一倍。由此推算，每秒 10 億次的計算機在一天內(nèi)最多也就分解一個不到 100 位的合數(shù)；而分解一個 200位的合數(shù)，用通用的方法，大概需要 2{200100}/3≈ 1010天的時間?，F(xiàn)在，無論計算機的速度還是數(shù)量，都不可能有超過 1010倍的增長。目前，十進制 129 位的數(shù)也被分解，因此，n要大于這些數(shù)。為了使模 n的分解難以實現(xiàn)，要求： （ 1）模 n 足夠大。這是為了防止采 用窮舉搜索來尋找 n 的因子。至于究竟需要多大，和當前的因子分解技術和具體密碼系統(tǒng)的應用背景有關。只要滿足使因子分解的代價大于解密獲取的利益即可。 （ 2)大素數(shù) p和 q應該足夠大，若 p 或 q 是小素數(shù)，窮舉搜索小素數(shù)集合，也會很快找到 p， q。另外 p和 q相差不能太小，因為若 p 和 q 大小相若，則可通過對模 n 取平方根，較快地找到 p、 q。 （ 3)大素數(shù) p和 q應為隨機產(chǎn)生，不能具有特殊形式或取自某個素數(shù)表，顯然，具有特殊形式的素數(shù)首先是因子分解的嘗試對象。 RSA 參數(shù)的選擇 RSA 遭受攻擊的很多情況是因為算法實現(xiàn)的 一些細節(jié)上的漏洞所導致的，所以在使用 RSA算法構造密碼系統(tǒng)時，為保證安全，在生成大素數(shù)的基礎上，還必須認真仔細選擇參數(shù)，防止漏洞的形成。根據(jù) RSA 加解密過程，其主要參數(shù)有三個：模數(shù) N，加密密鑰 e，解密密鑰 d。 河南理工大學畢業(yè)設計（論文）說明書 10 模數(shù) N 的確定 雖然迄今人們無法證明，破解 RSA系統(tǒng)等于對 N因子分解，但一般相信 RSA系統(tǒng)的安全性等同于因子分解，即：若能分解因子 N，即能攻破 RSA系統(tǒng)，若能攻破 RSA系統(tǒng)，即能分解因子。因此，在使用 RSA系統(tǒng)時，對于模數(shù) N的選擇非常重要。在 RSA算法中，通過產(chǎn)生的兩個大素數(shù) P和 q相乘得 到模數(shù)Ｎ，而后分別通過對它們的數(shù)學運算得到密鑰對。由此，分解模數(shù)Ｎ得到 P和 q是最顯然的攻擊方法，當然也是最困難的方法，如果模數(shù) n被分解，攻擊者利用得到的 P和 q便可計算出 ()N? =(P1)x(q1)，進而通過公開密鑰ｅ由 1(mod ( ))ed N?? 解密密鑰 d，則 RSA體制立刻被攻破。相當一部分的對 RSA的攻擊就是試圖分解模數(shù) N，選擇合適的Ｎ是實現(xiàn) RSA算法并防止漏洞的重要環(huán)節(jié)。一般地，模數(shù) N的確定可以遵循以下幾個原則： （ 1） P和ｑ之差要大。 （ 2） pl和 q1的最大公因子應很小。 當 p和 q相差很小時，在已知 n的情況下，可假定 二者的平均值 2pq? 為 n ，然后利用 22( ) ( )22p q p qN????，若等式右邊 2()2pq? 可開方，則得到 ()2pq? 及()2pq? ，即 N被分解。 （ 3） P和 q必須為強素數(shù)。 一素數(shù) P如果滿足 : 條件一：存在兩個大素數(shù) 1p ， 2p ，使得 1p |p1且 2p |p+1； 條件二：存在四個大素數(shù) 1 2 1 2, , ,r r s s 使得1 1 1 1 2 2 2 2| 1 , | 1 , | 1 , | 1r p s p r p s p? ? ? ?。則此素數(shù)為強素數(shù)。其中 1 2 1 2, , ,r s s 稱為 3級的素數(shù)， 1p ， 2p 稱為 2級的素數(shù)， P則稱為 1級的素數(shù)，很明顯地，任何素數(shù)均為 3級的素數(shù)。只有兩個強素數(shù)的積所構成的 n，其因子分解才是較難的數(shù)學問題。 （ 4） P和 q應大到使得因子分解 N為計算上不可能。 RSA的安全性依賴于大數(shù)的因子分解，若能因子分解模數(shù) N，則 RSA即被攻破，因此模數(shù) N必須足夠大直至因子分解 N在計算上不可行。因子分解問題為密碼學最基本的難題之一，如今，因子分解的算法已有 很大 的進步，但仍不足以說明 RSA可破解。為保證安全性，實際應用中所選擇的素數(shù) P和拿至少應該為 300位以上的二進制數(shù)，相應的模數(shù)Ⅳ河南理工大學畢業(yè)設計（論文）說明書 11 將是 600位以上的二進制數(shù)。 目前， SET(Secure Electronic Transaction)協(xié)議中要求 CA采用 2048比特長的密鑰，其他實體使用 1024比特的密鑰。隨著計算能力的提高和分布式運算的發(fā)展，安全密鑰的長度將是動態(tài)增長的。 Jadith Moore給出了使用 RSA時有關模數(shù)的一些限制： （ 1）若給定模數(shù)的一個加 /解密密鑰指數(shù)對已知，攻擊者就能分解這個模數(shù)。 （ 2）若給定模數(shù)的一個加 /解密密鑰指數(shù)對已知，攻擊者無需分解模 數(shù) 就可以計算出別的加 /解密密鑰指數(shù)對。 （ 3）在通信網(wǎng)絡中，利用 RSA的協(xié)議不應該使用公共模數(shù)。 （ 4）消息應該用隨機數(shù)填充以避免對加密指數(shù)的攻擊。 e 的選取原則 在 RSA算法中， e和 n互質(zhì)的條件容易滿足，如果選擇較小的 e，則加、解密的速度加快，也便于存儲，但會導致安全問題。 一般地， e的選取有如下原則： （ 1） e不能夠太小。在 RSA系統(tǒng)中，每人的公開密鑰 P只要滿足 ( , ( )) 1gcd e N? ?即可，也即 e可以任意選擇，為了減少加密運算時間，很多人采用盡可能小的 e值，如 3。但是已經(jīng)證明低指數(shù)將會導致安全問題，故此，一般選擇 e為 16位的素數(shù)，可以有效防止攻擊，又有較快速度。 （ 2） e應選擇使其在 mod ( )N? 的階為最大。即存在 i，使得 1 mod ( )ieN??