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

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

2、的文件以及密鑰文件都是文本文件。給出關(guān)鍵類(lèi)類(lèi)圖、整個(gè)應(yīng)用程序的結(jié)構(gòu)描述文檔、關(guān)鍵模塊流程圖、較詳細(xì)的接口文檔、所有源代碼。對(duì)應(yīng)用程序進(jìn)行測(cè)試，對(duì)測(cè)試結(jié)果進(jìn)行分析研究，進(jìn)而對(duì)應(yīng)用程序進(jìn)行改進(jìn)，對(duì)關(guān)鍵算法進(jìn)行盡可能的優(yōu)化，最終得到一個(gè)在windows運(yùn)行的可以用指定密鑰對(duì)任意文件進(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è)計(jì)與實(shí)現(xiàn)6</p><p>　　2.1 需求分析與總體設(shè)計(jì)6</p><p>　　2.1.1 功能分析6</p>

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

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

10、>　　3.2.3 加密解密測(cè)試23</p><p>　　3.2.4 性能分析與改進(jìn)優(yōu)化26</p><p>　　3.3 使用中國(guó)余數(shù)定理27</p><p>　　第4章 可移植模塊的簡(jiǎn)要說(shuō)明與開(kāi)發(fā)前景29</p><p><b>　　結(jié)束語(yǔ)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公鑰加密算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的

12、算法。它易于理解和操作，也十分流行。算法的名字以發(fā)明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。雖然自1978年提出以來(lái)，RSA的安全性一直未能得到理論上的證明，但它經(jīng)歷了各種攻擊，至今（2006年）未被完全攻破。隨著越來(lái)越多的商業(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ú)處不在。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗(yàn)證、各種信用卡使用的數(shù)字證書(shū)、智能移動(dòng)電話和存儲(chǔ)卡的驗(yàn)證功能芯片等，大多數(shù)使用RSA技術(shù)。</p><p>　　當(dāng)今公鑰加密更廣泛應(yīng)用于互聯(lián)網(wǎng)身份認(rèn)證，本課題將公鑰加密算法RSA應(yīng)用于小型文件加密。將任意文件加密成文本的解決方案，使其使用更加靈活。整個(gè)

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

15、　　取素?cái)?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)作為公開(kāi)密鑰，</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é)議見(jiàn)http://www.di-mgt.com.au/rsa_alg.html ，提及的算法中的字母與協(xié)議文檔中的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、SA算法加密任意一個(gè)文件，加密生成的數(shù)據(jù)為純文本。</p><p>　　④可以裝載加密過(guò)的文件，并用指定的密鑰解密還原出原文件。</p><p>　　⑤提示信息完整、操作舒適、圖形界面雅觀</p><p>　　按上述描述，給出Use Case和Statechart如圖2-1。</p><p>　　圖2-1 本項(xiàng)目的 Use Case和S

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

54、lt;p>　　歸納分析以上方法，對(duì)于任意指數(shù)E，可采用如圖2-4的算法流程計(jì)算 。</p><p>　　圖2-4 冪模運(yùn)算分解為乘模運(yùn)算的一種流程</p><p>　　按照上述流程，列舉兩個(gè)簡(jiǎn)單的冪模運(yùn)算實(shí)例來(lái)形象的說(shuō)明這種方法。</p><p><b>　?、偾蟮闹?lt;/b></p><p>　　開(kāi)始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>　　②求的值</b><

57、;/p><p>　　開(kāi)始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 = 不需要計(jì)算E = (E-1)/2 =0</p><p>　　最終D = 9 即為所求。</p><p>　　觀察上述算法，發(fā)現(xiàn)E根據(jù)奇偶除以二或減一除以二實(shí)際就是二進(jìn)制的移位操作，所以要知道需要

59、如何乘模變量，并不需要反復(fù)對(duì)E 進(jìn)行除以二或減一除以二的操作，只需要驗(yàn)證E 的二進(jìn)制各位是0 還是1 就可以了。同樣是計(jì)算，下面給出從右到左掃描二進(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)將上述算法稱(chēng)為平方乘積二進(jìn)制快速算法，例如參考文獻(xiàn)中的《基于RSA算法的一種新的加密核設(shè)計(jì)》，其實(shí)這種

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

