畢業(yè)設計（論文）基于RSA的加密解密系統(tǒng)的設計與實現(xiàn)

1、武漢工程大學郵電與信息工程學院武漢工程大學郵電與信息工程學院 畢業(yè)設計（論文）畢業(yè)設計（論文） 基于基于 rsarsa 的加密解密系統(tǒng)的設計與實現(xiàn)的加密解密系統(tǒng)的設計與實現(xiàn) basedbased onon rsarsa encryptionencryption andand decryptiondecryption systemsystem designdesign andand implementationimplementation 學生姓名 學 號 專業(yè)班級 網(wǎng)絡工程網(wǎng)絡工程 0701 指導教師 2011 年年 5 月月 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 作者聲明作者聲明

2、本人聲明所呈交的論文是我個人在導師指導下進行的研究工作及取得的研究 成果，除了文中特別加以標注的地方外，沒有任何剽竊、抄襲、造假等違反學術 道德、學術規(guī)范的行為，也沒有侵犯任何其他人或組織的科研成果及專利。與我 一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示了 謝意。如本畢業(yè)設計（論文）引起的法律結果完全由本人承擔。 畢業(yè)設計（論文）成果歸武漢工程大學郵電與信息工程學院所有。 特此聲明。 作者專業(yè)： 作者學號： 作者簽名： _年_月_日 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 摘摘 要要 隨著電子計算機的飛速發(fā)展，全球網(wǎng)絡普遍化。人們的工作、生活、學習都 離不開網(wǎng)

3、絡。然而在網(wǎng)絡的互相交流、保證個人的安全、隱私非常的重要。 本論文闡述了密碼在網(wǎng)絡生活中的重要作用。密碼技術是保護信息安全的 主要手段之一。它不僅具有保證信息機密性的信息加密功能，而且具有數(shù)字簽 名、身份驗證、秘密分存、系統(tǒng)安全等功能。因此，使用密碼技術不僅可以保 證信息的機密性，而且可以保證信息的完整性和確定性，防止信息被篡改、偽 造和假冒。rsa 公鑰密碼算法是迄今為止在理論上最為成熟、完善的公鑰密碼 體制。 從提出到現(xiàn)在已經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為 是目前最優(yōu)秀的公鑰方案之一。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽 名和密鑰分配與管理的算法。它易于理解和操作，也很流

4、行。 關鍵詞：關鍵詞：rsa 加密 解密 公鑰 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） abstract along with the rapid development of computer, and a global network generalization. peoples work, life and study is inseparable from the network. however, in the mutual exchanges and communication network. ensure personal security, privacy is v

5、ery important. this paper expounds the password on the network to the important role of life. password protect information security technology is one of the main means. it has not only ensuring information confidential information encryption functions, and with digital signatures, identity authentic

6、ation, secret points to save, system security, and other functions. therefore, using cipher technology can not only ensure the confidentiality of information, but also can ensure the completeness and uncertainty of information, prevent information tampered, forge and hypocrisy. rsa public-key crypto

7、system is by far the most mature in theory, perfect public key cryptosystems. now from pose to the test of experience various attacks for people to accept, gradually, generally, is now one of the most outstanding public-key scheme. it is the first can used for data encryption could also be used for

8、digital signatures and key distribution and management of the algorithm. it is easy to understand and operation, is also very popular. key words： rsa ; encryption; decryption; public key 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 1 目目 錄錄 第第 1 章章 rsa 簡紹簡紹.2 1.1 什么是 rsa.2 1.2 rsa 的速度 .3 1.3 加密算法的缺點 .3 1.4 rsa 算法描述 .4 第第

9、 2 章章 rsa 加密解密體質簡介加密解密體質簡介.5 2.1 公鑰密碼算法 .5 2.2 rsa 體質算法過程 .6 2.3 rsa 體質的實現(xiàn) .6 2.4 rsa 的安全性 .7 2.5 rsa 算法中的數(shù)字簽名 .8 2.6 明文加密及密文解密 .8 第第 3 章章 rsa 算法介紹和需求分析算法介紹和需求分析.9 3.1 公鑰加密算法 rsa.9 3.2 rsa 算法介紹 .11 3.3 rsa 算法需求分析 .12 3.4 rsa 算法特點 .14 3.5 rsa 的選擇密文攻擊 .15 3.6 rsa 的公共模數(shù)攻擊 .15 第第 4 章章 rsa 算法代碼及運行結果算法代碼及

10、運行結果.17 4.1 rsa 算法代碼 .17 4.2 rsa 算法結果分析 .24 第第 5 章章 總結與展望總結與展望.25 參考文獻參考文獻.26 致謝致謝.27 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 2 第第 1 章章 rsa 簡紹簡紹 一個公開環(huán)境下的信息加密，在加密算法是公開的情況下，唯一能保證 信息加密的是密鑰。在常規(guī)的對稱加密算法中，如 des，加密解密密鑰是相 同的，如信息的發(fā)送者和合法接收者使用相同的密鑰，意味前提條件為信息 發(fā)送者和合法接收者互相認識或者互相信任，而且意味著密鑰將分布在通信 的的每一個節(jié)點，由此帶來了密鑰管理問題。如果泄露了密鑰意味著公開了 所

