基于java的rsa文件加密軟件的設(shè)計與實現(xiàn)畢業(yè)設(shè)計論文

1、<p><b>　　摘 要</b></p><p>　　分析RSA算法的應(yīng)用現(xiàn)狀，論證文件加密應(yīng)用RSA算法的可行性和意義。設(shè)計一套完整實用的RSA文件加密解決方案，具體編碼實現(xiàn)。對RSA算法進(jìn)行研究，從常規(guī)RSA算法出發(fā)，用C++實現(xiàn)RSA加密算法類庫，并在32位windows平臺封裝成組件。在.Net平臺引用此組件，實現(xiàn)可以對任意文件進(jìn)行RSA加密操作的窗體應(yīng)用程序。經(jīng)過加密

2、的文件以及密鑰文件都是文本文件。給出關(guān)鍵類類圖、整個應(yīng)用程序的結(jié)構(gòu)描述文檔、關(guān)鍵模塊流程圖、較詳細(xì)的接口文檔、所有源代碼。對應(yīng)用程序進(jìn)行測試，對測試結(jié)果進(jìn)行分析研究，進(jìn)而對應(yīng)用程序進(jìn)行改進(jìn)，對關(guān)鍵算法進(jìn)行盡可能的優(yōu)化，最終得到一個在windows運行的可以用指定密鑰對任意文件進(jìn)行RSA加密并可解密的完整應(yīng)用程序，和一些相關(guān)的可移植組件。</p><p>　　關(guān)鍵詞 RSA RSA算法 文件加密 加密成文本&l

3、t;/p><p><b>　　Abstract</b></p><p>　　Do research about the application area of RSA encryption and reason that RSA can be used for file encryption. Design a RSA file-encrypt solution and

4、complete an application on Microsoft Windows?. Design a C++ class based on normal RSA algorithm. And make a DLL module based on the class. Then complete a .Net Framework? window-application using that DLL. The applicatio

5、n can encrypt any file and decrypt them. The file after encryption can be saved as a text file. And the encryption-keys also can be</p><p>　　Keywords RSA RSA algorithm file encryption encrypt to text &

6、lt;/p><p><b>　　目 錄</b></p><p><b>　　前 言1</b></p><p>　　第1章 RSA應(yīng)用現(xiàn)狀及應(yīng)用于文件加密的分析2</p><p>　　1.1 RSA算法介紹與應(yīng)用現(xiàn)狀2</p><p>　　1.2 RSA應(yīng)用于文件加密的

7、分析3</p><p>　　1.2.1 文件加密使用RSA的可行性3</p><p>　　1.2.2 文件加密使用RSA的意義4</p><p>　　第2章 RSA文件加密軟件的設(shè)計與實現(xiàn)6</p><p>　　2.1 需求分析與總體設(shè)計6</p><p>　　2.1.1 功能分析6</p>

8、<p>　　2.1.2 工程方案選擇7</p><p>　　2.2 各部分的設(shè)計與開發(fā)8</p><p>　　2.2.1 實現(xiàn)RSA加密算法的C++核心類庫8</p><p>　　2.2.2 封裝C++核心類庫的DLL組件18</p><p>　　2.2.3 引用DLL的.Net類與實現(xiàn)文件操作功能的窗體應(yīng)用程序19&l

9、t;/p><p>　　第3章 軟件整體測試與分析改進(jìn)20</p><p>　　3.1 編寫測試各項性能需要的精確計時類20</p><p>　　3.2 測試數(shù)據(jù)與分析改進(jìn)20</p><p>　　3.2.1 密鑰生成測試20</p><p>　　3.2.2 數(shù)據(jù)輸入輸出測試23</p><p

10、>　　3.2.3 加密解密測試23</p><p>　　3.2.4 性能分析與改進(jìn)優(yōu)化26</p><p>　　3.3 使用中國余數(shù)定理27</p><p>　　第4章 可移植模塊的簡要說明與開發(fā)前景29</p><p><b>　　結(jié)束語30</b></p><p><b

11、>　　謝 辭31</b></p><p><b>　　參考文獻(xiàn)32</b></p><p><b>　　附 錄33</b></p><p><b>　　前 言</b></p><p>　　RSA公鑰加密算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的

12、算法。它易于理解和操作，也十分流行。算法的名字以發(fā)明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。雖然自1978年提出以來，RSA的安全性一直未能得到理論上的證明，但它經(jīng)歷了各種攻擊，至今（2006年）未被完全攻破。隨著越來越多的商業(yè)應(yīng)用和標(biāo)準(zhǔn)化工作，RSA已經(jīng)成為最具代表性的公鑰加密技術(shù)。VISA、MasterCard、IBM、Microsoft等公司協(xié)力制定的安全電子交易標(biāo)準(zhǔn)（S

13、ecure Electronic Transactions，SET）就采用了標(biāo)準(zhǔn)RSA算法，這使得RSA在我們的生活中幾乎無處不在。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗證、各種信用卡使用的數(shù)字證書、智能移動電話和存儲卡的驗證功能芯片等，大多數(shù)使用RSA技術(shù)。</p><p>　　當(dāng)今公鑰加密更廣泛應(yīng)用于互聯(lián)網(wǎng)身份認(rèn)證，本課題將公鑰加密算法RSA應(yīng)用于小型文件加密。將任意文件加密成文本的解決方案，使其使用更加靈活。整個

14、工程的分層設(shè)計，給引用移植和后續(xù)開發(fā)帶來便利。</p><p>　　第1章 RSA應(yīng)用現(xiàn)狀及應(yīng)用于文件加密的分析</p><p>　　1.1 RSA算法介紹與應(yīng)用現(xiàn)狀</p><p>　　RSA算法可以簡單敘述如下：</p><p><b>　　<密鑰生成></b></p><p>

15、　　取素數(shù)p，q，令n=p×q.</p><p>　　取與(p-1)×(q-1)互素的整數(shù)e，</p><p>　　由方程d×e=1 (mod (p-1)×(q-1))解出d，</p><p>　　二元組(e,n)作為公開密鑰，</p><p>　　二元組(d,n)作為私有密鑰．</p>

16、<p><b>　　<加密解密></b></p><p>　　b=ae mod n，c=bd mod n.</p><p>　　附錄中給出了證明a=c (mod n).</p><p>　　(具體的RSA算法協(xié)議見http://www.di-mgt.com.au/rsa_alg.html ，提及的算法中的字母與協(xié)議文檔中的

17、一致，不再另做解釋)</p><p>　　RSA公開密鑰加密算法自20世紀(jì)70年代提出以來，已經(jīng)得到了廣泛認(rèn)可和應(yīng)用。發(fā)展至今，電子安全領(lǐng)域的各方面已經(jīng)形成了較為完備的國際規(guī)范。RSA作為最重要的公開密鑰算法，在各領(lǐng)域的應(yīng)用數(shù)不勝數(shù)。RSA在硬件方面，以技術(shù)成熟的IC應(yīng)用于各種消費類電子產(chǎn)品。</p><p>　　RSA在軟件方面的應(yīng)用，主要集中在Internet上。加密連接、數(shù)字簽名和數(shù)

