基于rsa加密算法畢業(yè)論文--數(shù)據(jù)通信中的rsa加密算法的設(shè)計與實現(xiàn)

1、<p>　　本科畢業(yè)設(shè)計(論文)</p><p>　　題目： 數(shù)據(jù)通信中的RSA加密算法的設(shè)計與實現(xiàn) </p><p>　　系 ( 院 )： 電子與計算機(jī)系 </p><p>　　專業(yè)(方向)：電子信息工程(信息處理) </p><p>　　班 級： </p>&

2、lt;p>　　學(xué) 生： </p><p>　　指導(dǎo)教師： </p><p><b>　　摘 要</b></p><p>　　數(shù)據(jù)通信是依照一定的通信協(xié)議，利用數(shù)據(jù)傳輸技術(shù)在兩個終端之間傳遞數(shù)據(jù)信息的一種通信方式和通信業(yè)務(wù)。隨著數(shù)據(jù)通信的迅速發(fā)展而帶來了數(shù)據(jù)失密問題。信息被非法截取和數(shù)據(jù)

3、庫資料被竊的事例經(jīng)常發(fā)生，在日常生活中信用卡密碼被盜是常見的例子。所以數(shù)據(jù)加密成為十分重要的問題，它能保證數(shù)據(jù)的安全性和不可篡改性。 RSA加密算法以它難以破譯的優(yōu)點，被廣泛的使用在電子商務(wù)和VPN中。</p><p>　　本文針對非對稱性加密RSA算法，采用軟件Visual C++6.0進(jìn)行程序編寫。根據(jù)模乘法運(yùn)算和模指數(shù)運(yùn)算的數(shù)學(xué)原理所編寫的程序在進(jìn)行測試后，能夠通過輸入兩個素數(shù)進(jìn)行運(yùn)算從而實現(xiàn)明文與密文之間

4、的轉(zhuǎn)換，然后通過對公鑰和私鑰的管理，對所傳輸?shù)臄?shù)據(jù)進(jìn)行保護(hù)，讓數(shù)據(jù)只能由發(fā)送者和接收者閱讀，以達(dá)到數(shù)據(jù)通信中數(shù)據(jù)無法被他人破譯的目的。</p><p>　　關(guān)鍵詞:RSA算法，數(shù)據(jù)通信，加密, 解密。</p><p>　　Data communication of the RSA encryption algorithm in the Design and Implementation&l

5、t;/p><p><b>　　Abstract</b></p><p>　　Data communications in accordance with certain communication protocols, the use of data transmission technology in the transmission of data between t

6、wo terminals as a means of communication of information and communication business. With the rapid development of data communications and has brought the issue of data compromise. Unlawful interception of information and

7、 database information on frequent instances of theft, credit card in their daily lives stolen passwords is a common example. Theref</p><p>　　In this paper, asymmetric RSA encryption algorithm, the use of sof

8、tware for Visual C + +6.0 programming. According to Die multiplication and modular exponentiation by the mathematical principles in the preparation of test procedures can be adopted for the importation of two prime numbe

9、rs and computing in order to achieve explicit conversion between the ciphertext, and then through a public key and private key management, for the transmission of data protection, so that data can only be made by t</p

10、><p>　　Keywords: RSA algorithms, data communication, encryption, decryption.</p><p><b>　　目錄</b></p><p><b>　　摘 要I</b></p><p>　　AbstractII</p>

11、;<p><b>　　第1章 引言1</b></p><p><b>　　1.1題目背景1</b></p><p>　　1.2國內(nèi)外現(xiàn)狀1</p><p>　　1.3本課題的主要工作2</p><p>　　第2章 數(shù)據(jù)通信中的加密技術(shù)3</p><p&g

12、t;　　2.1數(shù)據(jù)加密技術(shù)的起源和發(fā)展3</p><p>　　2.2數(shù)據(jù)加密的方法3</p><p>　　2.3密鑰的管理5</p><p>　　2.4數(shù)據(jù)加密的標(biāo)準(zhǔn)5</p><p>　　2.5數(shù)據(jù)加密的應(yīng)用6</p><p><b>　　2.6本章小結(jié)6</b></p>

13、<p>　　第3章 數(shù)據(jù)加密中的RSA算法8</p><p>　　3.1 RSA公鑰密碼體制概述8</p><p>　　3.2 RSA公鑰密碼體制安全性分析9</p><p>　　3.3 RSA算法的缺點10</p><p>　　3.4 本章小結(jié)10</p><p>　　第4章 RSA數(shù)據(jù)加

14、密中的實現(xiàn)11</p><p>　　4.1隨機(jī)大素數(shù)的產(chǎn)生11</p><p>　　4.1.1素數(shù)的分布11</p><p>　　4.1.2大素數(shù)生成的方法12</p><p>　　4.1.3 Miller Rabin素性測試法12</p><p>　　4.1.4基于Miller Rabin素性測試法的新的素

15、數(shù)生成方法13</p><p>　　4.2密鑰的生成及加密和解密14</p><p>　　4.2.1最大公因子gcd運(yùn)算14</p><p>　　4.2.2模n求逆元運(yùn)算16</p><p>　　4.2.3模n的大數(shù)冪乘運(yùn)算17</p><p>　　4.2.4模n的大數(shù)冪乘運(yùn)算17</p>&

16、lt;p>　　4.3 RSA算法分析18</p><p>　　4.3.1 RSA安全性分析18</p><p>　　4.3.2 RSA時間復(fù)雜度分析19</p><p>　　4.4本章小結(jié)19</p><p>　　第5章 RSA算法的實現(xiàn)21</p><p>　　5.1選定組合算法的準(zhǔn)則21<

17、/p><p>　　5.2模冪組合算法的實現(xiàn)21</p><p>　　5.3試驗與運(yùn)行結(jié)果22</p><p><b>　　總結(jié)24</b></p><p><b>　　參考文獻(xiàn)25</b></p><p><b>　　致謝26</b></p&

18、gt;<p><b>　　附錄27</b></p><p><b>　　第1章 引言</b></p><p><b>　　1.1題目背景</b></p><p>　　在當(dāng)今的信息社會中，每天都有大量的信息在傳輸、交換、存儲和處理，而這些處理過程幾乎都要依賴強(qiáng)大的計算機(jī)系統(tǒng)來完成。一旦

19、計算機(jī)系統(tǒng)發(fā)生安全問題，就可能造成信息的丟失、篡改、偽造、假冒，以及系統(tǒng)遭受破壞等嚴(yán)重后果。因此，如何保證計算機(jī)系統(tǒng)的安全，是當(dāng)前一個需要立即解決的十分嚴(yán)峻的問題。</p><p>　　通常保障網(wǎng)絡(luò)信息安全的方法有兩大類:一是以防火墻技術(shù)為代表的被動防衛(wèi)型，二是建立在數(shù)據(jù)加密，用戶授權(quán)確認(rèn)機(jī)制上的開放型網(wǎng)絡(luò)安全保障技術(shù)。</p><p>　　防火墻技術(shù)，就是在局域網(wǎng)與外部網(wǎng)絡(luò)之間設(shè)立一個服