11、有密鑰。 如果是加密密鑰和解密密鑰不相同，我們可以把加密密鑰公開作為公鑰， ，信息合法的接收者保管解密密鑰作為私鑰，則以上提到的問題可以解決。 公鑰密碼體制于 1976 年由 w.diffie 和 m.hellman 提出，同時， r.merkle 也獨立提出了這一體制。這種密碼體制采用了一對密鑰加密密 鑰和解密密鑰（且從解密密鑰推出加密密鑰是不可行的） ，這一對密鑰中， 一個可以公開（稱之為公鑰） ，另一個為用戶專用（私鑰） 。 rsa 算法是目前應用最廣的公鑰密碼，有 rivest，shamir 和 adleman 在 1977 年提出，它基于一個非常簡單的數(shù)論難題，很容易將兩個素數(shù)相乘，

12、 但分解該乘積卻十分艱難，從而，該乘積可以公開且可作為加密密鑰。不能 從該乘積恢復出這倆個素數(shù)。解密密鑰需要用到這兩個素數(shù)。從而用很簡單 的形式實現(xiàn)了非常可靠的密碼系統(tǒng)。 1.11.1 rsarsa 算法簡介算法簡介 rsa 算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。 rsa 是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種 攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。rsa 的 安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 rsa 的難度與大數(shù) 分解難度等價。即 rsa 的重大缺陷是無法從理論上把握它的保密性能如何，而 且密碼學界

13、多數(shù)人士傾向于因子分解不是 npc 問題。 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 3 1.21.2 rsarsa 的速度的速度 由于進行的都是大數(shù)計算，使得 rsa 最快的情況也比 des 慢上好幾倍，無 論是軟件還是硬件實現(xiàn)。速度一直是 rsa 的缺陷。一般來說只用于少量數(shù)據(jù)加 密。rsa 的速度比對應同樣安全級別的對稱密碼算法要慢 1000 倍左右。 1.31.3 加密算法的缺點加密算法的缺點 （1）產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術的限制，因而難以做到一次一密。 （2）rsa 的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 rsa 的難度與大數(shù)分解難度等價，而且密碼學界多

14、數(shù)人士傾向于因子分解不是 npc 問題。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保 留了輸入的乘法結構： n mod dmxddxm 這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征每個人都能使用公 鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議， 保證工作過程中實體不對其他實體任意產(chǎn)生的信息解密，不對自己一無所知的信 息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用 one-way hash function 對文檔作 hash 處理，或同時使用不同的簽名算法。除了利用公共 模數(shù)，人們還嘗試一些利用解密指數(shù)或等等攻擊. n （3）速度太慢

15、,由于 rsa 的分組長度太大，為保證安全性，n 至少也要 600 bitx 以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量 級；且隨著大數(shù)分解技術的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。 目前，set(secure electronic transaction)協(xié)議中要求 ca 采用 2048 比特長的密鑰， 其他實體使用 1024 比特的密鑰。為了速度問題,目前人們廣泛使用單,公鑰密碼結 合使用的方法,優(yōu)缺點互補:單鑰密碼加密速度快,人們用它來加密較長的文件,然后 用 rsa 來給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發(fā)問題。 武漢工程大學郵電與信息工程學院畢

16、業(yè)設計（論文） 4 1.41.4 rsarsa 算法描述算法描述 rsa 的安全性依賴于大數(shù)分解。公鑰和私鑰都是兩個大素數(shù)（ 大于 100 個 十進制位）的函數(shù)。據(jù)猜測，從一個密鑰和密文推斷出明文的難度等同于分解兩 個大素數(shù)的積。 1.1 密鑰的生成 (1)選擇兩個大素數(shù)， 和。計算： pq pqn 和歐拉函數(shù)值： 11qpn (2)隨機取一整數(shù) ,且 和互素。此時求的滿足：e ne1e nd nedmod1 則 ad 1 nmod （3）將 和作為公開密鑰，作為私人密鑰。end 其中，, , ,和都是私密的陷門（四項并不是相互獨立的） ，這p q nd 些信息是不可以泄漏的。 1.2 加密

17、（1）獲得信息接收者的公開密鑰ene, （2）將明文分組：, , ,使得每個, ,1,2，0mm 1m1mknmi 0n 1k （3）對每一組明文組用以下公式變換 e mimiecinmod （4）得到密文,，0cc 1c2c1ck 1.3 解密 （1）對每一組密文做解密變換 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 5 d cicidminmod （2）合并分組得到明文，,，0mm 1m2m1mk 第第 2 章章 rsa 加密解密體質簡介加密解密體質簡介 rsa 公鑰密碼算法是迄今為止在理論上最為成熟、完善的公鑰密碼體制。 從提出到現(xiàn)在已經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是

