RSA密碼體制研究及算法的局部改進和實現(xiàn)_畢業(yè)論文終結(jié)版

1、南 華 大 學畢業(yè)論文任務書學 院： 數(shù)理學院 題 目： 起 止 時 間： 2013 年 12 月 10日 至 2014 年 5 月 24日 學 生 姓 名： 專 業(yè) 班 級： 信息與計算科學 2010級01班 指 導 老 師： 系 主 任： 許友軍 院 長： 歐 陽 自 根 2013 年 12 月 18 日畢業(yè)論文的內(nèi)容及要求1. 畢業(yè)論文目標和內(nèi)容：充分掌握RSA密碼體制，以RSA算法為基礎(chǔ)，局部改進算法，盡量考慮在不過多增加計算機運算負擔的情況下提高算法的安全性，使改進的RSA密碼體制能得到初步的實現(xiàn)；然后，通過軟件設(shè)計實現(xiàn)算法。2. 畢業(yè)論文要求：1) 了解RSA密碼體制的數(shù)學基礎(chǔ)和不

2、足。2) 掌握相關(guān)的數(shù)學知識，并利用這些知識改進RSA算法。3) 熟練運用C語言編程。3. 畢業(yè)論文進度安排：2009-2010學年第1學期1. 11.911.16指導老師指導學生選題。2. 11.1712.10指導老師給學生下任務書。3. 12.1110年1月19日學生完成文獻綜述和開題報告。2009-2010學年第2學期4. 第一周第八周完成論文主體初稿。5. 第九周第十周中期檢查，指導教師審閱論文初稿，提出修改意見。6. 第十一周學生修改論文。7. 第十二周學生寫論文中英文摘要。8. 第十三周畢業(yè)論文定稿和裝訂成冊交指導老師和評閱老師。9. 第十四周畢業(yè)論文答辯。4. 主要參考文獻：1

3、密碼學（第二版），北京：機械工業(yè)出版社，2000,1-4002 Douglas R Stinson著，馮登國譯.密碼學原理與實踐（第二版）.北京：電子工業(yè)出版社，2003,1-2623 李紅軍，繆旭東.數(shù)據(jù)加密在網(wǎng)絡(luò)安全中的應用.微型機遇應用，2002（10）：31-334 潘承洞，潘成彪.數(shù)論（第二版）.北京：北京大學出版社，2004-115 李強，張繼永.一種改進得分RSA快速算法.小型微型計算機系統(tǒng)，2001,22（1）：70-726 周德新.實現(xiàn)RSA的高效算法.桂林電子工業(yè)學院學報，1996，（6）：1-57 Michael Welschenbach.密碼編碼學加密方法的C與C+實現(xiàn)

4、.北京：北京大學出版社，19998 譚浩強.C程序設(shè)計.北京：清華大學出版社，19959 陳運.一種新的快速RSA算法.電子科技大學學報，1996,24（2）：223-22810 陳運.一種組合RSA算法.電子科技大學學報，1996，25（2）：116-11911 Paul Garrett著，吳世忠等譯.密碼學導引.機械工業(yè)出版社，2003.8（注：不少于15篇參考文獻）南華大學本科生畢業(yè)論文開題報告數(shù)理學院 信息與計算科學 2010級 01班 設(shè)計（論文）題目RSA密碼體制研究及算法的局部改進和實現(xiàn)設(shè)計（論文）題目來源導師擬題設(shè)計（論文）題目類型理論研究型起止時間2013.10. 1-201

5、4.5.22一、 設(shè)計（論文）依據(jù)及研究意義： 自20世紀90年代以來，計算機網(wǎng)絡(luò)技術(shù)使得計算機應用得到進一步普及和發(fā)展，但是如何保證信息的安全卻是一個十分重要的問題。公鑰密碼體制中，解密和加密密鑰不同，解密和加密可分離，通信雙方無須事先交換密鑰就可建立起保密通信,較好地解決了傳統(tǒng)密碼體制在網(wǎng)絡(luò)通信中出現(xiàn)的問題。另外，隨著電子商務的發(fā)展，網(wǎng)絡(luò)上資金的電子交換日益頻繁，如何防止信息的偽造和欺騙也成為非常重要的問題。數(shù)字簽名可以起到身份認證，核準數(shù)據(jù)完整性的作用。而RSA算法在公鑰密碼體制和數(shù)字簽名中占有重要的地位。RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。從提出到現(xiàn)在已

6、近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。但RSA也是被研究得最廣泛的公鑰算法，再優(yōu)秀的密碼體制也存在著不足和安全隱患，因此對它進行適當改進，優(yōu)化它的算法是一件很有意義的工作。二、 設(shè)計（論文）主要研究的內(nèi)容、預期目標：（技術(shù)方案、路線）主要研究的內(nèi)容：改進RSA密碼體制所用到的數(shù)學知識，特別的數(shù)論方面；RSA加密解密算法和加密解密的過程；RSA的安全性和速度；根據(jù)RSA保密性能，如何優(yōu)化它的算法，使它的安全性和加解密時間達到更優(yōu)；如何設(shè)計軟件來更好的實現(xiàn)這種改進的RSA密碼體制。預期目標：首先，充分掌握RSA密碼體制，以RSA算法為基礎(chǔ)，局部改進算法