20、務(wù)器，將它們之間隔離開來，建立起一個安全網(wǎng)關(guān)，從而保護(hù)內(nèi)部網(wǎng)免受非法用戶的侵入。</p><p>　　數(shù)據(jù)加密技術(shù)是可以與防火墻配合使用的一種安全技術(shù)，這種技術(shù)可以提高信息系統(tǒng)及數(shù)據(jù)的安全性和保密性、防止秘密數(shù)據(jù)被外部破解所采用的主要技術(shù)手段之一。按其不同的作用，數(shù)據(jù)加密技術(shù)主要分為數(shù)據(jù)傳輸、數(shù)據(jù)存儲、數(shù)據(jù)完整性的鑒別以及密鑰管理技術(shù)四種。加密技術(shù)是通過計算機(jī)網(wǎng)絡(luò)中的加密機(jī)構(gòu)，把網(wǎng)絡(luò)中的各種原始數(shù)字信息(明文)按

21、照某種特定的加密算法變換成與</p><p>　　明文完全不同的數(shù)字信息，即轉(zhuǎn)換成密文。計算機(jī)網(wǎng)絡(luò)中的加密技術(shù)主要采用鏈路加密和端對端加密等兩種方式。</p><p>　　通常情況是將這兩種加密模式結(jié)合起來共同使用，即可保證網(wǎng)內(nèi)用戶的數(shù)據(jù)安全，又可提供用戶之間的身份鑒別與認(rèn)證。</p><p><b>　　1.2國內(nèi)外現(xiàn)狀</b></p&

22、gt;<p>　　RSA被廣泛應(yīng)用于各種安全或認(rèn)證領(lǐng)域，如web服務(wù)器和瀏覽器信息安全、Email的安全和認(rèn)證、對遠(yuǎn)程登錄的安全保證和各種電子信用卡系統(tǒng)的核心。硬件上，如安全電話、以太網(wǎng)卡和智能卡也多采用RSA技術(shù)。而幾乎所Internet安全協(xié)議如S/MIME,SSL和S/WAN都引入了RSA加密方法。IS09796標(biāo)準(zhǔn)把RSA列為一種兼容的加密算法，使得RSA的應(yīng)用目前非常廣泛。RSA模數(shù)n=pq是RSA算法的安全性的

23、核心。如果模數(shù)n被分解，則RSA體制立刻被攻破。如果RSA算法是安全的，那么n=pq必須足夠大，使得因式分解模數(shù)n在計算上不可行的?；诎踩钥紤]，實際應(yīng)用中所選擇的素數(shù)p和q至少應(yīng)該為100位以上的十進(jìn)制數(shù)，相應(yīng)的模數(shù)n=pq將是200位的十進(jìn)制數(shù)。C E Shannon建議使用至少100位長度的大素數(shù)，從而得到長度為200位以上的大整數(shù)模數(shù)n。</p><p>　　RSA算法的缺點是加密速度慢，模數(shù)n的長度越

24、大，加/解密運(yùn)算所需要的時間就越長，算法實現(xiàn)的速度也就越慢。為了盡可能使用大的模數(shù)而又不影響系統(tǒng)實現(xiàn)的速度，實際應(yīng)用中通常使用專門的硬件實現(xiàn)RSA算法。</p><p>　　最重要的影響速度的實現(xiàn)細(xì)節(jié)是加/解密中的大數(shù)運(yùn)算。大數(shù)模冪乘運(yùn)算是RSA算法的核心運(yùn)算，也是運(yùn)算速度提高的關(guān)鍵。高效的大數(shù)模冪乘算法可以有效提高系統(tǒng)速度。需要每做一次平方或乘法運(yùn)算后，就要作一次模運(yùn)算，當(dāng)n的值很大時，做一次模運(yùn)算所需的時間比

25、做一次平方或一次乘法所需的時間更多，是影響算法實現(xiàn)速度的關(guān)鍵。但在實際加密解密過程中，n可能是幾個數(shù)的乘積，如RSA算法中，n是兩個大素數(shù)的乘積。這時可通過中國剩余定理進(jìn)行變換，降低指數(shù)的數(shù)量級.</p><p>　　1.3本課題的主要工作</p><p>　　本文選擇RSA數(shù)字加密體制為研究對象，討論了RSA實現(xiàn)過程中，每一步的具體實現(xiàn)算法。RSA加密算法是第一個成熟的、迄今為止理論上最

26、成功的公開鑰密系統(tǒng)。它的安全性基礎(chǔ)是數(shù)論和計算復(fù)雜性理論中的下述論斷:</p><p>　　求兩個大素數(shù)的乘積在計算上是容易的，但若要分解兩個大素數(shù)的積而求出它的素因子則在計算上是困難的。但是，在進(jìn)行加密和解密運(yùn)算時的整數(shù)求冪運(yùn)算耗時很大，影響了運(yùn)算速度，因此，人們提出了多種實現(xiàn)算法，以加快運(yùn)算速度，例如本文提到的SMM算法和指數(shù)2K進(jìn)制化法等。這些算法都是從某一方面入手，在一定程度上加快了運(yùn)算速度。本文通過分析

27、這些算法的特點，提出了一種綜合性的組合方法，在原有算法的基礎(chǔ)上更進(jìn)一步地加快了運(yùn)算速度。</p><p>　　本文首先介紹了加密算法的數(shù)學(xué)基礎(chǔ)，從數(shù)學(xué)理論上分析了RSA算法的原理;然后通過C++程序進(jìn)行實現(xiàn)。 </p><p>　　第2章 數(shù)據(jù)通信中的加密技術(shù)</p><p>　　隨著信息化的應(yīng)用水平不斷提高，尤其是電子政務(wù)和電子商務(wù)的蓬勃發(fā)展，互聯(lián)網(wǎng)絡(luò)的信息安全問

28、題越來越引起全社會的重視。數(shù)字化辦公和生活面臨一系列的嚴(yán)重“威脅”。由于互聯(lián)網(wǎng)的開放性，我們面臨各種各樣的安全威脅。網(wǎng)上傳輸?shù)泥]件可能被截取，信息的內(nèi)容可能被篡改;電子商務(wù)過程中，信用卡帳號和密碼可能暴露在第二者面前;一些人可能會假冒合法用戶身份或者假冒網(wǎng)站來用于一些非法目的，而事后又對自己的行為進(jìn)行抵賴:系統(tǒng)可能由于黑客的攻擊而無法提供有效的服務(wù)。這些問題給計算機(jī)從業(yè)人員揭示信息安全問題的嚴(yán)重性。</p><p&g

29、t;　　因此如何保證信息的機(jī)密性、完整性、不可抵賴性、有效性，成為網(wǎng)絡(luò)安全關(guān)注的核心問題。人們由此采用防火墻和數(shù)據(jù)加密等技術(shù)來保障網(wǎng)絡(luò)本身的安全。</p><p>　　2.1數(shù)據(jù)加密技術(shù)的起源和發(fā)展</p><p>　　早在互聯(lián)網(wǎng)出現(xiàn)之前，密碼技術(shù)已經(jīng)廣泛應(yīng)用于軍事和民用方面。有記載的最早的密碼系統(tǒng)可能是希一臘歷史學(xué)家Polybios發(fā)明的Polvbios格板，它是一種替換密碼系統(tǒng)。人們很