18、字證書的核心算法廣泛使用RSA。日常應(yīng)用中，有比較著名的工具包Open SSL(SSL，Security Socket Layer,是一個安全傳輸協(xié)議，在Internet上進(jìn)行數(shù)據(jù)保護(hù)和身份確認(rèn)。Open SSL是一個開放源代碼的實現(xiàn)了SSL及相關(guān)加密技術(shù)的軟件包，由加拿大的Eric Yang等發(fā)起編寫的。相關(guān)詳細(xì)介紹見http://www.openssl.org/about/ )。Open SSL應(yīng)用RSA實現(xiàn)簽名和密鑰交換，已經(jīng)在各

19、種操作系統(tǒng)得到非常廣泛的應(yīng)用。另外，家喻戶曉的IE瀏覽器，自然也實現(xiàn)了SSL協(xié)議，集成了使用RSA技術(shù)的加密功能，結(jié)合MD5和SHA1，主要用于數(shù)字證書和數(shù)字簽名，對于習(xí)慣于使用網(wǎng)上購物和網(wǎng)上銀行的用戶來說，幾乎天天都在使用RSA技術(shù)。</p><p>　　RSA更出現(xiàn)在要求高度安全穩(wěn)定的企業(yè)級商務(wù)應(yīng)用中。在當(dāng)今的企業(yè)級商務(wù)應(yīng)用中，不得不提及使用最廣泛的平臺j2ee。事實上，在j2se的標(biāo)準(zhǔn)庫中，就為安全和加密服

20、務(wù)提供了兩組API：JCA和JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如證書、數(shù)字簽名、報文摘要和密鑰對產(chǎn)生器； JCA由幾個實現(xiàn)了基本的加密技術(shù)功能的類和接口組成，其中最主要的是java.security包，此軟件包包含的是一組核心的類和接口，Java中數(shù)字簽名的方法就集中在此軟件包中。JCE(Java Cryptography Extension) 在JCA的基礎(chǔ)上作了擴(kuò)展

21、，JCE也是由幾個軟件包組成，其中最主要的是javax.crypto包，此軟件包提供了JCE加密技術(shù)操作API。javax.crypto中的Cipher類用于具體的加密和解密。在上述軟件包的實現(xiàn)中，集成了應(yīng)用RSA算法的各種數(shù)據(jù)加密規(guī)范(RSA算法應(yīng)用規(guī)范介紹參見： http://www.rsasecurity.com/rsalabs/node.asp?id=2146 ，這些API內(nèi)部支持的算法不僅</p><p&g

22、t;　　單機(jī)應(yīng)用程序使用RSA加密尚比較少見，例如使用RSA加密任意一個文件。</p><p>　　1.2 RSA應(yīng)用于文件加密的分析</p><p>　　1.2.1 文件加密使用RSA的可行性</p><p>　　通過1.1節(jié)的論述，不難看出RSA當(dāng)今的應(yīng)用多在于數(shù)字簽名和證書等方面。之所以只應(yīng)用于這些短小數(shù)據(jù)的加密解密，是因為RSA算法加密極慢，速度是DES對稱

23、密鑰加密速度的千分之一左右。正是因為這樣，把RSA應(yīng)用于普通文件加密的想法一直被忽略。通常文件被想象成大數(shù)據(jù)塊，但是實際上在日常應(yīng)用中，有些極其重要的文本資料是并不太大的，比如因擔(dān)心遺忘而用普通文本記錄的銀行帳號和密碼、不應(yīng)被陌生人知道的重要電話號碼、幾千字節(jié)大的重要小圖片等。</p><p>　　雖然RSA加密運算的速度十分慢，但是在PC性能越來越好的今天，對于幾千字節(jié)的數(shù)據(jù)進(jìn)行一次幾百位密鑰的RSA加密，所消

24、耗的時間應(yīng)該是可以接受的。下面結(jié)合大數(shù)運算程序的調(diào)試，從理論上簡單的分析消耗時間。在一臺普通配置的PC機(jī)上對一個整數(shù)進(jìn)行冪模運算，因為公開密鑰的e通常取的較小，所以指數(shù)取一個小整數(shù)，比如C353，模一個70字節(jié)長的整數(shù)(140位十六進(jìn)制，大數(shù)單元以線性組方式實現(xiàn)，對應(yīng)到RSA算法中，這相當(dāng)于約560bit的n)，調(diào)試一個函數(shù)測試，按初等數(shù)論中的知識對程序進(jìn)行算法優(yōu)化，最終在一臺配置為AMD Athron2800+，外頻333MHZ，物理

25、內(nèi)存512MB的PC上測試需要約45毫秒時間。如果按這種速度，逐字節(jié)對1KB的數(shù)據(jù)進(jìn)行同樣的運算，所消耗的時間理論上為45毫秒的1024倍即約45秒。這個時間并不是非常長。</p><p>　　其實從一個簡單的角度來說，既然RSA用于數(shù)字簽名可行，那就完全可以用于同樣大小的普通文件。對于較大的文件，如果分成與數(shù)字簽名同樣大小的段(這里假設(shè)數(shù)字簽名較短，不分段一次計算加密完成)，分開的各段逐一進(jìn)行加密運算，那所需要

26、的時間也只是按文件大小線性的增長。通常數(shù)字簽名為幾十字節(jié)，加密運算并不需要很長的等待，這就說明對于幾百字節(jié)或一兩K字節(jié)大小的文件來說，如果進(jìn)行RSA加密，并不會是非常漫長的工作。當(dāng)然，如果文件更大，加密就顯得十分漫長了。比如按前面敘述的45毫秒大數(shù)運算程序推理，加密1M字節(jié)大小的文件需要約1天的時間。所以，要在普通PC用幾百位以上的長密鑰RSA加密文件，文件不能過大，一般可以接受的上限是幾KB。如果要在較短時間內(nèi)加密大文件，需要縮短密鑰

27、長度以減小運算量，這將帶來安全性隱患。</p><p>　　本文的第3章將根據(jù)實際調(diào)試好的軟件，測試給出具體的時間消耗數(shù)據(jù)。例如，在一臺配置為AMD Athron2800+，外頻333MHZ，物理內(nèi)存512MB的PC上測試實現(xiàn)的軟件，以560bit的n逐字節(jié)加密一個1KB大小的文件需要55秒。通常記錄如銀行帳號密碼等重要數(shù)據(jù)的文本文件大小不足百字節(jié)，加密只需要數(shù)秒鐘。所以對于小型文件，進(jìn)行較長密鑰的RSA加密是完

28、全可行的。</p><p>　　1.2.2 文件加密使用RSA的意義</p><p>　　如1.2.1節(jié)所述，小型文件加密可以使用RSA。比如，因擔(dān)心遺忘而用普通文本記錄的銀行帳號和密碼、不應(yīng)被陌生人知道的重要電話號碼、幾千字節(jié)大的重要小圖片等?？尚械姆椒ㄎ幢厥潜匾模拘」?jié)討論何種文件適合用非對稱密鑰加密，即RSA加密文件的意義所在。</p><p>　　對于前面

29、敘述的帶有重要信息的小型文本和二進(jìn)制數(shù)據(jù)的維護(hù)，①如果不加密，將無法放心的保存在計算機(jī)上，尤其是連網(wǎng)的或機(jī)房里的公共計算機(jī)。②如果借助功能強大的大型多用戶數(shù)據(jù)保護(hù)程序維護(hù)幾個小型文件，顯得十分煩瑣，好比殺雞用牛刀。③如果采用對稱密鑰加密，即加密解密的密鑰相同，只適合部分情況。在某些情況下，使用對稱密鑰加密文件，交流使用不夠方便。比如，張三由于某種原因，需要將自己的某個文件在公共計算機(jī)上留給李四，而不希望別人看到內(nèi)容。如果采用對稱密鑰加密

30、，張三和李四提前約好一個密碼就可以。但是如果張三想要在同一臺公共計算機(jī)上再留一個秘密文件給王五，而不希望別人看到，就要和王五另外約定一個密碼。如果需要在這臺公共計算機(jī)上留十個文件給不同的人，自己就要記和十個人約定好的密碼，這樣以來交流起來不夠方便，因為對于張三，要自己維護(hù)太多的密鑰。非對稱密鑰(公開密鑰方式)恰好解決這樣的問題。只要大家都在這臺計算機(jī)或這臺計算機(jī)可以訪問到的地方，留下自己的公開密鑰，一切就變的容易解決了。張三要留給李四的

31、文件，就用李四的公開密鑰加密，要留給王五的文件，就用王五的公開密鑰加密。李四和王五只要把留給自己的文件用自己的私</p><p>　　一種更實際的情況是，我們想通過Internet上的公眾論壇或郵件發(fā)送重要保密信息給某人。例如發(fā)送一個銀行帳號和密碼給某人。這種情況要保證安全，在當(dāng)今互聯(lián)網(wǎng)絡(luò)上是比較棘手的。①如果用公眾論壇直接留言給指定用戶，論壇管理員和服務(wù)器管理員通常有方法看到數(shù)據(jù)。②如果發(fā)送郵件，雖然傳送過程是

32、加密的，但是密碼畢竟是由郵件服務(wù)器維護(hù)，所以系統(tǒng)管理員通常也有辦法看到內(nèi)容。問題的關(guān)鍵在于我們所有的數(shù)據(jù)包括密鑰保存在服務(wù)器之上。在這種情況下，我們需要使用公開密鑰方式，并自己維護(hù)私有密鑰。RSA文件加密可以靈活的解決這些問題。例如，我們可以將任意一個文件用某人的公開密鑰加密變換成一段可以復(fù)制粘貼的文本，然后粘貼在公眾互聯(lián)網(wǎng)上，對方只需把需要解密的文本復(fù)制保存成一個文本文件，在本地機(jī)用自己的私有密鑰解密即可。我們可以將自己的私有密鑰通過

33、DES加密后保存在自己的移動磁盤上，使用的時候只要將其解密讀取即可，用完后立即從當(dāng)前操作環(huán)境清除。這樣，我們自己維護(hù)自己的私有密鑰，利用簡單并且公開的方式，可以安全傳送任意小型數(shù)據(jù)，包括一切二進(jìn)制文件。</p><p>　　所以，對于使用小型文件進(jìn)行數(shù)據(jù)交換的情況，更好的方案是通過一個小型應(yīng)用程序?qū)@些文件進(jìn)行非對稱密鑰加密。為了適合前面敘述的在公共BBS與特定的某人交流重要保密信息的情況，加密生成的數(shù)據(jù)應(yīng)該是文

