網(wǎng)絡與信息安全課程設計報告

網(wǎng)絡與信息安全》課程設計報告班級：07網(wǎng)絡工程（3）班學號： 姓名：韓立偉題目： 加密軟件的設計評閱:成績:2010-1-07RSA算法加密軟件的設計摘要：分析RSA算法的應用現(xiàn)狀，論證文件加密應用RSA算法的可行性和意義。設計一套完整實用的RSA文件加密解決方案，具體編碼實現(xiàn)。對RSA算法進行研究，從常規(guī)RSA算法出發(fā)，用C#實現(xiàn)RSA加密算法類庫，并在32位windows平臺封裝成組件。在.Net平臺引用此組件，實現(xiàn)可以對任意文件進行RSA加密操作的窗體應用程序。經(jīng)過加密的文件以及密鑰文件都是文本文件。給出關鍵類類圖、整個應用程序的結構描述文檔、關鍵模塊流程圖、較詳細的接口文檔、所有源代碼。對應用程序進行測試，對測試結果進行分析研究，進而對應用程序進行改進，對關鍵算法進行盡可能的優(yōu)化，最終得到一個在windows運行的可以用指定密鑰對任意文件進行RSA加密并可解密的完整應用程序，和一些相關的可移植組件。關鍵詞：rsa,RSA算法，文件加密，加密成文本目錄TOC\o"1-5"\h\z\o"CurrentDocument"第1章RSA應用現(xiàn)狀及應用于文件加密的分析 ?4\o"CurrentDocument"RSA算法介紹與應用現(xiàn)狀 .4\o"CurrentDocument"RSA應用于文件加密的分析 .5\o"CurrentDocument"1.2.1文件加密使用RSA的可行性 5\o"CurrentDocument"1.2.2文件加密使用RSA的意義 6\o"CurrentDocument"第2章RSA文件加密軟件的設計與實現(xiàn) 7\o"CurrentDocument"2.1需求分析與總體設計 7\o"CurrentDocument"功能分析 7\o"CurrentDocument"工程方案選擇 8\o"CurrentDocument"2.2各部分的設計與開發(fā) 10\o"CurrentDocument"2.2.1實現(xiàn)RSA加密算法的C#核心類庫 10\o"CurrentDocument"3.2測試數(shù)據(jù)與分析改進 14\o"CurrentDocument"3.2.1密鑰生成測試 14\o"CurrentDocument"3.2.2數(shù)據(jù)輸入輸出測試 16\o"CurrentDocument"3.2.3加密解密測試 16\o"CurrentDocument"總結與體會 .17致謝 .17參考文獻…………17—1—前言RSA公鑰加密算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也十分流行。算法的名字以發(fā)明者的姓氏首字母命名：RonRivest,AdiShamir和LeonardAdleman。雖然自1978年提出以來，RSA的安全性一直未能得到理論上的證明，但它經(jīng)歷了各種攻擊，至今(2007年)未被完全攻破。隨著越來越多的商業(yè)應用和標準化工作，RSA已經(jīng)成為最具代表性的公鑰加密技術。VISA、MasterCard、IBM、Microsoft等公司協(xié)力制定的安全電子交易標準(SecureElectronicTransactions,SET)就采用了標準RSA算法，這使得RSA在我們的生活中幾乎無處不在。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗證、各種信用卡使用的數(shù)字證書、智能移動電話和存儲卡的驗證功能芯片等，大多數(shù)使用RSA技術。當今公鑰加密更廣泛應用于互聯(lián)網(wǎng)身份認證，本課題將公鑰加密算法RSA應用于小型文件加密。將任意文件加密成文本的解決方案，使其使用更加靈活。整個工程的分層設計給引用移植和后續(xù)開發(fā)帶來便利。第1章RSA應用現(xiàn)狀及應用于文件加密的分析1.1RSA算法介紹與應用現(xiàn)狀RSA算法可以簡單敘述如下：＜密鑰生成＞取素數(shù)p,q,令n=pXq.取與(p-1)X(q-1)互素的整數(shù)e,由方程dXe=l(mod(p-1)X(q-1))解出d,二元組(e,n)作為公開密鑰，二元組(d,n)作為私有密鑰.＜加密解密＞b=aemodn,c=bdmodn.附錄中給出了證明a=c(modn).RSA公開密鑰加密算法自20世紀70年代提出以來，已經(jīng)得到了廣泛認可和應用。發(fā)展至今，電子安全領域的各方面已經(jīng)形成了較為完備的國際規(guī)范。RSA作為最重要的公開密鑰算法，在各領域的應用數(shù)不勝數(shù)。RSA在硬件方面，以技術成熟的IC應用于各種消費類電子產(chǎn)品。RSA在軟件方面的應用，主要集中在Internet上。加密連接、數(shù)字簽名和數(shù)字證書的核心算法廣泛使用RSA。日常應用中，有比較著名的工具包OpenSSL(SSL,SecuritySocketLayer,是一個安全傳輸協(xié)議，在Internet上進行數(shù)據(jù)保護和身份確認。OpenSSL是一個開放源代碼的實現(xiàn)了SSL及相關加密技術的軟件包，由加拿大的EricYang等發(fā)起編寫的。相關詳細介紹見/about/)°0penSSL應用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è)級商務應用中。在當今的企業(yè)級商務應用中，不得不提及使用最廣泛的平臺j2ee。事實上，在j2se的標準庫中，就為安全和加密服務提供了兩組API：JCA和JCE。JCA(JavaCryptographyArchitecture)提供基本的加密框架，如證書、數(shù)字簽名、報文摘要和密鑰對產(chǎn)生器；JCA由幾個實現(xiàn)了基本的加密技術功能的類和接口組成，其中最主要的是java.security包,此軟件包包含的是一組核心的類和接口，Java中數(shù)字簽名的方法就集中在此軟件包中。JCE(JavaCryptographyExtension)在JCA的基礎上作了擴展，JCE也是由幾個軟件包組成，其中最主要的是javax.crypto包，此軟件包提供了JCE加密技術操作API。javax.crypto中的Cipher類用于具體的加密和解密。在上述軟件包的實現(xiàn)中，集成了應用RSA算法的各種數(shù)據(jù)加密規(guī)范(RSA算法應用規(guī)范介紹參見：/rsalabs/node.asp?id=2146，這些API內部支持的算法不僅僅只有RSA，但是RSA是數(shù)字簽名和證書中最常用的)，用戶程序可以直接使用java標準庫中提供的API進行數(shù)字簽名和證書的各種操作。單機應用程序使用RSA加密尚比較少見，例如使用RSA加密任意一個文件。RSA應用于文件加密的分析1.2.1文件加密使用RSA的可行性通過1.1節(jié)的論述，不難看出RSA當今的應用多在于數(shù)字簽名和證書等方面。之所以只應用于這些短小數(shù)據(jù)的加密解密，是因為RSA算法加密極慢，速度是DES對稱密鑰加密速度的千分之一左右。正是因為這樣，把RSA應用于普通文件加密的想法一直被忽略。通常文件被想象成大數(shù)據(jù)塊，但是實際上在日常應用中，有些極其重要的文本資料是并不太大的，比如因擔心遺忘而用普通文本記錄的銀行帳號和密碼、不應被陌生人知道的重要電話號碼、幾千字節(jié)大的重要小圖片等。其實從一個簡單的角度來說，既然RSA用于數(shù)字簽名可行，那就完全可以用于同樣大小的普通文件。對于較大的文件，如果分成與數(shù)字簽名同樣大小的段(這里假設數(shù)字簽名較短，不分段一次計算加密完成)，分開的各段逐一進行加密運算，那所需要的時間也只是按文件大小線性的增長。通常數(shù)字簽名為幾十字節(jié)，加密運算并不需要很長的等待，這就說明對于幾百字節(jié)或一兩K字節(jié)大小的文件來說，如果進行RSA加密,并不會是非常漫長的工作。當然，如果文件更大，加密就顯得十分漫長了。比如按前面敘述的45毫秒大數(shù)運算程序推理，加密1M字節(jié)大小的文件需要約1天的時間。所以，要在普通PC用幾百位以上的長密鑰RSA加密文件，文件不能過大，一般可以接受的上限是幾KB。如果要在較短時間內加密大文件，需要縮短密鑰長度以減小運算量，這將帶來安全性隱患。本文的第3章將根據(jù)實際調試好的軟件，測試給出具體的時間消耗數(shù)據(jù)。例如，在一臺配置為AMDAthron2800+,外頻333MHZ,物理內存512MB的PC上測試實現(xiàn)的軟件，以560bit的n逐字節(jié)加密一個1KB大小的文件需要55秒。通常記錄如銀行帳號密碼等重要數(shù)據(jù)的文本文件大小不足百字節(jié)，加密只需要數(shù)秒鐘。所以對于小型文件，進行較長密鑰的RSA加密是完全可行的。文件加密使用RSA的意義如1.2.1節(jié)所述，小型文件加密可以使用RSA。比如，因擔心遺忘而用普通文本記錄的銀行帳號和密碼、不應被陌生人知道的重要電話號碼、幾千字節(jié)大的重要小圖片等?？尚械姆椒ㄎ幢厥潜匾模拘」?jié)討論何種文件適合用非對稱密鑰加密，即RSA加密文件的意義所在。對于前面敘述的帶有重要信息的小型文本和二進制數(shù)據(jù)的維護，①如果不加密，將無法放心的保存在計算機上，尤其是連網(wǎng)的或機房里的公共計算機。②如果借助功能強大的大型多用戶數(shù)據(jù)保護程序維護幾個小型文件，顯得十分煩瑣，好比殺雞用牛刀。③如果采用對稱密鑰加密，即加密解密的密鑰相同，只適合部分情況。在某些情況下，使用對稱密鑰加密文件，交流使用不夠方便。比如，張三由于某種原因，需要將自己的某個文件在公共計算機上留給李四，而不希望別人看到內容。如果采用對稱密鑰加密，張三和李四提前約好一個密碼就可以。但是如果張三想要在同一臺公共計算機上再留一個秘密文件給王五，而不希望別人看到，就要和王五另外約定一個密碼。如果需要在這臺公共計算機上留十個文件給不同的人，自己就要記和十個人約定好的密碼，這樣以來交流起來不夠方便，因為對于張三，要自己維護太多的密鑰。非對稱密鑰（公開密鑰方式）恰好解決這樣的問題。只要大家都在這臺計算機或這臺計算機可以訪問到的地方，留下自己的公開密鑰，一切就變的容易解決了。張三要留給李四的文件，就用李四的公開密鑰加密，要留給王五的文件，就用王五的公開密鑰加密。李四和王五只要把留給自己的文件用自己的私有密鑰解密，就可以得到留給自己的文件了。顯然，非對稱密鑰體制更適合多用戶交流，而將這種加密方式直接應用于文件加密，使我們在公開場合的交流更加靈活方便。一種更實際的情況是，我們想通過Internet上的公眾論壇或郵件發(fā)送重要保密信息給某人。例如發(fā)送一個銀行帳號和密碼給某人。這種情況要保證安全，在當今互聯(lián)網(wǎng)絡上是比較棘手的。①如果用公眾論壇直接留言給指定用戶，論壇管理員和服務器管理員通常有方法看到數(shù)據(jù)。②如果發(fā)送郵件，雖然傳送過程是加密的，但是密碼畢竟是由郵件服務器維護，所以系統(tǒng)管理員通常也有辦法看到內容。問題的關鍵在于我們所有的數(shù)據(jù)包括密鑰保存在服務器之上。在這種情況下，我們需要使用公開密鑰方式，并自己維護私有密鑰oRSA文件加密可以靈活的解決這些問題。例如，我們可以將任意一個文件用某人的公開密鑰加密變換成一段可以復制粘貼的文本，然后粘貼在公眾互聯(lián)網(wǎng)上，對方只需把需要解密的文本復制保存成一個文本文件，在本地機用自己的私有密鑰解密即可。我們可以將自己的私有密鑰通過DES加密后保存在自己的移動磁盤上，使用的時候只要將其解密讀取即可，用完后立即從當前操作環(huán)境清除。這樣，我們自己維護自己的私有密鑰，利用簡單并且公開的方式，可以安全傳送任意小型數(shù)據(jù)，包括一切二進制文件。所以，對于使用小型文件進行數(shù)據(jù)交換的情況，更好的方案是通過一個小型應用程序對這些文件進行非對稱密鑰加密。為了適合前面敘述的在公共BBS與特定的某人交流重要保密信息的情況，加密生成的數(shù)據(jù)應該是文本，這樣可以方便復制粘貼。綜上所述，使用前面敘述的方式加密文件有兩點重要意義：①應用非對稱密鑰加密任意文件，使非對稱密鑰的應用不僅僅局限于互聯(lián)網(wǎng)絡。②非對稱加密后的數(shù)據(jù)變換成文本，使得我們可以通過幾乎任何方式安全傳遞任意文件，比如在只有http的環(huán)境使用xml方式。第2章RSA文件加密軟件的設計與實現(xiàn)2.1需求分析與總體設計2.1.1功能分析經(jīng)過1.2.2節(jié)的論述，我們可以將對軟件的要求總結如下：可以按要求的位數(shù)生成非對稱密鑰?？梢员４婷荑€和裝載密鑰，密鑰保存為純文本?？梢杂弥付荑€以RSA算法加密任意一個文件，加密生成的數(shù)據(jù)為純文本。可以裝載加密過的文件，并用指定的密鑰解密還原出原文件。提示信息完整、操作舒適、圖形界面雅觀按上述描述，給出UseCase和Statechart如圖2T。