30、早以前將密碼系統(tǒng)分為代替和換位密碼兩種。</p><p>　　從密碼史的發(fā)展來看，1949年，信息論的創(chuàng)始人仙農(nóng)(C. E.Shannon)發(fā)表了一篇著名的文章，論證了一般經(jīng)典加密方法都是可以破解的。到了60年代，隨著電子技術(shù)、信息技術(shù)的發(fā)展及結(jié)構(gòu)代數(shù)、可計算性理論和復(fù)雜度理論的研究，密碼學(xué)又進(jìn)入了一個新的時期。我們當(dāng)前所應(yīng)用的密碼體制，都是屬于近代非經(jīng)典的密碼體制。70年代后期出現(xiàn)的數(shù)據(jù)加密標(biāo)準(zhǔn)DES(Data

31、FncryptionStandard)和公開密鑰密碼(非對稱密碼)體制(Publickeycrypto一system)是近代密碼學(xué)發(fā)展史上的兩個重要里程碑。</p><p>　　目前，最著名公開密鑰密碼體制是RSA體制，它是由美國MIT的二位科學(xué)家Rivest, Shamir不II Adleman于1976年提出的，是一種基于數(shù)論中大數(shù)分解的理論。由于RSA的安全性和實用性，它是當(dāng)前使用最廣泛的公鑰密碼系統(tǒng)，即可

32、以進(jìn)行加密，也可以進(jìn)行數(shù)字簽名。保障了數(shù)據(jù)的完整性、機(jī)密性，解決了身份認(rèn)證問題和不可抵賴性問題.</p><p>　　2.2數(shù)據(jù)加密的方法</p><p>　　數(shù)據(jù)加密的方法通常分為兩大類:對稱式加密體制 (常規(guī)密鑰密碼體制)和非對稱式加密體制(公開密鑰密碼體制)。</p><p>　　對稱式加密就是加密和解密使用同一個密鑰，通常稱之為"Session K

33、ey”這種加密技術(shù)曾經(jīng)被廣泛采用，其原理如圖2-1所示。如美國政府所采用的DES加密標(biāo)準(zhǔn)就是一種典型的“對稱式”加密法，它的Session Key長度為56位。</p><p>　　非對稱式加密就是加密和解密所使用的不是同一個密鑰，通常有兩個密鑰，稱為“公鑰”和“私鑰’夕，它們兩個必需配對使用，否則不能打開加密文件。這里的“公鑰”是指可以對外公布的，“私鑰”則不能，只能由持有人一個人知道。它的優(yōu)越性就在這里，因為

34、對稱式的加密方法如果是在網(wǎng)絡(luò)上傳輸加密文件就很難把密鑰告訴對方，不管用什么方法都有可能被他人竊聽到。而非對稱式的加密方法有兩個密鑰，目_其中的“公鑰”是可以公開的，也就不怕別人知道，收件人解密時只要用自己的私鑰即可以，這樣就很好地避免了密鑰的傳輸安全性問題。非對稱加密工作原理如圖2-2所示。</p><p><b>　　2.3密鑰的管理</b></p><p>　　密

35、鑰既然要求保密，這就涉及到密鑰的管理問題，密鑰的管理涉及到以下幾個方面:</p><p>　　(1)密鑰使用的時效和次數(shù)</p><p>　　如果用戶使用同樣密鑰多次與其他用戶交換信息，那么密鑰也同其它任何密碼一樣存在著一定的安全性。雖然用戶的私鑰是不對外公開的，但是也很難保證私鑰長期的保密性，很難保證長期以來不被泄漏。如果入侵者偶然地知道了用戶的密鑰，那么用戶曾經(jīng)和其他用戶交換的每一條消

36、息都不再是保密的。另外使用一個特定密鑰加密的信息越多，提供給竊聽者的材料也就越多，從某種意義上來講也就越不安全了。因此，一般強(qiáng)調(diào)僅將一個對話密鑰用于一條信息中或一次對話中，或者建立一種按時更換密鑰的機(jī)制以減小密鑰暴露的可能性。</p><p><b>　　(2)多密鑰的管理</b></p><p>　　假設(shè)在某機(jī)構(gòu)中有100用戶，如果任意兩個用戶之間可以進(jìn)行秘密對話，

37、那么總共需要多少密鑰呢?每個人需要知道多少密鑰呢? 如果任何兩個用戶之間通信需要不同的密鑰，則總共需要4950個密鑰，而且每個人應(yīng)記住99個密鑰。如果機(jī)構(gòu)的用戶更多，這種辦法就顯然過于平庸。</p><p>　　Kerberos提供了一種解決這個較好方案，它是由MIT發(fā)明的，使保密密鑰的管理和分發(fā)變得十分容易，但這種方法本身還存在一定的缺點。為能在互聯(lián)網(wǎng)上提供一個實用的解決方案，Kerberos建立了一個安全的、

38、可信任的密鑰分發(fā)中心(Key Distribution Center,KDC)，每個用戶只要知道一個和KDC進(jìn)行會話的密鑰就可以了，而不需要知道成百上千個不同的密鑰。</p><p>　　2.4數(shù)據(jù)加密的標(biāo)準(zhǔn)</p><p>　　對稱密鑰加密算法DES (Data Encryption Standard)是由工BM公司在70年代發(fā)展起來的，并經(jīng)政府的加密標(biāo)準(zhǔn)篩選后，于1977年被正式批準(zhǔn)并

39、作為美國聯(lián)邦信息處理標(biāo)準(zhǔn)。DES使用64位密鑰對64位的數(shù)據(jù)塊進(jìn)行加密，并對64位的數(shù)據(jù)塊進(jìn)行16輪編碼。64位密鑰中，有8位奇偶校驗位，實際密鑰長度只有56位。每輪編碼時，一個48位的“每輪”密鑰值由_5 6位的完整密鑰得出來。DES用軟件進(jìn)行解碼需用很長時間，而用硬件解碼速度非?？臁τ贒ES的最后一次評估是在1994年，美國己決定1998開始，不在使用DES。目前，新的加密標(biāo)準(zhǔn)AES正在征集、評估和制定中。盡管如此，DES對于推動

40、密碼理論的發(fā)展和應(yīng)用起了重大作用。</p><p>　　RSA是另外一種非常著名的公鑰加密體制，由Ron Rivest, AdiShami:以及Leonard Adleman于1978年提出，一該體制至今仍被公認(rèn)為是一個安全性能良好的密碼體制。該算法是基于大數(shù)不可能被質(zhì)因數(shù)分解假設(shè)的公鑰體系。簡單地說就是找兩個很大的質(zhì)數(shù)。一個對外公開的為“公鑰”(Public key)，另一個不告訴任何人，稱為“私鑰”(Priv

41、ate key)。這兩個密鑰是互補(bǔ)的，也就是說用公鑰加密的密文可以用私鑰解密，反過來也一樣。</p><p>　　DES被公認(rèn)為世界上第一個實用的密碼算法標(biāo)準(zhǔn)。它的出現(xiàn)適應(yīng)了電子化和信息化的要求，是一種加/解密標(biāo)準(zhǔn)，適合于硬件實現(xiàn)，因此它的算法被制成專門的芯片，應(yīng)用于加密機(jī)中。DES現(xiàn)在仍被廣泛應(yīng)用于金融和商業(yè)領(lǐng)域。RSA則是非對稱密鑰的實際標(biāo)準(zhǔn)。</p><p>　　在實際應(yīng)用中，通常是

42、DES和RSA加密算法同時使用。由于DES加確牟密速度上的優(yōu)勢，因此數(shù)據(jù)的加/解密通常是用DES完成的，而 DES使用的密鑰是通過應(yīng)用RSA算法生成的數(shù)字信封來傳遞的，保障了密鑰傳遞的安全性。</p><p>　　2.5數(shù)據(jù)加密的應(yīng)用</p><p>　　數(shù)據(jù)加密技術(shù)的應(yīng)用是多方面的，但最為廣泛的還是在電子商務(wù)和VPN上的應(yīng)用。</p><p>　　(1)在電子商務(wù)

