【正文】 該算法中，需要選取和待測自然數(shù) n互素的隨機(jī)數(shù) a， n屬于 [N， N+t]， an。為保險(xiǎn)起見，可增大自然數(shù)區(qū)域的長度，即增加 t的值，這里取 k=3。對 p和 q的主要限制是，首先，為避免橢圓曲線因子分解算法， p和 q應(yīng)有大致相同的比特長度。譬如，用 3， 5， 7篩值，則進(jìn)入第 4步時去掉了 54％的奇數(shù)，用小于 100的所有素?cái)?shù)篩值，去掉了 76％的奇數(shù)，用小于 256的所有素?cái)?shù)篩值則去掉了 80％的奇數(shù)，??。若 P通過測試，則產(chǎn)生另一個 a重新測試。 但是在實(shí)際應(yīng)用中，為了減少計(jì)算量，加速產(chǎn)生素?cái)?shù)，采用了如下的實(shí)現(xiàn)步驟： 1）產(chǎn)生一個 n比特的隨機(jī)數(shù) P； 2)設(shè)置最高位和最低位為 1(最高位為 1確保素?cái)?shù)達(dá)到要求的位數(shù)，最低位為 1確保它是奇數(shù) )。 MillerRabin素?cái)?shù)檢測法描述如下：首先選取待測的隨機(jī)數(shù) n，計(jì)算 b， 2b 是能夠整除 n1的 2的最大冪數(shù)。早在兩千多年前，古希臘學(xué)者歐幾里德 (Euclid)就在其名著《幾何原木》中給出證明：素?cái)?shù)有無窮多個。所謂消息處理，指的是 RSA的四種操作：加密、解密、簽名、驗(yàn)證，主要是 模冪運(yùn)算，是 RSA算法的關(guān)鍵運(yùn)算。若 d的長度過小，則猜測的空間變小，猜中的可能性加大，已有證明當(dāng) d 14N 時，可以由連分式算 法在多項(xiàng)式時間內(nèi)求出 d值。例如 IC卡應(yīng)用中， IC卡 CPU的計(jì)算能力遠(yuǎn)低于計(jì)算機(jī)主機(jī)。即存在 i，使得 1 mod ( )ieN?? ， ( 1) ( 1)2pqi ? ? ?? 39。 一般地， e的選取有如下原則： ① e不能夠太小。 ②若給定模數(shù)的一個加 /解密密鑰指數(shù)對已知，攻擊者無需分解模數(shù)Ⅳ就可以計(jì)算出別的加 /解密密鑰指數(shù)對。為保證安全性，實(shí)際應(yīng)用中所選擇的素?cái)?shù) P和拿至少應(yīng)該為 300位以上的二進(jìn)制數(shù)，相應(yīng)的模數(shù)Ⅳ將是 600位以上的二進(jìn)制數(shù)。只 有兩個強(qiáng)素?cái)?shù)的積所構(gòu)成的 n，其因子分解才是較難的數(shù)學(xué)問題。 ③ P和 q必須為強(qiáng)素?cái)?shù)。相當(dāng)一部分的對 RSA的攻擊就是試圖分解模數(shù) N，選擇合適的Ｎ是實(shí)現(xiàn) RSA算法并防止漏洞的重要環(huán)節(jié)。 模數(shù) N的確定 雖然迄今人們無法證明，破解 RSA系統(tǒng)等于對 N因子分解，但一般相信 RSA系統(tǒng)的安全 性等同于因子分解，即：若能分解因子 N，即能攻破 RSA系統(tǒng)，若能攻破 RSA系統(tǒng)，即能分解因子Ⅳ。 基于以上的分析來考慮，本文選取模為二進(jìn)制 1024 位的 RSA 算法，采用隨機(jī)數(shù)產(chǎn)生函數(shù)結(jié)合 MillerRabin 素?cái)?shù)檢測來產(chǎn)生大素?cái)?shù)，且 p 和 q 的位數(shù)不相同，從一定程度上保證了算法的安全性。只要滿足使因子分解的代價大于解密獲取的利益即可。目前，十進(jìn)制 129 位的數(shù)也被分解，因此， n要大于這些數(shù)。 RSA 公鑰 密碼體制的公開密鑰是目前最難分解的一類合數(shù)，專用的分解方法和數(shù)域篩的方法都不會對這類數(shù)構(gòu)成危險(xiǎn)。 分解大整數(shù)模 n是最顯而易見的攻擊方法。 RSA 的安全性討論 判斷一個密碼系統(tǒng)是否安全，不能從算法設(shè)計(jì)角度分析，而應(yīng)該看其能否抵抗各種攻擊。攻擊者通過獲取明文消息的部分信息，進(jìn)而可以破譯或恢復(fù)整個明文信息。 設(shè) m是明文，兩個加密密鑰分別為 1e 和 2e ，共同的模數(shù)為 n，兩個密文為： 11 modec m n? 22 modec m n? 由于 1e 和 2e 是互素的，由擴(kuò)展的歐幾里德算法可以找到 r和 s，使之滿足 121re se?? 假設(shè) r是負(fù)數(shù) (其中必有一個為負(fù)數(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 ，則可以恢復(fù)出明文 m。采用小的 e、 d可以加快加密和驗(yàn)證簽名RSA加解密系統(tǒng)的研究與實(shí)現(xiàn) 第 22 頁 共 53 頁 的速度，而且所需的存儲空間小，但是如果 e、 d太小，則容易受到小指數(shù)攻擊，包括低加密指數(shù)攻擊和低解密指數(shù)攻擊。令攻擊者的消息為 X，他首先任取一個數(shù) N，計(jì)算 (mod )ey N n? (e是 T的公鑰 )，然后計(jì)算 M=yx，送給 T， T將簽名的結(jié)果 (mod )dMn送給攻擊者，則有： 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的簽 名。 ②騙取仲裁簽名。 隨 機(jī) 選 取 rn ，計(jì)算 1 (mod )ey r n? ，這意味 1(mod )dr y n? 。大整數(shù)分解研究一直足數(shù)論與密碼理論研究的重要課題。 RSA單向函數(shù)求逆的安全性沒有真正因式分解模數(shù)的安全性高，而且目前人們也無法證明這兩者等價。從嚴(yán)格的技術(shù)角度上來說這是不正確的，在數(shù)學(xué)上至今還未證明分解模數(shù)就是攻擊 RSA的最佳方法，也未證明分解大整數(shù)就是 NP問題 (表示那些能在多項(xiàng)式時間內(nèi)利用“不確定性 圖靈機(jī)可以求解的問題 )。 4S 計(jì)算 , (mod )Ae Am s n? 。在數(shù)字化世界里，則需要數(shù)字簽名和驗(yàn)證來取代手寫簽名功能， RSA就提供了這種數(shù)字簽名和驗(yàn)證機(jī)制。 3S 用戶 A通過網(wǎng)絡(luò)把密文 C發(fā)送給用戶 B。 RSA 應(yīng)用舉例 (1) 保密信息傳輸 這里通過例子來說明用戶之間用 RSA來進(jìn)行保密信息的傳輸，所采用的簡單協(xié)議僅僅是為了說明問題，在實(shí)際應(yīng)用中，為了安全，所采用的協(xié)議要復(fù)雜得多。加密過程用計(jì)算式表示為 modBe Bc m n? ●解密：輸入的待處理消息為密文 c，使用的密鑰為用 B的私鑰 ( , )BBdn；輸出為解密后的信息組明文 m。然而，它們的運(yùn)算核心相同，均為大數(shù)的模冪運(yùn)算，差別僅在于輸入輸出的不同，下面以數(shù)學(xué)表達(dá)式說明這四種處理過程。 1)取兩個大素?cái)?shù) p和 q(保密 )； 2)計(jì)算模 N=p q(公開 )，以及歐拉函數(shù) ()N? =(p一 1) (q1)(保密 )，其中 ()N? 是 N的歐拉函數(shù)值； 3)隨機(jī)選取整數(shù) e(公開 )，滿足 1e ()N? ,且 gcd(e， ()N? )=1； 4)計(jì)算 d(保密 )，滿足保密 d e≡ 1(mod ( )N? ),d是 e在模 ()N? 下的乘法逆元； 5)以（ e,N）為公鑰，（ d,N）為私鑰，銷毀 p,q, ()N? 。一般 求乘法逆元以歐幾里德算法為佳。因此在上述算法中， (a， n)=( 0r ， 1r )=(1r ， 2r )=? 1( , )mmrr? =。 歐幾里德算法是古希臘數(shù)學(xué)家歐幾里德給出的求兩個自然數(shù)的最大公約數(shù)的方法，如果 (a， n)=1，則 b一定存在。 華北科技學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 15 頁 共 53 頁 對于素?cái)?shù) P來說， ( ) 1pp? ??，所以費(fèi)爾馬定理實(shí)際是歐拉定理的一個推論。歐拉定理也有一種等價形式： ( ) 1 (mo d )ma a m? ? ? 。即 ()n? 為模 n既約剩余系中所有元素的個數(shù)。 所謂運(yùn)算 a mod n表示求 a被 n除的余數(shù)，成為模運(yùn)算。 完全剩余系 (Complete Set of Residues)：若將每一剩余類中取一數(shù)為代表，形成一個集合，則此集合稱為模 n的完全剩余系，以 Zn表示。目前，還沒有人能夠從理論上證明單向函數(shù)是存在的。若對任意 X1≠ X2， X1,X2∈ A，有 f(X1)≠ f(X2)，則稱 f為 1一 l映射，或可逆函數(shù)。單向函數(shù)不能直接用作密碼體制，因?yàn)槿绻脝蜗蚝瘮?shù)文進(jìn)行加密，即使是合法的接收者也不能還原出明文，因?yàn)閱蜗蚝瘮?shù)的逆運(yùn)算是難的。在公鑰密碼體制中最典型的就是 RSA公鑰加密算法，下面主要研究其原理與實(shí)現(xiàn)。 密碼體制的分類 密碼體制根據(jù)加密算法與 解密算法所使用的密鑰是否相同可以分為對稱密鑰體制和非對稱密鑰體制。鑒別服務(wù)包括對身份的鑒別和對數(shù)據(jù)源的鑒別。為提供這種安全屬性用戶必須有檢測非授權(quán)修改的能力?？偟膩碚f，在信息安全的諸多涉及方面中，密碼學(xué)主要為存儲和傳輸中的數(shù)字信息提供如下幾個方面的安全保護(hù)。因此，更有實(shí)際意義的是在計(jì)算上不可破譯的密碼體制。 密碼學(xué)中的安全性定義 荷蘭密碼學(xué)家 Kerckhoff對密碼 安全性分析做了如下假設(shè)：一個信息安全系統(tǒng)的安全性取決于對密鑰本身的保護(hù)，而不是對系統(tǒng)或者通信硬件的安全保護(hù)。 (Knownplaintext Attack)：密碼攻擊者知道一些明文和相應(yīng) 的密文。對抗這種攻擊方法是設(shè)法使明文的統(tǒng)計(jì)特性和密文的統(tǒng)計(jì)特性不一樣。對一個密碼系統(tǒng)采取截獲密文進(jìn)行分析的這類攻擊稱為被動攻擊 (Passive Attack)；另一種是主動攻擊 (Active Attack)，即非法入侵者主動向系統(tǒng)進(jìn)行攻擊，采取刪除、更改、增添、偽造等手段向系統(tǒng)插入假信息，以達(dá)到竊取非法華北科技學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 11 頁 共 53 頁 信息的目的。解密函數(shù) D(c)作用于密文來恢復(fù)明文，公式表示為 D(c)=m。 （ 3）密碼算法 (algorithm)：是用于加密和解密的數(shù)學(xué)函數(shù)，通常有兩個相關(guān)函數(shù)：一為加密，一為解密。在計(jì)算機(jī)通訊中，采用密碼技術(shù)將信息隱蔽起來，再將隱蔽后的信息傳輸出去，使信息在傳輸過程中即使被竊取或截獲，竊取者也不能了解信息的內(nèi)容，從而保證信息傳輸?shù)陌踩? RSA加解密系統(tǒng)的研究與實(shí)現(xiàn) 第 10 頁 共 53 頁 2 密碼學(xué)概述 密碼學(xué)的歷史極為久遠(yuǎn)，其起源可以追溯到遠(yuǎn)古時代，人類有記載的通信密碼始于公元前 400 年。介紹了大素?cái)?shù)的生成與檢測，模冪運(yùn)算的實(shí)現(xiàn)，大整數(shù)的四則運(yùn)算等。 第 4章 RSA算法 介紹。 第 2章密碼學(xué)概述。但是，隨著計(jì)算機(jī)軟、硬件的不斷發(fā)展，數(shù)據(jù)量也在急劇增大，對加密的速度要求也越來越高，人們需要不斷改進(jìn)加密算法，以提高加密運(yùn)算的速度。 RSR算法。其本質(zhì)是減小求冪運(yùn)算中的基數(shù)的大小，但并沒有考慮指數(shù)的情況，故只是在一定的程度上改進(jìn)了原算法的效率。由 Rivest等人在 RSA體制建立時提出，是把乘方后求模的計(jì)算改為在邊乘方邊求模的計(jì)算，以減小中間結(jié)果的數(shù)值，盡量避免大數(shù)的乘方計(jì)算。 國內(nèi)外研究 現(xiàn)狀與水平 RSA公鑰密碼體制是在 1978年由 R． L． Rivest， A． Shamir和 L． Adleman三人在文章《實(shí)現(xiàn)數(shù)字簽名和公鑰密碼體制的一種方法》中共同提出的，是最具代表性的公鑰密碼體制。其安全性也是基于數(shù)學(xué)上的一個難題：將兩個大素?cái)?shù)相乘比較容易，反之，將一個大數(shù)分解為素因子的乘積則比較困難。公鑰密碼體制既可用于密鑰傳遞又可用于數(shù)字簽名，用途十分廣泛，但速度較低，可以說，速度是其最顯著的缺陷。傳統(tǒng)密碼體制中 ，加密、解密使用相同的密鑰。信息安全技術(shù)在計(jì)算機(jī)和網(wǎng)絡(luò)通信中占有重要地位。計(jì)算機(jī)網(wǎng)絡(luò)在方便了人們生活的同時，也提高了人們的工作效率。密碼技術(shù)是信息安全的核心，它是實(shí)現(xiàn)保密性、完整性不可否認(rèn)的關(guān)鍵。public key cryptography。詳細(xì)的討論了大素?cái)?shù)的生成與實(shí)現(xiàn)，密鑰對的產(chǎn)生，模冪運(yùn)算的實(shí)現(xiàn)以及大整數(shù)的四則運(yùn)算。首先介紹了 RSA算法的數(shù)學(xué)理論基礎(chǔ)，其中包括歐拉函數(shù)與歐拉定理、費(fèi)爾馬定理，乘法逆元及其求法等。簡單的介紹了密碼體制根據(jù)加密算法與解密算法所使用的密鑰是否相同可以分為對稱密鑰體制和非對稱密鑰體制。 RSA密碼算法體制是一種公開密鑰算法，其加密密鑰和算法本身都 可以公開，解密密鑰則歸用戶私人擁有。 RSA加解密算法的實(shí)現(xiàn)主要在大素 數(shù)的產(chǎn)生，密鑰對的生成，模冪運(yùn)算的實(shí)現(xiàn)以及大整數(shù)的存儲與運(yùn)算這四方面的問題。 RSA密碼體制是目前比較成 熟的公鑰密碼體制，可用于數(shù)據(jù)加解密、數(shù)字簽名、身份驗(yàn)證等。對稱密鑰算法中，加密、解密都使用相同的密鑰。例如網(wǎng)上銀行的開通、網(wǎng)上購物的流行以及企業(yè)之間的商業(yè)機(jī)密，銀行與銀行之間的業(yè)務(wù)往來，這一切的一切都離不開信息的安全傳輸。因此在當(dāng)前的網(wǎng)絡(luò)環(huán)境下，敏感信息的保護(hù)已經(jīng)成為一個很重要的問題，一個安全、健壯的信息系統(tǒng)離不開各種信息安全技術(shù)的支持。非對稱密鑰算法又稱公鑰密碼算法，即加密、解密使用兩個不同的密鑰。在各種安全或認(rèn)證領(lǐng)域，如 WEB服務(wù)器和瀏覽器信息安全、 Email的安全和認(rèn)證、對遠(yuǎn)程登陸的安全保證和各種電子信用卡系統(tǒng)，起著安全核心的作用，而用微電子技術(shù)將加密算法轉(zhuǎn)換成硬件實(shí)現(xiàn)，不僅加解密速度快，而且抗物理攻擊能力強(qiáng)，所以研究如何用硬件快速實(shí)現(xiàn) RSA有著重要的現(xiàn)實(shí)意義。本論文根據(jù)這幾方面的問題一一做了詳細(xì)的介紹，其中大素?cái)?shù)的產(chǎn)生采用 MillerRabin素?cái)?shù)檢測法。從誕生那天起， RSA就因?yàn)榘踩珡?qiáng)度高、使用方便等卓越性能受到關(guān)注，并得到廣泛應(yīng)用。對稱密鑰體制中，加密、解密都使用相同的密鑰。詳細(xì)描述了加密與解密的原理和 RSA算法容易受到的各種攻擊以及 RSA的參數(shù)選擇與安全性問題。 關(guān)鍵詞： RSA；公鑰密碼系統(tǒng)；大素?cái)?shù)；模冪運(yùn)算 華北科技學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 5 頁 共 53 頁 RSA encryption algorithm of research and implementation INTRODUCTION Since 1990,with the rapid development of puter and work technology has been applied to all the field in pe