18、目前最優(yōu) 秀的公鑰方案之一。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名和密鑰分配 與管理的算法。它易于理解和操作，也很流行。因為它既可用于加密,又可用于簽 名,并為用戶的公開密鑰簽發(fā)公鑰證書、發(fā)放證書、管理證書等,提高了服務質量， 所以, rsa 公開密鑰密碼在當今的信息交換過程中已得到廣泛的應用和實踐， rsa 公鑰密碼體制在世界許多地方已經(jīng)成為事實上的標準。 2.12.1 公鑰密碼算法公鑰密碼算法 公鑰密碼算法最主要的特點是加密和解密使用不同的密鑰，且加密密鑰能公 開，而僅需保守解密密鑰的機密的密碼算法。在這種加密算法中，從公開的加密 密鑰無法推導出保密的解密密鑰，也無法從加密密鑰和密文恢

19、復出相應的明文。 最有影響的公鑰密碼算法是 rsa，它能抵抗到目前為止己知的所有密碼攻擊。 rsa 算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，算法的名字以發(fā) 明者的名字命名。rsa 算法的安全性依賴于大數(shù)分解問題的難解性。算法中使用 的公鑰和私鑰都是兩個大素數(shù)（大于 100 個十進制位）的函數(shù)。據(jù)猜測，從一個 密鑰和密文推斷出明文的難度等同于分解兩個大素數(shù)的積。rsa 算法在 isakmp/oakley 框架中被用做一種可能的身份認證方式。diffie-hellman 密鑰交 換算法是 isakmpioakley 框架的一個關鍵組成部分。在一個密鑰協(xié)商會話的開 始階段通信參與方通過使

20、用 diffe-hellman 算法產(chǎn)生雙方共享的密鑰，這些密鑰將 被用于密鑰協(xié)商協(xié)議的后續(xù)步驟。 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 6 在實際應用中，人們通常將對稱密鑰算法和公鑰密碼算法結合在一起使用， 以實現(xiàn)最佳性能。即使用某個對稱密鑰密碼體制來加密需傳遞的機要信息，而同 時使用 rsa 等非對稱密鑰密碼體制來傳送 des 的密鑰。這樣就可以綜合發(fā)揮兩 種密碼體制的優(yōu)勢，即 des 高速簡便性和 rsa 密鑰管理的方便和安全性。 2.22.2 rsarsa 體質算法過程體質算法過程 rsa 密碼體制使用了模的非負最小完全剩余系中的運算，這里 n 是兩個不n 同的素數(shù)和q的乘積

21、。rsa 體制的算法過程如下：p 首先產(chǎn)生密鑰，過程如下： （1）隨機產(chǎn)生兩個長度為位的素數(shù)和。2kpq （2）計算公鑰；（是位的長度）。qppublickeypublickeyk （3）隨機產(chǎn)生一個加密密鑰，2=keye=（n）-1，其中keye gcd（keye，（n）=1。 注意這是保證解密密鑰 keyekeyd mod()(n)=1 有解的充要條件，（n） 稱為 n 的歐拉函數(shù)，值為：（n）=（p-1）*（q-1）。 （4）求解解密密鑰 keyd=keye-1 mod （n） ，keye-1 為解密密鑰 keyd 的逆元 ，此公式原方程為（keyekeyd mod(n)=1）。 由此公

22、鑰，加密密鑰和解密密鑰全部產(chǎn)生。 其次，對明文加密或對密文進行解密，過程如下： （1）加密： c = mkeye mod publickey；其中 m 表示明文，c 表示密文。 （2）解密： m = ckeyd mod publickey； 其中 m 表示明文，c 表示密文。 2.32.3 rsarsa 體質的實現(xiàn)體質的實現(xiàn) rsa 密碼體制的實現(xiàn)是一個比較復雜的過程，它涉及到素數(shù)的產(chǎn)生、大整數(shù) 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 7 模運算等數(shù)學運算。rsa 體制中，p、q 均為大的素數(shù)，如何有效地產(chǎn)生大素數(shù) 將是實現(xiàn) rsa 體制所需解決的第一個問題。 通常情況下，人們使用一種

23、概率算法來產(chǎn)生大素數(shù)。這是因為 p、q 都是 大素數(shù)，如果使用因子分解的辦法來求素數(shù) p、q，這樣的難度與對 rsa 進行攻 擊（既分解大合數(shù)）實際上是相同的，在計算機是可行的。 概率算法的工作過程一般并不著眼于產(chǎn)生素數(shù)，而是首先隨機地產(chǎn)生一個 大奇數(shù)，然后使用概率性算法判定該奇數(shù)是否為素數(shù)（這樣的過程一般稱為素性 檢測）。 2.42.4 rsarsa 的安全性的安全性 rsa 的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上 的證明，因為沒有證明破解 rsa 就一定需要作大數(shù)分解。假設存在一種無須分 解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前，rsa 的一些變種算 法