43、方面的應(yīng)用</p><p>　　電子商務(wù)(E-business)允許顧客和商家可以在網(wǎng)上進(jìn)行各種商務(wù)活動，同時不必?fù)?dān)心相應(yīng)的商務(wù)信息被盜用，比如信用卡號碼、商品報價等。RSA的出現(xiàn)，提高網(wǎng)上交易的安全性，從而使電子商務(wù)走向?qū)嵱贸蔀榭赡堋?lt;/p><p>　　NETSCAPE公司提供了一種基于RSA的安全套接層協(xié)議SSL(Secure Sockets Layer)即為數(shù)據(jù)加密技術(shù)在電子商務(wù)方

44、面應(yīng)用的一個典型案例。</p><p>　　SSL2. 0用電子證書(Electric certificate)來實行身份進(jìn)行驗證后，雙方就可以用保密密鑰進(jìn)行安全的會話了。它同時使用“對稱”和“非對稱”加密方法，在客戶與電子商務(wù)的服務(wù)器進(jìn)行溝通的過程中，客戶會產(chǎn)生一個Session Key，然后客戶用服務(wù)器端的公鑰將Session Key進(jìn)行加密，再傳給服務(wù)器端，在雙方都知道Session Key后，傳輸?shù)臄?shù)據(jù)都

45、是以Session Key進(jìn)行加密與解密的，但服務(wù)器端發(fā)給用戶的公鑰必需先向有關(guān)發(fā)證機(jī)關(guān)中請，以得到公證。</p><p>　　SSL協(xié)議是一個比較優(yōu)秀而久經(jīng)考驗的網(wǎng)絡(luò)安全協(xié)議，一般情況下能夠抵抗竊聽、篡改、會話劫持、中間人等多種攻擊手段。協(xié)議的設(shè)計模式為“契入式”，與高層應(yīng)用協(xié)議和低層網(wǎng)絡(luò)協(xié)議無關(guān)，可以方便地集成到多種網(wǎng)絡(luò)環(huán)境中去，可根據(jù)不同的安全需求，選擇協(xié)議提供得多種密碼算法和密鑰交換協(xié)議。SSL目前在We

46、b和電子商務(wù)中的應(yīng)用相當(dāng)廣泛。</p><p>　　(2)加密技術(shù)在VPN中的應(yīng)用 </p><p>　　目前，跨地域國際化的機(jī)構(gòu)越來越多。一個機(jī)構(gòu)在多個城市、國家設(shè)有分支機(jī)構(gòu)。每一個機(jī)構(gòu)都有自己的局域網(wǎng)LAN (Local AreaNetwork)。事實上，很多機(jī)構(gòu)一般租用專用線路來連結(jié)這些虛擬的局域網(wǎng)。這種情況下，機(jī)構(gòu)內(nèi)部的重要文件、數(shù)據(jù)是通過廣域網(wǎng)進(jìn)行傳輸，因此網(wǎng)絡(luò)的安全問題最

47、為重要。具有加密/解密功能的路由器等設(shè)備的出現(xiàn)，使通過廣域網(wǎng)組成局域網(wǎng)成為可能，即所謂的的虛擬專用網(wǎng)(Virtual Private Network, VPN)。當(dāng)數(shù)據(jù)離開發(fā)送者所在的局域網(wǎng)時，該數(shù)據(jù)首先被用戶湍連接到互聯(lián)網(wǎng)上的路由器進(jìn)行硬件加密，數(shù)據(jù)在互聯(lián)網(wǎng)上是以加密的形式傳送的，當(dāng)達(dá)到目的LAN的路由器時，該路由器就會對數(shù)據(jù)進(jìn)行解密，這樣目的LAN中的用戶就可以看到真正的信息了。而加密解密過程對于普通的非網(wǎng)絡(luò)管理用戶來說，是透明的，

48、既普通用戶無需考慮VPN及加密解密的相關(guān)問題。因此，對普通用戶來說， VPN在使用過程中和一般</p><p>　　LAN沒有任何區(qū)別。</p><p><b>　　2.6本章小結(jié)</b></p><p>　　本章對數(shù)據(jù)加密技術(shù)作了簡要的介紹，其中包括數(shù)據(jù)加密技術(shù)的起源、發(fā)展，數(shù)據(jù)加密技術(shù)的概念，密鑰管理等密碼技術(shù)各方面的內(nèi)容。此外還對數(shù)字簽名

49、技術(shù)作了介紹。數(shù)字簽名技術(shù)實際上是數(shù)據(jù)加密技術(shù)在應(yīng)用上的延伸，是目前網(wǎng)上交易活動中，身份驗證技術(shù)的重要組成部分。而基于公開密鑰機(jī)制的數(shù)字簽名技術(shù)在應(yīng)用中，占有統(tǒng)治地位，尤其是基于RSA公鑰的數(shù)字簽名體制在應(yīng)用中更為廣泛。在接下來的一章，就將詳細(xì)介紹基于RSA的數(shù)字簽名體制。</p><p>　　第3章 數(shù)據(jù)加密中的RSA算法</p><p>　　目前企業(yè)面臨的計算環(huán)境和過去有很大的變化，

50、許多數(shù)據(jù)資源能夠依靠網(wǎng)絡(luò)來遠(yuǎn)程存取，而且越來越多的通訊依賴于公共網(wǎng)絡(luò)公共網(wǎng)絡(luò)（如 Internet），而這些環(huán)境并不保證實體間的安全通信，數(shù)據(jù)在傳輸過程可能被其它人讀取或篡改。</p><p>　　加密將防止數(shù)據(jù)被查看或修改，并在原本不安全的信道上提供安全的通信信道，它達(dá)到以下目的：</p><p>　　保密性：防止用戶的標(biāo)識或數(shù)據(jù)被讀取。 </p><p>　　數(shù)

51、據(jù)完整性：防止數(shù)據(jù)被更改。 </p><p>　　身份驗證：確保數(shù)據(jù)發(fā)自特定的一方。</p><p>　　3.1 RSA公鑰密碼體制概述</p><p>　　RSA公鑰密碼體制于1978年，由美國麻省理工學(xué)院Rivest,Shami:和Adleman二人提出的，至今為止仍被公認(rèn)為是公鑰密碼體制中最優(yōu)秀的加密算法，被認(rèn)為是密碼學(xué)發(fā)展史上的第二個里程碑.它是一種特殊的可

52、逆摸指數(shù)運(yùn)算的加密體制，其理論基礎(chǔ)是數(shù)論中的一條重要論斷:求兩個大素數(shù)之積是容易的，而將一個具有大素數(shù)因子的合數(shù)進(jìn)行分解卻是非常困難的。除了用于加密之外，它還能用于數(shù)字簽名和身份認(rèn)證。RSA公鑰密碼體制過程描述如下:</p><p>　　(1)選取兩個大素數(shù)和.</p><p>　　(2)計算（公開)，歐拉函數(shù))。</p><p>　　(3)隨機(jī)選取正整數(shù)e, ，滿

53、足, e是公開的加密密鑰。</p><p>　　(4)計算d，滿足. d是保密的解密密鑰。</p><p>　　(5)加密變換:對明文,明文為(Zn為明文空間)</p><p>　　(6)解密變換:對密文,明文為</p><p>　　可以證明，解密變換是加密變換的逆變換。</p><p><b>　　例:&l

54、t;/b></p><p><b>　　(1)生成密鑰:</b></p><p>　　選擇兩個互質(zhì)的質(zhì)數(shù);</p><p><b>　　取 ;</b></p><p><b>　　由，得d=147;</b></p><p>　　所以，保密的解密密鑰