7、，盡量考慮在不過多增加計算機運算負擔的情況下提高算法的安全性，使改進的RSA密碼體制能得到初步的實現(xiàn)；然后，通過軟件設(shè)計實現(xiàn)算法。三、設(shè)計（論文）的研究重點及難點： 重點: 如何利用合適的數(shù)學知識來改進RSA的加密解密算法，使RSA算法的安全性和使用時間達到更優(yōu)。難點：如何設(shè)計軟件來更好的實現(xiàn)改進的RSA密碼體制。4 設(shè)計（論文）研究方法及步驟（進度安排）：方法：利用數(shù)學基礎(chǔ)知識對密碼體制算法進行優(yōu)化。步驟：第一步：充分的了解密碼學的相關(guān)背景和知識。 第二步：掌握RSA密碼體制的數(shù)學基礎(chǔ)知識。第三步：深入地對RSA密碼體制進行研究。第四步：針對RSA密碼體制的不足，對它進行適當?shù)母倪M。第五步：

8、對改進的RSA密碼體制進行設(shè)計軟件，使它初步的實現(xiàn)。第六步：進行設(shè)計測試用例。第七步：得出結(jié)論，分析改進的RSA密碼體制的優(yōu)缺點。5 進行設(shè)計（論文）所需條件：在指導老師的指導下，選擇各種有關(guān)參考資料。通過圖書館尋找有關(guān)參考文獻，通過網(wǎng)絡(luò)對RSA密碼體制進一步的認識。在設(shè)計軟件時，通過C語言編寫改進的RSA密碼算法，通過在計算機上實驗，最終得出結(jié)果。6 指導教師意見：簽名： 年 月 日RSA密碼體制研究及算法的局部改進和實現(xiàn)信息與計算科學專業(yè)2006級 （南華大學數(shù)理學院 湖南衡陽 ）指導老師： 摘要：密碼學是信息安全技術(shù)的核心，公鑰密碼體制又稱為雙鑰體制，其加、解密密鑰不同，可以公開加密密鑰

9、，而僅需保密解密密鑰，從而具有數(shù)字簽名、鑒別等新功能，被廣泛應用于金融、商業(yè)等社會生活各領(lǐng)域。RSA加密算法是第一個較為完善的公開密鑰算法。然而，該算法所采用的冪剩余計算會耗費太多的時間，一直是制約其廣泛應用的瓶頸。本文首先對RSA的數(shù)論基礎(chǔ)進行研究，并對RSA密碼體制進行分析；然后在此基礎(chǔ)上提出了一種高效算法，即在原算法的基礎(chǔ)上，對有關(guān)實現(xiàn)環(huán)節(jié)進行了部分的改進，從而提高了加密解密的速度；最后用C語言實現(xiàn)了改進的算法并進行了對比測試。本論文所介紹的算法雖然對RSA算法進行了某些局部改進，但還有一些不夠完善的地方，有待于進一步提高。關(guān)鍵詞：密碼學；RSA；快速算法；加密；解密Study on R

10、SA cryptosystem and partial improved algorithm and its realizationChangHeng XuSchool of Mathematics and Physical Sciences, University of South China,Hengyang, Hunan, China, ,Tutor: Abstract：Cryptography is the core of the information security. The public key system is also called the double key syst

11、em, where the encryption process is different with the decryption process. Since the public key system can publish its public key and keep its private key secret, it has part new applications such as the digital signature and authentication, which is widely used in every field of the society. RSA is

12、 the first quite perfect Public Key Algorithm. However the time-consuming modulo exponentiation computation, which has always been the bottleneck of RSA, restricts its wider application. First of all, this paper studies the number on the basis of RSA, and analyzes the RSA cryptosystem; Then on the b

13、asis, put forward an efficient algorithm, that is the basis of the original algorithm, right on the realization of part of the partial enhancement by improved the speed of encryption decryption; Finally, use Combined Language to implement the improved algorithm and have tested. Although this paper m

14、akes some improvement to the RSA algorithm, there are still some facets to be improved later.Keywords: Cryptography; RSA; Fast algorithm; Encryption; Decryption目錄摘要iAbstractii目錄iii引 言1第一章緒論21.1問題的提出21.2密碼學概述31.3RSA的研究意義41.4本論文研究內(nèi)容4第二章 RSA的數(shù)論基礎(chǔ)52.1數(shù)論的基本概況52.2歐拉函數(shù)、歐拉定理和費爾馬定理62.3同余及模運算6第三章 RSA密碼體制的分析與研

