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

　　

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