基于RSA加密算法本科畢業(yè)設(shè)計論文

桂林理工大學(xué)本科畢業(yè)設(shè)計·論文PAGEPAGE27桂林理工大學(xué)本科畢業(yè)設(shè)計·論文1桂林理工大學(xué)GUILINUNIVERSITYOFTECHNOLOGY本科畢業(yè)設(shè)計(論文)題目：數(shù)據(jù)通信中的RSA加密算法的設(shè)計與實(shí)現(xiàn)

摘要數(shù)據(jù)通信是依照一定的通信協(xié)議，利用數(shù)據(jù)傳輸技術(shù)在兩個終端之間傳遞數(shù)據(jù)信息的一種通信方式和通信業(yè)務(wù)。隨著數(shù)據(jù)通信的迅速發(fā)展而帶來了數(shù)據(jù)失密問題。信息被非法截取和數(shù)據(jù)庫資料被竊的事例經(jīng)常發(fā)生，在日常生活中信用卡密碼被盜是常見的例子。所以數(shù)據(jù)加密成為十分重要的問題，它能保證數(shù)據(jù)的安全性和不可篡改性。RSA加密算法以它難以破譯的優(yōu)點(diǎn)，被廣泛的使用在電子商務(wù)和VPN中。本文針對非對稱性加密RSA算法，采用軟件VisualC++6.0進(jìn)行程序編寫。根據(jù)模乘法運(yùn)算和模指數(shù)運(yùn)算的數(shù)學(xué)原理所編寫的程序在進(jìn)行測試后，能夠通過輸入兩個素數(shù)進(jìn)行運(yùn)算從而實(shí)現(xiàn)明文與密文之間的轉(zhuǎn)換，然后通過對公鑰和私鑰的管理，對所傳輸?shù)臄?shù)據(jù)進(jìn)行保護(hù)，讓數(shù)據(jù)只能由發(fā)送者和接收者閱讀，以達(dá)到數(shù)據(jù)通信中數(shù)據(jù)無法被他人破譯的目的。關(guān)鍵詞:RSA算法，數(shù)據(jù)通信，加密,解密。DatacommunicationoftheRSAencryptionalgorithmintheDesignandImplementationTeacher:ChenFeistudent:LuHuiAbstractDatacommunicationsinaccordancewithcertaincommunicationprotocols,theuseofdatatransmissiontechnologyinthetransmissionofdatabetweentwoterminalsasameansofcommunicationofinformationandcommunicationbusiness.Withtherapiddevelopmentofdatacommunicationsandhasbroughttheissueofdatacompromise.Unlawfulinterceptionofinformationanddatabaseinformationonfrequentinstancesoftheft,creditcardintheirdailylivesstolenpasswordsisacommonexample.Therefore,dataencryptionhasbecomeaveryimportantissue,itcanensuredatasecurityandcannotbetamperwithnature.RSAencryptionalgorithmtothemeritsofitdifficulttodecipher,waswidelyusedinthee-commerceandVPN.Inthispaper,asymmetricRSAencryptionalgorithm,theuseofsoftwareforVisualC++6.0programming.AccordingtoDiemultiplicationandmodularexponentiationbythemathematicalprinciplesinthepreparationoftestprocedurescanbeadoptedfortheimportationoftwoprimenumbersandcomputinginordertoachieveexplicitconversionbetweentheciphertext,andthenthroughapublickeyandprivatekeymanagement,forthetransmissionofdataprotection,sothatdatacanonlybemadebythesenderandtherecipienttoread,inordertoachievedatacommunicationsdatacannotbethepurposeofdecipheringtheothers.Keywords:RSAalgorithms,datacommunication,encryption,decryption.目錄摘要 IAbstract II第1章引言 11.1題目背景 11.2國內(nèi)外現(xiàn)狀 11.3本課題的主要工作 2第2章數(shù)據(jù)通信中的加密技術(shù) 32.1數(shù)據(jù)加密技術(shù)的起源和發(fā)展 32.2數(shù)據(jù)加密的方法 32.3密鑰的管理 52.4數(shù)據(jù)加密的標(biāo)準(zhǔn) 52.5數(shù)據(jù)加密的應(yīng)用 62.6本章小結(jié) 6第3章數(shù)據(jù)加密中的RSA算法 83.1RSA公鑰密碼體制概述 83.2RSA公鑰密碼體制安全性分析 93.3RSA算法的缺點(diǎn) 103.4本章小結(jié) 10第4章RSA數(shù)據(jù)加密中的實(shí)現(xiàn) 114.1隨機(jī)大素數(shù)的產(chǎn)生 114.1.1素數(shù)的分布 114.1.2大素數(shù)生成的方法 124.1.3MillerRabin素性測試法 124.1.4基于MillerRabin素性測試法的新的素數(shù)生成方法 134.2密鑰的生成及加密和解密 144.2.1最大公因子gcd運(yùn)算 144.2.2模n求逆元運(yùn)算 164.2.3模n的大數(shù)冪乘運(yùn)算 174.2.4模n的大數(shù)冪乘運(yùn)算 174.3RSA算法分析 184.3.1RSA安全性分析 184.3.2RSA時間復(fù)雜度分析 194.4本章小結(jié) 19第5章RSA算法的實(shí)現(xiàn) 215.1選定組合算法的準(zhǔn)則 215.2模冪組合算法的實(shí)現(xiàn) 215.3試驗(yàn)與運(yùn)行結(jié)果 22總結(jié) 24參考文獻(xiàn) 25致謝 26附錄 27第1章引言1.1題目背景在當(dāng)今的信息社會中，每天都有大量的信息在傳輸、交換、存儲和處理，而這些處理過程幾乎都要依賴強(qiáng)大的計算機(jī)系統(tǒng)來完成。一旦計算機(jī)系統(tǒng)發(fā)生安全問題，就可能造成信息的丟失、篡改、偽造、假冒，以及系統(tǒng)遭受破壞等嚴(yán)重后果。因此，如何保證計算機(jī)系統(tǒng)的安全，是當(dāng)前一個需要立即解決的十分嚴(yán)峻的問題。通常保障網(wǎng)絡(luò)信息安全的方法有兩大類:一是以防火墻技術(shù)為代表的被動防衛(wèi)型，二是建立在數(shù)據(jù)加密，用戶授權(quán)確認(rèn)機(jī)制上的開放型網(wǎng)絡(luò)安全保障技術(shù)。防火墻技術(shù)，就是在局域網(wǎng)與外部網(wǎng)絡(luò)之間設(shè)立一個服務(wù)器，將它們之間隔離開來，建立起一個安全網(wǎng)關(guān)，從而保護(hù)內(nèi)部網(wǎng)免受非法用戶的侵入。數(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ù)字信息(明文)按照某種特定的加密算法變換成與明文完全不同的數(shù)字信息，即轉(zhuǎn)換成密文。計算機(jī)網(wǎng)絡(luò)中的加密技術(shù)主要采用鏈路加密和端對端加密等兩種方式。通常情況是將這兩種加密模式結(jié)合起來共同使用，即可保證網(wǎng)內(nèi)用戶的數(shù)據(jù)安全，又可提供用戶之間的身份鑒別與認(rèn)證。1.2國內(nèi)外現(xiàn)狀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算法的安全性的核心。如果模數(shù)n被分解，則RSA體制立刻被攻破。如果RSA算法是安全的，那么n=pq必須足夠大，使得因式分解模數(shù)n在計算上不可行的?；诎踩钥紤]，實(shí)際應(yīng)用中所選擇的素數(shù)p和q至少應(yīng)該為100位以上的十進(jìn)制數(shù)，相應(yīng)的模數(shù)n=pq將是200位的十進(jìn)制數(shù)。CEShannon建議使用至少100位長度的大素數(shù)，從而得到長度為200位以上的大整數(shù)模數(shù)n。RSA算法的缺點(diǎn)是加密速度慢，模數(shù)n的長度越大，加/解密運(yùn)算所需要的時間就越長，算法實(shí)現(xiàn)的速度也就越慢。為了盡可能使用大的模數(shù)而又不影響系統(tǒng)實(shí)現(xiàn)的速度，實(shí)際應(yīng)用中通常使用專門的硬件實(shí)現(xiàn)RSA算法。最重要的影響速度的實(shí)現(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)算所需的時間比做一次平方或一次乘法所需的時間更多，是影響算法實(shí)現(xiàn)速度的關(guān)鍵。但在實(shí)際加密解密過程中，n可能是幾個數(shù)的乘積，如RSA算法中，n是兩個大素數(shù)的乘積。這時可通過中國剩余定理進(jìn)行變換，降低指數(shù)的數(shù)量級.1.3本課題的主要工作本文選擇RSA數(shù)字加密體制為研究對象，討論了RSA實(shí)現(xiàn)過程中，每一步的具體實(shí)現(xiàn)算法。RSA加密算法是第一個成熟的、迄今為止理論上最成功的公開鑰密系統(tǒng)。它的安全性基礎(chǔ)是數(shù)論和計算復(fù)雜性理論中的下述論斷:求兩個大素數(shù)的乘積在計算上是容易的，但若要分解兩個大素數(shù)的積而求出它的素因子則在計算上是困難的。但是，在進(jìn)行加密和解密運(yùn)算時的整數(shù)求冪運(yùn)算耗時很大，影響了運(yùn)算速度，因此，人們提出了多種實(shí)現(xiàn)算法，以加快運(yùn)算速度，例如本文提到的SMM算法和指數(shù)2K進(jìn)制化法等。這些算法都是從某一方面入手，在一定程度上加快了運(yùn)算速度。本文通過分析這些算法的特點(diǎn)，提出了一種綜合性的組合方法，在原有算法的基礎(chǔ)上更進(jìn)一步地加快了運(yùn)算速度。本文首先介紹了加密算法的數(shù)學(xué)基礎(chǔ)，從數(shù)學(xué)理論上分析了RSA算法的原理;然后通過C++程序進(jìn)行實(shí)現(xiàn)。 第2章數(shù)據(jù)通信中的加密技術(shù)隨著信息化的應(yīng)用水平不斷提高，尤其是電子政務(wù)和電子商務(wù)的蓬勃發(fā)展，互聯(lián)網(wǎng)絡(luò)的信息安全問題越來越引起全社會的重視。數(shù)字化辦公和生活面臨一系列的嚴(yán)重“威脅”。由于互聯(lián)網(wǎng)的開放性，我們面臨各種各樣的安全威脅。網(wǎng)上傳輸?shù)泥]件可能被截取，信息的內(nèi)容可能被篡改;電子商務(wù)過程中，信用卡帳號和密碼可能暴露在第二者面前;一些人可能會假冒合法用戶身份或者假冒網(wǎng)站來用于一些非法目的，而事后又對自己的行為進(jìn)行抵賴:系統(tǒng)可能由于黑客的攻擊而無法提供有效的服務(wù)。這些問題給計算機(jī)從業(yè)人員揭示信息安全問題的嚴(yán)重性。因此如何保證信息的機(jī)密性、完整性、不可抵賴性、有效性，成為網(wǎng)絡(luò)安全關(guān)注的核心問題。人們由此采用防火墻和數(shù)據(jù)加密等技術(shù)來保障網(wǎng)絡(luò)本身的安全。2.1數(shù)據(jù)加密技術(shù)的起源和發(fā)展早在互聯(lián)網(wǎng)出現(xiàn)之前，密碼技術(shù)已經(jīng)廣泛應(yīng)用于軍事和民用方面。有記載的最早的密碼系統(tǒng)可能是希一臘歷史學(xué)家Polybios發(fā)明的Polvbios格板，它是一種替換密碼系統(tǒng)。人們很早以前將密碼系統(tǒng)分為代替和換位密碼兩種。從密碼史的發(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(DataFncryptionStandard)和公開密鑰密碼(非對稱密碼)體制(Publickeycrypto一system)是近代密碼學(xué)發(fā)展史上的兩個重要里程碑。目前，最著名公開密鑰密碼體制是RSA體制，它是由美國MIT的二位科學(xué)家Rivest,Shamir不IIAdleman于1976年提出的，是一種基于數(shù)論中大數(shù)分解的理論。由于RSA的安全性和實(shí)用性，它是當(dāng)前使用最廣泛的公鑰密碼系統(tǒng)，即可以進(jìn)行加密，也可以進(jìn)行數(shù)字簽名。保障了數(shù)據(jù)的完整性、機(jī)密性，解決了身份認(rèn)證問題和不可抵賴性問題.2.2數(shù)據(jù)加密的方法數(shù)據(jù)加密的方法通常分為兩大類:對稱式加密體制(常規(guī)密鑰密碼體制)和非對稱式加密體制(公開密鑰密碼體制)。對稱式加密就是加密和解密使用同一個密鑰，通常稱之為"SessionKey”這種加密技術(shù)曾經(jīng)被廣泛采用，其原理如圖2-1所示。如美國政府所采用的DES加密標(biāo)準(zhǔn)就是一種典型的“對稱式”加密法，它的SessionKey長度為56位。發(fā)送者發(fā)送者加密相同的密鑰加密的信息接受者解密明文明文2-1對稱密碼算法示意圖非對稱式加密就是加密和解密所使用的不是同一個密鑰，通常有兩個密鑰，稱為“公鑰”和“私鑰’夕，它們兩個必需配對使用，否則不能打開加密文件。這里的“公鑰”是指可以對外公布的，“私鑰”則不能，只能由持有人一個人知道。它的優(yōu)越性就在這里，因?yàn)閷ΨQ式的加密方法如果是在網(wǎng)絡(luò)上傳輸加密文件就很難把密鑰告訴對方，不管用什么方法都有可能被他人竊聽到。而非對稱式的加密方法有兩個密鑰，目_其中的“公鑰”是可以公開的，也就不怕別人知道，收件人解密時只要用自己的私鑰即可以，這樣就很好地避免了密鑰的傳輸安全性問題。非對稱加密工作原理如圖2-2所示。加密密鑰EB明文明文解密接受者加密的信息加密密鑰EB（公開）加密發(fā)送者解密密鑰DB（保密）EB≠DB≠DB2-2非對稱性密碼算法示意圖加密密鑰EB明文明文解密接受者加密的信息加密密鑰EB（公開）加密發(fā)送者解密密鑰DB（保密）EB≠DB≠DB2-2非對稱性密碼算法示意圖2.3密鑰的管理密鑰既然要求保密，這就涉及到密鑰的管理問題，密鑰的管理涉及到以下幾個方面:(1)密鑰使用的時效和次數(shù)如果用戶使用同樣密鑰多次與其他用戶交換信息，那么密鑰也同其它任何密碼一樣存在著一定的安全性。雖然用戶的私鑰是不對外公開的，但是也很難保證私鑰長期的保密性，很難保證長期以來不被泄漏。如果入侵者偶然地知道了用戶的密鑰，那么用戶曾經(jīng)和其他用戶交換的每一條消息都不再是保密的。另外使用一個特定密鑰加密的信息越多，提供給竊聽者的材料也就越多，從某種意義上來講也就越不安全了。因此，一般強(qiáng)調(diào)僅將一個對話密鑰用于一條信息中或一次對話中，或者建立一種按時更換密鑰的機(jī)制以減小密鑰暴露的可能性。(2)多密鑰的管理假設(shè)在某機(jī)構(gòu)中有100用戶，如果任意兩個用戶之間可以進(jìn)行秘密對話，那么總共需要多少密鑰呢?每個人需要知道多少密鑰呢?如果任何兩個用戶之間通信需要不同的密鑰，則總共需要4950個密鑰，而且每個人應(yīng)記住99個密鑰。如果機(jī)構(gòu)的用戶更多，這種辦法就顯然過于平庸。Kerberos提供了一種解決這個較好方案，它是由MIT發(fā)明的，使保密密鑰的管理和分發(fā)變得十分容易，但這種方法本身還存在一定的缺點(diǎn)。為能在互聯(lián)網(wǎng)上提供一個實(shí)用的解決方案，Kerberos建立了一個安全的、可信任的密鑰分發(fā)中心(KeyDistributionCenter,KDC)，每個用戶只要知道一個和KDC進(jìn)行會話的密鑰就可以了，而不需要知道成百上千個不同的密鑰。2.4數(shù)據(jù)加密的標(biāo)準(zhǔn)對稱密鑰加密算法DES(DataEncryptionStandard)是由工BM公司在70年代發(fā)展起來的，并經(jīng)政府的加密標(biāo)準(zhǔn)篩選后，于1977年被正式批準(zhǔn)并作為美國聯(lián)邦信息處理標(biāo)準(zhǔn)。DES使用64位密鑰對64位的數(shù)據(jù)塊進(jìn)行加密，并對64位的數(shù)據(jù)塊進(jìn)行16輪編碼。64位密鑰中，有8位奇偶校驗(yàn)位，實(shí)際密鑰長度只有56位。每輪編碼時，一個48位的“每輪”密鑰值由_56位的完整密鑰得出來。DES用軟件進(jìn)行解碼需用很長時間，而用硬件解碼速度非?？?。對于DES的最后一次評估是在1994年，美國己決定1998開始，不在使用DES。目前，新的加密標(biāo)準(zhǔn)AES正在征集、評估和制定中。盡管如此，DES對于推動密碼理論的發(fā)展和應(yīng)用起了重大作用。RSA是另外一種非常著名的公鑰加密體制，由RonRivest,AdiShami:以及LeonardAdleman于1978年提出，一該體制至今仍被公認(rèn)為是一個安全性能良好的密碼體制。該算法是基于大數(shù)不可能被質(zhì)因數(shù)分解假設(shè)的公鑰體系。簡單地說就是找兩個很大的質(zhì)數(shù)。一個對外公開的為“公鑰”(Publickey)，另一個不告訴任何人，稱為“私鑰”(Privatekey)。這兩個密鑰是互補(bǔ)的，也就是說用公鑰加密的密文可以用私鑰解密，反過來也一樣。DES被公認(rèn)為世界上第一個實(shí)用的密碼算法標(biāo)準(zhǔn)。它的出現(xiàn)適應(yīng)了電子化和信息化的要求，是一種加/解密標(biāo)準(zhǔn)，適合于硬件實(shí)現(xiàn)，因此它的算法被制成專門的芯片，應(yīng)用于加密機(jī)中。DES現(xiàn)在仍被廣泛應(yīng)用于金融和商業(yè)領(lǐng)域。RSA則是非對稱密鑰的實(shí)際標(biāo)準(zhǔn)。在實(shí)際應(yīng)用中，通常是DES和RSA加密算法同時使用。由于DES加確牟密速度上的優(yōu)勢，因此數(shù)據(jù)的加/解密通常是用DES完成的，而DES使用的密鑰是通過應(yīng)用RSA算法生成的數(shù)字信封來傳遞的，保障了密鑰傳遞的安全性。2.5數(shù)據(jù)加密的應(yīng)用數(shù)據(jù)加密技術(shù)的應(yīng)用是多方面的，但最為廣泛的還是在電子商務(wù)和VPN上的應(yīng)用。(1)在電子商務(wù)方面的應(yīng)用電子商務(wù)(E-business)允許顧客和商家可以在網(wǎng)上進(jìn)行各種商務(wù)活動，同時不必?fù)?dān)心相應(yīng)的商務(wù)信息被盜用，比如信用卡號碼、商品報價等。RSA的出現(xiàn)，提高網(wǎng)上交易的安全性，從而使電子商務(wù)走向?qū)嵱贸蔀榭赡?。NETSCAPE公司提供了一種基于RSA的安全套接層協(xié)議SSL(SecureSocketsLayer)即為數(shù)據(jù)加密技術(shù)在電子商務(wù)方面應(yīng)用的一個典型案例。SSL2.0用電子證書(Electriccertificate)來實(shí)行身份進(jìn)行驗(yàn)證后，雙方就可以用保密密鑰進(jìn)行安全的會話了。它同時使用“對稱”和“非對稱”加密方法，在客戶與電子商務(wù)的服務(wù)器進(jìn)行溝通的過程中，客戶會產(chǎn)生一個SessionKey，然后客戶用服務(wù)器端的公鑰將SessionKey進(jìn)行加密，再傳給服務(wù)器端，在雙方都知道SessionKey后，傳輸?shù)臄?shù)據(jù)都是以SessionKey進(jìn)行加密與解密的，但服務(wù)器端發(fā)給用戶的公鑰必需先向有關(guān)發(fā)證機(jī)關(guān)中請，以得到公證。SSL協(xié)議是一個比較優(yōu)秀而久經(jīng)考驗(yàn)的網(wǎng)絡(luò)安全協(xié)議，一般情況下能夠抵抗竊聽、篡改、會話劫持、中間人等多種攻擊手段。協(xié)議的設(shè)計模式為“契入式”，與高層應(yīng)用協(xié)議和低層網(wǎng)絡(luò)協(xié)議無關(guān)，可以方便地集成到多種網(wǎng)絡(luò)環(huán)境中去，可根據(jù)不同的安全需求，選擇協(xié)議提供得多種密碼算法和密鑰交換協(xié)議。SSL目前在Web和電子商務(wù)中的應(yīng)用相當(dāng)廣泛。(2)加密技術(shù)在VPN中的應(yīng)用目前，跨地域國際化的機(jī)構(gòu)越來越多。一個機(jī)構(gòu)在多個城市、國家設(shè)有分支機(jī)構(gòu)。每一個機(jī)構(gòu)都有自己的局域網(wǎng)LAN(LocalAreaNetwork)。事實(shí)上，很多機(jī)構(gòu)一般租用專用線路來連結(jié)這些虛擬的局域網(wǎng)。這種情況下，機(jī)構(gòu)內(nèi)部的重要文件、數(shù)據(jù)是通過廣域網(wǎng)進(jìn)行傳輸，因此網(wǎng)絡(luò)的安全問題最為重要。具有加密/解密功能的路由器等設(shè)備的出現(xiàn)，使通過廣域網(wǎng)組成局域網(wǎng)成為可能，即所謂的的虛擬專用網(wǎng)(VirtualPrivateNetwork,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ò)管理用戶來說，是透明的，既普通用戶無需考慮VPN及加密解密的相關(guān)問題。因此，對普通用戶來說，VPN在使用過程中和一般LAN沒有任何區(qū)別。2.6本章小結(jié)本章對數(shù)據(jù)加密技術(shù)作了簡要的介紹，其中包括數(shù)據(jù)加密技術(shù)的起源、發(fā)展，數(shù)據(jù)加密技術(shù)的概念，密鑰管理等密碼技術(shù)各方面的內(nèi)容。此外還對數(shù)字簽名技術(shù)作了介紹。數(shù)字簽名技術(shù)實(shí)際上是數(shù)據(jù)加密技術(shù)在應(yīng)用上的延伸，是目前網(wǎng)上交易活動中，身份驗(yàn)證技術(shù)的重要組成部分。而基于公開密鑰機(jī)制的數(shù)字簽名技術(shù)在應(yīng)用中，占有統(tǒng)治地位，尤其是基于RSA公鑰的數(shù)字簽名體制在應(yīng)用中更為廣泛。在接下來的一章，就將詳細(xì)介紹基于RSA的數(shù)字簽名體制。第3章數(shù)據(jù)加密中的RSA算法目前企業(yè)面臨的計算環(huán)境和過去有很大的變化，許多數(shù)據(jù)資源能夠依靠網(wǎng)絡(luò)來遠(yuǎn)程存取，而且越來越多的通訊依賴于公共網(wǎng)絡(luò)公共網(wǎng)絡(luò)（如Internet），而這些環(huán)境并不保證實(shí)體間的安全通信，數(shù)據(jù)在傳輸過程可能被其它人讀取或篡改。加密將防止數(shù)據(jù)被查看或修改，并在原本不安全的信道上提供安全的通信信道，它達(dá)到以下目的：保密性：防止用戶的標(biāo)識或數(shù)據(jù)被讀取。數(shù)據(jù)完整性：防止數(shù)據(jù)被更改。身份驗(yàn)證：確保數(shù)據(jù)發(fā)自特定的一方。3.1RSA公鑰密碼體制概述RSA公鑰密碼體制于1978年，由美國麻省理工學(xué)院Rivest,Shami:和Adleman二人提出的，至今為止仍被公認(rèn)為是公鑰密碼體制中最優(yōu)秀的加密算法，被認(rèn)為是密碼學(xué)發(fā)展史上的第二個里程碑.它是一種特殊的可逆摸指數(shù)運(yùn)算的加密體制，其理論基礎(chǔ)是數(shù)論中的一條重要論斷:求兩個大素數(shù)之積是容易的，而將一個具有大素數(shù)因子的合數(shù)進(jìn)行分解卻是非常困難的。除了用于加密之外，它還能用于數(shù)字簽名和身份認(rèn)證。RSA公鑰密碼體制過程描述如下:(1)選取兩個大素數(shù)和.(2)計算（公開)，歐拉函數(shù))。(3)隨機(jī)選取正整數(shù)e,，滿足,e是公開的加密密鑰。(4)計算d，滿足.d是保密的解密密鑰。(5)加密變換:對明文,明文為(Zn為明文空間)(6)解密變換:對密文,明文為可以證明，解密變換是加密變換的逆變換。例:(1)生成密鑰:選擇兩個互質(zhì)的質(zhì)數(shù);取;由，得d=147;所以，保密的解密密鑰為d=147，公開的加密密鑰公鑰為e=3,n=253;明文空間為(2)加密原文:假設(shè)原文m的數(shù)字為16_5，用公鑰加密原文。(3)解碼密文:A=C，由此可以看出RSA算法的一般過程。3.2RSA公鑰密碼體制安全性分析RSA體制中，加密密鑰e與大整數(shù)n是公開的，而解密密鑰d與大素數(shù)p和q是保密的。雖然在RSA的加密與解密密鑰建立后，p和q不再需要，但p和q也絕不能泄露。若n被分解，則也就不保密，e公開，d就可以計算出來，RSA便被破譯。己知n，求得，則P和q可以求得。因?yàn)楦鶕?jù)歐拉定理，，又有據(jù)此列出方程:由以上方程組，可以求得p和q。因?yàn)閜和q都是大素數(shù)，根據(jù)現(xiàn)在已知的結(jié)果，因子分解n是最好的算法，此時復(fù)雜性為:若n為200位于進(jìn)制數(shù)，則用每秒107次運(yùn)算的高速計算機(jī)，也要108年才能得到計算結(jié)果?？梢姡琑SA的素數(shù)分解確實(shí)存在一定的難度。為安全起見，對p和q要求:p和q的相差不大;(p-1)和(q-1)有大素數(shù)因子;很小，滿足這樣條件的素數(shù)稱做安全素數(shù)。RSA的出現(xiàn)使得大整數(shù)分解因式這一古老的問題再次被重視，近些年來出現(xiàn)的不少比較高級的因數(shù)分解方法使“安全素數(shù)”的概念也在不停的演化。所以，選擇傳統(tǒng)上認(rèn)為是“安全素數(shù)”并不一定有效的增加安全性，比較保險的方法就是選擇足夠大的素數(shù)。因?yàn)閿?shù)越大，對其分解因式的難度也就越大!對n和密鑰長度的選擇取決于用戶保密的需要。密鑰長度越大，安全性也就越高，但是相應(yīng)的計算速度也就越慢。由于高速計算機(jī)的出現(xiàn)，以前認(rèn)為己經(jīng)很具安全性的512位密鑰長度己經(jīng)不再滿足人們的需要。1997年，RSA組織公布當(dāng)時密鑰長度的標(biāo)準(zhǔn):個人使用768位密鑰，公司使用1024位密鑰，而一些非常重要的機(jī)構(gòu)使用2048位密鑰。3.3RSA算法的缺點(diǎn)RSA的缺點(diǎn)主要有：A)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n至少也要600bits以上，使運(yùn)算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。3.4本章小結(jié)RSA算法在理論上的重大缺陷就是并不能證明分解因數(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,SSL不IISWAN都引入了RSA加密方法。IS09796標(biāo)準(zhǔn)把RSA列為一種兼容的加密算法，使得RSA的應(yīng)用目前非常廣泛。任何一種事物有出現(xiàn)、繁榮，也不可避免的會走向滅亡。在沒有找到快速進(jìn)行大整數(shù)分解因式方法的時候，RSA顯示了不可比擬的優(yōu)點(diǎn)。而當(dāng)分解因式不再是難題的時候，RSA算法也就將失去存在的價值。第4章RSA數(shù)據(jù)加密中的實(shí)現(xiàn)RSA算法,它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字就是發(fā)明者的名字：RonRivest,AdiShamir和LeonardAdleman,但RSA的安全性一直未能得到理論上的證明，RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題，RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA算法實(shí)現(xiàn)數(shù)據(jù)加密的主要步驟分為：1、獲取密鑰，這里是產(chǎn)生密鑰，實(shí)際應(yīng)用中可以從各種存儲介質(zhì)上讀取密鑰。2、加密。3、解密。4.1隨機(jī)大素數(shù)的產(chǎn)生公鑰密碼學(xué)需要大素數(shù)，因此，大素數(shù)的快速有效隨機(jī)生成方法是公鑰密碼學(xué)中的一個重要問題，具有非常顯著的實(shí)用價值。顯然，通過對一個隨機(jī)數(shù)進(jìn)行因子分解，我們可以判斷這個隨機(jī)數(shù)是否為素數(shù)。如果這個隨機(jī)數(shù)能被因子分解，則它不是素數(shù)，否則它一定是素數(shù)。但是，大素數(shù)的因子分解是一個復(fù)雜的問題，到現(xiàn)在還沒有找到一個快速有效的算法來對大整數(shù)進(jìn)行因子分解。因此，不能試圖通過對隨機(jī)數(shù)進(jìn)行因子分解來生成大素數(shù)。正確的生成大素數(shù)的方法是對生成的隨機(jī)數(shù)先測試它是否為素數(shù)，而不是對它進(jìn)行因子分解。這種素性測試比因子分解要容易得多，己經(jīng)有許多素性測試方法能夠確定一個隨機(jī)數(shù)是否為素數(shù)。如果合數(shù)通過一個素性測試的概率足夠小，則這個素性測試就是很可靠的。實(shí)際上，對于許多素性測試方法，合數(shù)通過測試的概率可以受到人為的控制，即是可以把合數(shù)通過測試的概率設(shè)定的足夠小。4.1.1素數(shù)的分布要討論素數(shù)的生成問題，首先要討論素數(shù)的分布。素數(shù)的分布是極不均勻的，素數(shù)越大，分布也就越稀疏。首先，存在無窮多個素數(shù)。對此，我們可以證明。假設(shè)正整數(shù)中只有k個素數(shù)，設(shè)為。令,則n>1。如果n是素數(shù)，則顯然n與都不相同，這與只有k個素數(shù)的假設(shè)相矛后。如果n不是素數(shù)，則n一定有一個素數(shù)因子,，否則由于以及,所以,這與p是素數(shù)相矛盾。故p與都不相同，這與只有k個素數(shù)的假設(shè)想矛盾。因此素數(shù)有無窮多個。其次，我們可以根據(jù)素數(shù)定理，發(fā)現(xiàn)素數(shù)的分布情況。素數(shù)定理的描述為:設(shè),為不大于x的整數(shù)的個數(shù)，則根據(jù)素數(shù)定理，可以估計出長度為t位的素數(shù)大約有個。例如，一個長度為256位的隨機(jī)數(shù)的素數(shù)的概率為而一個長度為64位的隨機(jī)數(shù)的素數(shù)的概率為由此可見，位數(shù)越多，素數(shù)的分布越為稀疏。4.1.2大素數(shù)生成的方法產(chǎn)生素數(shù)的一般方法可以分為兩類，即確定性素數(shù)產(chǎn)生方法和概率性素數(shù)產(chǎn)生方法。（1）確定性素數(shù)產(chǎn)生方法確定性素數(shù)產(chǎn)生方法產(chǎn)生的數(shù)必然是素數(shù)。然而其產(chǎn)生的素數(shù)卻帶有一定的限制。假若算法設(shè)計不佳，便容易構(gòu)造出帶有規(guī)律性的素數(shù)，使密碼分析者能夠分析出素數(shù)的變化，進(jìn)而可以猜到該系統(tǒng)中使用的素數(shù)。此類方法主要有兩類，即基于Lucas定理和基于Pocklington定理的確定性素數(shù)產(chǎn)生方法。這里簡單介紹基于Lucas定理的確定性素數(shù)產(chǎn)生方法。此方法需要求得素數(shù)n-1的全部素因子。Lucas定理：設(shè)，存在一個正整數(shù)且，且對于n-1的每一個素q，均滿足a，則n為素數(shù)。(2)概率性素數(shù)產(chǎn)生方法概率性素數(shù)產(chǎn)生方法產(chǎn)生的數(shù)僅僅是偽素數(shù)。其缺點(diǎn)在于，盡管其產(chǎn)生合數(shù)的可能性很小，但是這種可能性仍然存在:其優(yōu)點(diǎn)是產(chǎn)生的偽素數(shù)沒有規(guī)律性，而且產(chǎn)生的速度也比較快。此類方法是生成大素數(shù)的主要方法，其中著名有:MillerRabin與SolovayStrassen算法等。本文討論MillRabin算法。4.1.3MillerRabin素性測試法MillerRabin素性測試法是在實(shí)際中應(yīng)用非常廣的一種素性測試方案，可以用來判定某隨機(jī)數(shù)是否為素數(shù)。其定義如下:設(shè)是一個奇數(shù)，設(shè)，其中s是非負(fù)整數(shù)，是奇數(shù)，設(shè)，如果，或者存在一個r,，使得則稱n通過以b為基的Miller-Rabin測試。下面是Miller-Rabin素性測試的依據(jù)，包括兩個定理:定理一：設(shè)p是一個素數(shù)，對任意整數(shù)b，如果，則p一定可以通過以b為基的Miller-Rabin測試。定理二：如果n>2是一個奇合數(shù)，則至多有個b，0<b<n，使得n通過以b為基的Miller-Rabin測試。4.1.4基于MillerRabin素性測試法的新的素數(shù)生成方法這里提出一種將Miller-Rabin素性測試法和Lucas結(jié)合的強(qiáng)素數(shù)生成算法。強(qiáng)素數(shù)的概念GordonJ于1984年提出，強(qiáng)素數(shù)p應(yīng)該滿足4個條件:(1)p是一個位數(shù)足夠暢的隨機(jī)選取素數(shù);(2)p-1含有一個大的素數(shù)因子r;(3)p+1含有一個大的素數(shù)因子s;(4)r-1含有一個大的素數(shù)因子t。若p-1含有一個大的素數(shù)因子r，則，j為整數(shù)，由于p與r均為奇數(shù)(大素數(shù))，所以j一定是偶數(shù)。由此，也可以用如下三個等式來表示強(qiáng)素數(shù)p:綜上，若素數(shù)p滿足:，則稱p為強(qiáng)素數(shù)。Miller-Rabin素性測試法和Lucas結(jié)合的強(qiáng)素數(shù)生成算法步驟如下:(1)生成偽素數(shù)利用MillerRabin素數(shù)測試法，s為正整數(shù)，隨即選取D個小于s的不同正整數(shù)，若、關(guān)于它們均通過Miller檢測，則5為合數(shù)的概率不大于(1/4)D?；舅枷肴缢惴鞒虉D4-1所示下：若C為任意正整數(shù)，則每ln(c)個數(shù)中有一個素數(shù)，所以在m附近找Ln(m)次后仍末成功，便可重新生成隨機(jī)數(shù)m，繼續(xù)在m附近尋找。由于MillerRabin檢測不能百分之百確定一致為素數(shù)，所以要進(jìn)一步確證。(2)素數(shù)的確證基于Lucas定理，確定s是否為素數(shù)，算法基本思想如下1)分解n-1，使q，為不同素數(shù);2)a←1;3)a←a+l;4)若a≥n，則n可能非素數(shù)，轉(zhuǎn)3);5)若，轉(zhuǎn)7);否則轉(zhuǎn)3):6)，則n是素數(shù)，否則轉(zhuǎn)3);7)退出。(3)生成強(qiáng)偽素數(shù)首先，根據(jù)s求出r，使，令r形樣利用找到并確證r的素性。其次根據(jù)r求出p，使。如果P通過D(D>30)次MillerRabin檢測，則可以人為P是一個素數(shù)。大素數(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少密碼的長度。4.2密鑰的生成及加密和解密為了建立密碼系統(tǒng)，用戶A需要完成以下各步驟（1）A產(chǎn)生兩個大素數(shù)p和q；（2）A計算n=pq和；（3）A選擇一個隨機(jī)數(shù)，使得；（4）A計算；（5）A將n和a作為他的公鑰直接公開;（6）加密變換和解密變換。由上述過程，我們可以看出RSA加密系統(tǒng)的主要工作為大素數(shù)的生成、最大公因子gcd、模n求逆和模n的大數(shù)冪乘的算法。上一節(jié)，已經(jīng)討論了大素數(shù)的生成算法，這里主要討論最大公因子gcd、模n求逆和模n的大數(shù)冪乘的算法。4.2.1最大公因子gcd運(yùn)算這里采用經(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算法如下:(1);(2)(3)如r=0，則;(4)如果r≠0，則，，轉(zhuǎn)第(2)步。以下對這一算法稍作改進(jìn):令為Euclid算法中第i次對賦值后的值，為Euclid算法中第i次對賦值后的值，,規(guī)定。利用數(shù)學(xué)歸納法容易證明:對任意，存在整數(shù)使得事實(shí)上，當(dāng)時，取則顯然有假設(shè)i=j時，式(4-15)和(4-16)成立，則當(dāng)i=j+l時，其中q(j)為Euclid算法中第i次對q賦值后q的值，規(guī)定，因此從上面的討論可知，存在整數(shù)a和b使得.可以對Euclid算法做一點(diǎn)修改，使之可以同時求出gcd(n,u)和滿足上式的整數(shù)a和b，稱之?dāng)U展Euclid算法，此算法描述如下:(3)如果r=0，則;(4)如果r≠0，則，則轉(zhuǎn)(2)步。以上即為擴(kuò)展的Euclid算法，該算法在計算模n求逆時，頗有用處。4.2.2模n求逆元運(yùn)算這里來討論模n求逆元的算法。設(shè)n和u都是正整數(shù)，模n的逆就是滿足的整數(shù)v,?？梢宰C明，對于正整數(shù)，對于，存在。使得的充分必要條件是。證明必要性:對于任意，存在整數(shù)q使得,假設(shè)。因?yàn)?，所以，即對任意，都有，因此，如果存在，使得，則必然有。證明充分性：假設(shè)，則存在整數(shù)a和b使于是令，則。由上述定理的充要性證明可以得知，利用擴(kuò)展的Euclid算法可以求得u模n的逆，以擴(kuò)展的Euclid算法為基礎(chǔ)，可以得到模n求逆的算法如下：(1);(2);(3)如果r≠0，則；(4)如果≠1，則u模n不存在逆元；(5)如果=1，則u模n逆元為。舉例說明上述算法，求13模35的逆元:35=2×13+9,9=1×35-2×13,13=1×9+4,4=1×13-1×9=-1×35+3×9=2×4+1,1=1×9-2×4=3×35-8×13,所以13模35的逆元為4.2.3模n的大數(shù)冪乘運(yùn)算RSA公鑰密碼體制中，加密和解密時都要進(jìn)行運(yùn)算，下面給出一個計算的快速算法。(1)a←x,b←r,c←1;(2)如果b=0，則輸出結(jié)果c，結(jié)束;(3)如果bmod2≠0，則轉(zhuǎn)到第(5)步;(4)轉(zhuǎn)第(3)步:，(5)，轉(zhuǎn)第(2)步。舉例說明上述算法，求13模35的逆元:35=2×13+9,9=1×35-2×13,13=1×9+4,4=1×13-1×9=-1×35+3×13,9=2×4+1,1=1×9-2×4=3×35-8×13,所以13模35的逆元為(-8)mod35=2704.2.4模n的大數(shù)冪乘運(yùn)算RSA公鑰密碼體制中，加密和解密時都要進(jìn)行xrmodn的運(yùn)算，下面給出一個計算xrmodn的快速算法。(1)a←x,b←r,c←1;(2)如果b=0，則輸出結(jié)果c，結(jié)束;(3)如果，則轉(zhuǎn)到第(5)步;(4)b←b/2,轉(zhuǎn)第(3)步:，(5)，轉(zhuǎn)第(2)步。例如:計算322mod12以上主要介紹了RSA數(shù)字簽名過程中，每個密鑰和加密解密過程中所涉及到的相關(guān)的算法。以上算法，均從數(shù)論的角度加以論證，在理論上切實(shí)可行。當(dāng)然，在實(shí)際項(xiàng)目中，根據(jù)要求，某些步驟還尚需要做相應(yīng)的調(diào)整。4.3RSA算法分析RSA公鑰密碼體制是目前常用的一種密碼體制，無論從數(shù)論的角度，還是從實(shí)踐的角度，都己經(jīng)證明了RSA的正確性。雖然到目前為止，還沒有足夠的證據(jù)其安全性，但是依照目前的計算機(jī)運(yùn)算能力，要破譯RSA密鑰是有相當(dāng)難度的，所以RSA完全可以應(yīng)用于普通的電子商務(wù)和電子政務(wù)工作之中。4.3.1RSA安全性分析RSA的安全性，是基于大整數(shù)的素分解問題的難解性，即把n分解為p、q的困難程度。攻擊者破譯RSA公鑰密碼體制的步驟為:(1)分解n求出p、q;(2)由，求出由(3)由，求出d。為了更好地防范分解攻擊，RSA體制的發(fā)明者認(rèn)為要仔細(xì)地選擇素數(shù)p和q，在選擇p和q時還要注意以下方面:(1)p和q在位數(shù)上要相差幾位數(shù)字;(2)(p-1)和(q-1)都應(yīng)含有大的素數(shù)因子，以增加加攻擊者猜算出的困難性;(3)都應(yīng)當(dāng)小。使用RSA公鑰密碼體制，要求用戶選擇兩個素數(shù)p和q，其中p和q是保密的，并要求p與q不相等，對p和q的乘積可以公開。實(shí)際上，所謂攻擊者破譯RSA密碼體制，指的是由e,n來推算d,。若p>q，則可按以下步驟分解n:(1)因和由求得;(2)因，得到(3)由求出p;(4)q=r/p;這樣求得了P和q，完成了對r的因子分解。從數(shù)學(xué)上講，求一個對n不互素的數(shù)x就等價于破譯了算法。這是因?yàn)椋簒和r的gcd可能等于P或者q，而其值可以用歐幾里德算法計算出來。實(shí)際上，若r足夠大，則沒必要擔(dān)心由x這個數(shù)來破譯算法。在的區(qū)間中有個與r互素的數(shù)，且有個與r非互素的數(shù)。所以偶然出現(xiàn)含有p或q作為因子的一個數(shù)的概率等于:對于數(shù)值很大的p和q，這個概率是非常小的。以目前的常規(guī)個人計算機(jī)為工具來進(jìn)行因子分解，其工作量是非線性增長的，分析見表4-l:N的位數(shù)所需時間503.9小時75104天10074年2003.8×109年3004.0×1015年5004.2×1025年因此，在安全性要求不是特別高的系統(tǒng)中，可以認(rèn)為RSA是安全的。4.3.2RSA時間復(fù)雜度分析RSA運(yùn)算過程涉及到大量的計算，所需時間相對于DES等加密算法來說，運(yùn)算時間較長。但由于其良好的安全性和成熟的密鑰管理機(jī)制，RSA在實(shí)際工作中，被廣泛采用。4.4本章小結(jié)RSA從20世紀(jì)80年代產(chǎn)生至今，始終以其成熟的工作體制和良好的安全性而被廣泛的應(yīng)用于實(shí)際項(xiàng)目之中。RSA的安全性雖然沒有通過數(shù)學(xué)上的論證，因此，其安全性主要體現(xiàn)在大素數(shù)的分解這一復(fù)雜問題上。通過實(shí)踐證明，RSA在目前的計算機(jī)運(yùn)行能力下，還是相對安全的。RSA在未來的很長一段時間中，必將保持旺盛的生命力。近年來，隨著電子商務(wù)、電子政務(wù)等網(wǎng)上行為的增加，對于加密技術(shù)的研究日趨活躍。而對于RSA的研究，同樣處于活躍的狀態(tài)。由于RSA本身框架的成熟，因此，對于RSA的研究主要體現(xiàn)在，對其子步驟算法的改進(jìn)和研究，比如對于模n求逆算法的改進(jìn)、最大公因子算法的改進(jìn);將RSA和其他算法、體制結(jié)合應(yīng)用，比如目前在各計算機(jī)科技期刊上經(jīng)常見到的關(guān)于門限RSA體制的研究成果。本章主要討論了RSA內(nèi)部各步驟的算法實(shí)現(xiàn)。第5章RSA算法的實(shí)現(xiàn)基于前面的分析，本章給出了一種實(shí)現(xiàn)RSA的快速高效算法，并介紹了利用組合算法實(shí)現(xiàn)大整數(shù)快速模冪乘運(yùn)算的具體實(shí)現(xiàn)過程，以及在實(shí)現(xiàn)過程中所遇到的關(guān)鍵問題及解決方法。5.1選定組合算法的準(zhǔn)則1.準(zhǔn)確性原則一個算法必須滿足它自身是正確的，即可以得到想要的計算結(jié)果。2.高效性原則算法必須是有效的，即是高效的算法。3.簡單性原則簡單性原則不僅要使算法要盡量的容易實(shí)現(xiàn)，而且要盡量使程序容易被用戶使用。4.實(shí)用性原則要求算法確實(shí)可行，不僅是在理論上是正確的，還要求在實(shí)際上也能達(dá)到預(yù)期的效果。5.2模冪組合算法的實(shí)現(xiàn)本文前面介紹了一系列大數(shù)模冪運(yùn)算及其改進(jìn)算法，具體的實(shí)現(xiàn)方法步驟如下：（1）任意選取兩個不同的大質(zhì)數(shù)p和q，計算乘積；（2）任意選取一個大整數(shù)d，d與互質(zhì)，整數(shù)d用做加密密鑰。注重d的選取是很輕易的，例如所有大于p和q的質(zhì)數(shù)都可用.；（3）確定解密密鑰n，由，根據(jù)d，p和q可以輕易地計算出n，即為逆元；（4）公開整數(shù)r和d，但是不公開n；（5）規(guī)定明文動態(tài)分布空間L，輸入明文，通過計算成為密文；（6）將密文C解密為明文；具體程序見附錄。5.3試驗(yàn)與運(yùn)行結(jié)果開發(fā)環(huán)境：P43.0CPU，512M內(nèi)存，80G硬盤，17寸顯示器操作系統(tǒng)：WindowsXP開發(fā)工具：VisuslC++6.0仿真結(jié)果：其中p,q為2位素數(shù)，計算p與q的乘積，輸入整數(shù)d，d可以取大于p,q的素數(shù)小于p,q乘積，要求與(p－1)*(q－1)互質(zhì)，計算d的逆元，輸入明文動態(tài)空間L，要求明文字節(jié)數(shù)不得超過L，否則任務(wù)終止。系統(tǒng)計算密文，然后計算明文舉例如圖：輸入2個素數(shù)：p=11,q=311,當(dāng)輸入不是素數(shù)時會提示如下計算出p與q的乘積r為3421，（p-1）于(q-1)乘積為3100，輸入隨機(jī)大整數(shù)例如353，與3100僅有公約數(shù)1，如輸入錯誤時會有如下提示計算353的逆元,由n*d=1mod((p－1)*(q－1))可得逆元為2617，規(guī)定明文動態(tài)分配空間，此時我規(guī)定的是64個字節(jié)，輸入明文12345678，通過C=Pemodulor計算將會轉(zhuǎn)化為密文：126823071168383236924402366，再通過將其轉(zhuǎn)換回來就為12345678在實(shí)際生活中，取素數(shù)p=11,q=311,公開乘積r,保密d與逆元n，當(dāng)小A發(fā)出明文12345678時，對其加密，得到密文126823071168383236924402366，發(fā)給小C，他通過認(rèn)證可得到明文12345678總結(jié)在當(dāng)今的信息社會中，每天都有大量的信息在傳輸、交換存儲和處理，而這些處理過程幾乎都要依賴強(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é)與信息安全方面做了簡要的概述，具體論述了RSA公鑰密碼體制，RSA已經(jīng)成為一種國際公認(rèn)的公鑰密碼體制，在實(shí)際應(yīng)用中也最為廣泛。文章對RSA公鑰密碼體制的數(shù)學(xué)基礎(chǔ)，加密算法，簽名算法，安全性及參數(shù)的選擇做了詳細(xì)的討論。在當(dāng)今還沒有一個較RSA公鑰密碼系統(tǒng)更為優(yōu)秀的密碼系統(tǒng)出現(xiàn)之前，能夠有效地改進(jìn)RSA密碼算法的運(yùn)行速度也是當(dāng)今密碼學(xué)主要的一個研究方向。此外，在實(shí)踐中還可能發(fā)現(xiàn)本文研究未涉及的新問題，還需不斷的歸納、總結(jié)，并提出相應(yīng)的解決方法。參考文獻(xiàn)[1]盧開澄，郭保安，戴一奇等計算機(jī)系統(tǒng)安全.重慶:重慶出版社，1999[2]李海泉，李鍵.計算機(jī)系統(tǒng)安全技術(shù).北京:人民郵電出版社，2001[3]黃元飛，陳麟，唐三平.信息安全與加密解密核心技術(shù).上海:浦東電子出版社，2001[4]李紅軍，繆旭東.數(shù)據(jù)加密在網(wǎng)絡(luò)安全中的應(yīng)用.微型機(jī)與應(yīng)用，2002(10):3133[5]StevePurser.APracticalGuidetoManagingInformationSecurity.USA:ArtechHouseBooks,2004[6]王育民，劉建偉．通信網(wǎng)的安全．西安：西安電子科技大學(xué)出版社，1999，50-213[7]王宇潔，張曉丹，徐占文等．一種新的組合快速RSA算法．沈陽工業(yè)大學(xué)學(xué)報，2001，27(2)：224-227[8]DLou，CChang．Anadaptiveexponentiationmethod．TheJournalofsystemsandsoftware，1998，42：59-69[9]PhillipsBJ，BurgessN．Implementing1024-bitsRSAexponentiationona32-bitsprocessorcore．IEEEInternationalconferenceonApplicationSpecificSystems，Architectureandprocessor(ASAP’00)，2000[10]胡建軍，李愛武．中國剩余定理提高RSA解密速度的分析．現(xiàn)代計算機(jī)，2003，2(21)：10-11[11]馮登國等，《密碼學(xué)導(dǎo)引》，科學(xué)出版社，1999.4,4-12[12]曹珍富，《公鑰密碼學(xué)》，黑龍江教育出版社，1993.10,15-28[13]談嫻茹，基于DES和RSA的網(wǎng)絡(luò)數(shù)據(jù)安全系統(tǒng)，中國民航學(xué)院學(xué)報，2003.21(A02)，133-136[14]BruceSchneier著.吳世忠等譯《，應(yīng)用密碼學(xué)協(xié)議算法與c源程序》，機(jī)械工業(yè)出版社，2000,118-132[15]顧冠群等，密鑰管理的設(shè)計與實(shí)現(xiàn)，電信科學(xué)，1992.2,47-51[16]王立勝等，數(shù)據(jù)加密標(biāo)準(zhǔn)DES分析及其攻擊研究，計算機(jī)工程，2003,29(13)，130-132[17]王克苑等，SSL安全性分析研究，合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版)2004,27(1)，-87-91[18]劉鐵民等，VPN網(wǎng)絡(luò)隧道技術(shù)的研究，電信工程技術(shù)與標(biāo)準(zhǔn)化，2003(12).-55-57[19]張燕，數(shù)字簽名技術(shù)的研究，計算機(jī)時代，1998(5),20-22[20]賀衛(wèi)紅等，RSA公鑰密碼體制在數(shù)字簽名中的應(yīng)用，微機(jī)發(fā)展，2003(9)，49-51致謝本論文是在導(dǎo)師老師的悉心指導(dǎo)下完成的。從論文選題、資料收集、數(shù)據(jù)整理到論文的撰寫，每個環(huán)節(jié)老師都給予了我無微不至的關(guān)懷和毫無保留的指導(dǎo)，提出了許多寶貴的意見和建議。老師淵博的學(xué)術(shù)知識、嚴(yán)謹(jǐn)?shù)目蒲袘B(tài)度和誨人不倦的治學(xué)精神都在潛移默化的感染著我，使我受益匪淺，終生難忘。值此論文完成之際，請導(dǎo)師接受我最衷心的感謝和最誠摯的敬意。感謝等幾位同學(xué)在工作、學(xué)習(xí)中給予我的關(guān)心和支持，我們互相幫助，共同渡過了研究生階段學(xué)習(xí)的美好時光。感謝桂林理工大學(xué)的各位老師，特別是電子與計算機(jī)系的領(lǐng)導(dǎo)和老師們。他們在我的學(xué)習(xí)和論文撰寫、答辯過程中，均給予了我莫大的幫助。此致致謝基于C8051F單片機(jī)直流電動機(jī)反饋控制系統(tǒng)的設(shè)計與研究基于單片機(jī)的嵌入式Web服務(wù)器的研究MOTOROLA單片機(jī)MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機(jī)溫度控制系統(tǒng)的研制基于MCS-51系列單片機(jī)的通用控制模塊的研究基于單片機(jī)實(shí)現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機(jī)控制的二級倒立擺系統(tǒng)的研究基于增強(qiáng)型51系列單片機(jī)的TCP/IP協(xié)議棧的實(shí)現(xiàn)基于單片機(jī)的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機(jī)系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機(jī)的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機(jī)的交流伺服電機(jī)運(yùn)動控制系統(tǒng)研究與開發(fā)基于單片機(jī)的泵管內(nèi)壁硬度測試儀的研制基于單片機(jī)的自動找平控制系統(tǒng)研究基于C8051F040單片機(jī)的嵌入式系統(tǒng)開發(fā)基于單片機(jī)的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機(jī)實(shí)現(xiàn)一種基于單片機(jī)的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機(jī)的在線間歇式濁度儀的研制基于單片機(jī)的噴油泵試驗(yàn)臺控制器的研制基于單片機(jī)的軟起動器的研究和設(shè)計基于單片機(jī)控制的高速快走絲電火花線切割機(jī)床短循環(huán)走絲方式研究基于單片機(jī)的機(jī)電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機(jī)的智能手機(jī)充電器基于單片機(jī)的實(shí)時內(nèi)核設(shè)計及其應(yīng)用研究基于單片機(jī)的遠(yuǎn)程抄表系統(tǒng)的設(shè)計與研究基于單片機(jī)的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機(jī)系統(tǒng)單片機(jī)系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機(jī)的液體點(diǎn)滴速度自動檢測儀的研制基于單片機(jī)系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機(jī)的電能采集終端的設(shè)計和應(yīng)用基于單片機(jī)的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機(jī)單片機(jī)控制系統(tǒng)的研制基于單片機(jī)的數(shù)字磁通門傳感器基于單片機(jī)的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機(jī)的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機(jī)控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機(jī)的多生理信號檢測儀基于單片機(jī)的電機(jī)運(yùn)動控制系統(tǒng)設(shè)計Pico專用單片機(jī)核的可測性設(shè)計研究基于MCS-51單片機(jī)的熱量計基于雙單片機(jī)的智能遙測微型氣象站MCS-51單片機(jī)構(gòu)建機(jī)器人的實(shí)踐研究基于單片機(jī)的輪軌力檢測基于單片機(jī)的GPS定位儀的研究與實(shí)現(xiàn)基于單片機(jī)的電液伺服控制系統(tǒng)用于單片機(jī)系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機(jī)的時控和計數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機(jī)和CPLD的粗光柵位移測量系統(tǒng)研究單片機(jī)控制的后備式方波UPS提升高職學(xué)生單片機(jī)應(yīng)用能力的探究基于單片機(jī)控制的自動低頻減載裝置研究基于單片機(jī)控制的水下焊接電源的研究基于單片機(jī)的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機(jī)的氚表面污染測量儀的研制基于單片機(jī)的紅外測油儀的研究96系列單片機(jī)仿真器研究與設(shè)計基于單片機(jī)的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機(jī)的溫度智能控制系統(tǒng)的設(shè)計與實(shí)現(xiàn)基于MSP430單片機(jī)的電梯門機(jī)控制器的研制基于單片機(jī)的氣體測漏儀的研究基于三菱M16C/6N系列單片機(jī)的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機(jī)和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機(jī)的膛壁溫度報警系統(tǒng)設(shè)計基于AVR單片機(jī)的低壓無功補(bǔ)償控制器的設(shè)計基于單片機(jī)船舶電力推進(jìn)電機(jī)監(jiān)測系統(tǒng)基于單片機(jī)網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機(jī)的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機(jī)的疊圖機(jī)研究與教學(xué)方法實(shí)踐基于單片機(jī)嵌入式Web服務(wù)器技術(shù)的研究及實(shí)現(xiàn)基于AT89S52單片機(jī)的通用數(shù)據(jù)采集系統(tǒng)基于單片機(jī)的多道脈沖幅度分析儀研