15、究83.1RSA簡述83.2RSA算法的描述93.3RSA計算方法123.3.1加密和解密123.3.2密鑰的生成123.3.3大數(shù)運算處理133.3.4素數(shù)的產(chǎn)生143.4RSA的安全性及分析163.4.1RSA的參數(shù)選擇173.4.2RSA的安全性分析193.5RSA的速度20第四章 RSA算法分析與改進214.1RSA算法分析214.1.1傳統(tǒng)RSA算法214.1.2目前主要的RSA算法244.2RSA算法的改進284.2.1對除法與取模進行改進284.2.2對BR (Binary Representation) 算法進行改進31第五章 RSA算法改進后的實現(xiàn)與測試335.1RSA實現(xiàn)的

16、語言的選擇335.2算法的設(shè)計流程345.3RSA加密體制的測試355.4原算法與新算法的比較39結(jié)束語41參考文獻42致 謝44引 言隨著計算機技術(shù)的快速發(fā)展促進了網(wǎng)絡(luò)技術(shù)的迅速發(fā)展與廣泛應用。通過網(wǎng)絡(luò)傳輸或獲取信息，已從軍事、政治、外交等重要領(lǐng)域日益普及到人們?nèi)粘Ｉ畹母鱾€領(lǐng)域。因而，保障信息在網(wǎng)絡(luò)傳輸?shù)倪^程中不受各種干擾破壞或不發(fā)生泄露，已成為當今信息時代的一個重要問題。保障信息的安全就是要保障信息在傳輸、獲取、存儲、處理以及使用的過程中，信息的機密性、完整性、不可抵賴性和可用性不受到無意或惡意破壞。如今許多傳統(tǒng)上基于紙面的簽字蓋章，諸如存單、支票、合同、租約等，已陸續(xù)轉(zhuǎn)化為數(shù)字電子媒體

17、的形式出現(xiàn)。這種轉(zhuǎn)化前景輝煌，雖然在技術(shù)上還存在些問題，但對社會、經(jīng)濟、生活產(chǎn)生了深刻的影響。保密通信進入計算機網(wǎng)絡(luò)，傳統(tǒng)密碼便暴露出它的嚴重弱點。傳統(tǒng)密碼要求通信雙方用的密鑰是通過秘密信道私下商定的，這本身就是極不安全的。RSA是一種國際公認的理想公鑰密碼體制，到目前為止仍不失為最有希望的一種公鑰密碼。它的基礎(chǔ)是數(shù)論的歐拉定理，其安全性依賴于大數(shù)的因數(shù)分解的困難性。它表達方式簡單，保密性強，沒有密鑰管理的麻煩；并且具有數(shù)字簽名、認證和鑒別等功能，特別適合于現(xiàn)代保密通信的需要。但它的主要障礙在于大數(shù)的模冪乘算法效率比較低，難以實際應用，所以提高大數(shù)模冪乘運算的效率便成為非常重要的課題。第一章

18、緒論1.1 問題的提出科技的發(fā)展，信息從基于紙面轉(zhuǎn)化為基于數(shù)字電子技術(shù)的形式，從中也產(chǎn)生了不少問題，在生成、傳輸、保存、驗證和鑒定等多方面出現(xiàn)了新技術(shù)需求、問題和困難。特別是安全問題：怎樣才能確保原始信息不被竊聽，不被偽造、篡改，怎樣確認信息發(fā)送者的真實性，怎樣才能保證信息發(fā)送者無法抵賴等等。而且，我們有很多的機密、甚至價值高的重要信息要在公開的網(wǎng)絡(luò)上傳送，這無疑增加了困難?！肮_密鑰密碼體制”的方法在一定的程度上成功地解決了一些問題，并在某個領(lǐng)域也得到了應用。在一定程度上說，網(wǎng)絡(luò)安全就是信息安全。信息的保密性、完整性、可用性、可靠性和不可抵賴性等相關(guān)技術(shù)都是信息安全的研究領(lǐng)域。信息安全的技術(shù)

19、可分為承載數(shù)據(jù)的系統(tǒng)安全、數(shù)據(jù)安全及事務安全三個方面。系統(tǒng)安全包括訪問控制、防火墻、物理隔離等保護技術(shù)，入侵檢測、安全審計、漏洞掃描、病毒掃描等檢測技術(shù)，還包括負載均衡、冗余備份等恢復技術(shù)。而密碼技術(shù)通過加密、鑒別、身份識別、數(shù)字簽名等機制構(gòu)成數(shù)據(jù)安全、事務安全的基本工具集。密碼技術(shù)和訪問控制技術(shù)共同構(gòu)成信息安全保護的核心技術(shù)。一般網(wǎng)絡(luò)信息安全保障的方法可分為兩大類：以防火墻技術(shù)為中心的被動防衛(wèi)；建立在數(shù)據(jù)加密上的開放型網(wǎng)絡(luò)安全保障技術(shù)。防火墻是一種由計算機硬件和軟件的組合，使互聯(lián)網(wǎng)與內(nèi)部網(wǎng)絡(luò)間建立起一個安全網(wǎng)關(guān)，保護內(nèi)部網(wǎng)免受非法用戶的侵入，即一個把互聯(lián)網(wǎng)與內(nèi)部網(wǎng)隔開的屏障。使用防火墻是保障