63、模算法（主要著作發(fā)表于1985年），從而避免了通常求模算法中費(fèi)時(shí)的除法步驟。本軟件僅僅是應(yīng)用Montgomery(蒙哥馬利)算法，算法的具體推導(dǎo)證明需要頗多數(shù)論知識(shí)，不在本文的討論范圍內(nèi)，如需了解可參見(jiàn)蒙哥馬利的相關(guān)著作。下面簡(jiǎ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。對(duì)于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>　　因?yàn)?，故t為整數(shù)；同時(shí)，得。由于，M(m) 中t結(jié)果范圍是0≤t<2n，返回時(shí)如果t不小于n，應(yīng)返回t-n。</p><p>　　本軟件程序中，RSA核心運(yùn)算使用的乘

66、模算法就是 M(A*B)。雖然M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個(gè)乘模算法進(jìn)行計(jì)算了。本軟件起初未使用Montgomery 乘模算法時(shí)，加密速度比使用Montgomery乘模算法慢，但速度相差不到一個(gè)數(shù)量級(jí)。</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); //從低位到高位檢測(cè)二進(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>　　在具體的實(shí)現(xiàn)中，對(duì)應(yīng)monty類(lèi)的mul和exp方法。全局函數(shù)modexp初始化monty對(duì)象并調(diào)用其exp方法，使用的時(shí)候直接調(diào)用modexp即可。</p><p>　　3. 尋找素?cái)?shù)?Eratosthenes篩選與Fermat素?cái)?shù)測(cè)試</p><p>　　首先要說(shuō)明的

72、是，事實(shí)上，當(dāng)今的計(jì)算機(jī)還不足以聰明到立刻計(jì)算生成一個(gè)很大的隨機(jī)素?cái)?shù)。一般來(lái)說(shuō)，要得到100%準(zhǔn)確的大素?cái)?shù)，都是通過(guò)查已經(jīng)計(jì)算好的素?cái)?shù)表的方式。但是素?cái)?shù)表的方式給RSA的安全性帶來(lái)隱患，因?yàn)楣粽呷绻玫搅嗣荑€生成時(shí)所使用的素?cái)?shù)表，攻破RSA加密的難度將會(huì)大大降低。本程序起初使用素?cái)?shù)表的方式，后來(lái)考慮到安全性問(wèn)題，生成密鑰的方式改為隨機(jī)計(jì)算生成。這樣，短時(shí)間內(nèi)如果要得到一個(gè)100%準(zhǔn)確的大素?cái)?shù)是很困難的，只能以盡可能高的概率得到一個(gè)大素

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

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

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

76、剔除(即把數(shù)組b[]的對(duì)應(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對(duì)各小素?cái)?shù)因子p求模的辦法，得到當(dāng)前p在素?cái)?shù)搜索范圍內(nèi)的最小倍數(shù)在b[]中的對(duì)應(yīng)位置，將其剔除后，不斷后移p個(gè)位置，將這個(gè)小素?cái)?shù)因子p在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖2-5所示。在完成對(duì)所有小素?cái)?shù)因子的類(lèi)

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

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

81、lt;/b></p><p>　　const rep = 4; //測(cè)試次數(shù)</p><p>　　const unsigned any[rep] = { 2,3,5,7 }; //測(cè)試用的底數(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計(jì)算any[i]p-1mod p。</p><p><b>　　return 1;</b></p><p><

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

84、p>　　綜上所述，總結(jié)素?cái)?shù)尋找的流程，如圖2-6所示。</p><p>　　圖2-6 函數(shù)find_prime尋找素?cái)?shù)的流程框圖</p><p>　　得到了大素?cái)?shù)，即RSA算法中的p、q，我們就可以計(jì)算出密鑰，進(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>　　而針對(duì)不定方程ax-by=1 的最小整數(shù)解，古今中外都進(jìn)行過(guò)詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國(guó)有秦九韶的“大衍求一術(shù)”。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說(shuō)明用歐幾里德算法求解二元一次不定方程的最小整數(shù)解。</p>

86、<p>　　給定不定方程11x-49y=1，求最小的x</p><p>　　（1） 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 )用來(lái)完成這種算法。對(duì)應(yīng)前面的敘述，參數(shù)a對(duì)應(yīng)A，參數(shù)m對(duì)應(yīng)M，函數(shù)返回值即為B的最小值。</p><p>　　5. 按常規(guī)RSA算法實(shí)現(xiàn)加密與解密</p><p>　　最后，類(lèi)RSA_san基于前面的準(zhǔn)備工作，實(shí)現(xiàn)RSA密鑰生成和加解密的功能(算法在此不再贅述，RSA算法協(xié)議見(jiàn)http://www.di-mgt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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