34、本，這樣可以方便復(fù)制粘貼。</p><p>　　綜上所述，使用前面敘述的方式加密文件有兩點重要意義：①應(yīng)用非對稱密鑰加密任意文件，使非對稱密鑰的應(yīng)用不僅僅局限于互聯(lián)網(wǎng)絡(luò)。②非對稱加密后的數(shù)據(jù)變換成文本，使得我們可以通過幾乎任何方式安全傳遞任意文件，比如在只有http的環(huán)境使用xml方式。</p><p>　　第2章 RSA文件加密軟件的設(shè)計與實現(xiàn)</p><p>

35、　　2.1 需求分析與總體設(shè)計</p><p>　　2.1.1 功能分析</p><p>　　經(jīng)過1.2.2節(jié)的論述，我們可以將對軟件的要求總結(jié)如下：</p><p>　?、倏梢园匆蟮奈粩?shù)生成非對稱密鑰。</p><p>　?、诳梢员４婷荑€和裝載密鑰，密鑰保存為純文本。</p><p>　　③可以用指定密鑰以R

36、SA算法加密任意一個文件，加密生成的數(shù)據(jù)為純文本。</p><p>　　④可以裝載加密過的文件，并用指定的密鑰解密還原出原文件。</p><p>　?、萏崾拘畔⑼暾?、操作舒適、圖形界面雅觀</p><p>　　按上述描述，給出Use Case和Statechart如圖2-1。</p><p>　　圖2-1 本項目的 Use Case和S

37、tatechart</p><p>　　根據(jù)以上分析，一般來說，需要進(jìn)行編碼的程序有 </p><p>　　①RSA密鑰生成 ②RSA加密解密 ③任意文件的讀取和保存操作 ④各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換 ⑤圖形操作界面。</p><p>　　2.1.2 工程方案選擇</p><p>　　結(jié)合現(xiàn)有的常見開發(fā)模式綜合分析，有多種實現(xiàn)方案，下面陳述其中

38、幾種，并分析選擇一種解決方案，并給出工程框架。</p><p>　　1.整個工程使用java平臺實現(xiàn)</p><p>　　RSA密鑰生成、RSA加密解密的功能實現(xiàn)十分簡單，因為標(biāo)準(zhǔn)庫中集成幾乎所有功能，不需要從RSA算法出發(fā)進(jìn)行編碼。在j2se標(biāo)準(zhǔn)庫中，javax.crypto中的Cipher類用于具體的加密和解密，java.security包直接提供了數(shù)字簽名的相關(guān)方法。因為有強大的標(biāo)

39、準(zhǔn)庫支持，文件的讀取和保存操作、各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換、圖形操作界面的實現(xiàn)也很簡單(使用java.io java.awt或javax.swing 等包)，如果結(jié)合一種快速開發(fā)的IDE，比如JBuilder，整個軟件可以在很短的時間內(nèi)編碼完成。如果不考慮非PC設(shè)備和機(jī)器效率等問題，java平臺幾乎是最佳解決方案。但是缺點也很明顯，如果想把核心算法和功能應(yīng)用到非PC設(shè)備(例如嵌入式手持設(shè)備)，則要求設(shè)備上有支持前面提及的加密類庫的CVM；

40、對于在PC上運行，JVM的數(shù)據(jù)運算速度要遠(yuǎn)遠(yuǎn)落后于本地化代碼在PC上的運算速度，本軟件需要進(jìn)行大量運算，這一點不適合由java完成。</p><p>　　2.整個工程使用.Net平臺實現(xiàn)</p><p>　　與使用java平臺完全類似，加密等有.Net基礎(chǔ)類庫的支持，不需要大量編碼實現(xiàn)，另外由于Visual Studio的強大便利，這種規(guī)模的工程可以十分迅速的完成。缺點是只能在有微軟.N