20、網(wǎng)絡(luò)安全的第一步，選擇一款合適的防火墻，是保護信息安全不可缺少的一道屏障。數(shù)據(jù)加密技術(shù)，也稱密碼技術(shù)，是與防火墻配合使用的安全技術(shù)，是為提高信息系統(tǒng)及數(shù)據(jù)的安全行和保密性，防止數(shù)據(jù)被外部竊取、破壞的主要技術(shù)手段。數(shù)據(jù)加密技術(shù)主要分為數(shù)據(jù)傳輸、數(shù)據(jù)存儲、數(shù)據(jù)完整性的鑒別以及密鑰管理技術(shù)四種。數(shù)據(jù)傳輸加密技術(shù)目的是對傳輸中的數(shù)據(jù)流加密；數(shù)據(jù)存儲加密技術(shù)目的是防止在存儲環(huán)節(jié)上的數(shù)據(jù)失密；數(shù)據(jù)完整性鑒別技術(shù)目的是對介入信息的傳送、存取、處理的人的身份和相關(guān)數(shù)據(jù)內(nèi)容進行驗證，一般包括口令、密鑰、身份、數(shù)據(jù)等項的鑒別；密鑰管理積水包括密鑰的產(chǎn)生、分配保存、更換與銷毀等環(huán)節(jié)上的保密措施。RSA算法是第一個既

21、能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，它易于理解，操作簡單。并且RSA被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已由二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，也被普遍認為是目前最優(yōu)秀的公鑰方案之一。但也有個缺點，RSA算法核心進行的都是大數(shù)計算，使得相同的條件下RSA最快情況也比DES慢上100倍，無論軟件還是硬件實現(xiàn)，速度一直是RSA的缺陷。所以，研究RSA的效率是最有意義的課題。隨著計算機的不斷發(fā)展，網(wǎng)絡(luò)的不斷普及，網(wǎng)絡(luò)安全更加成為人們的焦點，在這方面的研究領(lǐng)域?qū)⒆兊脑絹碓街匾?。我們也知道世上沒有絕對安全的網(wǎng)絡(luò)，只有相對安全的網(wǎng)絡(luò)。當然，網(wǎng)絡(luò)安全的其得也必須通過不斷地完善，不斷地對現(xiàn)階段的

22、安全系統(tǒng)進行改進，提高安全系數(shù)。1.2 密碼學概述密碼學的歷史悠久，可以追溯到遠古時代，人類有記載的通信密碼始于公元前400年。密碼學的一些常用基本概念有：密碼學是研究信息及信息系統(tǒng)安全傳統(tǒng)的科學，它起源于保密通信技術(shù)。密碼學又分為密碼編碼學與密碼分析學。研究如何對信息編碼，以實現(xiàn)信息及通信保密的科學成為密碼編碼學；研究如何破解或攻擊加密信息的科學稱為密碼分析學。明文是指發(fā)送方想要發(fā)給接受方的消息；密文是指明文被加密后的消息；加密是將明文變換為密文的過程；解密是將密文恢復為明文的過程。密碼學是在編碼與破譯的矛盾斗爭中逐步發(fā)展起來的，并隨著計算機等先進科學技術(shù)的發(fā)展與應用，已成為一門綜合性、交叉

23、性學科。它在發(fā)展中經(jīng)歷了4個階段：古典密碼術(shù)（手工操作密碼），有幾千年的歷史；第二階段機器密碼時代；第三階段是傳統(tǒng)密碼學，是種密碼技術(shù)或密碼術(shù)；第四階段是現(xiàn)代公鑰密碼學。如今，密碼學早已成為一門熱門的學科，在理論和方法上都有了巨大的發(fā)展。根據(jù)加密和解密是否相同，可以對它進行密碼體制的分類。大體分為單鑰密碼體制與雙鑰密碼體制兩類。單鑰加密體制，即從其中一個容易推出另一個，典型的有：DES、三重DES、AES等；雙鑰密碼體制（又稱公鑰密碼體制），它有兩個本質(zhì)上完全不同的密鑰，即利用私鑰持有人的相應公鑰對信息加密后通過公共信道發(fā)送給私鑰持有人，其典型的有RSA密碼體制等。1.3 RSA的研究意義 R

24、SA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的所有密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標準。RSA算法基于一個十分簡單的數(shù)論事實：將兩個大素數(shù)相乘十分容易，但那時想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也很流行。 RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界