55、為d=147，公開的加密密鑰公鑰為e=3,n=253;明文空間為</p><p><b>　　(2)加密原文:</b></p><p>　　假設(shè)原文m的數(shù)字為16_5，用公鑰加密原文。</p><p><b>　　(3)解碼密文:</b></p><p>　　A=C，由此可以看出RSA算法的一般過程

56、。</p><p>　　3.2 RSA公鑰密碼體制安全性分析</p><p>　　RSA體制中，加密密鑰e與大整數(shù)n是公開的，而解密密鑰d與大素數(shù)p和q是保密的。雖然在RSA的加密與解密密鑰建立后，p和q不再需要，但p和q也絕不能泄露。若n被分解，則也就不保密，e公開，d就可以計算出來，RSA便被破譯。己知n，求得，則P和q可以求得。因為根據(jù)歐拉定理，，又有據(jù)此列出方程:</p>

57、;<p>　　由以上方程組，可以求得p和q。因為p和q都是大素數(shù)，根據(jù)現(xiàn)在已知的結(jié)果，因子分解n是最好的算法，此時復(fù)雜性為:</p><p>　　若n為200位于進(jìn)制數(shù)，則用每秒107次運(yùn)算的高速計算機(jī)，也要108年才能得到計算結(jié)果。可見，RSA的素數(shù)分解確實存在一定的難度。</p><p>　　為安全起見，對p和q要求:p和q的相差不大;(p-1)和(q-1)有大素數(shù)因子;

58、很小，滿足這樣條件的素數(shù)稱做安全素數(shù)。</p><p>　　RSA的出現(xiàn)使得大整數(shù)分解因式這一古老的問題再次被重視，近些年來出現(xiàn)的不少比較高級的因數(shù)分解方法使“安全素數(shù)”的概念也在不停的演化。所以，選擇傳統(tǒng)上認(rèn)為是“安全素數(shù)”并不一定有效的增加安全性，比較保險的方法就是選擇足夠大的素數(shù)。因為數(shù)越大，對其分解因式的難度也就越大!對n和密鑰長度的選擇取決于用戶保密的需要。密鑰長度越大，安全性也就越高，但是相應(yīng)的計算速

59、度也就越慢。由于高速計算機(jī)的出現(xiàn)，以前認(rèn)為己經(jīng)很具安全性的512位密鑰長度己經(jīng)不再滿足人們的需要。1997年，RSA組織公布當(dāng)時密鑰長度的標(biāo)準(zhǔn):個人使用768位密鑰，公司使用1024位密鑰，而一些非常重要的機(jī)構(gòu)使用2048位密鑰。</p><p>　　3.3 RSA算法的缺點</p><p>　　RSA的缺點主要有： </p><p>　　A)產(chǎn)生密鑰很麻煩，受到素

60、數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。</p><p>　　B)分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運(yùn)算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。</p><p><b>　　3.4 本章小結(jié)</b></p><p>　　RSA算法

61、在理論上的重大缺陷就是并不能證明分解因數(shù)絕對是困難的。RSA方法既可用于保密、也能用于簽名和認(rèn)證，許多流行的操作系統(tǒng)如微軟、Apple, Sun和Novell都在其產(chǎn)品上融入了RSA。同時，RSA也被廣泛應(yīng)用于各種安全或認(rèn)證領(lǐng)域，如web服務(wù)器和瀏覽器信息安全、Email的安全和認(rèn)證、對遠(yuǎn)程登錄的安全保證和各種電子信用卡系統(tǒng)的核心。硬件上，如安全電話、以太網(wǎng)卡和I智能卡也多采用RSA技術(shù)。而且?guī)缀跛蠭nternet安全協(xié)議如SMME,

62、 SSL不II SWAN都引入了RSA加密方法。IS09796標(biāo)準(zhǔn)把RSA列為一種兼容的加密算法，使得RSA的應(yīng)用目前非常廣泛。任何一種事物有出現(xiàn)、繁榮，也不可避免的會走向滅亡。在沒有找到快速進(jìn)行大整數(shù)分解因式方法的時候，RSA顯示了不可比擬的優(yōu)點。而當(dāng)分解因式不再是難題的時候，RSA算法也就將失去存在的價值。</p><p>　　第4章 RSA數(shù)據(jù)加密中的實現(xiàn)</p><p>　　R

63、SA算法,它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字就是發(fā)明者的名字：Ron Rivest, AdiShamir 和Leonard Adleman, 但RSA的安全性一直未能得到理論上的證明， RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題， R

64、SA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。</p><p>　　RSA算法實現(xiàn)數(shù)據(jù)加密的主要步驟分為：</p><p>　　1、獲取密鑰，這里是產(chǎn)生密鑰，實際應(yīng)用中可以從各種存儲介質(zhì)上讀取密鑰。</p><p>

65、<b>　　2、加密。</b></p><p><b>　　3、解密。</b></p><p>　　4.1隨機(jī)大素數(shù)的產(chǎn)生</p><p>　　公鑰密碼學(xué)需要大素數(shù)，因此，大素數(shù)的快速有效隨機(jī)生成方法是公鑰密碼學(xué)中的一個重要問題，具有非常顯著的實用價值。顯然，通過對一個隨機(jī)數(shù)進(jìn)行因子分解，我們可以判斷這個隨機(jī)數(shù)是否為素數(shù)。

66、如果這個隨機(jī)數(shù)能被因子分解，則它不是素數(shù)，否則它一定是素數(shù)。但是，大素數(shù)的因子分解是一個復(fù)雜的問題，到現(xiàn)在還沒有找到一個快速有效的算法來對大整數(shù)進(jìn)行因子分解。因此，不能試圖通過對隨機(jī)數(shù)進(jìn)行因子分解來生成大素數(shù)。正確的生成大素數(shù)的方法是對生成的隨機(jī)數(shù)先測試它是否為</p><p>　　素數(shù)，而不是對它進(jìn)行因子分解。這種素性測試比因子分解要容易得多，己經(jīng)有許多素性測試方法能夠確定一個隨機(jī)數(shù)是否為素數(shù)。如果合數(shù)通過一個

67、素性測試的概率足夠小，則這個素性測試就是很可靠的。實際上，對于許多素性測試方法，合數(shù)通過測試的概率可以受到人為的控制，即是可以把合數(shù)通過測試的概率設(shè)定的足夠小。</p><p>　　4.1.1素數(shù)的分布</p><p>　　要討論素數(shù)的生成問題，首先要討論素數(shù)的分布。素數(shù)的分布是極不均勻的，素數(shù)越大，分布也就越稀疏。</p><p>　　首先，存在無窮多個素數(shù)。對此

68、，我們可以證明。假設(shè)正整數(shù)中只有k個素數(shù)，設(shè)為。令,則n>1。如果n是素數(shù)，則顯然n與都不相同，這與只有k個素數(shù)的假設(shè)相矛后。如果n不是素數(shù)，則n一定有一個素數(shù)</p><p>　　因子, ，否則由于以及,所以,這與p是素數(shù)相矛盾。故p與都不相同，這與只有k個素數(shù)的假設(shè)想矛盾。因此素數(shù)有無窮多個。</p><p>　　其次，我們可以根據(jù)素數(shù)定理，發(fā)現(xiàn)素數(shù)的分布情況。素數(shù)定理的描述為:

69、設(shè), 為不大于x的整數(shù)的個數(shù)，則</p><p>　　根據(jù)素數(shù)定理，可以估計出長度為t位的素數(shù)大約有</p><p>　　個。例如，一個長度為256位的隨機(jī)數(shù)的素數(shù)的概率為</p><p>　　而一個長度為64位的隨機(jī)數(shù)的素數(shù)的概率為</p><p>　　由此可見，位數(shù)越多，素數(shù)的分布越為稀疏。</p><p>　　4