24、已被證明等價于大數(shù)分解。不管怎樣，分解 n 是最顯然的攻擊方法。現(xiàn)在，人 們已能分解 140 多個十進制位的大素數(shù)。因此，模數(shù) n 必須選大一些，因具體適 用情況而定。若 n 被因式分解成功，則 rsa 便被攻破。還不能證明對 rsa 攻擊 的難度和分解 n 的難度相當，但也沒有比因式分解 n 更好的攻擊方法。已知 n， 求得(n)（n 的歐拉函數(shù)） ，則 p 和 q 可以求得。因為根據(jù)歐拉定理，(n) = (p-1) (q-1) = pq (p + q) + 1。和(p q )2 = (p + q)2 4pq；據(jù)此列出方程，求得 p 和 q。 另一個攻擊 rsa 的方法是根據(jù) c ae mo

25、d n 來計算 c1/e mod n。這種攻擊方 式?jīng)]有一種普遍的實現(xiàn)方法，也不知道是否其難度與對 n 因式分解相當。但是在 一些特殊的情況下，當多個相關的信息用同樣的密鑰加密時，可能很容易被攻破。 當然也有其他一些方法，不是面向完全攻破rsa，而只是希望得到一部 分信息或者針對 rsa 的實現(xiàn)用非一般性的手段來攻擊即使買通某些人得到 保密密鑰也是一種方法！ 為安全起見，對 p 和 q 要求：p 和 q 的相差不大；(p-1)和(q-1)有大素數(shù)因子； gcd(p-1,q-1)很小，滿足這樣條件的素數(shù)稱做安全素數(shù)。rsa 的出現(xiàn)使得大整數(shù)分 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 8

26、解因式這一古老的問題再次被重視，近些年來出現(xiàn)的不少比較高級的因數(shù)分解方 法使“安全素數(shù)”的概念也在不停的演化。所以，選擇傳統(tǒng)上認為是“安全素數(shù)” 并不一定有效的增加安全性，比較保險的方法就是選擇足夠大的素數(shù)。因為數(shù)越 大，對其分解因式的難度也就越大！對 n 和密鑰長度的選擇取決于用戶保密的需 要。密鑰長度越大，安全性也就越高，但是相應的計算速度也就越慢。由于高速 計算機的出現(xiàn)，以前認為已經(jīng)很具安全性的 512 位密鑰長度已經(jīng)不再滿足人們的 需要。1997 年，rsa 組織公布當時密鑰長度的標準：個人使用 768 位密鑰，公 司使用 1024 位密鑰，而一些非常重要的機構使用 2048 位密鑰。

27、當時的人們預計 到個人使用的 768 位密鑰將在兩年后就會生存期滿，那么也就是指今年！所以密 鑰長度的選取也要考慮到這個長度不再具效力的預計時間。 rsa 的安全性并不能僅靠密鑰的長度來保證。在 rsa 算法中，還有一種值 得注意的現(xiàn)象，那就是存在一些 n = pq，使得待加密消息經(jīng)過若干次 rsa 變換后 就會恢復成原文。這不能不說是 rsa 本身具有的一個缺點，選擇密鑰時必須注 意避免這種數(shù)。 2.52.5 rsarsa 算法中的數(shù)字簽名算法中的數(shù)字簽名 rsa 既可以用來加密數(shù)據(jù)，也可以用于身份認證。和 hash 簽名相比，在公 鑰系統(tǒng)中，由于生成簽名的密鑰只存儲于用戶的計算機中，安全系

28、數(shù)大一些。 rsa 算法中數(shù)字簽名技術實際上是通過一個哈希函數(shù)來實現(xiàn)的。數(shù)字簽名 的特點是它代表了文件的特征，文件如果發(fā)生改變，數(shù)字簽名的值也將發(fā)生變化。 不同的文件將得到不同的數(shù)字簽名。一個最簡單的哈希函數(shù)是把文件的二進制碼 累加，取最后的若干位。哈希函數(shù)對發(fā)送數(shù)據(jù)的雙方都是公開的。 2.62.6 明文加密及密文解密明文加密及密文解密 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 9 （1）明文加密 用戶加密密鑰(3,33)將數(shù)字化明文分組信息加密成密文。由 cme (mod n)得： 因此，得到相應的密文信息為：11，26，16。 （2）密文解密 用戶 b 收到密文，若將其解密，只需要計

29、算 mcd (mod n)，即： 用戶 b 得到明文信息為：11，05，25。根據(jù)上面的編碼表將其轉換為英 文，我們又得到了恢復后的原文“key”。 第第 3 章章 rsa 算法介紹和需求分析算法介紹和需求分析 3.13.1 公鑰加密算法公鑰加密算法 rsarsa 傳統(tǒng)的加密技術都是秘密密鑰加密技術，也稱單密鑰加密技術。也就是說， 消息發(fā)送者使用一把密鑰將消息加密，而消息接收者須使用同一密鑰將其解密。 比如數(shù)據(jù)加密標準 des。這就產(chǎn)生了一個重要的密鑰管理問題，如何告訴對方這 個密鑰。除非是在耳邊小聲告訴或者寄一封掛號信，如果在網(wǎng)路上傳輸，無論如 何也不能保證這個寶貴的密鑰不被一直肆機的敵人截