25、多數(shù)人士傾向于因子分解不是NPC問題。RSA的缺點主要有：產(chǎn)生密鑰比較麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制。難以做到一次一密；分組長度太大，為保證安全性，n至少也要600bits以上，使運算代價很大，尤其是速度比較慢。1.4 本論文研究內(nèi)容本文對RSA密碼體制進行研究，對它的算法進行研究分析，提出RSA算法改進方案以提高計算效率。研究內(nèi)容：（1）對RSA的數(shù)論基礎(chǔ)進行研究；（2）對RSA密碼體制進行分析與研究；（3）對RSA算法進行分析與改進；（4）綜合以上研究，改進算法；（5）基于改進的算法，實現(xiàn)算法，測試結(jié)論。第二章 RSA的數(shù)論基礎(chǔ)在密碼學中需要使用到很多數(shù)學理論，例如數(shù)論、信息論、復雜度理論等

26、，他們是設(shè)計密碼系統(tǒng)及協(xié)議不可缺少的工具，其中數(shù)論是密碼學中（特別是公鑰密碼體制系統(tǒng)中）最重要的數(shù)學基礎(chǔ)，因此有必要對有關(guān)數(shù)學理論做些簡單的介紹，下面主要介紹RSA算法的數(shù)學基礎(chǔ)知識。2.1 數(shù)論的基本概況數(shù)論就是指研究整數(shù)性質(zhì)的一門理論。整數(shù)的基本元素是素數(shù)，所以，數(shù)論的本質(zhì)是對素數(shù)性質(zhì)的研究。數(shù)論大致上可以分為初等數(shù)論（古典數(shù)論）和高等數(shù)論（近代數(shù)論）。如今RSA算法主要應用到的是初等數(shù)論，下面我們就真對初等數(shù)論進行簡單的闡述。初等數(shù)論是數(shù)論中不求助于其他數(shù)學學科的幫助，研究數(shù)的規(guī)律，特別是整數(shù)性質(zhì)的數(shù)學分支。它是數(shù)論的一個最古老的分支。它以算術(shù)方法為主要研究方法，主要內(nèi)容有整數(shù)的整除理論

27、、同余理論、連分數(shù)理論和某些特殊不定方程。換言之，初等數(shù)論就是用初等、樸素的方法去研究數(shù)論。另外還有解析數(shù)論（用解析的方法研究數(shù)論。）、代數(shù)數(shù)論（用代數(shù)結(jié)構(gòu)的方法研究數(shù)論）。它有著悠久的歷史，初等數(shù)論已經(jīng)經(jīng)歷了2000年的歷史，公元前300年，歐幾里得發(fā)現(xiàn)了素數(shù)是數(shù)論的基石，他自己證明了有無窮多個素數(shù)。公元前250年古希臘數(shù)學家埃拉托塞尼發(fā)明了一種篩法。2000年來，數(shù)論學的一個最重要的任務，就是尋找一個可以表示所有素數(shù)的統(tǒng)一公式，或者稱為素數(shù)普遍公式，經(jīng)過人類巨大的心血，后來發(fā)現(xiàn)了一種篩法可以轉(zhuǎn)換成為一個素數(shù)產(chǎn)生公式。中國古代對初等數(shù)論的研究有也著光輝的成就，周髀算經(jīng)、孫子算經(jīng)、張邱建算經(jīng)、

28、數(shù)書九章等古文獻上都有記載。孫子定理比歐洲早500年， 西方常稱此定理為中國剩余定理，秦九韶的大衍求一術(shù)也馳名世界。如今初等數(shù)論不僅是研究純數(shù)學的基礎(chǔ)，也是許多學科的重要工具。它的應用是多方面的，如計算機科學、組合數(shù)學、密碼學、信息論等。如公開密鑰體制的提出是數(shù)論在密碼學中的重要應用。2.2 歐拉函數(shù)、歐拉定理和費爾馬定理歐拉函數(shù)：是一個定義在正整數(shù)上的函數(shù)，其值等于序列0，1，2，3，n-1中與n互素的數(shù)的個數(shù)。即(n)為模n既約剩余系中所有元素的個數(shù)。歐拉定理：對于互質(zhì)的正整數(shù)a和n，即a和n的最大公約數(shù)是1，則有a(n) 1 (mod n)。其中(n)稱為歐拉函數(shù)，它是比n小且與n互素的

29、正整數(shù)的個數(shù)。證明：首先證明下面這個命題：對于集合Zn=x1,x2,.,x(n),其中xi(i=1,2,(n)是不大于n且與n互素的數(shù)，即n的一個化簡剩余系，或稱簡系，或稱縮系)，考慮集合S = a*x1(mod n),a*x2(mod n),.,a*x(n)(mod n) ，則S = Zn 。證明：（1） 由于a,n互質(zhì)，xi也與n互質(zhì)，則a*xi也一定于p互質(zhì)，因此，任意xi，a*xi(mod n) 必然是Zn的一個元素 ；（2） 對于Zn中兩個元素xi和xj，如果xi xj 則a*xi(mod n) a*xi(mod n)，這個由a、p互質(zhì)和消去律可以得出。所以，很明顯，S=Zn 。既然