70、.1.2大素數(shù)生成的方法</p><p>　　產(chǎn)生素數(shù)的一般方法可以分為兩類，即確定性素數(shù)產(chǎn)生方法和概率性素數(shù)產(chǎn)生方法。</p><p>　?。?）確定性素數(shù)產(chǎn)生方法</p><p>　　確定性素數(shù)產(chǎn)生方法產(chǎn)生的數(shù)必然是素數(shù)。然而其產(chǎn)生的素數(shù)卻帶有一定的限制。假若算法設(shè)計不佳，便容易構(gòu)造出帶有規(guī)律性的素數(shù)，使密碼分析者能夠分析出素數(shù)的變化，進(jìn)而可以猜到該系統(tǒng)中使用的

71、素數(shù)。此類方法主要有兩類，即基于Lucas定理和基于Pocklington定理的確定性素數(shù)產(chǎn)生方法。這里簡單介紹基于Lucas定理的確定性素數(shù)產(chǎn)生方法。此方法需要求得素數(shù)n-1的全部素因子。Lucas定理：設(shè)，存在一個正整數(shù)且，且對于n-1的每一個素q，均滿足a，則n為素數(shù)。</p><p>　　(2)概率性素數(shù)產(chǎn)生方法</p><p>　　概率性素數(shù)產(chǎn)生方法產(chǎn)生的數(shù)僅僅是偽素數(shù)。其缺點在

72、于，盡管其產(chǎn)生合數(shù)的可能性很小，但是這種可能性仍然存在:其優(yōu)點是產(chǎn)生的偽素數(shù)沒有規(guī)律性，而且產(chǎn)生的速度也比較快。</p><p>　　此類方法是生成大素數(shù)的主要方法，其中著名有:Miller Rabin與Solovay Strassen算法等。本文討論Mill Rabin算法。</p><p>　　4.1.3 Miller Rabin素性測試法</p><p>　　

73、Miller Rabin素性測試法是在實際中應(yīng)用非常廣的一種素性測試方案，可以用來判定某隨機(jī)數(shù)是否為素數(shù)。其定義如下:</p><p>　　設(shè)是一個奇數(shù)，設(shè)，其中s是非負(fù)整數(shù)，是奇數(shù)，設(shè)，如果，</p><p>　　或者存在一個r,，使得</p><p>　　則稱n通過以b為基的Miller-Rabin測試。下面是Miller-Rabin素性測試的依據(jù)，包括兩個定理

74、:</p><p>　　定理一：設(shè)p是一個素數(shù)，對任意整數(shù)b，如果 ，則p一定可以通過以b為基的Miller-Rabin測試。</p><p>　　定理二：如果n>2是一個奇合數(shù)，則至多有個b，0<b<n，使得n通過以b為基的Miller-Rabin測試。</p><p>　　4.1.4基于Miller Rabin素性測試法的新的素數(shù)生成方法<

75、;/p><p>　　這里提出一種將Miller-Rabin素性測試法和Lucas結(jié)合的強(qiáng)素數(shù)生成算法。強(qiáng)素數(shù)的概念Gordon J于1984年提出，強(qiáng)素數(shù)p應(yīng)該滿足4個條件:</p><p>　　(1)p是一個位數(shù)足夠暢的隨機(jī)選取素數(shù);</p><p>　　(2)p-1含有一個大的素數(shù)因子r;</p><p>　　(3)p+1含有一個大的素數(shù)因子

76、s;</p><p>　　(4)r-1含有一個大的素數(shù)因子t。</p><p>　　若p-1含有一個大的素數(shù)因子r，則，j為整數(shù)，由于</p><p>　　p與r均為奇數(shù)(大素數(shù))，所以j一定是偶數(shù)。由此，也可以用如下</p><p>　　三個等式來表示強(qiáng)素數(shù)p:</p><p>　　綜上，若素數(shù)p滿足:，則稱p為強(qiáng)素

77、數(shù)。Miller-Rabin素性測試法和Lucas結(jié)合的強(qiáng)素數(shù)生成算法步驟如下:</p><p><b>　　(1)生成偽素數(shù)</b></p><p>　　利用Miller Rabin素數(shù)測試法，s為正整數(shù)，隨即選取D個小于s的不同正整數(shù)，若、關(guān)于它們均通過Miller檢測，則5為合數(shù)的概率不大于(1/4)D?；舅枷肴缢惴鞒虉D4-1所示下：</p>

78、<p>　　若C為任意正整數(shù)，則每ln(c)個數(shù)中有一個素數(shù)，所以在m附近找Ln(m)次后仍末成功，便可重新生成隨機(jī)數(shù)m，繼續(xù)在m附近尋找。由于Miller Rabin檢測不能百分之百確定一致為素數(shù)，所以要進(jìn)一步確證。</p><p><b>　　(2)素數(shù)的確證</b></p><p>　　基于Lucas定理，確定s是否為素數(shù)，算法基本思想如下</p

79、><p>　　1)分解n-1，使q，為不同素數(shù);</p><p><b>　　2)a←1;</b></p><p><b>　　3)a←a+l;</b></p><p>　　4)若a≥n，則n可能非素數(shù)，轉(zhuǎn)3);</p><p>　　5)若，轉(zhuǎn)7);否則轉(zhuǎn)3):</p>

80、;<p>　　6) ，則n是素數(shù)，否則轉(zhuǎn)3);</p><p><b>　　7)退出。</b></p><p><b>　　(3)生成強(qiáng)偽素數(shù)</b></p><p>　　首先，根據(jù)s求出r，使，令r形樣利用找到并確證r的素性。其次根據(jù)r求出p，使。如果P通過D(D>30)次Miller Rabin檢

81、測，則可以人為P是一個素數(shù)。</p><p>　　大素數(shù)的選取對RSA系統(tǒng)的安全而言至關(guān)重要。一個直接方法是分解n，求出因子p與q，進(jìn)而求得解前的分解能力大約為130位十進(jìn)制數(shù)，但512比特(154位于進(jìn)制數(shù))模長的RSA體制的安全性已經(jīng)受到一定的威脅。專家建比特(308位十進(jìn)制數(shù))模長。由于密碼長度直接影響系統(tǒng)運(yùn)行的速度，所以對要不是特別高的系統(tǒng)，可以適當(dāng)?shù)臏p少密碼的長度。</p><p&g

82、t;　　4.2密鑰的生成及加密和解密</p><p>　　為了建立密碼系統(tǒng)，用戶A需要完成以下各步驟</p><p>　　（1）A產(chǎn)生兩個大素數(shù)p和q； </p><p>　　（2）A計算n=pq和；</p><p>　?。?）A選擇一個隨機(jī)數(shù)，使得；</p><p><b>　?。?）A計算；</b&

83、gt;</p><p>　　（5）A將n和a作為他的公鑰直接公開;</p><p>　?。?）加密變換和解密變換。</p><p>　　由上述過程，我們可以看出RSA加密系統(tǒng)的主要工作為大素數(shù)的生成、最大公因子gcd、模n求逆和模n的大數(shù)冪乘的算法。上一節(jié)，已經(jīng)討論了大素數(shù)的生成算法，這里主要討論最大公因子gcd、模n求逆和模n的大數(shù)冪乘的算法。</p>