30、獲。這是一件很麻煩，有時 甚至是做不到的事，特別是，如果你想和許許多多你根本不認識的人實現(xiàn)秘密通 訊，用這種秘密密鑰加密技術就根本不可能。公開密鑰加密技術解決了這個難題。 在公開密鑰加密技術中，加密密鑰與解密密鑰是不一樣的。加密者可以將加密密 鑰公開，成為公開密鑰，而仍將解密密鑰保密，作為秘密密鑰。任何人如果想向 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 10 其發(fā)送加密消息，都可以找到公開密鑰，然而，以其加密的消息卻必須用加密者 自己保留的秘密密鑰才能解密，別人只知道公開密鑰，因而無法閱讀該消息。如 果想向另一個人發(fā)送加密消息，則可以先去找他的公開密鑰（既然是公開的，因 而往往不用與他

31、本人作事先聯(lián)系，甚至不必認識他） ，然后用此密鑰加密我想發(fā) 送的消息給他，除了他本人之外，別人是無法閱讀這個消息的。 下面就要描述 rsa 加密算法的流程了： 首先, 找出三個數(shù)： p、 q、 r，其中 p 和 q 是兩個相異的質數(shù)， r 是與 (p-1)(q-1) 互質的數(shù)。 接著, 找出 e, 使得 re 1 mod (p-1)(q-1)。這個 e 一定存在, 因為 r 與 (p-1) (q-1) 互質, 用輾轉相除法就可以得到了。 再來, 計算 n = pq。 （n，e）便是 public key。 （n，r）就是 private key。 p 和 q 應該被銷毀掉（pgp 為了用中國的

32、同余理論加快加密運算保留了 p 和 q， 不過它們是用 idea 加密過再存放的） 加密的過程是, 若待加密信息為 a, 將其看成是一個大整數(shù), 假設 a = n 的話, 就將 a 表成 s 進位 (s = n, 通常取 s = 2t)，則每一位數(shù)均小 于 n，然後分段編碼。 接下來, 計算 c ae mod n, (0 = c n)。b 就是編碼后的信息。 解碼的過程是, 計算 m br mod c (0 = c pq)，可以證明 m 和 a 其實是 相等的。也就是需要得到的沒有加密的信息。 如果第三者進行竊聽時, 他會得到幾個數(shù): m，n(=pq)，b。他如果要解碼的話, 必須想辦法得到

33、r。所以, 他必須先對 n 作質因數(shù)分解。如果他能夠成功的分解 n，得到這兩個質數(shù) p 和 q，那么就表明此算法被攻破。 rsa 算法是利用了數(shù)學中存在的一種單向性。一般說來，許多數(shù)學中的函數(shù) 都有“單向性” ，這就是說，有許多運算本身并不難，但如果你想把它倒回去， 作逆運算，那就難了。最簡單的例子：除法比乘法難，開方比乘方難，這是誰都 知道的。對于 rsa 來說，用公開密鑰加密后，如果想再通過公開密鑰解密是很 困難的。這個困難性就表現(xiàn)在對 n 的因式分解上。若 n=pq 被因式分解， （p-1） （q-1）就可以算出，繼而算出解密密鑰 m。所以 rsa 算法的基礎就是一個假設： 武漢工程大學

34、郵電與信息工程學院畢業(yè)設計（論文） 11 對 n 的因式分解是很困難的。 rsa 算法在理論上的重大缺陷就是并不能證明分解因數(shù)絕對是如此之困難， 也許我們?nèi)蘸罂梢哉业揭环N能夠快速分解大數(shù)的因數(shù)的算法，從而使 rsa 算法 失效。如果有人偶然發(fā)現(xiàn)了快速將大數(shù)分解因數(shù)的方法，并將其保密，則他有可 能在一段時間內(nèi)獲得極為巨大的力量。 目前 rsa 被廣泛應用于各種安全或認證領域，如 web 服務器和瀏覽器信息 安全、email 的安全和認證、對遠程登錄的安全保證和各種電子信用卡系統(tǒng)的核 心。 與單鑰加密方法比較，rsa 的缺點就是運算較慢。用 rsa 方法加密、解密、 簽名和認證都是一系列求模冪運算