30、這樣，那么 （a*x1 a*x2.a*x(n)）(mod n) = （a*x1(mod n) a*x2(mod n) . a*x(n)(mod n)）(mod n) = （x1 x2 . x(n)）(mod n) ，考慮上面等式左邊和右邊，左邊等于(a*（x1 x2 . x(n)）) (mod n)，右邊等于x1 x2 . x(n)）(mod n)，而x1 x2 . x(n)(mod n)和n互質(zhì)根據(jù)消去律，可以從等式兩邊約去，就得到：a(n) 1 (mod n)費爾馬定理：a是不能被質(zhì)數(shù)p整除的正整數(shù)，則有a(p-1) 1 (mod p)，同樣有個推論，對于不能被質(zhì)數(shù)p整除的正整數(shù)a，有ap

31、 a (mod p)。證明這定理很簡單，由于(p) = p-1，代入歐拉定理即可證明。2.3 同余及模運算 同余：假定有三個整數(shù)a，b，m（m0），當我們稱a在模m與b同余，是指當且僅當a與b的差為m的整數(shù)倍，即a-b=nm，其中n為任一整數(shù)。若a與b在模m中同余，我們可以寫為a b (mod m)。剩余類：一個整數(shù)被正整數(shù)n除后，余數(shù)有n種情形：0，1，2，3，n-1，它們彼此對模n不同余。這表明，每個整數(shù)恰與這n個整數(shù)中某一個對模n同余。這樣一來，按模n是否同余對整數(shù)集進行分類，可以將整數(shù)集分成n個兩兩不相交的子集。我們把所有與整數(shù)a對模n同余的整數(shù)構(gòu)成的集合叫做模n的一個剩余類。 確切地

32、說，若x是一個給定的正整數(shù),則全體整數(shù)可以分成x個集，記作x,x,x-1,其中=0,1,-1 xi是由一切形如axi(a=0,1,2,)的整數(shù)所組成的集。完全剩余系：從模n的每個剩余類中各取一個數(shù)，得到一個由n個數(shù)組成的集合，叫做模n的一個完全剩余系。例如，一個數(shù)除以4的余數(shù)只能是0，1，2，3，0，1，2，3和4，5，-2，11是模4的完全剩余系?？梢钥闯?和4，1和5，2和-2，3和11關(guān)于模4同余，這4組數(shù)分別屬于4個剩余類。從0到n-1的整數(shù)組成的集合構(gòu)成了模n的“完全剩余系”。這意味著，對每個整數(shù)a，它的模n剩余是從0到n-1之間的某個整數(shù)。所謂模運算就是運算a mod n，表示求a

33、被n除的余數(shù)。既約剩余系：又稱簡化剩余系，即在模n互質(zhì)的完全剩余類中，若將所有與n互素的剩余類形成一個集合，則稱此集合為模n的既約剩余系。例如n=10時，0，1，2，3，4，5，6，7，8，9為模10的完全剩余系；而1,3,7,9,為模10的既約剩余系。第三章 RSA密碼體制的分析與研究3.1 RSA簡述公開密鑰算法是在1976年由當時在美國斯坦福大學的迪菲（Diffie）和赫爾曼(Hellman)兩人首先發(fā)明的（論文NewDirectioninCryptography）。但目前最流行的RSA是1977年由MIT教授RonaldL.Rivest,AdiShamir和LeonardM.Adlem

34、an共同開發(fā)的,分別取自三名數(shù)學家的名字的第一個字母來構(gòu)成的。1976年提出的公開密鑰密碼體制思想不同于傳統(tǒng)的對稱密鑰密碼體制，它要求密鑰成對出現(xiàn)，一個為加密密鑰(e)，另一個為解密密鑰(d)，且不可能從其中一個推導出另一個。自1976年以來，已經(jīng)提出了多種公開密鑰密碼算法，其中許多是不安全的，一些認為是安全的算法又有許多是不實用的，它們要么是密鑰太大，要么密文擴展十分嚴重。多數(shù)密碼算法的安全基礎(chǔ)是基于一些數(shù)學難題，這些難題專家們認為在短期內(nèi)不可能得到解決。因為一些問題(如因子分解問題)至今已有數(shù)千年的歷史了。公鑰加密算法也稱非對稱密鑰算法，用兩對密鑰：一個公共密鑰和一個專用密鑰。用戶要保障專

35、用密鑰的安全；公共密鑰則可以發(fā)布出去。公共密鑰與專用密鑰是有緊密關(guān)系的，用公共密鑰加密的信息只能用專用密鑰解密，反之亦然。由于公鑰算法不需要聯(lián)機密鑰服務器，密鑰分配協(xié)議簡單，所以極大簡化了密鑰管理。除加密功能外，公鑰系統(tǒng)還可以提供數(shù)字簽名。公鑰加密算法中使用最廣的是RSA。RSA使用兩個密鑰，一個公共密鑰，一個專用密鑰。如用其中一個加密，則可用另一個解密，密鑰長度從40到2048bit可變，加密時也把明文分成塊，塊的大小可變，但不能超過密鑰的長度，RSA算法把每一塊明文轉(zhuǎn)化為與密鑰長度相同的密文塊。密鑰越長，加密效果越好，但加密解密的開銷也大，所以要在安全與性能之間折衷考慮，一般64位是較合適