84、<p>　　4.2.1最大公因子gcd運(yùn)算</p><p>　　這里采用經(jīng)典的Euclid算法為基礎(chǔ)進(jìn)行運(yùn)算C。這個算法就是公元前300年，歐幾里德在其著作《幾何原本》)中所闡述的求兩個數(shù)的最大公約數(shù)的過程(即輾轉(zhuǎn)相除法)。設(shè)定n和u兩個正整數(shù)，則一定存在整數(shù)q和r使得n=qu+r,其中，不難看出，由此，我們得到求兩個正整數(shù)的最大公因子的Euclid算法如下:</p><p>

85、;<b>　　(1);</b></p><p><b>　　(2)</b></p><p>　　(3)如r=0，則;</p><p>　　(4)如果r≠0，則，，轉(zhuǎn)第(2)步。</p><p>　　以下對這一算法稍作改進(jìn):</p><p>　　令為Euclid算法中第i次對賦

86、值后的值，為Euclid算法中第i次對賦值后的值，,規(guī)定。利用數(shù)學(xué)歸納法容易證明:對任意，存在整數(shù)使得</p><p>　　事實上，當(dāng)時，取則顯然有</p><p>　　假設(shè)i=j時，式(4-15)和(4-16)成立，則當(dāng)i=j+l時， </p><p>　　其中q(j)為Euclid算法中第i次對q賦值后q的值，規(guī)定</p><p><

87、;b>　　，因此</b></p><p>　　從上面的討論可知，存在整數(shù)a和b使得.</p><p>　　可以對Euclid算法做一點修改，使之可以同時求出gcd(n,u)和滿足上式的整數(shù)a和b，稱之?dāng)U展Euclid算法，此算法描述如下:</p><p>　　(3)如果r=0，則;</p><p>　　(4)如果r≠0，則&

88、lt;/p><p><b>　　，則轉(zhuǎn)(2)步。</b></p><p>　　以上即為擴(kuò)展的Euclid算法，該算法在計算模n求逆時，頗有用處。</p><p>　　4.2.2模n求逆元運(yùn)算</p><p>　　這里來討論模n求逆元的算法。設(shè)n和u都是正整數(shù)，模n的逆就是滿足的整數(shù)v,。</p><p&g

89、t;　　可以證明，對于正整數(shù)，對于，存在。使得的充分必要條件是。</p><p>　　證明必要性:對于任意，存在整數(shù)q使得,</p><p>　　假設(shè)。因為，所以，即對任意，都有，因此，如果存在，使得，則必然有。</p><p>　　證明充分性：假設(shè)，則存在整數(shù)a和b使于是</p><p><b>　　令，則。</b>&

90、lt;/p><p>　　由上述定理的充要性證明可以得知，利用擴(kuò)展的Euclid算法可以求得u模n的逆，以擴(kuò)展的Euclid算法為基礎(chǔ)，可以得到模n求逆的算法如下：</p><p><b>　　(1);</b></p><p><b>　　(2);</b></p><p>　　(3)如果r≠0，則；<

91、;/p><p>　　(4)如果≠1，則u模n不存在逆元；</p><p>　　(5)如果=1，則u模n逆元為。</p><p>　　舉例說明上述算法，求13模35的逆元:</p><p>　　35=2×13+9,9=1×35-2×13,</p><p>　　13=1×9+4,4=1&

92、#215;13-1×9=-1×35+3×</p><p>　　9=2×4+1,1=1×9-2×4=3×35-8×13,</p><p>　　所以13模35的逆元為</p><p>　　4.2.3模n的大數(shù)冪乘運(yùn)算</p><p>　　RSA公鑰密碼體制中，加密和解

93、密時都要進(jìn)行運(yùn)算，下面給出一個計算的快速算法。</p><p>　　(1)a←x,b←r,c←1;</p><p>　　(2)如果b=0，則輸出結(jié)果c，結(jié)束;</p><p>　　(3)如果b mod 2≠0，則轉(zhuǎn)到第(5)步;</p><p>　　(4)轉(zhuǎn)第(3)步:，</p><p>　　(5)，轉(zhuǎn)第(2)步。&l

94、t;/p><p>　　舉例說明上述算法，求13模35的逆元:</p><p>　　35=2×13+9,9=1×35-2×13,</p><p>　　13=1×9+4,4=1×13-1×9=-1×35+3×13,</p><p>　　9=2×4+1,1=1&#

95、215;9-2×4=3×35-8×13,</p><p>　　所以13模35的逆元為(-8)mod 35=270</p><p>　　4.2.4模n的大數(shù)冪乘運(yùn)算</p><p>　　RSA公鑰密碼體制中，加密和解密時都要進(jìn)行xrmod n的運(yùn)算，下面給出一個計算xrmod n的快速算法。</p><p>　　(

96、1)a←x,b←r,c←1;</p><p>　　(2)如果b=0，則輸出結(jié)果c，結(jié)束;</p><p>　　(3)如果，則轉(zhuǎn)到第(5)步;</p><p>　　(4)b←b/2,轉(zhuǎn)第(3)步:，</p><p>　　(5)，轉(zhuǎn)第(2)步。</p><p>　　例如:計算322mod 12 </p>&l

97、t;p>　　以上主要介紹了RSA數(shù)字簽名過程中，每個密鑰和加密解密過程中所涉及到的相關(guān)的算法。以上算法，均從數(shù)論的角度加以論證，在理論上切實可行。當(dāng)然，在實際項目中，根據(jù)要求，某些步驟還尚需要做相應(yīng)的調(diào)整。</p><p>　　4.3 RSA算法分析</p><p>　　RSA公鑰密碼體制是目前常用的一種密碼體制，無論從數(shù)論的角度，還是從實踐的角度，都己經(jīng)證明了RSA的正確性。雖然到

98、目前為止，還沒有足夠的證據(jù)其安全性，但是依照目前的計算機(jī)運(yùn)算能力，要破譯RSA密鑰是有相當(dāng)難度的，所以RSA完全可以應(yīng)用于普通的電子商務(wù)和電子政務(wù)工作之中。</p><p>　　4.3.1 RSA安全性分析</p><p>　　RSA的安全性，是基于大整數(shù)的素分解問題的難解性，即把n分解為p、q的困難程度。攻擊者破譯RSA公鑰密碼體制的步驟為:</p><p>　　

99、(1)分解n求出p、q;</p><p><b>　　(2)由，求出由</b></p><p><b>　　(3)由，求出d。</b></p><p>　　為了更好地防范分解攻擊，RSA體制的發(fā)明者認(rèn)為要仔細(xì)地選擇素數(shù)p和q，在選擇p和q時還要注意以下方面:</p><p>　　(1)p和q在位數(shù)上

100、要相差幾位數(shù)字;</p><p>　　(2)(p-1)和(q-1)都應(yīng)含有大的素數(shù)因子，以增加加攻擊者猜算出的困難性;</p><p>　　(3)都應(yīng)當(dāng)小。使用RSA公鑰密碼體制，要求用戶選擇兩個素數(shù)p和q，其中p和q是保密的，并要求p與q不相等，對p和q的乘積可以公開。實際上，所謂攻擊者破譯RSA密碼體制，指的是由e,n來推算d, 。若p>q，則可按以下步驟分解n:</p&g

101、t;<p><b>　　(1)因和由求得;</b></p><p><b>　　(2)因，得到</b></p><p><b>　　(3)由求出p;</b></p><p><b>　　(4)q=r/p;</b></p><p>　　這樣求得

