【導讀】RSA加解密系統(tǒng)的研究與實現(xiàn)

　　

【正文】 開密鑰是目前最難分解的一類合數(shù)，專用的分解方法和數(shù)域篩的方法都不會對這類數(shù)構成危險。對于在 100 位至 200 位之間的數(shù)，每增加 3位，則分解時間將增加一倍。由此推算，每秒 10 億次的計算機在一天內最多也就分解一個不到 100 位的合數(shù)；而分解一個 200 位的合數(shù)，用通用的方法，大概需要 (200 100)/3 102 10? ? 天的時間。現(xiàn)在，無論計算機的速度，還是數(shù)量，都不可能有超過 1010 倍的增長。目前，十進制 129 位的數(shù)也被分解，因此， n要大于這些數(shù)。為了使模 n的分解難以實現(xiàn)，要求： 1）模 n足夠大。這是為了防止采用窮舉搜索來尋找 n的因子。至于究竟 需要多大，和當前的因子分解技術和具體密碼系統(tǒng)的應用背景有關。只要滿足使因子分解的代價大于解密獲取的利益即可。 2)大素數(shù) p和 q應該足夠大，若 p或 q是小素數(shù)，窮舉搜索小素數(shù)集合，也會很快RSA加解密系統(tǒng)的研究與實現(xiàn) 第 24 頁 共 53 頁 找到 p， q。另外 p 和 q 相差不能太小，因為若 p和 q大小相若，則可通過對模 n 取平方根，較快地找到 p、 q。 3)大素數(shù) p和 q應為隨機產生，不能具有特殊形式或取自某個素數(shù)表，顯然，具有特殊形式的素數(shù)首先是因子分解的嘗試對象。 基于以上的分析來考慮，本文選取模為二進制 1024 位的 RSA 算法，采用隨機數(shù)產生函數(shù)結合 MillerRabin 素數(shù)檢測來產生大素數(shù)，且 p 和 q 的位數(shù)不相同，從一定程度上保證了算法的安全性。這些重要函數(shù)的實現(xiàn)將會在后續(xù)章節(jié)給出詳細的實現(xiàn)方案。 RSA參數(shù)的選擇 RSA遭受攻擊的很多情況是因為算法實現(xiàn)的一些細節(jié)上的漏洞所導致的，所以在使用 RSA算法構造密碼系統(tǒng)時，為保證安全，在生成大素數(shù)的基礎上，還必須認真仔細選擇參數(shù)，防止漏洞的形成。根據(jù) RSA加解密過程，其主要參數(shù)有三個：模數(shù) N，加密密鑰e，解密密鑰 d。 模數(shù) N的確定 雖然迄今人們無法證明，破解 RSA系統(tǒng)等于對 N因子分解，但一般相信 RSA系統(tǒng)的安全 性等同于因子分解，即：若能分解因子 N，即能攻破 RSA系統(tǒng)，若能攻破 RSA系統(tǒng)，即能分解因子Ⅳ。因此，在使用 RSA系統(tǒng)時，對于模數(shù) N的選擇非常重要。在 RSA算法中，通過產生的兩個大素數(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的確定可以遵循以下幾個原則： ① P和ｑ之差要大。 當 p和 q相差很小時，在已知 n的情況下，可假定二者的平均值 2pq? 為 n ，然后利用 22( ) ( )22p q p qN????，若等式右邊 2()2pq? 可開方，則得到 ()2pq? 及華北科技學院畢業(yè)設計（論文） 第 25 頁 共 53 頁 ()2pq? ，即 N被分解。 ② P— l和 q一 1的最大公因子應很小。 ③ 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 r s s 稱為 3級的素數(shù)， 1p ， 2p 稱為 2級的素數(shù)， P則稱為 1級的素數(shù)，很明顯地，任何素數(shù)均為 3級的素數(shù)。只 有兩個強素數(shù)的積所構成的 n，其因子分解才是較難的數(shù)學問題。 ④ P和 q應大到使得因子分解 N為計算上不可能。 RSA的安全性依賴于大數(shù)的因子分解，若能因子分解模數(shù) N，則 RSA即被攻破，因此模數(shù) N必須足夠大直至因子分解 N在計算上不可行。因子分解問題為密碼學最基本的難題之一，如今，因子分解的算法已有長足的進步，但仍不足以說明 RSA可破解。為保證安全性，實際應用中所選擇的素數(shù) P和拿至少應該為 300位以上的二進制數(shù)，相應的模數(shù)Ⅳ將是 600位以上的二進制數(shù)。 目前， SET(Secure Electronic Transaction)協(xié)議中要求 CA采用 2048比特長的密鑰，其他實體使用 1024比特的密鑰。隨著計算能力的提高和分布式運算的發(fā)展，安全密鑰的長度將是動態(tài)增長的。 Jadith Moore給出了使用 RSA時有關模數(shù)的一些限制： ①若給定模數(shù)的一個加 /解密密鑰指數(shù)對已知，攻擊者就能分解這個模數(shù)。 ②若給定模數(shù)的一個加 /解密密鑰指數(shù)對已知，攻擊者無需分解模數(shù)Ⅳ就可以計算出別的加 /解密密鑰指數(shù)對。 ③在通信網(wǎng)絡中，利用 RSA的協(xié)議不應該使用公共模數(shù)。 ④消息應該用隨機數(shù)填充以避免對加密指數(shù)的攻擊。 e的選取原則 在 RSA算法中， e和矽 (Ⅳ )互質的條件容易滿足，如果選擇較小的 e，則加、解密的RSA加解密系統(tǒng)的研究與實現(xiàn) 第 26 頁 共 53 頁 速度加快，也便于存儲，但會導致安全問題。 一般地， e的選取有如下原則： ① e不能夠太小。在 RSA系統(tǒng)中，每人的公開密鑰 P只要滿足 ( , ( )) 1gcd e N? ?即可，也即 e可以任意選擇，為了減少加密運算時間，很多人采用盡可能小的 e值，如 3。但是已經(jīng)證明低指數(shù)將會導致安全問題，故此，一般選擇 e為 16位的素數(shù)，可以有效防止攻擊，又有較快速度。 ② e應選擇使其在 mod ( )N? 的階為最大。即存在 i，使得 1 mod ( )ieN?? ， ( 1) ( 1)2pqi ? ? ?? 39?？梢杂行Э箵艄?。 d的選取原則 一般地，私密密鑰 d要 大于 14N 。在許多應用場合，常希望使用位數(shù)較短的密鑰以降低解密或簽名的時間。例如 IC卡應用中， IC卡 CPU的計算能力遠低于計算機主機。長度較短的 d可以減少 IC卡的解密或簽名時間，而讓較復雜的加密或驗證預算 (e長度較長 )由快速的計算機主機運行。一個直接的問題就是：解密密鑰 d的長度減少是否會造成安全性的降低 ?很明顯地，若 d的長度太小，則可以利用已知明文 M加密后得 modeC M N? ，再直接猜測 d，求出 moddCN是否等于 M。若是，則猜測 J下確，否則繼續(xù)猜測。若 d的長度過小，則猜測的空間變小，猜中的可能性加大，已有證明當 d 14N 時，可以由連分式算 法在多項式時間內求出 d值。因此其長度不能過小。 華北科技學院畢業(yè)設計（論文） 第 27 頁 共 53 頁 5 RSA 算法的系統(tǒng)及實現(xiàn) 由前面的分析知道， RSA算法的實現(xiàn)都是基于大數(shù)的運算， RSA算法實現(xiàn)主要包括大素數(shù)的產生、密鑰對的產生和消息處理。大素數(shù)的產生是指大素數(shù) p和 q的產生，這是 RSA算法的基礎，沒有合適的 p， q， RSA就成了空話；密鑰對的產生，就是指公鑰和私鑰的產生，現(xiàn)代密碼系統(tǒng)的安全性幾乎完全等價于密鑰的安全性，因此，必須尋求合適的密鑰對，沒有理想的密鑰對， RSA將千里之堤，潰于蟻穴。所謂消息處理，指的是 RSA的四種操作：加密、解密、簽名、驗證，主要是 模冪運算，是 RSA算法的關鍵運算。 由此可見，實現(xiàn) RSA算法需要解決三個問題： 1) 如何產生大素數(shù) p和 q； 2) 如何產生加密和解密所需的密鑰 e和 d； 3) 如何實現(xiàn)模冪運算；由于其中涉及了大量的模運算和指數(shù)運算，因此這是 RSA算法實現(xiàn)的關鍵。 由前面分析可知， RSA算法可以應用于加密，解密，簽名，驗證中，且都是基于密鑰的模冪運算，區(qū)別僅在于輸入以及選取的密鑰不同，因此，本設計以 1024位的 RSA加密算法為例，說明 RSA公鑰體制的實現(xiàn)。 圖 51給出了 RSA加密過程的系統(tǒng)框圖： 圖 RSA算法的 系統(tǒng)框圖 隨機數(shù)產生 大素數(shù)產生 密鑰對生成 明文輸入 密文輸出 模冪運算 RSA加解密系統(tǒng)的研究與實現(xiàn) 第 28 頁 共 53 頁 RSA加密系統(tǒng)的實現(xiàn)流程圖如圖 5． 2所示 ： 圖 RSA加密系統(tǒng)框圖 5． 1 大素數(shù)生成實現(xiàn) 從 2． 3可知， RSA算法的首要條件是產生大素數(shù) p和 q，用以構成模 n，這是整個算法的基礎。早在兩千多年前，古希臘學者歐幾里德 (Euclid)就在其名著《幾何原木》中給出證明：素數(shù)有無窮多個。自從 Euclid證明了素數(shù)的無限性后，兩千多年來數(shù)學家及數(shù)學愛好者一直企圖找出產生素數(shù)的公式。 此類方法中較著名的有 SolovayStrassen有算法、 Lehmann算法、 MillerRabin算法等。在實際中應用最多的是 MillerRabin素數(shù)檢測，也稱為偽素數(shù)檢測。 MillerRabin素數(shù)檢測法描述如下：首先選取待測的隨機數(shù) n，計算 b， 2b 是能夠整除 n1的 2的最大冪數(shù)。然后計算 m，使得 n=2b m+l。 明文輸入 隨機數(shù)產生 得到密鑰 e 和 d 選擇 e，求乘法逆元 d 產生大素數(shù) p 和 q MillerRabin 素數(shù)檢測 模冪運算 密文輸出 華北科技學院畢業(yè)設計（論文） 第 29 頁 共 53 頁 1)隨機選取 a∈ (1， n)； 2)設 j=O，算 modmz a n? ； 3)若 z=l或者 z=n1則 n通過測試，可能是素數(shù)； 4)如果 jO或者 z=1，則 n不是素數(shù)； 5)令 j=j+1，若 jb且 z≠ n一 1令 2 modz z n? ，然后回到 4)步； 若 z=n1，則 n通過檢測，可能是素數(shù)； 6)若 j=b，且 z≠ n1，則 n不是素數(shù)。 對 a選取 k個不同的隨機值，重復 k次這樣的運算，若 n都能通過這樣的測試，則可斷定 n不是素數(shù)的概率不超過 4k? 。 但是在實際應用中，為了減少計算量，加速產生素數(shù)，采用了如下的實現(xiàn)步驟： 1）產生一個 n比特的隨機數(shù) P； 2)設置最高位和最低位為 1(最高位為 1確保素數(shù)達到要求的位數(shù)，最低位為 1確保它是奇數(shù) )。 3)對 P用小素數(shù) 3， 5， 7， 11等篩值。在具體的實現(xiàn)中可以測試 P是否被小于 256的所有素數(shù)整除，本設計中采用的是測試 P對所有小于 1023的素數(shù)的整除性。 4)用一個隨機數(shù) a對 P作 MillerRabin測試。若 P通過測試，則產生另一個 a重新測試。通常做 5次測試后， P為素數(shù)的概率己經(jīng)很高 (超過 99． 9％ )，如果 P未能通過 5次測試，生成另一個 P重新進行測試。 上述第 3步稱作“篩值法”。進行 MillerRabin測試之前，對 P用小素數(shù)篩值，效果顯著。譬如，用 3， 5， 7篩值，則進入第 4步時去掉了 54％的奇數(shù)，用小于 100的所有素數(shù)篩值，去掉了 76％的奇數(shù)，用小于 256的所有素數(shù)篩值則去掉了 80％的奇數(shù)，??。事實上，用小于 n的所有素數(shù)篩值后，剩下的奇數(shù)占所有奇數(shù)的比例為 。 n越大， 就越小，去 掉的合數(shù)就越多，剩下的奇數(shù)為素數(shù)的概率就越大；當然， n選得越大，進入 MillerRabin正式測試之前的預計算量就越大。 針對 RSA算法，素數(shù)的 p和 q的選取應該使得 n=p q的分解不可行。對 p和 q的主要限制是，首先，為避免橢圓曲線因子分解算法， p和 q應有大致相同的比特長度。考慮上述情況，本設計采取的方案如下： RSA加解密系統(tǒng)的研究與實現(xiàn) 第 30 頁 共 53 頁 確定大素數(shù) p和 q的長度：本設計采用 1024位的模值，因此 p和 q的位數(shù)大約為 512位，考慮到 p和 q不能太接近，也不能取太小的值，我們取素數(shù) p的比特長為 500～ 510之間的值，然后再定素數(shù)的長 (為模 n的 長度減去素數(shù) P的長度 )。 確定搜索空問：得到了大素數(shù) p及 q的長度，我們就可以在該長度范圍內隨機搜索大素數(shù) p和 q，由素數(shù)定理知，在比特長為 512的自然數(shù)中，大約每 178個連續(xù)的奇自然數(shù)，就有一個素數(shù)口 J。因而，對我們選取的自然數(shù)區(qū)域 [N， N+t]， t=k*178， N是隨機數(shù)，其長為所求素數(shù)的長度，即比特長在 512左右，該區(qū)域基本上會含有素數(shù)。為保險起見，可增大自然數(shù)區(qū)域的長度，即增加 t的值，這里取 k=3。 篩值：先用值小于 r的小素數(shù)，對自然數(shù)區(qū)域 [N， N+t]進行篩值，篩去 是這些小素數(shù)的倍數(shù)的合數(shù)?？紤]到篩 值算法的計算量隨 r的加大增加得并 不太多，我們取 r為 1023。 MillerRabin檢測：這是目前最實用、效率最高、計算量最小的算法。該算法中，需要選取和待測自然數(shù) n互素的隨機數(shù) a， n屬于 [N， N+t]， an。為節(jié)省計算量，我們取a為篩值算法中使用的小素數(shù)，它們顯然滿足要求。