36、的。RSA的一個比較知名的應用是SSL，在美國和加拿大SSL用128位RSA算法，由于出口限制，在其它地區(qū)（包括中國）通用的則是40位版本。RSA算法研制的最初理念與目標是努力使互聯(lián)網(wǎng)安全可靠，旨在解決DES算法秘密密鑰的利用公開信道傳輸分發(fā)的難題。而實際結(jié)果不但很好地解決了這個難題；還可利用RSA來完成對電文的數(shù)字簽名以抗對電文的否認與抵賴；同時還可以利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對電文的非法篡改，以保護數(shù)據(jù)信息的完整性。RSA算法很好的完成對電文的數(shù)字簽名以抗對數(shù)據(jù)的否認與抵賴；利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對電文的非法篡改，以保護數(shù)據(jù)信息的完整性。目前為止，很多種加密技術(shù)采用了RSA算法

37、，比如PGP（PrettyGoodPrivacy）加密系統(tǒng)，它是一個工具軟件，向認證中心注冊后就可以用它對文件進行加解密或數(shù)字簽名，PGP所采用的就是RSA算法。由此可以看出RSA有很好的應用。3.2 RSA算法的描述 RSA使用了以大整數(shù)為模的同余指數(shù)運算。按照特定的方式選擇一個大整數(shù)n，明文（密文）分組是小于數(shù)n的非負整數(shù)。即用二進制表示時分組長度必須小于或等于 。對于某個明文分組M和密文分組C，加密及解密的形式如下： =mod n =mod n=()mod n=mod n這里e稱為加密指數(shù)，d稱為解密指數(shù)。明文發(fā)送方和接收方都必須知道n的值。發(fā)送方知道e的值，而只有接收方知道d的值。這是

38、一種公開密鑰為KU=e，n，且私有密鑰為KR=d，n的公開密鑰加密算法。要使這個算法能夠滿足公開密鑰加密的要求，必須符合如下條件：（1）有可能找到e、d、n的值，使得對所有Mn有 ；（2）對于所有Mn的值，要計算于相對來說是簡單的；（3）僅知道e和n時，無法算出d。需要找到具有下列形式的關(guān)系： =給定兩個互異的素數(shù)p和q，以及兩個整數(shù)n和m，使得n=pq且0mn，m與n互素。由Enler定理，有 于是對于任意整數(shù)k，下列關(guān)系成立： 其中是歐拉totient函數(shù)，表示不超過n且與n互素的整數(shù)個數(shù)。對于互異的素數(shù)p和q，有。選擇e、d使得 它等價于 也就是說d和e是以為模的乘法逆元，。注意到要求e

39、與d均與是互素的。綜上所述可以給出RSA方案。它的參數(shù)有：P、q：兩個互異素數(shù) （私有，選擇）n：n=pq （公開，計算出）e：滿足1e(n)及gcd（(n)，e）=1 （公開，選擇）d：d （私有，計算出）私有密鑰由d，n組成，公開密鑰由e，n組成。假設(shè)用戶A公布了它的公開密鑰，而用戶B希望向A發(fā)送一個報文M（0Mn），那么B計算出并傳輸C。在收到這個密文時，用戶A通過計算進行解密。現(xiàn)在來檢驗計算確實恢復出明文M。選擇了e和d，使得 ，即 所以可設(shè) 當gcd（M，n）=1時，由Euler定理可得 當gcd（M，n）1時，由gcd（M，n）|n知gcd（M，n）=p或q。不妨設(shè)gcd（M，n）

40、=p，則p|M，令M=sp，1sq。因gcd（M，q）=1，由Fermat定理可得 于是 ，即 由此得 ，即另一方面，由p|M可得 因為gcd（p，q）=1，由初等知識可得 即 下圖總結(jié)歸納了RSA算法的實現(xiàn)過程。1. 密鑰的產(chǎn)生 選擇大素數(shù)：p、q p和q是互異素數(shù) 計 算： n=pq 計 算： (n)=（p-1）（q-1） 選擇 整數(shù)：e gcd（(n)，e）=1；1e(n) 計 算：d 公開 密鑰： KU=e，n 私有 密鑰： KR=d，n2. 加 密 明 文： 0Mn 密 文： 3. 解 密 密 文： 0 Cn 明 文： M=3.3 RSA計算方法現(xiàn)在轉(zhuǎn)而討論使用RSA時的計算復雜性問