確定了戟幾的密胡決型(pibhckeyorprwatekey)密韜文件成功打開并讀入了昭應?■了RSA相關的各*

笄戰(zhàn)功顯示了更新結果AT7k：r^Ttc-

了保存撫柞成功中中「云賓培：E甲『I空絹確定了戟幾的密胡決型(pibhckeyorprwatekey)密韜文件成功打開并讀入了昭應?■了RSA相關的各*

笄戰(zhàn)功顯示了更新結果AT7k：r^Ttc-

了保存撫柞成功中中「云賓培：E甲『I空絹I書竹蓋存內publickmyu-privatAkey)功寫入丈件圖形用=界■血給出11童航辭童云,t￡J尖下I 準務奸了將捉作的皴據(jù)罐存區(qū)〔從:仃衿、r戸九陸丈辭密的數(shù)據(jù)圖2-1本項目的UseCase和Statechart根據(jù)以上分析，一般來說，需要進行編碼的程序有①RSA密鑰生成②RSA加密解密③任意文件的讀取和保存操作④各環(huán)節(jié)必要的數(shù)據(jù)編碼轉換⑤圖形操作界面。2.1.2工程方案選擇結合現(xiàn)有的常見開發(fā)模式綜合分析，有多種實現(xiàn)方案，下面陳述其中幾種，并分析選擇一種解決方案，并給出工程框架。(1.)整個工程使用java平臺實現(xiàn)RSA密鑰生成、RSA加密解密的功能實現(xiàn)十分簡單，因為標準庫中集成幾乎所有功能，不需要從RSA算法出發(fā)進行編碼。在j2se標準庫中，javax.crypto中的Cipher類用于具體的加密和解密，java.security包直接提供了數(shù)字簽名的相關方法。因為有強大的標準庫支持，文件的讀取和保存操作、各環(huán)節(jié)必要的數(shù)據(jù)編碼轉換、圖形操作界面的實現(xiàn)也很簡單(使用java.iojava.awt或javax.swing等包)，如果結合一種快速開發(fā)的IDE，比如JBuilder，整個軟件可以在很短的時間內編碼完成。如果不考慮非PC設備和機器效率等問題，java平臺幾乎是最佳解決方案。但是缺點也很明顯，如果想把核心算法和功能應用到非PC設備(例如嵌入式手持設備)，則要求設備上有支持前面提及的加密類庫的CVM；對于在PC上運行，JVM的數(shù)據(jù)運算速度要遠遠落后于本地化代碼在PC上的運算速度，本軟件需要進行大量運算，這一點不適合由java完成。(2.)整個工程使用.Net平臺實現(xiàn)與使用java平臺完全類似，加密等有.Net基礎類庫的支持，不需要大量編碼實現(xiàn)，另外由于VisualStudio的強大便利，這種規(guī)模的工程可以十分迅速的完成。缺點是只能在有微軟.NetFramework的環(huán)境運行，在Windows操作系統(tǒng)，.NetFramework的機器效率好于java平臺，但是相比于本地化的代碼，還是十分拖沓的。(3.)整個工程使用Windows本地化程序實現(xiàn)在不應用Windows或第三方現(xiàn)成組件的情況下，需從RSA算法出發(fā)編碼實現(xiàn)。其他各功能的設計開發(fā)，如文件操作、數(shù)據(jù)編碼轉換和圖形界面等，可以使用ATL、MFC或WindowsAPI實現(xiàn)。這種工程幾乎是為Windows量身訂做，執(zhí)行效率最好。但是對于非PC設備，只能方便的移植到運行Windows嵌入式操作系統(tǒng)的設備，向其他操作系統(tǒng)移植困難，需要重新編寫大量代碼。通常解決本地化代碼的移植問題，都是使用C++標準庫，即功能盡量多的由C++標準庫完成，這樣在移植的時候，只需要重新編寫操作系統(tǒng)相關的代碼即可。這種開發(fā)方式比起前兩種，缺點就是設計開發(fā)模式陳舊，代碼煩瑣，不方便維護；流行的Net上的語言引用各種功能比較麻煩。(4.)考慮可能的復用，針對具體情況分層開發(fā)實現(xiàn)綜合考慮復用性、可維護性和執(zhí)行效率，較妥當?shù)姆椒ㄊ欠謱釉O計。核心的RSA算法由C++類庫實現(xiàn)，針對用戶所在的操作系統(tǒng)封裝成本地化組件。其他各功能如文件操作、數(shù)據(jù)編碼轉換和圖形界面等，由托管代碼借助虛擬機平臺標準庫的功能快速開發(fā)實現(xiàn)(本文針對選用.Net上的C#論述，選用java由JNI或其他方式調用本地組件，設計模式上是完全類似的)。這種開發(fā)方式，核心功能集中在最底層，在不斷的封裝中針對具體環(huán)境對組件功能不斷擴充，任意一個層面的封裝都可以被直接應用到其他項目，比如在Web使用以前為某窗體程序寫的組件、給嵌入式設備交叉編譯算法庫等。但是每一層都需要依賴底層的所有組件。圖2-2形象的說明了分層設計給復用帶來的好處。選用第四種設計方案，上層使用C#,底層算法使用C++，可以由一個VisualStudio解決方案管理，給調試帶來極大的方便。整個工程分四層，實現(xiàn)RSA加密算法的C++核心類庫、封裝C++核心類庫的DLL組件、引用DLL的.Net類、實現(xiàn)文件操作功能的.Net窗體應用程序。2.2節(jié)詳細介紹各部分的設計與開發(fā)?？紤]到工作量，本軟件加解密數(shù)據(jù)沒有嚴格遵從RSA標準PKCS#1，而是在滿足設計要求的前提下，以一種盡可能簡單的方式實現(xiàn)加密和解密。2.2各部分的設計與開發(fā)2.2.1實現(xiàn)RSA加密算法的C#核心類庫(1.)大數(shù)存儲和四則運算根據(jù)RSA算法的要求，為了實現(xiàn)大數(shù)的各種復雜運算，需要首先實現(xiàn)大數(shù)存儲和基本四則運算的功能。當今開源的大數(shù)運算C++類有很多，多用于數(shù)學分析、天文計算等，本文選用了一個流行的大數(shù)類型，并針對RSA算法和本項目的具體需要對其進行了擴充和改進。下面簡單介紹大數(shù)存儲和四則運算的實現(xiàn)原理。最先完成的功能是大數(shù)的存儲，存儲功能由flex_unit類提供。和普通的類型一樣，每一個大數(shù)對應一個flex_unit的實例。類flex_unit中,用一個無符號整數(shù)指針unsigned*a指向一塊內存空間的首地址，這塊內存空間用來存儲一個大數(shù)，所以可以說，大數(shù)是被存儲在一個以unsigned為單元的線性組中。在方法voidreserve(unsignedx)中通過C++的new來給a開辟空間，當flex_unit的實例中被存入比當前存儲的數(shù)更大的數(shù)時，就會調用reserve來增加存儲空間,但是當flex_unit的實例中被存入比當前存儲的數(shù)更小的數(shù)時，存儲空間并不會自動緊縮，這是為了在運算的時候提高執(zhí)行效率。結合指針a,有兩個重要的無符號整數(shù)來控制存儲，unsignedz和unsignedn，z是被分配空間的單元數(shù)，隨數(shù)字變大不斷增大，不會自己緊縮，而n是當前存儲的大數(shù)所占的單元數(shù)，組成一個大數(shù)的各unsigned單元的存入和讀出由set、get方法完成，變量n是只讀的。類型unsigned在32位機是32位的，所以對于flex_unit這個大數(shù)類來說，每個大數(shù)最大可以達到個字節(jié)長，這已經(jīng)超過了32位機通常的最大內存容量，所以是足夠進行RSA所需要的各種運算的。圖2-3形象的說明了大數(shù)存儲類flex_unit對大數(shù)的管理。(2.)尋找素數(shù)?Eratosthenes篩選與Fermat素數(shù)測試首先要說明的是，事實上，當今的計算機還不足以聰明到立刻計算生成一個很大的隨機素數(shù)。一般來說，要得到100%準確的大素數(shù)，都是通過查已經(jīng)計算好的素數(shù)表的方式。但是素數(shù)表的方式給RSA的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所使用的素數(shù)表，攻破RSA加密的難度將會大大降低。本程序起初使用素數(shù)表的方式，后來考慮到安全性問題，生成密鑰的方式改為隨機計算生成。這樣，短時間內如果要得到一個100%準確的大素數(shù)是很困難的，只能以盡可能高的概率得到一個大素數(shù)。經(jīng)過和小節(jié)，所有的大數(shù)運算功能都準備完畢，在此基礎上，本工程將尋找素數(shù)的功能置于類Prime_factory_san之中。外部只要調用本類實例的成員vlongfind_prime(vlong&start)就可以以大數(shù)start為起點，得到一個數(shù)，這個數(shù)是素數(shù)的概率很大。下面介紹尋找素數(shù)的原理。首先在需要尋找素數(shù)的整數(shù)范圍內對整數(shù)進行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構造了一個數(shù)組b[]，大小為一輪素數(shù)搜索的范圍，記搜索范圍大小為SSOb[0]到b[SS]分別對應大數(shù)start到start+SS。b[]中所有元素先初始化為1,如果對應的大數(shù)確定為合數(shù)，就將b[]中對應的元素置為0。最后，只需對那些b[]中為1的元素對應的大數(shù)進行比較確切的素數(shù)測試即可，只要被測試的數(shù)是素數(shù)概率達到一定門限，就判這個數(shù)為素數(shù)。這樣做既保證了這段程序可以在短時間內執(zhí)行完，又保證了可以以比較高的準確度得到素數(shù)。函數(shù)find_prime先把b□的所有元素賦值為1,然后按參數(shù)start給標記數(shù)組b[]的各元素賦0值。下面描述標記數(shù)組b[]的賦0值算法。首先，在類Prime_factory_san被構造的時候，構造函數(shù)中從2開始搜尋一些小素數(shù)，記錄在數(shù)組pl[]中，共記錄NP個。這些小素數(shù)用來當作因子，他們的倍數(shù)將被從大素數(shù)搜索范圍內剔除(即把數(shù)組b[]的對應元素標記為0)，剔除的程序代碼如下。for(i=0;i<np;i++){unsignedp=pl[i];unsignedr=start%vlong(p);if(r)r=p-r;while(r<SS)

{b[r]=0;r+=p;}}這里利用start對各小素數(shù)因子p求模的辦法，得到當前p在素數(shù)搜索范圍內的最小倍數(shù)在b[]中的對應位置，將其剔除后，不斷后移p個位置，將這個小素數(shù)因子p在搜索范圍內的所有倍數(shù)全部剔除，如圖2-5所示。在完成對所有小素數(shù)因子的類似操作后，他們的倍數(shù)在搜索范圍內的位置標記b[r]被全部標記為0。實際上這就是Eratosthenes篩選法。b[x]b[x+p]b[x+2p]b[x+3p]b[x+4p] b[x+5p]數(shù)軸素數(shù)搜索范圍start到start+SS小素數(shù)因b[x]b[x+p]b[x+2p]b[x+3p]b[x+4p] b[x+5p]數(shù)軸素數(shù)搜索范圍start到start+SS小素數(shù)因.子P搜索起點start對應b[0]住巨離start：p-(start丿—modp)$：剔除。b中對應元素標記為0設在剛執(zhí)行到while時r>0x=r圖2-5在素數(shù)搜索范圍內剔除小素數(shù)因子p的倍數(shù)接下來，對可能為素數(shù)的數(shù)(即標記數(shù)組b[]中值為1的元素對應的數(shù))進行素數(shù)測試。數(shù)論學家利用費馬小定理研究出了多種素數(shù)測試方法，本程序使用一種最簡單的方式，直接應用費馬小定理。取一個與p互素的整數(shù)A，對于大素數(shù)p來說應該滿足Ap-1modp=1,但是我們把p代入一個大整數(shù)，滿足這個關系的數(shù)不一定是素數(shù)。這時我們改變A,進行多次測試，如果多次測試都通過，這個數(shù)是素數(shù)的概率就比較大。按這種原理，我們編寫素數(shù)測試函數(shù)如下。intis_probable_prime_san(constvlong&p){constrep=4;//測試次數(shù)constunsignedany[rep]={2,3,5,7};//測試用的底數(shù)for(unsignedi=0;i<rep;i+=1)if(modexp(any[i],p-vlong(1),p)!=vlong(1))return0;//modexp是幕模函數(shù)，按上一小節(jié)敘述的算法編碼。//這里modexp計算any[i]p-imodp。return1;}測試通過，程序就判定這個數(shù)為找到的素數(shù)，將找到的素數(shù)返回給上層程序使用。在這里其實有一個不可忽視的問題，就是得到一個測試通過的合數(shù)。對于這種情況，RSA算法加密解密是否還可以實現(xiàn)，是一個需要從數(shù)學角度論證的問題。因為得到素數(shù)的概率很高經(jīng)過一整天的生成密鑰和加密操作，沒有發(fā)現(xiàn)失敗的密鑰，所以本文暫沒有對這個問題進行討論。綜上所述，總結素數(shù)尋找的流程，如圖2-6所示。圖2-6函數(shù)find_prime尋找素數(shù)的流程框圖得到了大素數(shù)，即RSA算法中的p、q,我們就可以計算出密鑰，進行加密等操作了。3.2測試數(shù)據(jù)與分析改進3.2.1密鑰生成測試生成密鑰運算最費時的工作是尋找素數(shù)。如小節(jié)所敘述，尋找素數(shù)是一項頗為復雜的工作，其速度可能受以下變量的影響：RSA加密需要的n的位數(shù)（尋找素數(shù)的整數(shù)起點大小start）、大素數(shù)測試時底數(shù)A的個數(shù)（針對一個整數(shù)的素數(shù)測試次數(shù)）、小素數(shù)因子p的個數(shù)NP、一輪尋找遍歷的整數(shù)個數(shù)SS等。其中最具影響力的因素顯然是RSA加密需要的n的位數(shù)。以下對各變量分別進行測試，暫且忽略操作系統(tǒng)調度對測試的影響。（1.）測試加密使用的n位數(shù)對耗時的影響即在固定A、NP、SS等變量的情況下，改變加密位數(shù)n,測試密鑰生成的時間消耗情況。測試時，A取4個值，分別為2、3、5、7，NP取200，SS取1000。測試PC配置為CPUCR1.7GHZ/外頻100MHZ/物理內存512MDDR/MSI6398主板845Ultra-AD芯片組，下文測試中，未說明PC配置的也都在同一PC完成，不再重復。在較常用的1024位RSA加密時，用本軟件的算法，測試時最長出現(xiàn)了17秒多的計算，雖然這對于用戶來說時漫長的等待，但是考慮到安全性，還是舍棄了素數(shù)表和密鑰庫的方案，而使用大素數(shù)隨機生成，用戶可以把生成的私鑰單獨加密保存在可靠的存儲空間內，以獲得更高的安全性。表3-1僅能從實驗的角度直觀理解，具體到一次密鑰生成的運算，所需要的時間是很不確定的，比如，一次1280位的密鑰生成，需要的時間完全可能比一次896位的密鑰生成時間短，由于素數(shù)分布規(guī)律非常奧妙，加上測試運算需要的時間頗長，這里很難給出對于一個具體位數(shù)的密鑰生成所需時間的統(tǒng)計模型。另外需要說明的是，表3-1的加密位數(shù)在實際軟件設置時并不嚴格。這是因為，實際作為參數(shù)設置的是兩個大素數(shù)的搜索起點。如果隨機生成的起點整數(shù)大小比較接近更長一位的整數(shù)的話（例如FFFF很接近10000）,向后尋找所得到的素數(shù)很可能長出一位。而且，兩個k位長的整數(shù)相乘的結果也未必是2k位，比如100*100=10000，相乘結果是2k-1位。所以，在表3-1實際測試填寫時，加密位數(shù)可能會有幾位的差距，但是這不礙大局。（2.）測試底數(shù)A對耗時的影響為了保證生成素數(shù)的成功率，A至少要有4個。如果少于4個，則素數(shù)測試失敗的可能性比較大，經(jīng)過測試發(fā)現(xiàn)不可以忽略。小節(jié)曾經(jīng)提到，如果素數(shù)測試通過了合數(shù)，就可能產(chǎn)生錯誤的密鑰，使加密解密操作失敗。所以測試A的時候，最少有讓其取4個值。而取6個值以上，測試算法失敗的概率已經(jīng)非常小，沒有什么實用意義，所以這里測試A從4個到6個的情況。固定其他變量：n取512位和1024位（即素數(shù)搜索起點位數(shù)設置為32和64），NP取200，SS取1000。從理論上說，對于同樣的起點，素數(shù)測試次數(shù)越多，需要的時間就越長?？梢钥闯?，對于512bit密鑰，A取從4個到6個，對隨機密鑰的產(chǎn)生時間影響不大。但是對于較長的1024bit密鑰，A取4個和A取6個值，密鑰生成時間產(chǎn)生明顯差距，A取6個值時生成隨機密鑰需要的平均時間比A取4個值時長數(shù)秒之多。為了同時保證密鑰生成速度和素數(shù)的準確程度，我們在實際使用時取A為5個值，即2、3、5、7、11。（3.）測試小素數(shù)因子個數(shù)NP對耗時的影響固定其他變量：A取5個分別為2、3、5、7、11,n取512位和1024位（即素數(shù)搜索起點位數(shù)設置為32和64），SS取1000。由于測試時間漫長，測試的數(shù)據(jù)量比較有限。這里并沒有看出什么明顯的規(guī)律。而且通過本次測試還可以發(fā)現(xiàn)，表3-3中NP為200，n為1024bit測試的一行，變量設置和表3-2中A設置為2、3、5、7、11，n為1024bit的一行完全一致（對應還有一行n為512bit的數(shù)據(jù)變量設置一致），但是耗時平均差距相差4秒之多（512bit的一行差距不到1秒）?？梢妼τ陂L密鑰，同一種情況測試5個數(shù)據(jù)取均值并不能精確的說明問題，除非測試得到的數(shù)據(jù)有很明顯的大幅差距，例如前面兩段測試n的位數(shù)和A的個數(shù)的耗時影響情況。這里也正是因為前面提到的，對于大整數(shù)來說，可能出現(xiàn)在較長一段區(qū)間中沒有素數(shù)的情況，使得同樣設置的各次密鑰生成耗時的可能范圍很大，再加上大素數(shù)分布規(guī)律奧妙，觀察5次測試結果的均值對于不很明顯的規(guī)律顯得意義不大。實際使用中，設置NP值為200。（4.）測試SS對耗時的影響同樣未發(fā)現(xiàn)明顯規(guī)律，在使用中設置SS為1000。數(shù)據(jù)輸入輸出測試主要測試文件的輸入輸出性能。實際上就是測試.Net基礎類庫中實現(xiàn)文件操作的System.10中的StreamReader、StreamWriter等類的讀寫性能。直接在VisualStudio調試一個簡單的C#文件讀寫程序，得到本軟件