35、組成的。在實際應用中，經(jīng)常選擇一個較小的 公鑰或者一個組織使用同一個公鑰，而組織中不同的人使用不同的 n。這些措施 使得加密快于解密而認證快于簽名。一些快速的算法比如基于快速傅立葉變換的 方法可以有效減少計算步驟，但是在實際中這些算法由于太復雜而不能廣泛的使 用，而且對于一些典型的密鑰長度它們可能會更慢。 3.23.2 rsarsa 算法介紹算法介紹 rsa 算法可以簡單敘述如下： 取素數(shù) p，q，令 n=pq. 取與(p-1)(q-1)互素的整數(shù) e， 由方程 de=1 (mod (p-1)(q-1)解出 d， 二元組(e,n)作為公開密鑰， 二元組(d,n)作為私有密鑰 b=ae mod

36、n，c=bd mod n. 附錄中給出了證明 a=c (mod n). rsa 公開密鑰加密算法自 20 世紀 70 年代提出以來，已經(jīng)得到了廣泛認可和 應用。發(fā)展至今，電子安全領域的各方面已經(jīng)形成了較為完備的國際規(guī)范。rsa 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 12 作為最重要的公開密鑰算法，在各領域的應用數(shù)不勝數(shù)。rsa 在硬件方面，以技 術成熟的 ic 應用于各種消費類電子產(chǎn)品。 rsa 在軟件方面的應用，主要集中在 internet 上。加密連接、數(shù)字簽名和數(shù) 字證書的核心算法廣泛使用 rsa。日常應用中，有比較著名的工具包 open ssl(ssl，security so

37、cket layer,是一個安全傳輸協(xié)議，在 internet 上進行數(shù)據(jù)保 護和身份確認。open ssl 是一個開放源代碼的實現(xiàn)了 ssl 及相關加密技術的軟 件包，由加拿大的 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è)級商務應用中。在當今

38、的企業(yè)級商務 應用中，不得不提及使用最廣泛的平臺 j2ee。事實上，在 j2se 的標準庫中，就為 安全和加密服務提供了兩組 api：jca 和 jce。 jca (java cryptography architecture)提供基本的加密框架，如證書、數(shù)字簽名、報文摘要和密鑰對產(chǎn)生器； jca 由幾個實現(xiàn)了基本的加密技術功能的類和接口組成，其中最主要的是 java.security 包，此軟件包包含的是一組核心的類和接口，java 中數(shù)字簽名的方法 就集中在此軟件包中。jce(java cryptography extension) 在 jca 的基礎上作了擴 展，jce 也是由幾個軟件包

39、組成，其中最主要的是 javax.crypto 包，此軟件包提供 了 jce 加密技術操作 api。javax.crypto 中的 cipher 類用于具體的加密和解密。 在上述軟件包的實現(xiàn)中，集成了應用 rsa 算法的各種數(shù)據(jù)加密規(guī)范，這些 api 內(nèi)部支持的算法不僅僅只有 rsa，但是 rsa 是數(shù)字簽名和證書中最常用的)，用 戶程序可以直接使用 java 標準庫中提供的 api 進行數(shù)字簽名和證書的各種操作。 3.33.3 rsarsa 算法需求分析算法需求分析 實現(xiàn) rsa 算法需要涉及以下幾個方面的問題 （1） 挑選加密用的素數(shù) （2） 如何提高機密算法的速度 武漢工程大學郵電與信息

40、工程學院畢業(yè)設計（論文） 13 （3） 加秘冪次 e,解密冪次 d 的選取 注：設 a1、a2 是兩個整數(shù)，d 是 a1、a2 的 最大公約數(shù)，記作 d=(a1,a2) 進行因式分解很困難，但是判定一個數(shù)是否是素數(shù)則簡單很多，所以試圖分 解隨機數(shù)是不可取的，正確的做法是對產(chǎn)生的隨機數(shù)測試是否為素數(shù)。測試的原 理是 fermat 小定理，對于一個待測試的奇數(shù) p，如果對于任意的小于 p 的 w,應該 有(w,p)=1，并且滿足: wm-11(mod p) 如果找到這個 w，可以看成是 p 是素數(shù)的一個證據(jù)，如果 p 和 w 關系不滿足 fermat 小定理，則立刻知道 p 不是素數(shù)，找到一個證據(jù)

41、可以認為 p 是素數(shù)的幾率 只有 50%，我們找到的證據(jù)越多，p 是素數(shù)的證據(jù)越充分，由此可以認為找到 k 個證據(jù)，p 不是素數(shù)的幾率只有 2-k。實際上還有一個例外，carmichael 數(shù)是所有 小于它的數(shù)都可以是他的素數(shù)的證據(jù)，即滿足 fermat 小定理的形式，但 carmichael 數(shù)是奇合數(shù)，但 carmichael 滿足一定條件，一個 carmichael 數(shù)總是沒 有平方因子，而且當且僅當所有 p 是可整除 m 的素數(shù)，而 p-1 也可整除 m-1 時， 一個沒有平方因子的奇合數(shù) m 是一個 carmichael 數(shù)。所以按照這個條件排除 carmichael 數(shù)。 實際的做