41、題。實際上需要考慮的問題有：加密/解密、密鑰的生成、大數(shù)運算的處理和素數(shù)的產(chǎn)生。下面就來討論下以上問題。3.3.1 加密和解密在RSA中，加密和解密都涉及計算一個整數(shù)的冪，然后模n。如果先對整數(shù)進行指數(shù)運算，然后再進行模n運算，那么中間結(jié)果將極其巨大。幸運的是，可以利用取模運算的一個特性：因而，可以對中間結(jié)果進行模n運算，這就使計算實際可行。另外一個考慮是指數(shù)運算的效率，因為在RSA中碰到的可能是非常大的指數(shù)。為了了解如何才能提高效率，考慮計算。直接的方法需要15次乘法：然而，可以只用4次乘法得到同樣的最后結(jié)果。如果重復對每次的部分結(jié)果取平方，依次得到、。一般地，假定希望算出的值，其中和是整數(shù)

42、。如果將表示為一個二進制數(shù)、，那么有： 因而 3.3.2 密鑰的生成在應用RSA密碼體制之前，必須先生產(chǎn)生密鑰，即必須先選擇兩個大素數(shù)與，然后再選取相對較小的正整數(shù)，并計算出。由于與得積是公開的，所以為了防止攻擊者用窮搜索法獲得與，與必須是足夠大的素數(shù)。因而，有效地獲取大素數(shù)是實現(xiàn)RSA密碼體制需要解決的一個關(guān)鍵問題。然而，遺憾的是，目前還沒有特別有效的方法可以產(chǎn)生任意打的素數(shù)?，F(xiàn)在通常的辦法是：隨機選取一個適當大的奇數(shù)，然后檢驗它是否為素數(shù)，若非素數(shù)，則隨機選另一個奇數(shù)檢測它是否為素數(shù)，如此繼續(xù)，直到找到一個大素數(shù)為止。目前素性檢測的方法基本上都是概率性的，即這些檢測方法只能確定一個給定整數(shù)

43、可能是素數(shù)。但有些檢測方法可使檢測一個整數(shù)是素數(shù)的概率接近1.0，比如附錄中介紹的非常有效且被廣泛采用的Miller-Rabin算法。2002年印度理工大學的3位學者提出一種（多項式時間）快速確定性算法，可以證明一個整數(shù)是素數(shù)。其效率不如概率算法高。確定了足夠大的素數(shù)、后，就可借助擴展的Eucidean算法來求得滿足條件0且z=1, 那麼p不是素數(shù)。（5） 設(shè)j=j+1。如果j且zp-1,設(shè)z=z2 mod p，然后回到(4)。如果z=p-1，那麼p通過測試，可能為素數(shù)。（6） 如果j=b 且zp-1，不是素數(shù)。如表3.2，可以看到Miller-Rabin中，最耗時的模冪運算只有一次，因此在速

44、度上是有一定優(yōu)勢的（表中的p是隨機二進制序列中某處連續(xù)出現(xiàn)的“0”的個數(shù)，通常p不會太大）。 表3.2 素性測試算法比較減法 移位 模冪 模乘Miller-Rabin1p1 1 Lehmann112 無3.4 RSA的安全性及分析密碼學所討論的系統(tǒng)，其實安全性是重要的。再好的密碼系統(tǒng)，如果安全性不好則也是一文不值。同時，密碼系統(tǒng)的安全性也很難用理論證明（事實上證明一個安全系統(tǒng)是安全的很難，但若該系統(tǒng)不安全，證明它是不安全的則很容易）。如今RSA從提出到現(xiàn)在已經(jīng)近而是年，經(jīng)歷了各種攻擊和考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰密碼體制之一。然而在一定環(huán)境條件下，RSA實現(xiàn)細節(jié)的疏忽會導致

45、對RSA算法的有效攻擊。因此，對RSA體制實現(xiàn)的各個環(huán)節(jié)進行個充分的考慮，避免安全性缺陷是相當有必要的。3.4.1 RSA的參數(shù)選擇RSA算法的安全性等價于分解n的困難性，但在實際的應用中，在很多時候是因為算法實現(xiàn)的細節(jié)漏洞導致的，因此，在RSA算法構(gòu)造密碼系統(tǒng)時，為了保證系統(tǒng)的安全需要仔細地選擇使用的參數(shù)。根據(jù)RSA加解密過程，其中主要的參數(shù)有三個：模數(shù)n，加密密鑰e，解密密鑰。5. 模數(shù)n的確定RSA模數(shù)是RSA算法安全性的核心。如果模數(shù)n被分解，則RSA公鑰密碼體制將立刻被攻擊，所以選擇合適的n是實現(xiàn)RSA算法的重要環(huán)節(jié)。一般來說，模數(shù)n的選擇可以遵守以下4個原則：（1），要求和為強素數(shù)；強素數(shù)指存在兩個大素數(shù)使得存在4個大素數(shù)，使得稱為三級素數(shù)，為二級素數(shù)。（2）和之差要大，相差幾位以上；（3）與的最大公因子要?。唬?）和要足夠大。這是應用RSA算法要遵守的最基本原則，如果RSA算法是安全的，則必須足夠大，使得因式分解模數(shù)n在計算上是不可行的，下面是一般性使用原則：（1）