102、了P和q，完成了對r的因子分解。</p><p>　　從數(shù)學(xué)上講，求一個對n不互素的數(shù)x就等價于破譯了算法。</p><p>　　這是因為：x和r的gcd可能等于P或者q，而其值可以用歐幾里德算法計算出來。實際上，若r足夠大，則沒必要擔(dān)心由x這個數(shù)來破譯算法。在的區(qū)間中有</p><p>　　個與r互素的數(shù)，且有個與r非互素的數(shù)。所以偶然出現(xiàn)含有p或q作為因子的一個

103、數(shù)的概率等于:</p><p>　　對于數(shù)值很大的p和q，這個概率是非常小的。</p><p>　　以目前的常規(guī)個人計算機(jī)為工具來進(jìn)行因子分解，其工作量是非線性增長的，分析見表4-l: </p><p>　　因此，在安全性要求不是特別高的系統(tǒng)中，可以認(rèn)為RSA是安全的。</p><p>　　4.3.2 RSA時間復(fù)雜度分析</p>

104、<p>　　RSA運(yùn)算過程涉及到大量的計算，所需時間相對于DES等加密算法來說，運(yùn)算時間較長。但由于其良好的安全性和成熟的密鑰管理機(jī)制，RSA在實際工作中，被廣泛采用。</p><p><b>　　4.4本章小結(jié)</b></p><p>　　RSA從20世紀(jì)80年代產(chǎn)生至今，始終以其成熟的工作體制和良好的安全性而被廣泛的應(yīng)用于實際項目之中。RSA的安全性

105、雖然沒有通過數(shù)學(xué)上的論證，因此，其安全性主要體現(xiàn)在大素數(shù)的分解這一復(fù)雜問題上。通過實踐證明，RSA在目前的計算機(jī)運(yùn)行能力下，還是相對安全的。RSA在未來的很長一段時間中，必將保持旺盛的生命力。</p><p>　　近年來，隨著電子商務(wù)、電子政務(wù)等網(wǎng)上行為的增加，對于加密技術(shù)的研究日趨活躍。而對于RSA的研究，同樣處于活躍的狀態(tài)。由于RSA本身框架的成熟，因此，對于RSA的研究主要體</p><

106、p>　　現(xiàn)在，對其子步驟算法的改進(jìn)和研究，比如對于模n求逆算法的改進(jìn)、最大公因子算法的改進(jìn);將RSA和其他算法、體制結(jié)合應(yīng)用，比如目前在各計算機(jī)科技期刊上經(jīng)常見到的關(guān)于門限RSA體制的研究成果。</p><p>　　本章主要討論了RSA內(nèi)部各步驟的算法實現(xiàn)。</p><p>　　第5章 RSA算法的實現(xiàn)</p><p>　　基于前面的分析，本章給出了一種實現(xiàn)

107、RSA的快速高效算法，并介紹了利用組合算法實現(xiàn)大整數(shù)快速模冪乘運(yùn)算的具體實現(xiàn)過程，以及在實現(xiàn)過程中所遇到的關(guān)鍵問題及解決方法。</p><p>　　5.1選定組合算法的準(zhǔn)則</p><p><b>　　1.準(zhǔn)確性原則</b></p><p>　　一個算法必須滿足它自身是正確的，即可以得到想要的計算結(jié)果。</p><p>

108、<b>　　2.高效性原則</b></p><p>　　算法必須是有效的，即是高效的算法。</p><p><b>　　3.簡單性原則</b></p><p>　　簡單性原則不僅要使算法要盡量的容易實現(xiàn)，而且要盡量使程序容易被用戶使用。</p><p><b>　　4.實用性原則</

109、b></p><p>　　要求算法確實可行，不僅是在理論上是正確的，還要求在實際上也能達(dá)到預(yù)期的效果。</p><p>　　5.2模冪組合算法的實現(xiàn)</p><p>　　本文前面介紹了一系列大數(shù)模冪運(yùn)算及其改進(jìn)算法，具體的實現(xiàn)方法步驟如下：</p><p>　?。?）任意選取兩個不同的大質(zhì)數(shù)p和q，計算乘積；</p>&l

110、t;p>　?。?）任意選取一個大整數(shù)d，d與互質(zhì)，整數(shù)d用做加密密鑰。注重d的選取是很輕易的，例如所有大于p和q的質(zhì)數(shù)都可用.；</p><p>　　（3）確定解密密鑰n，由，根據(jù)d，p和q可以輕易地計算出n，即為逆元；</p><p>　　（4）公開整數(shù)r和d，但是不公開n；</p><p>　　（5）規(guī)定明文動態(tài)分布空間L，輸入明文，通過計算成為密文；&l

111、t;/p><p>　?。?）將密文C解密為明文；</p><p><b>　　具體程序見附錄。</b></p><p>　　5.3試驗與運(yùn)行結(jié)果</p><p>　　開發(fā)環(huán)境：P43.0CPU，512M內(nèi)存，80G硬盤，17寸顯示器</p><p>　　操作系統(tǒng)：Windows XP</p>

112、;<p>　　開發(fā)工具：Visusl C++6.0</p><p><b>　　仿真結(jié)果：</b></p><p>　　其中p,q為2位素數(shù)，計算p與q的乘積，輸入整數(shù)d，d可以取大于p,q的素數(shù)小于p,q乘積，要求與(p－1)*(q－1)互質(zhì)，計算d的逆元，</p><p>　　輸入明文動態(tài)空間L，要求明文字節(jié)數(shù)不得超過L，否

113、則任務(wù)終止。</p><p>　　系統(tǒng)計算密文，然后計算明文</p><p><b>　　舉例如圖：</b></p><p>　　輸入2個素數(shù)：p=11,q=311,當(dāng)輸入不是素數(shù)時會提示如下</p><p>　　計算出p與q的乘積r為3421，（p-1）于(q-1)乘積為3100，輸入隨機(jī)大整數(shù)例如353，與3100僅

114、有公約數(shù)1，如輸入錯誤時會有如下提示</p><p>　　計算353的逆元,由n*d=1mod((p－1)*(q－1))可得逆元為2617，規(guī)定明文動態(tài)分配空間，此時我規(guī)定的是64個字節(jié)，輸入明文12345678，通過C = Pe modulo r計算將會轉(zhuǎn)化為密文：1268 2307 116 838 323 692 440 2366，再通過將其轉(zhuǎn)換回來就為12345678</p><p>

115、;　　在實際生活中，取素數(shù)p=11,q=311,公開乘積r,保密d與逆元n，當(dāng)小A發(fā)出明文12345678時，對其加密，得到密文1268 2307 116 838 323 692 440 2366，發(fā)給小C，他通過認(rèn)證可得到明文12345678</p><p><b>　　總結(jié)</b></p><p>　　在當(dāng)今的信息社會中，每天都有大量的信息在傳輸、交換存儲和處理，

116、而這些處理過程幾乎都要依賴強(qiáng)大的計算機(jī)系統(tǒng)來完成。一旦計算機(jī)系統(tǒng)發(fā)生安全問題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系統(tǒng)遭受搗亂、破壞等嚴(yán)重后果，輕者造成計算機(jī)系統(tǒng)運(yùn)行效率低下，重者造成計算機(jī)系統(tǒng)的徹底癱瘓。因此，如何保證計算機(jī)系統(tǒng)的安全是當(dāng)前一個需要立即解決的十分嚴(yán)峻的問題。密碼學(xué)的基本目的是使在不安全信道中通信的兩方以一種使他們的對手不能明白和理解的通信內(nèi)容的方式進(jìn)行通信。本文對密碼學(xué)與信息安全方面做了簡要的概述，具體論述