42、法是： （1） 產(chǎn)生一個 n 為的隨機數(shù) p； （2） 設高位和低位為 1，這樣確保 p 有 n 位且為奇數(shù)； （3） 檢查確保 p 不能被任何小素數(shù)整除:如 3,5,7，11 等，可以用算法測試 p 對小于 256 或者 2000 的所有素數(shù)的整除性； （4） 對某隨機數(shù) wp 運行如下測試，如果測試通過則另選一個 a，做五次。 測試方 法如下： 假定 p 是一個待測的奇數(shù)，設 2s 是可以整除 p-1 的 2 的最高次冪，即 p- 1=2sr step1:選擇一個數(shù) w，其中 1w1 則可以判定 p 不是素數(shù)； 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 14 step2:如果 wr1

43、(mod p)或 wr-1(mod p)，則 p 可能是素數(shù)； step3：s=1； step4:如果 ss，則 w(2s)r)-1(mod p)，則 p 可能是素數(shù)，w(2sr) 1(mod p)，則可能不是素數(shù)，否則 s=s+1,重復 step4： step5：這時 s=s，如果 w(2sr)1(mod p),則 p 可能是素數(shù)。 如果失敗，則可以表明 p 不是素數(shù)，如果通過 3、4 測試們不是素數(shù)的幾率 就很低了。 rsa 算法的加解密過程其實是一個冪運算和模運算相結合的過程，如果計 算 cme(mod n) 先計算 me,再計算 me(mod n)，米的運算量非常巨大，而且保存 me

44、也需要 很大的存儲空間，不失一般性地我們假設 m,e,均為 256 位，我們將我們需要的 log2（me）=e*log2(m)=2264 位來保存中間結果，可見采用直接的模冪運算是不 可行的。 加解密運算中的冪模運算我們可以乘法運算和求模運算實現(xiàn)，由于模運算對 加法乘法運算可分配，即： (a+b)mod n=(a mod n)+(b mod n) (a*b)mod n=(a mod n)*(b mod n) 所以可以對冪運算中和加法運算中的中間結果直接使用模運算，降低運算強 度，可以說，這是我們進行簡化的基礎。 加密冪次 e 和解密冪次 d 的選取 根據(jù)第一部分 rsa 算法的描述，e 和 d

45、 是相關的，其中的一個確定了，就可 以確定另外一個，從安全的角度而言，e 和 d 都應該大一些，否則如果 e,d 選取不 當，會導致一定的安全問題。但 e 和 d 的選取在一定程度上也會影響到加密的速 度。 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 15 3.43.4 rsarsa 算法特點算法特點 rsa 算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。 rsa 是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊 的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。rsa 的安全 性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 rsa 的難度與大

46、數(shù)分解 難度等價。即 rsa 的重大缺陷是無法從理論上把握它的保密性能如何，而且密 碼學界多數(shù)人士傾向于因子分解不是 npc 問題。 rsa 的缺點主要有：a)產(chǎn)生 密鑰很麻煩，受到素數(shù)產(chǎn)生技術的限制，因而難以做到一次一密。b)分組長度太 大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較 慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術的發(fā)展，這個長度還在 增加，不利于數(shù)據(jù)格式的標準化。目前，set(secure electronic transaction)協(xié)議 中要求 ca 采用 2048 比特長的密鑰，其他實體使用 1024 比特的密鑰。 這種算 法

47、 1978 年就出現(xiàn)了，它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。 它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：ron rivest, adishamir 和 leonard adleman。 rsa 算法是一種非對稱密碼算法，所謂非對 稱，就是指該算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。 rsa 的算法涉及三個參數(shù)，n、e1、e2。 其中，n 是兩個大質數(shù) p、q 的積， n 的二進制表示時所占用的位數(shù)，就是所謂的密鑰長度。 e1 和 e2 是一對相關 的值，e1 可以任意取，但要求 e1 與(p-1)*(q-1)互質；再選擇 e2，要求(e2*e1

48、) mod(p-1)*(q-1)=1。 (n 及 e1),(n 及 e2)就是密鑰對。 rsa 加解密的算法完 全相同,設 a 為明文，b 為密文，則：a=be1 mod n；b=ae2 mod n； e1 和 e2 可以互換使用，即： a=be2 mod n；b=ae1 mod n 3.53.5 rsarsa 的選擇密文攻擊的選擇密文攻擊 rsa 在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( blind)，讓擁有私鑰的實體簽署。然后，經(jīng)過計算就可得到它所想要的信息。實 際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘 武漢工程大學郵電與信息工程學院畢業(yè)設

49、計（論文） 16 法結構： ( xm )d = xd *md mod n 前面已經(jīng)提到，這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征-每個 人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用 好的公鑰協(xié)議，保證工作過程中實體不對其他實體任意產(chǎn)生的信息解密，不對自 己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首 先使用 one-way hashfunction 對文檔作 hash 處理，或同時使用不同的簽名算 法。在中提到了幾種不同類型的攻擊方法。 3.63.6 rsarsa 的公共模數(shù)攻擊的公共模數(shù)攻擊 若系統(tǒng)中共有一個模數(shù)，只是不同的人擁有不同的