41、et Framework的環(huán)境運行，在Windows操作系統(tǒng)，.Net Framework的機(jī)器效率好于java平臺，但是相比于本地化的代碼，還是十分拖沓的。</p><p>　　3.整個工程使用Windows本地化程序?qū)崿F(xiàn)</p><p>　　在不應(yīng)用Windows或第三方現(xiàn)成組件的情況下，需從RSA算法出發(fā)編碼實現(xiàn)。其他各功能的設(shè)計開發(fā)，如文件操作、數(shù)據(jù)編碼轉(zhuǎn)換和圖形界面等，可以使用

42、ATL、MFC或Windows API實現(xiàn)。這種工程幾乎是為Windows量身訂做，執(zhí)行效率最好。但是對于非PC設(shè)備，只能方便的移植到運行Windows嵌入式操作系統(tǒng)的設(shè)備，向其他操作系統(tǒng)移植困難，需要重新編寫大量代碼。通常解決本地化代碼的移植問題，都是使用C++標(biāo)準(zhǔn)庫，即功能盡量多的由C++標(biāo)準(zhǔn)庫完成，這樣在移植的時候，只需要重新編寫操作系統(tǒng)相關(guān)的代碼即可。這種開發(fā)方式比起前兩種，缺點就是設(shè)計開發(fā)模式陳舊，代碼煩瑣，不方便維護(hù)；流行的

43、.Net上的語言引用各種功能比較麻煩。</p><p>　　4.考慮可能的復(fù)用，針對具體情況分層開發(fā)實現(xiàn)</p><p>　　綜合考慮復(fù)用性、可維護(hù)性和執(zhí)行效率，較妥當(dāng)?shù)姆椒ㄊ欠謱釉O(shè)計。核心的RSA算法由C++類庫實現(xiàn)，針對用戶所在的操作系統(tǒng)封裝成本地化組件。其他各功能如文件操作、數(shù)據(jù)編碼轉(zhuǎn)換和圖形界面等，由托管代碼借助虛擬機(jī)平臺標(biāo)準(zhǔn)庫的功能快速開發(fā)實現(xiàn)(本文針對選用.Net上的C#論述

44、，選用java由JNI或其他方式調(diào)用本地組件，設(shè)計模式上是完全類似的)。這種開發(fā)方式，核心功能集中在最底層，在不斷的封裝中針對具體環(huán)境對組件功能不斷擴(kuò)充，任意一個層面的封裝都可以被直接應(yīng)用到其他項目，比如在Web使用以前為某窗體程序?qū)懙慕M件、給嵌入式設(shè)備交叉編譯算法庫等。但是每一層都需要依賴底層的所有組件。圖2-2形象的說明了分層設(shè)計給復(fù)用帶來的好處。</p><p>　　圖2-2 綜合考慮復(fù)用性、可維護(hù)性和執(zhí)行

45、效率的分層設(shè)計</p><p>　　選用第四種設(shè)計方案，上層使用C#，底層算法使用C++，可以由一個Visual Studio解決方案管理，給調(diào)試帶來極大的方便。整個工程分四層，實現(xiàn)RSA加密算法的C++核心類庫、封裝C++核心類庫的DLL組件、引用DLL的.Net類、實現(xiàn)文件操作功能的.Net窗體應(yīng)用程序。2.2節(jié)詳細(xì)介紹各部分的設(shè)計與開發(fā)。</p><p>　　考慮到工作量，本軟件加解

46、密數(shù)據(jù)沒有嚴(yán)格遵從RSA標(biāo)準(zhǔn)PKCS #1，而是在滿足設(shè)計要求的前提下，以一種盡可能簡單的方式實現(xiàn)加密和解密。</p><p>　　2.2 各部分的設(shè)計與開發(fā)</p><p>　　2.2.1 實現(xiàn)RSA加密算法的C++核心類庫</p><p>　　1. 大數(shù)存儲和四則運算</p><p>　　根據(jù)RSA算法的要求，為了實現(xiàn)大數(shù)的各種復(fù)雜運算，

47、需要首先實現(xiàn)大數(shù)存儲和基本四則運算的功能。當(dāng)今開源的大數(shù)運算C++類有很多，多用于數(shù)學(xué)分析、天文計算等，本文選用了一個流行的大數(shù)類型，并針對RSA算法和本項目的具體需要對其進(jìn)行了擴(kuò)充和改進(jìn)。下面簡單介紹大數(shù)存儲和四則運算的實現(xiàn)原理。</p><p>　　最先完成的功能是大數(shù)的存儲，存儲功能由flex_unit類提供。和普通的類型一樣，每一個大數(shù)對應(yīng)一個flex_unit的實例。類flex_unit中，用一個無符號

48、整數(shù)指針unsigned * a指向一塊內(nèi)存空間的首地址，這塊內(nèi)存空間用來存儲一個大數(shù)，所以可以說，大數(shù)是被存儲在一個以unsigned為單元的線性組中。在方法void reserve( unsigned x )中通過C++的new來給a開辟空間，當(dāng)flex_unit的實例中被存入比當(dāng)前存儲的數(shù)更大的數(shù)時，就會調(diào)用reserve來增加存儲空間，但是當(dāng)flex_unit的實例中被存入比當(dāng)前存儲的數(shù)更小的數(shù)時，存儲空間并不會自動緊縮，這是為

49、了在運算的時候提高執(zhí)行效率。結(jié)合指針a，有兩個重要的無符號整數(shù)來控制存儲，unsigned z和unsigned n，z是被分配空間的單元數(shù)，隨數(shù)字變大不斷增大，不會自己緊縮，而n是當(dāng)前存儲的大數(shù)所占的單元數(shù)，組成一個大數(shù)的各unsigned單元的存入和讀出由set、get方法完成，變量n是只讀的。類型unsigned在32位機(jī)是32位的，所以對于flex_unit這個大數(shù)類來說，每個大數(shù)最大可</p><p>

50、　　圖2-3 flex_unit對大數(shù)的管理</p><p>　　在flex_unit的存儲功能基礎(chǔ)上，將其派生，得到vlong_value，在vlong_value中實現(xiàn)四則運算函數(shù)，并實現(xiàn)強制轉(zhuǎn)換運算符unsigned，以方便大數(shù)類型和普通整數(shù)的互相賦值。當(dāng)大數(shù)被強制轉(zhuǎn)換為unsigned時，將取其最低四字節(jié)的值。四則運算實現(xiàn)的原理十分簡單，都是按最基本的算術(shù)原理實現(xiàn)的，四則運算過程的本質(zhì)就是按一定數(shù)制對數(shù)字

51、的計算，比如相加，就是低位單元對齊，逐單元相加并進(jìn)位，減法同理。而乘除法和取余也都是按照豎式運算的原理實現(xiàn)，并進(jìn)行了必要的優(yōu)化。雖然實現(xiàn)了四則運算函數(shù)，但是若是程序里的運算都要調(diào)用函數(shù)，顯得煩瑣而且看起來不美觀，所以我們另寫一個類vlong，關(guān)聯(lián)(Associate，即使用vlong_value類型的對象或其指針作為成員)vlong_value，在vlong重載運算符。這樣，當(dāng)我們操作vlong大數(shù)對象的時候，就可以像使用一個簡單類型一

52、樣使用各種運算符號了。之所以將vlong_value的指針作為成員而不是直接構(gòu)造的對象，也是為了提高執(zhí)行效率，因為大型對象的拷貝要消耗不少機(jī)器時間。</p><p>　　2. 大數(shù)冪模與乘模運算?Montgomery冪模算法</p><p>　　在實現(xiàn)了vlong類型后，大數(shù)的存儲和四則運算的功能都完成了。考慮到RSA算法需要進(jìn)行冪模運算，需要準(zhǔn)備實現(xiàn)這些運算的方法。所以寫一個vlong的

53、友元，完成冪模運算功能。冪模運算是RSA 算法中比重最大的計算，最直接地決定了RSA 算法的性能，針對快速冪模運算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了很多的解決方案。經(jīng)查閱相關(guān)數(shù)學(xué)著作，發(fā)現(xiàn)通常都是依據(jù)乘模的性質(zhì)，先將冪模運算化簡為乘模運算。</p><p>　　通常的分解習(xí)慣是指數(shù)不斷的對半分，如果指數(shù)是奇數(shù)，就先減去一變成偶數(shù)，然后再對半分，例如求D=，E=15，可分解為如下6個乘模運算。</p>&

54、lt;p>　　歸納分析以上方法，對于任意指數(shù)E，可采用如圖2-4的算法流程計算 。</p><p>　　圖2-4 冪模運算分解為乘模運算的一種流程</p><p>　　按照上述流程，列舉兩個簡單的冪模運算實例來形象的說明這種方法。</p><p><b>　?、偾蟮闹?lt;/b></p><p>　　開始D =

55、1P = 2 mod 17 = 2E = 15</p><p>　　E奇數(shù)D = DP mod n = 2P = PP mod n = 4E = (E-1)/2 =7</p><p>　　E奇數(shù)D = DP mod n = 8P = PP mod n = 16E = (E-1)/2 =3</p><p>　　E奇數(shù)

56、D = DP mod n = 9P = PP mod n = 1E = (E-1)/2 =1</p><p>　　E奇數(shù)D = DP mod n = 9P = PP mod n = 1E = (E-1)/2 =0</p><p>　　最終D = 9 即為所求。</p><p><b>　?、谇蟮闹?lt;/b><

57、;/p><p>　　開始D = 1P = 2 mod 17 = 2E = 8</p><p>　　E偶數(shù)D = 1P = PP mod n = 4E = E/2 =4</p><p>　　E偶數(shù)D = 1P = PP mod n = 3E = E/2 =2</p><p>　　E

58、偶數(shù)D = 1P = PP mod n = 9E = E/2 =1</p><p>　　E奇數(shù)D = DP mod n = 9P = 不需要計算E = (E-1)/2 =0</p><p>　　最終D = 9 即為所求。</p><p>　　觀察上述算法，發(fā)現(xiàn)E根據(jù)奇偶除以二或減一除以二實際就是二進(jìn)制的移位操作，所以要知道需要

59、如何乘模變量，并不需要反復(fù)對E 進(jìn)行除以二或減一除以二的操作，只需要驗證E 的二進(jìn)制各位是0 還是1 就可以了。同樣是計算，下面給出從右到左掃描二進(jìn)制位進(jìn)行的冪模算法描述，設(shè)中間變量D,P,E的二進(jìn)制各位下標(biāo)從左到右為u,u-1,u-2,…,0。</p><p>　　Powmod(C,E,n) </p><p><b>　　{</b></p><p

60、><b>　　D=1;</b></p><p>　　P=C mod n;</p><p>　　for i=0 to u do </p><p><b>　　{</b></p><p>　　if(Ei=1)D=D*P(mod n); </p><p>　　P=P*P(mo

61、d n);</p><p><b>　　}</b></p><p><b>　　return D;</b></p><p><b>　　}</b></p><p>　　有些文獻(xiàn)將上述算法稱為平方乘積二進(jìn)制快速算法，例如參考文獻(xiàn)中的《基于RSA算法的一種新的加密核設(shè)計》，其實這種

62、算法本質(zhì)上和圖2-4的流程完全一致，只是把根據(jù)指數(shù)奇偶分開的減一和除以二合并成對指數(shù)二進(jìn)制各位的判斷而已。在本軟件的代碼中采用直接掃描vlong二進(jìn)制各位的辦法。</p><p>　　剩下的問題就是乘模運算了。提高乘模運算的速度是提高模冪運算速度的關(guān)鍵。一般情況下，n是數(shù)百位乃至千位以上的二進(jìn)制整數(shù)，用普通的除法求模而進(jìn)行乘模運算是不能滿足速度的要求的。為此，Montgomery在1983年提出了一種模加右移的乘

63、模算法（主要著作發(fā)表于1985年），從而避免了通常求模算法中費時的除法步驟。本軟件僅僅是應(yīng)用Montgomery(蒙哥馬利)算法，算法的具體推導(dǎo)證明需要頗多數(shù)論知識，不在本文的討論范圍內(nèi)，如需了解可參見蒙哥馬利的相關(guān)著作。下面簡單描述RSA中常用的Montgomery(蒙哥馬利)算法供參考理解源程序。</p><p>　　選擇與模數(shù)n互素的基數(shù)R=2k，n滿足2k－1≤n<2k， n應(yīng)為奇數(shù)。并且選擇R-1

64、及n’，滿足0< R-1<n, 0< n’<n,使得 RR-1-nn’＝1。對于0≤m<Rn的任意整數(shù),Montgomery給出求模乘法mR-1 mod n 的快速算法M(m):</p><p><b>　　M(m)</b></p><p><b>　　{</b></p><p>　　if (

65、t≥n) return (t-n); </p><p>　　else return t;</p><p><b>　　}</b></p><p>　　因為，故t為整數(shù)；同時，得。由于，M(m) 中t結(jié)果范圍是0≤t<2n，返回時如果t不小于n，應(yīng)返回t-n。</p><p>　　本軟件程序中，RSA核心運算使用的乘

66、模算法就是 M(A*B)。雖然M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個乘模算法進(jìn)行計算了。本軟件起初未使用Montgomery 乘模算法時，加密速度比使用Montgomery乘模算法慢，但速度相差不到一個數(shù)量級。</p><p>　　將上述乘模算法結(jié)合前面敘述的冪模算法，構(gòu)成標(biāo)準(zhǔn)Montgomery冪模算法，即本軟件所使用的流程，敘述如下。</p>&