50、 e 和 d，系統(tǒng)將是危險的。 最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信 息無需私鑰就可得到恢復。設 p 為信息明文，兩個加密密鑰為 e1 和 e2，公共模 數(shù)是 n，則： c1 = pe1 mod n c2 = pe2 mod n 密碼分析者知道 n、e1、e2、c1 和 c2，就能得到 p。 因為 e1 和 e2 互質，故用 euclidean 算法能找到 r 和 s，滿足： r * e1 + s * e2 = 1 假設 r 為負數(shù)，需再用 euclidean 算法計算 c1(-1)，則 ( c1(-1) )(-r) * c2s = p mod n 另外，還有

51、其它幾種利用公共模數(shù)攻擊的方法?？傊?，如果知道給定模數(shù)的 一對 e 和 d，一是有利于攻擊者分解模數(shù)，一是有利于攻擊者計算出其它成對的 e和 d，而無需分解模數(shù)。解決辦法只有一個，那就是不要共享模數(shù) n。 rsa 的小指數(shù)攻擊。 有一種提高 rsa 速度的建議是使公鑰 e 取較小的值， 這樣會使加密變得易于實現(xiàn)，速度有 所提高。但這樣作是不安全的，對付辦法就是 e 和 d 都取較大的值。 rsa 算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 17 rsa 是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊 的考驗

52、，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。rsa 的安全 性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 rsa 的難度與大數(shù)分解 難度等價。即 rsa 的重大缺陷是無法從理論上把握它的保密性能如何，而且密 碼學界多數(shù)人士傾向于因子分解不是 npc 問題。 rsa 的缺點主要有：a)產(chǎn)生密 鑰很麻煩，受到素數(shù)產(chǎn)生技術的限制，因而難以做到一次一密。b)分組長度太大， 為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢， 較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術的發(fā)展，這個長度還在增加， 不利于數(shù)據(jù)格式的標準化。目前，set( secure el

53、ectronic transaction )協(xié)議中要求 ca 采用比特長的密鑰，其他實體使用比特的密鑰。 第第 4 章章 rsa 算法代碼及運行結果算法代碼及運行結果 4.14.1 rsarsa 算法代碼算法代碼 #include #include #include typedef int elemtype; elemtype p,q,e; elemtype fn; elemtype m,c; int flag = 0; typedef void (*msghandler) (void); struct msgmap 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 18 char ch; ms

54、ghandler handler; ; /* 公鑰 */ struct pu elemtype e; elemtype n; pu; /* 私鑰 */ struct pr elemtype d; elemtype n; pr; /* 判定一個數(shù)是否為素數(shù) */ bool test_prime(elemtype m) if (m = 1) return false; else if (m = 2) return true; else for(int i=2; i 0) binn = b % 2; n+; b /= 2; /* 候選菜單，主界面 */ void init() cout*endl;

55、cout* welcome to use rsa encoder *endl; cout* e.encrypt *endl; cout* d.decrypt *endl; cout* s.setkey *endl; cout* q.quit *endl; cout*endl; coutpress a key: in2 ? in1 : in2); elemtype b = ( in1 in2 ? in1 : in2); in1 = a; 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 20 in2 = b; /* 求最大公約數(shù) */ elemtype gcd(elemtype a, elemty

56、pe b) order(a,b); int r; if(b = 0) return a; else while(true) r = a % b; a = b; b = r; if (b = 0) return a; break; /* 用擴展的歐幾里得算法求乘法逆元 */ elemtype extend_euclid(elemtype m, elemtype bin) order(m,bin); elemtype a3,b3,t3; a0 = 1, a1 = 0, a2 = m; b0 = 0, b1 = 1, b2 = bin; 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 21 if (

57、b2 = 0) return a2 = gcd(m, bin); if (b2 =1) return b2 = gcd(m, bin); while(true) if (b2 =1) return b1; break; int q = a2 / b2; for(int i=0; i=0; i-) f = (f * f) % n; if(bini = 1) f = (f * a) % n; 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 22 return f; /* 產(chǎn)生密鑰 */ void produce_key() coutpq; while (!(test_prime(p) coutpq

58、; ; pr.n = p * q; pu.n = p * q; fn = (p - 1) * (q - 1); coutfn = fnendl; coute; while(gcd(fn,e)!=1) coute is error,try again!; coute; pr.d = (extend_euclid(fn,e) + fn) % fn; pu.e = e; flag = 1; coutpr.d: pr.d pr.n: pr.nendl; 武漢工程大學郵電與信息工程學院畢業(yè)設計（論文） 23 coutpu.e: pu.e pu.n: pu.nendl; /* 加密 */ void enc

59、rypt() if(flag = 0) coutsetkey first:endl; produce_key(); coutm; c = modular_multiplication(m,pu.e,pu.n); coutc is:cendl; /* 解密 */ void decrypt() if(flag = 0) coutsetkey first:endl; produce_key(); coutc; m = modular_multiplication(c,pr.d,pr.n); coutm is:mendl; /* 消息映射 */ msgmap messagemap = s,produce_key