67、lt;p><b>　　M(m)</b></p><p><b>　　{</b></p><p>　　k = ( m * n’ ) mod R;</p><p>　　x = (m + k*n ) / R;</p><p>　　if (x>=n) x -= n;</p><

68、;p><b>　　return x;</b></p><p><b>　　}</b></p><p>　　exp(C,E,n) </p><p><b>　　{</b></p><p><b>　　D=R-n;</b></p><

69、p>　　P=C*R mod n;</p><p><b>　　i=0;</b></p><p>　　while(true)</p><p><b>　　{</b></p><p>　　if(E的當(dāng)前二進(jìn)制位Ei==1)D=M(D*P); //從低位到高位檢測二進(jìn)制位</p>&l

70、t;p><b>　　i+=1;</b></p><p>　　if(i==E的二進(jìn)制位數(shù))break;</p><p><b>　　P=M(P*P);</b></p><p><b>　　}</b></p><p>　　return D*R-1 (mod n);</p

71、><p><b>　　}</b></p><p>　　在具體的實現(xiàn)中，對應(yīng)monty類的mul和exp方法。全局函數(shù)modexp初始化monty對象并調(diào)用其exp方法，使用的時候直接調(diào)用modexp即可。</p><p>　　3. 尋找素數(shù)?Eratosthenes篩選與Fermat素數(shù)測試</p><p>　　首先要說明的

72、是，事實上，當(dāng)今的計算機(jī)還不足以聰明到立刻計算生成一個很大的隨機(jī)素數(shù)。一般來說，要得到100%準(zhǔn)確的大素數(shù)，都是通過查已經(jīng)計算好的素數(shù)表的方式。但是素數(shù)表的方式給RSA的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所使用的素數(shù)表，攻破RSA加密的難度將會大大降低。本程序起初使用素數(shù)表的方式，后來考慮到安全性問題，生成密鑰的方式改為隨機(jī)計算生成。這樣，短時間內(nèi)如果要得到一個100%準(zhǔn)確的大素數(shù)是很困難的，只能以盡可能高的概率得到一個大素

73、數(shù)。</p><p>　　經(jīng)過2.2.1.1和2.2.1.2小節(jié)，所有的大數(shù)運算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素數(shù)的功能置于類Prime_factory_san之中。外部只要調(diào)用本類實例的成員vlong find_prime( vlong & start )就可以以大數(shù)start為起點，得到一個數(shù)，這個數(shù)是素數(shù)的概率很大。下面介紹尋找素數(shù)的原理。</p><p>　　首先

74、在需要尋找素數(shù)的整數(shù)范圍內(nèi)對整數(shù)進(jìn)行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構(gòu)造了一個數(shù)組b[]，大小為一輪素數(shù)搜索的范圍，記搜索范圍大小為SS。b[0]到b[SS]分別對應(yīng)大數(shù)start到start+SS。b[]中所有元素先初始化為1，如果對應(yīng)的大數(shù)確定為合數(shù)，就將b[]中對應(yīng)的元素置為0。最后，只需對那些b[]中為1的元素對應(yīng)的大數(shù)進(jìn)行比較確切的素數(shù)測試即可，只要被測試的數(shù)是素數(shù)概率達(dá)到一定門限，就判這個數(shù)為素數(shù)。這樣做既保證了

75、這段程序可以在短時間內(nèi)執(zhí)行完，又保證了可以以比較高的準(zhǔn)確度得到素數(shù)。</p><p>　　函數(shù)find_prime先把b[]的所有元素賦值為1，然后按參數(shù)start給標(biāo)記數(shù)組b[]的各元素賦0值。下面描述標(biāo)記數(shù)組b[]的賦0值算法。首先，在類Prime_factory_san被構(gòu)造的時候，構(gòu)造函數(shù)中從2開始搜尋一些小素數(shù)，記錄在數(shù)組pl[]中，共記錄NP個。這些小素數(shù)用來當(dāng)作因子，他們的倍數(shù)將被從大素數(shù)搜索范圍內(nèi)

76、剔除(即把數(shù)組b[]的對應(yīng)元素標(biāo)記為0)，剔除的程序代碼如下。</p><p>　　for (i=0;i<np;i++)</p><p><b>　　{</b></p><p>　　unsigned p = pl[i];</p><p>　　unsigned r = start % vlong(p);</p&

77、gt;<p>　　if (r) r = p - r;</p><p>　　while ( r < SS )</p><p><b>　　{</b></p><p><b>　　b[r] = 0;</b></p><p><b>　　r += p;</b>&l

78、t;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　這里利用start對各小素數(shù)因子p求模的辦法，得到當(dāng)前p在素數(shù)搜索范圍內(nèi)的最小倍數(shù)在b[]中的對應(yīng)位置，將其剔除后，不斷后移p個位置，將這個小素數(shù)因子p在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖2-5所示。在完成對所有小素數(shù)因子的類

79、似操作后，他們的倍數(shù)在搜索范圍內(nèi)的位置標(biāo)記b[r]被全部標(biāo)記為0。實際上這就是Eratosthenes篩選法。</p><p>　　圖2-5 在素數(shù)搜索范圍內(nèi)剔除小素數(shù)因子p的倍數(shù)</p><p>　　接下來，對可能為素數(shù)的數(shù)(即標(biāo)記數(shù)組b[]中值為1的元素對應(yīng)的數(shù))進(jìn)行素數(shù)測試。數(shù)論學(xué)家利用費馬小定理研究出了多種素數(shù)測試方法，本程序使用一種最簡單的方式，直接應(yīng)用費馬小定理。取一個與p互素

80、的整數(shù)A，對于大素數(shù)p來說應(yīng)該滿足Ap-1mod p=1，但是我們把p代入一個大整數(shù)，滿足這個關(guān)系的數(shù)不一定是素數(shù)。這時我們改變A，進(jìn)行多次測試，如果多次測試都通過，這個數(shù)是素數(shù)的概率就比較大。按這種原理，我們編寫素數(shù)測試函數(shù)如下。</p><p>　　int is_probable_prime_san( const vlong &p )</p><p><b>　　{&

81、lt;/b></p><p>　　const rep = 4; //測試次數(shù)</p><p>　　const unsigned any[rep] = { 2,3,5,7 }; //測試用的底數(shù)</p><p>　　for ( unsigned i=0; i<rep; i+=1 )</p><p>　　if ( modexp( an

82、y[i], p-vlong(1), p ) != vlong(1) ) return 0;</p><p>　　//modexp是冪模函數(shù)，按上一小節(jié)敘述的算法編碼。</p><p>　　//這里modexp計算any[i]p-1mod p。</p><p><b>　　return 1;</b></p><p><

83、;b>　　}</b></p><p>　　測試通過，程序就判定這個數(shù)為找到的素數(shù)，將找到的素數(shù)返回給上層程序使用。在這里其實有一個不可忽視的問題，就是得到一個測試通過的合數(shù)。對于這種情況，RSA算法加密解密是否還可以實現(xiàn)，是一個需要從數(shù)學(xué)角度論證的問題。因為得到素數(shù)的概率很高，經(jīng)過一整天的生成密鑰和加密操作，沒有發(fā)現(xiàn)失敗的密鑰， 所以本文暫沒有對這個問題進(jìn)行討論。</p><

84、p>　　綜上所述，總結(jié)素數(shù)尋找的流程，如圖2-6所示。</p><p>　　圖2-6 函數(shù)find_prime尋找素數(shù)的流程框圖</p><p>　　得到了大素數(shù)，即RSA算法中的p、q，我們就可以計算出密鑰，進(jìn)行加密等操作了。</p><p>　　4. 二元一次不定方程</p><p>　　在RSA 算法中，往往要在已知A、M的情況下

85、，求B的最小值，使得 (AB) mod M = 1。即相當(dāng)于求解B、N都是未知數(shù)的二元一次不定方程 AB-MN=1的最小整數(shù)解。</p><p>　　而針對不定方程ax-by=1 的最小整數(shù)解，古今中外都進(jìn)行過詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說明用歐幾里德算法求解二元一次不定方程的最小整數(shù)解。</p>

86、<p>　　給定不定方程11x-49y=1，求最小的x</p><p>　?。?） 11 x - 49 y = 1 49 mod 11 = 5</p><p>　?。?） 11 x - 5 y = 1 11 mod 5 = 1</p><p>　?。?）x - 5 y = 1 5 mod 1 = 0</p><p&

87、gt;<b>　　逆向代入：</b></p><p>　　令y=0 代入（3）得x=1</p><p>　　令x=1 代入（2）得y=2</p><p>　　令y=2 代入（1）得x=9</p><p>　　x=9;y=2即為所求。</p><p>　　程序中，全局函數(shù)vlong modinv(

88、const vlong &a, const vlong &m )用來完成這種算法。對應(yīng)前面的敘述，參數(shù)a對應(yīng)A，參數(shù)m對應(yīng)M，函數(shù)返回值即為B的最小值。</p><p>　　5. 按常規(guī)RSA算法實現(xiàn)加密與解密</p><p>　　最后，類RSA_san基于前面的準(zhǔn)備工作，實現(xiàn)RSA密鑰生成和加解密的功能(算法在此不再贅述，RSA算法協(xié)議見http://www.di-mgt

89、.com.au/rsa_alg.html)。為了方便閱讀，整個類的源程序中，所使用的變量字母均和RSA算法協(xié)議中一致。在類RSA_san的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對隨機(jī)密鑰的操作。之后可以直接使用類的其他成員進(jìn)行RSA加解密操作，也可以載入以前保存的密鑰或再次隨機(jī)生成密鑰。類中各成員頻繁的用到字符串和vlong類型的轉(zhuǎn)換，因為大數(shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。所以，需要實現(xiàn)一系列的

90、編碼轉(zhuǎn)換函數(shù)，比如將unsigned指針指向的一段空間里保存的一個大數(shù)，表示成十六進(jìn)制形式的字符串文本。編碼轉(zhuǎn)換通常是用C風(fēng)格的指針操作和sprintf函數(shù)來完成。</p><p>　　需要加密和解密的數(shù)據(jù)也是通過字符串參數(shù)置入的。由于字符串的結(jié)尾字符“\0”實際上也可能是需要加密的數(shù)據(jù)，所以置入的串長度并不能以“\0”來決定，程序里引入一個unsigned類型的參數(shù)來決定置入的串長度，這樣就解決了加密連0數(shù)據(jù)時

91、候被截斷的問題。</p><p>　　因為是對文件加密的軟件，需要加密的數(shù)據(jù)通常并不止幾字節(jié)，這時由上層程序?qū)?shù)據(jù)按用戶的設(shè)置分塊，分別加密或解密。本軟件默認(rèn)的分塊大小是1字節(jié)，即逐個字節(jié)作為參數(shù)，調(diào)用C++核心模塊中的方法。</p><p>　　加密解密流程均為標(biāo)準(zhǔn)RSA算法，具體過程和使用方法參見源程序和接口文檔。</p><p><b>　　6. 核

92、心類庫綜述</b></p><p>　　綜上幾小節(jié)所述，實現(xiàn)RSA加密算法的C++核心類庫由六個類組成，類名和對應(yīng)的功能描述總結(jié)如表2-1所示。各個類之間的關(guān)系如圖2-7所示。</p><p>　　表2-1 RSA加密算法的C++類庫中的類</p><p>　　圖2-7 C++核心功能類圖</p><p>　　另外需要說明的是，程

93、序中有幾個不屬于任何類的全局函數(shù)，比如應(yīng)用輾轉(zhuǎn)相除法求最大公約數(shù)的函數(shù)gcd、解同余方程的函數(shù)modinv等。按常規(guī)設(shè)計模式來說，不應(yīng)當(dāng)出現(xiàn)類之外的函數(shù)，但是因為這些函數(shù)使用頻繁，考慮到機(jī)器效率，直接置于全局，不再另行包裝。</p><p>　　2.2.2 封裝C++核心類庫的DLL組件</p><p>　　在Visual Studio當(dāng)前的解決方案中以VC++創(chuàng)建一個win32dll工程

94、，將測試好的實現(xiàn)RSA加密算法的C++核心類庫中的所有文件加入到此工程下，新建一對cpp和h文件，把可能用到的功能全部規(guī)劃為新文件中的全局函數(shù)，并以C接口導(dǎo)出，即__declspec(dllexport)。由于核心類庫的對外功能都使由RSA_san類提供的，所以在新cpp文件中全局的聲明一個RSA_san類的對象指針(RSA_san *WRSA)，全局函數(shù)int start_RSA_san()初始化*WRSA對象，在初始化成功后，其他全

95、局函數(shù)通過調(diào)用*WRSA對象的公開方法實現(xiàn)各種功能，如加密、讀取密鑰等。在關(guān)閉上層引用程序以前，應(yīng)執(zhí)行int finish_RSA_san()來釋放WRSA，該函數(shù)執(zhí)行delete WRSA的操作。其他接口函數(shù)的使用見DLL接口文檔。</p><p>　　另外，DLL組件可以自己在全局函數(shù)中實現(xiàn)一些其他功能，作為對核心類庫功能的補充。C接口的DLL組件可以被諸如VB、Delphi等開發(fā)環(huán)境方便的引用。</p

96、><p>　　2.2.3 引用DLL的.Net類與實現(xiàn)文件操作功能的窗體應(yīng)用程序</p><p>　　在C#編寫的.Net類里，使用特性[DllImport("sanpack_rsa.dll")]引用C接口的DLL組件。類中接口DLL的函數(shù)都以靜態(tài)成員的方式對外公開，其他.Net程序可以直接使用。在類庫中還提供了任意長度隨機(jī)串的生成函數(shù)，此函數(shù)用于生成尋找素數(shù)的大數(shù)起點。&

97、lt;/p><p>　　文件操作使用.Net基礎(chǔ)類庫中的System.IO中的類實現(xiàn)。一般因為文件操作十分簡單，用流輸入輸出的方式包裝完成，程序中將文件操作直接放在菜單項關(guān)聯(lián)的事件處理函數(shù)中。</p><p>　　窗體等圖形操作界面直接由Visual Studio的所見即所得的方式完成，不需要編碼實現(xiàn)。</p><p>　　最終實現(xiàn)的應(yīng)用程序，結(jié)構(gòu)如圖2-8所示。<

98、;/p><p>　　圖2-8 本軟件的Visual Studio解決方案</p><p>　　第3章 軟件整體測試與分析改進(jìn)</p><p>　　3.1 編寫測試各項性能需要的精確計時類</p><p>　　由于.Net基礎(chǔ)類庫提供的計時功能十分不精確，無法勝任軟件性能測試的工作，這里使用Windows API 函數(shù)QueryPerforman

99、ceCounter和QueryPerformanceFrequency進(jìn)行精確計時。功能被封裝在C#類HighResolutionTimer中，使用時只需構(gòu)造一個此類的對象，在計時開始的時候調(diào)用其Start方法，計時結(jié)束時調(diào)用其Stop方法，然后訪問其ElapsedTime屬性，就可以得到一個以秒為單位的float型精確的計時值了。API 函數(shù)QueryPerformanceCounter和QueryPerformanceFrequen

100、cy是靠查詢CPU的高精度計時器來計時的，所以可以輕松的精確到毫秒級計時。</p><p>　　附錄中給出了這個類的源代碼。</p><p>　　3.2 測試數(shù)據(jù)與分析改進(jìn)</p><p>　　3.2.1 密鑰生成測試</p><p>　　生成密鑰運算最費時的工作是尋找素數(shù)。如2.2.1.3小節(jié)所敘述，尋找素數(shù)是一項頗為復(fù)雜的工作，其速度可能

101、受以下變量的影響：RSA加密需要的n的位數(shù)（尋找素數(shù)的整數(shù)起點大小start）、大素數(shù)測試時底數(shù)A的個數(shù)（針對一個整數(shù)的素數(shù)測試次數(shù)）、小素數(shù)因子p的個數(shù)NP、一輪尋找遍歷的整數(shù)個數(shù)SS等。其中最具影響力的因素顯然是RSA加密需要的n的位數(shù)。以下對各變量分別進(jìn)行測試，暫且忽略操作系統(tǒng)調(diào)度對測試的影響。</p><p>　　1. 測試加密使用的n的位數(shù)對耗時的影響</p><p>　　即 在

102、固定A、NP、SS等變量的情況下，改變加密位數(shù)n，測試密鑰生成的時間消耗情況。測試時，A取4個值，分別為2、3、5、7，NP取200，SS取1000。測試PC配置為CPU CR1.7GHZ/外頻100MHZ/物理內(nèi)存512MDDR/MSI6398主板845 Ultra-AD芯片組，下文測試中，未說明PC配置的也都在同一PC完成，不再重復(fù)。統(tǒng)計數(shù)據(jù)如表3-1所示。表中各項對應(yīng)的全部測試數(shù)據(jù)見http://3mn.net/www/downl

103、oad/RSAkeygen_n-Ttest.txt ，包括兩個作為素數(shù)搜索起點的隨機(jī)數(shù)和生成的素數(shù)p、q以及e、d、n。</p><p>　　表3-1 RSA加密模數(shù)n與密鑰生成耗時的關(guān)系</p><p>　　觀察表3-1上的統(tǒng)計數(shù)據(jù)，很容易發(fā)現(xiàn)隨著加密位數(shù)的增加，密鑰生成需要的時間顯著增加。在測試范圍內(nèi)，隨著加密位數(shù)增大，每一行中的最大最小值差距也呈粗略的增大趨勢。也就是說對于長密鑰來

104、說，RSA隨機(jī)生成密鑰消耗時間的可能范圍較大。這是因為對于大整數(shù)來說，可能出現(xiàn)在較長一段區(qū)間中沒有素數(shù)的情況。</p><p>　　在較常用的1024位RSA加密時，用本軟件的算法，測試時最長出現(xiàn)了17秒多的計算，雖然這對于用戶來說時漫長的等待，但是考慮到安全性，還是舍棄了素數(shù)表和密鑰庫的方案，而使用大素數(shù)隨機(jī)生成，用戶可以把生成的私鑰單獨加密保存在可靠的存儲空間內(nèi)，以獲得更高的安全性。</p>&

105、lt;p>　　表3-1僅能從實驗的角度直觀理解，具體到一次密鑰生成的運算，所需要的時間是很不確定的，比如，一次1280位的密鑰生成，需要的時間完全可能比一次896位的密鑰生成時間短，由于素數(shù)分布規(guī)律非常奧妙，加上測試運算需要的時間頗長，這里很難給出對于一個具體位數(shù)的密鑰生成所需時間的統(tǒng)計模型。</p><p>　　另外需要說明的是，表3-1的加密位數(shù)在實際軟件設(shè)置時并不嚴(yán)格。這是因為，實際作為參數(shù)設(shè)置的是兩

106、個大素數(shù)的搜索起點。如果隨機(jī)生成的起點整數(shù)大小比較接近更長一位的整數(shù)的話（例如FFFF很接近10000），向后尋找所得到的素數(shù)很可能長出一位。而且，兩個k位長的整數(shù)相乘的結(jié)果也未必是2k位，比如100*100=10000，相乘結(jié)果是2k-1位。所以，在表3-1實際測試填寫時，加密位數(shù)可能會有幾位的差距，但是這不礙大局。</p><p>　　2. 測試底數(shù)A對耗時的影響</p><p>　　

107、為了保證生成素數(shù)的成功率，A至少要有4個。如果少于4個，則素數(shù)測試失敗的可能性比較大，經(jīng)過測試發(fā)現(xiàn)不可以忽略。2.2.1.3小節(jié)曾經(jīng)提到，如果素數(shù)測試通過了合數(shù)，就可能產(chǎn)生錯誤的密鑰，使加密解密操作失敗。所以測試A的時候，最少有讓其取4個值。而取6個值以上，測試算法失敗的概率已經(jīng)非常小，沒有什么實用意義，所以這里測試A從4個到6個的情況。固定其他變量：n取512位和1024位（即素數(shù)搜索起點位數(shù)設(shè)置為32和64），NP取200，SS取1

108、000。從理論上說，對于同樣的起點，素數(shù)測試次數(shù)越多，需要的時間就越長。實際測試結(jié)果如表3-2所示（其中A取4個的情況直接從表3-1復(fù)制數(shù)據(jù)，不再另做測試），表中各項對應(yīng)的全部測試數(shù)據(jù)見http://3mn.net/www/download/RSAkeygen_A-Ttest.txt ，包括兩個作為素數(shù)搜索起點的隨機(jī)數(shù)和生成的素數(shù)p、q以及e、d、n。</p><p>　　表3-2 素數(shù)測試底數(shù)A對密鑰生成時間

109、的影響</p><p>　　由表3-2可以看出，對于512bit密鑰，A取從4個到6個，對隨機(jī)密鑰的產(chǎn)生時間影響不大。但是對于較長的1024bit密鑰，A取4個和A取6個值，密鑰生成時間產(chǎn)生明顯差距，A取6個值時生成隨機(jī)密鑰需要的平均時間比A取4個值時長數(shù)秒之多。為了同時保證密鑰生成速度和素數(shù)的準(zhǔn)確程度，我們在實際使用時取A為5個值，即2、3、5、7、11。</p><p>　　3. 測試

110、小素數(shù)因子個數(shù)NP對耗時的影響</p><p>　　固定其他變量：A取5個分別為2、3、5、7、11，n取512位和1024位（即素數(shù)搜索起點位數(shù)設(shè)置為32和64），SS取1000。測試結(jié)果如表3-3所示。表中各項對應(yīng)的全部測試數(shù)據(jù)見http://3mn.net/www/download/RSAkeygen_P-Ttest.txt ，包括兩個作為素數(shù)搜索起點的隨機(jī)數(shù)和生成的素數(shù)p、q以及e、d、n。</p&