rsa算法的實(shí)現(xiàn)——畢業(yè)論文

1、<p><b>　　RSA算法的實(shí)現(xiàn)</b></p><p><b>　　摘 要</b></p><p>　　本文設(shè)計(jì)的是一套完整實(shí)用的RSA文件加密解決方案，并具體編碼實(shí)現(xiàn)。本文采用費(fèi)馬小定理測(cè)試素?cái)?shù)，使用Montgomery加快大數(shù)模乘運(yùn)算，用C++實(shí)現(xiàn)RSA加密算法類庫(kù)，并在32位windows平臺(tái)封裝成組件。在.Net平臺(tái)引用

2、此組件，實(shí)現(xiàn)可以對(duì)任意文件進(jìn)行RSA加密操作的窗體應(yīng)用程序。經(jīng)過(guò)加密的文件以及密鑰文件都是文本文件。本文首先給出關(guān)鍵類類圖、整個(gè)應(yīng)用程序的結(jié)構(gòu)描述文檔，然后對(duì)關(guān)鍵模塊流程圖、詳細(xì)的接口文檔進(jìn)行闡述，并給出關(guān)鍵的實(shí)現(xiàn)代碼，最后對(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)的可移植組件。

3、</p><p>　　關(guān)鍵詞： RSA；文件加密；Montgomery；費(fèi)馬定理</p><p>　　Implement of RSA Algorithm</p><p><b>　　Abstract</b></p><p>　　In this paper, a solution of encrypting file w

4、ith RSA algorithm and the codes of this system are introduced. Fermat theory is used to test prime number. Montgomery is used to cut short the time of modular multiplication of large number. The class library of RSA is i

5、mplemented in C++, and packaged to component on the platform of 32 bits windows. On the platform of .Net, the application is implemented with reference of this component and can encrypt any file with RSA. Both encrypted

6、files and key </p><p>　　Key words: RSA ; File Encryption ; Montgomery ; Fermat</p><p><b>　　目 錄</b></p><p><b>　　論文總頁(yè)數(shù)：35頁(yè)</b></p><p><b>　　

7、1 引言1</b></p><p><b>　　1.1課題背景1</b></p><p>　　1.2 RSA算法介紹與應(yīng)用現(xiàn)狀1</p><p>　　1.3 RSA應(yīng)用于文件加密的分析2</p><p>　　1.3.1 文件加密使用RSA的可行性2</p><p>　　1.

8、3.2 文件加密使用RSA的意義3</p><p>　　2 RSA文件加密軟件的設(shè)計(jì)與實(shí)現(xiàn)4</p><p>　　2.1 需求分析與總體設(shè)計(jì)4</p><p>　　2.1.1 功能分析4</p><p>　　2.1.2 工程方案選擇4</p><p>　　2.2 各部分的設(shè)計(jì)與開發(fā)5</p>

9、<p>　　2.2.1 實(shí)現(xiàn)RSA加密算法的C++核心類庫(kù)5</p><p>　　2.2.2 封裝C++核心類庫(kù)的DLL組件25</p><p>　　2.2.3 引用DLL的.Net類與實(shí)現(xiàn)文件操作功能的窗體應(yīng)用程序26</p><p>　　3 軟件整體測(cè)試與分析改進(jìn)27</p><p>　　3.1 編寫測(cè)試各項(xiàng)性能需要

10、的精確計(jì)時(shí)類27</p><p>　　3.2 測(cè)試數(shù)據(jù)與分析改進(jìn)27</p><p>　　3.2.1 密鑰生成測(cè)試27</p><p>　　3.2.2 數(shù)據(jù)輸入輸出測(cè)試28</p><p>　　3.2.3 加密解密測(cè)試29</p><p><b>　　結(jié) 論31</b></

11、p><p><b>　　參考文獻(xiàn)32</b></p><p><b>　　附 錄33</b></p><p><b>　　致 謝34</b></p><p><b>　　聲 明35</b></p><p>&l

12、t;b>　　1 引言</b></p><p><b>　　1.1課題背景</b></p><p>　　RSA公鑰加密算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也十分流行。算法的名字以發(fā)明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。雖然自1978年提出以來(lái)，RSA的安

13、全性一直未能得到理論上的證明，但它經(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)（Secure Electronic Transactions，SET）就采用了標(biāo)準(zhǔn)RSA算法，這使得RSA在我們的生活中幾乎無(wú)處不在。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗(yàn)證、各種信用卡使用的數(shù)字

14、證書、智能移動(dòng)電話和存儲(chǔ)卡的驗(yàn)證功能芯片等，大多數(shù)使用RSA技術(shù)。</p><p>　　當(dāng)今公鑰加密更廣泛應(yīng)用于互聯(lián)網(wǎng)身份認(rèn)證，本課題將公鑰加密算法RSA應(yīng)用于小型文件加密。將任意文件加密成文本的解決方案，使其使用更加靈活。整個(gè)工程的分層設(shè)計(jì)，給引用移植和后續(xù)開發(fā)帶來(lái)便利。</p><p>　　1.2 RSA算法介紹與應(yīng)用現(xiàn)狀</p><p>　　RSA算法可以簡(jiǎn)單

15、敘述如下：</p><p><b>　　<密鑰生成></b></p><p>　　取素?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&g

16、t;<p>　　二元組(e,n)作為公開密鑰，</p><p>　　二元組(d,n)作為私有密鑰．</p><p><b>　　<加密解密></b></p><p>　　b=ae mod n，c=bd mod n.</p><p>　　附錄中給出了證明a=c (mod n).</p>

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

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

19、戶曉的IE瀏覽器，自然也實(shí)現(xiàn)了SSL協(xié)議，集成了使用RSA技術(shù)的加密功能，結(jié)合MD5和SHA1，主要用于數(shù)字證書和數(shù)字簽名，對(duì)于習(xí)慣于使用網(wǎng)上購(gòu)物和網(wǎng)上銀行的用戶來(lái)說(shuō)，幾乎天天都在使用RSA技術(shù)。</p><p>　　1.3 RSA應(yīng)用于文件加密的分析</p><p>　　1.3.1 文件加密使用RSA的可行性</p><p>　　通過(guò)1.2節(jié)的論述，不難看出RSA

20、當(dāng)今的應(yīng)用多在于數(shù)字簽名和證書等方面。之所以只應(yīng)用于這些短小數(shù)據(jù)的加密解密，是因?yàn)镽SA算法加密極慢，速度是DES對(duì)稱密鑰加密速度的千分之一左右。正是因?yàn)檫@樣，把RSA應(yīng)用于普通文件加密的想法一直被忽略。通常文件被想象成大數(shù)據(jù)塊，但是實(shí)際上在日常應(yīng)用中，有些極其重要的文本資料是并不太大的，比如因擔(dān)心遺忘而用普通文本記錄的銀行帳號(hào)和密碼、不應(yīng)被陌生人知道的重要電話號(hào)碼、幾千字節(jié)大的重要小圖片等。</p><p>　

21、　雖然RSA加密運(yùn)算的速度十分慢，但是在PC性能越來(lái)越好的今天，對(duì)于幾千字節(jié)的數(shù)據(jù)進(jìn)行一次幾百位密鑰的RSA加密，所消耗的時(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)楣_密鑰的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è)

22、函數(shù)測(cè)試，按初等數(shù)論中的知識(shí)對(duì)程序進(jìn)行算法優(yōu)化，最終在一臺(tái)配置為AMD Athron2800+，外頻333MHZ，物理內(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ì)于較大的文件

23、，如果分成與數(shù)字簽名同樣大小的段(這里假設(shè)數(shù)字簽名較短，不分段一次計(jì)算加密完成)，分開的各段逐一進(jìn)行加密運(yùn)算，那所需要的時(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用

24、幾百位以上的長(zhǎng)密鑰RSA加密文件，文件不能過(guò)大，一般可以接受的上限是幾KB。如果要在較短時(shí)間內(nèi)加密大文件，需要縮短密鑰長(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秒。通常

25、記錄如銀行帳號(hào)密碼等重要數(shù)據(jù)的文本文件大小不足百字節(jié)，加密只需要數(shù)秒鐘。所以對(duì)于小型文件，進(jìn)行較長(zhǎng)密鑰的RSA加密是完全可行的。</p><p>　　1.3.2 文件加密使用RSA的意義</p><p>　　如1.3.1節(jié)所述，小型文件加密可以使用RSA。比如，因擔(dān)心遺忘而用普通文本記錄的銀行帳號(hào)和密碼、不應(yīng)被陌生人知道的重要電話號(hào)碼、幾千字節(jié)大的重要小圖片等?？尚械姆椒ㄎ幢厥潜匾?，本小

26、節(jié)討論何種文件適合用非對(duì)稱密鑰加密，即RSA加密文件的意義所在。</p><p>　　對(duì)于前面敘述的帶有重要信息的小型文本和二進(jìn)制數(shù)據(jù)的維護(hù)，①如果不加密，將無(wú)法放心的保存在計(jì)算機(jī)上，尤其是連網(wǎng)的或機(jī)房里的公共計(jì)算機(jī)。②如果借助功能強(qiáng)大的大型多用戶數(shù)據(jù)保護(hù)程序維護(hù)幾個(gè)小型文件，顯得十分煩瑣，好比殺雞用牛刀。③如果采用對(duì)稱密鑰加密，即加密解密的密鑰相同，只適合部分情況。在某些情況下，使用對(duì)稱密鑰加密文件，交流使用不

27、夠方便。比如，張三由于某種原因，需要將自己的某個(gè)文件在公共計(jì)算機(jī)上留給李四，而不希望別人看到內(nèi)容。如果采用對(duì)稱密鑰加密，張三和李四提前約好一個(gè)密碼就可以。但是如果張三想要在同一臺(tái)公共計(jì)算機(jī)上再留一個(gè)秘密文件給王五，而不希望別人看到，就要和王五另外約定一個(gè)密碼。如果需要在這臺(tái)公共計(jì)算機(jī)上留十個(gè)文件給不同的人，自己就要記和十個(gè)人約定好的密碼，這樣以來(lái)交流起來(lái)不夠方便，因?yàn)閷?duì)于張三，要自己維護(hù)太多的密鑰。非對(duì)稱密鑰(公開密鑰方式)恰好解決這樣

28、的問(wèn)題。只要大家都在這臺(tái)計(jì)算機(jī)或這臺(tái)計(jì)算機(jī)可以訪問(wèn)到的地方，留下自己的公開密鑰，一切就變的容易解決了。張三要留給李四的文件，就用李四的公開密鑰加密，要留給王五的文件，就用王五的公開密鑰加密。李四和王五只要把留給自己的文件用自己的私</p><p>　　綜上所述，使用前面敘述的方式加密文件有兩點(diǎn)重要意義：①應(yīng)用非對(duì)稱密鑰加密任意文件，使非對(duì)稱密鑰的應(yīng)用不僅僅局限于互聯(lián)網(wǎng)絡(luò)。②非對(duì)稱加密后的數(shù)據(jù)變換成文本，使得我們可

29、以通過(guò)幾乎任何方式安全傳遞任意文件，比如在只有http的環(huán)境使用xml方式。</p><p>　　2 RSA文件加密軟件的設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　2.1 需求分析與總體設(shè)計(jì)</p><p>　　2.1.1 功能分析</p><p>　　經(jīng)過(guò)1.3.2節(jié)的論述，我們可以將對(duì)軟件的要求總結(jié)如下：</p><p>

30、　　①可以按要求的位數(shù)生成非對(duì)稱密鑰。</p><p>　?、诳梢杂弥付荑€以RSA算法加密任意一個(gè)文件，加密生成的數(shù)據(jù)為純文本。</p><p>　?、劭梢匝b載加密過(guò)的文件，并用指定的密鑰解密還原出原文件。</p><p>　?、?提示信息完整、操作舒適、圖形界面雅觀</p><p>　　按上述描述，給出Use Case和Statec

31、hart如圖2-1。</p><p>　　圖2-1 本項(xiàng)目的 Use Case和Statechart</p><p>　　根據(jù)以上分析，一般來(lái)說(shuō)，需要進(jìn)行編碼的程序有 </p><p>　　①RSA密鑰生成 ②RSA加密解密 ③任意文件的讀取 ④各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換 ⑤圖形操作界面。</p><p>　　2.1.2 工程方案選擇</

32、p><p>　　綜合考慮復(fù)用性、可維護(hù)性和執(zhí)行效率，較妥當(dāng)?shù)姆椒ㄊ欠謱釉O(shè)計(jì)。核心的RSA算法由C++類庫(kù)實(shí)現(xiàn)，針對(duì)用戶所在的操作系統(tǒng)封裝成本地化組件。其他各功能如文件操作、數(shù)據(jù)編碼轉(zhuǎn)換和圖形界面等，由托管代碼借助虛擬機(jī)平臺(tái)標(biāo)準(zhǔn)庫(kù)的功能快速開發(fā)實(shí)現(xiàn)(本文針對(duì)選用.Net上的C#論述，選用java由JNI或其他方式調(diào)用本地組件，設(shè)計(jì)模式上是完全類似的)。這種開發(fā)方式，核心功能集中在最底層，在不斷的封裝中針對(duì)具體環(huán)境對(duì)組件

33、功能不斷擴(kuò)充，任意一個(gè)層面的封裝都可以被直接應(yīng)用到其他項(xiàng)目，比如在Web使用以前為某窗體程序?qū)懙慕M件、給嵌入式設(shè)備交叉編譯算法庫(kù)等。但是每一層都需要依賴底層的所有組件。圖2-2形象的說(shuō)明了分層設(shè)計(jì)給復(fù)用帶來(lái)的好處。</p><p>　　圖2-2 綜合考慮復(fù)用性、可維護(hù)性和執(zhí)行效率的分層設(shè)計(jì)</p><p>　　選用這種設(shè)計(jì)方案，上層使用C#，底層算法使用C++，可以由一個(gè)Visual St

34、udio解決方案管理，給調(diào)試帶來(lái)極大的方便。整個(gè)工程分四層，實(shí)現(xiàn)RSA加密算法的C++核心類庫(kù)、封裝C++核心類庫(kù)的DLL組件、引用DLL的.Net類、實(shí)現(xiàn)文件操作功能的.Net窗體應(yīng)用程序。2.2節(jié)詳細(xì)介紹各部分的設(shè)計(jì)與開發(fā)。</p><p>　　考慮到工作量，本軟件加解密數(shù)據(jù)沒有嚴(yán)格遵從RSA標(biāo)準(zhǔn)PKCS #1，而是在滿足設(shè)計(jì)要求的前提下，以一種盡可能簡(jiǎn)單的方式實(shí)現(xiàn)加密和解密。</p><

35、p>　　2.2 各部分的設(shè)計(jì)與開發(fā)</p><p>　　2.2.1 實(shí)現(xiàn)RSA加密算法的C++核心類庫(kù)</p><p>　　1. 大數(shù)存儲(chǔ)和四則運(yùn)算</p><p>　　根據(jù)RSA算法的要求，為了實(shí)現(xiàn)大數(shù)的各種復(fù)雜運(yùn)算，需要首先實(shí)現(xiàn)大數(shù)存儲(chǔ)和基本四則運(yùn)算的功能。當(dāng)今開源的大數(shù)運(yùn)算C++類有很多，多用于數(shù)學(xué)分析、天文計(jì)算等，本文選用了一個(gè)流行的大數(shù)類型，并針對(duì)R

36、SA算法和本項(xiàng)目的具體需要對(duì)其進(jìn)行了擴(kuò)充和改進(jìn)。下面簡(jiǎn)單介紹大數(shù)存儲(chǔ)和四則運(yùn)算的實(shí)現(xiàn)原理。</p><p>　　最先完成的功能是大數(shù)的存儲(chǔ)，存儲(chǔ)功能由flex_unit類提供。和普通的類型一樣，每一個(gè)大數(shù)對(duì)應(yīng)一個(gè)flex_unit的實(shí)例。類flex_unit中，用一個(gè)無(wú)符號(hào)整數(shù)指針unsigned * a指向一塊內(nèi)存空間的首地址，這塊內(nèi)存空間用來(lái)存儲(chǔ)一個(gè)大數(shù)，所以可以說(shuō)，大數(shù)是被存儲(chǔ)在一個(gè)以u(píng)nsigned為單元

37、的線性組中。在方法void reserve( unsigned x )中通過(guò)C++的new來(lái)給a開辟空間，當(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)緊縮，這是為了在運(yùn)算的時(shí)候提高執(zhí)行效率。結(jié)合指針a，有兩個(gè)重要的無(wú)符號(hào)整數(shù)來(lái)控制存儲(chǔ)，unsigned z和unsigned n，z是被分配空間的單元數(shù)，

38、隨數(shù)字變大不斷增大，不會(huì)自己緊縮，而n是當(dāng)前存儲(chǔ)的大數(shù)所占的單元數(shù)，組成一個(gè)大數(shù)的各unsigned單元的存入和讀出由set、get方法完成，變量n是只讀的。類型unsigned在32位機(jī)是32位的，所以對(duì)于flex_unit這個(gè)大數(shù)類來(lái)說(shuō)，每個(gè)大數(shù)最大可</p><p>　　圖2-3 flex_unit對(duì)大數(shù)的管理</p><p>　　在flex_unit的存儲(chǔ)功能基礎(chǔ)上，將其派生，得到

39、vlong_value，在vlong_value中實(shí)現(xiàn)四則運(yùn)算函數(shù)，并實(shí)現(xiàn)強(qiáng)制轉(zhuǎn)換運(yùn)算符unsigned，以方便大數(shù)類型和普通整數(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ù)字的計(jì)算，比如相加，就是低位單元對(duì)齊，逐單元相加并進(jìn)位，減法同理。而乘除法和取余也都是按照豎式運(yùn)算的原理實(shí)現(xiàn)，并進(jìn)行了必要的優(yōu)化。雖然實(shí)現(xiàn)了四則

40、運(yùn)算函數(shù)，但是若是程序里的運(yùn)算都要調(diào)用函數(shù)，顯得煩瑣而且看起來(lái)不美觀，所以我們另寫一個(gè)類vlong，關(guān)聯(lián)(Associate，即使用vlong_value類型的對(duì)象或其指針作為成員)vlong_value，在vlong重載運(yùn)算符。這樣，當(dāng)我們操作vlong大數(shù)對(duì)象的時(shí)候，就可以像使用一個(gè)簡(jiǎn)單類型一樣使用各種運(yùn)算符號(hào)了。之所以將vlong_value的指針作為成員而不是直接構(gòu)造的對(duì)象，也是為了提高執(zhí)行效率，因?yàn)榇笮蛯?duì)象的拷貝要消耗不少機(jī)器

41、時(shí)間。</p><p>　　2. 大數(shù)冪模與乘模運(yùn)算?Montgomery冪模算法</p><p>　　在實(shí)現(xiàn)了vlong類型后，大數(shù)的存儲(chǔ)和四則運(yùn)算的功能都完成了。考慮到RSA算法需要進(jìn)行冪模運(yùn)算，需要準(zhǔn)備實(shí)現(xiàn)這些運(yùn)算的方法。所以寫一個(gè)vlong的友元，完成冪模運(yùn)算功能。冪模運(yùn)算是RSA 算法中比重最大的計(jì)算，最直接地決定了RSA 算法的性能，針對(duì)快速冪模運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出

42、了很多的解決方案。經(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><p>　　歸納分析以上方法，對(duì)于任意指數(shù)E，可采用如圖2-4的算法流程計(jì)算 。</p><p>　　圖2-4

43、 冪模運(yùn)算分解為乘模運(yùn)算的一種流程</p><p>　　按照上述流程，列舉兩個(gè)簡(jiǎn)單的冪模運(yùn)算實(shí)例來(lái)形象的說(shuō)明這種方法。</p><p><b>　?、偾蟮闹?lt;/b></p><p>　　開始D = 1P = 2 mod 17 = 2E = 15</p><p>　　E奇數(shù)D = DP mod n

44、= 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ù)D = DP mod n = 9P = PP mod n = 1E= (E-1)/2 =1</p><p>　　E奇數(shù)D =

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

46、P = PP mod n = 4E = E/2 =4</p><p>　　E偶數(shù)D = 1P = PP mod n = 3E = E/2 =2</p><p>　　E偶數(shù)D = 1P = PP mod n = 9E = E/2 =1</p><p>　　E奇數(shù)D = DP mod n = 9P = 不需要計(jì)算E

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

48、左到右為u,u-1,u-2,…,0。</p><p>　　Powmod(C,E,n) </p><p><b>　　{</b></p><p><b>　　D=1;</b></p><p>　　P=C mod n;</p><p>　　for i=0 to u do <

49、/p><p><b>　　{</b></p><p>　　if(Ei=1)D=D*P(mod n); </p><p>　　P=P*P(mod n);</p><p><b>　　}</b></p><p><b>　　return D;</b></p

50、><p><b>　　}</b></p><p>　　有些文獻(xiàn)將上述算法稱為平方乘積二進(jìn)制快速算法，例如參考文獻(xiàn)中的《基于RSA算法的一種新的加密核設(shè)計(jì)》，其實(shí)這種算法本質(zhì)上和圖2-4的流程完全一致，只是把根據(jù)指數(shù)奇偶分開的減一和除以二合并成對(duì)指數(shù)二進(jìn)制各位的判斷而已。在本軟件的代碼中采用直接掃描vlong二進(jìn)制各位的辦法。</p><p>　　剩

51、下的問(wèn)題就是乘模運(yùn)算了。提高乘模運(yùn)算的速度是提高模冪運(yùn)算速度的關(guān)鍵。一般情況下，n是數(shù)百位乃至千位以上的二進(jìn)制整數(shù)，用普通的除法求模而進(jìn)行乘模運(yùn)算是不能滿足速度的要求的。為此，Montgomery在1983年提出了一種模加右移的乘模算法（主要著作發(fā)表于1985年），從而避免了通常求模算法中費(fèi)時(shí)的除法步驟。本軟件僅僅是應(yīng)用Montgomery(蒙哥馬利)算法，算法的具體推導(dǎo)證明需要頗多數(shù)論知識(shí)，不在本文的討論范圍內(nèi)，如需了解可參見蒙哥馬利

52、的相關(guān)著作。下面簡(jiǎn)單描述RSA中常用的Montgomery(蒙哥馬利)算法供參考理解源程序。</p><p>　　選擇與模數(shù)n互素的基數(shù)R=2k，n滿足2k－1≤n<2k， n應(yīng)為奇數(shù)。并且選擇R-1及n’，滿足0< R-1<n, 0< n’<n,使得 RR-1-nn’＝1。對(duì)于0≤m<Rn的任意整數(shù),Montgomery給出求模乘法mR-1 mod n 的快速算法M(m):&

53、lt;/p><p><b>　　M(m)</b></p><p><b>　　{</b></p><p>　　if (t≥n) return (t-n); </p><p>　　else return t;</p><p><b>　　}</b></p

54、><p>　　因?yàn)椋蕋為整數(shù)；同時(shí)，得。由于，M(m) 中t結(jié)果范圍是0≤t<2n，返回時(shí)如果t不小于n，應(yīng)返回t-n。</p><p>　　本軟件程序中，RSA核心運(yùn)算使用的乘模算法就是 M(A*B)。雖然M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個(gè)乘模算法進(jìn)行計(jì)算了。</p><p>　　將上述乘模算法結(jié)合前面敘述

55、的冪模算法，構(gòu)成標(biāo)準(zhǔn)Montgomery冪模算法，即本軟件所使用的流程，敘述如下。</p><p>　　M(m) //蒙哥馬利乘?！?lt;/p><p><b>　　{</b></p><p>　　k = ( m * n’ ) mod R;</p><p>　　x = (m + k*n ) / R;</p>&

56、lt;p>　　if (x>=n) x -= n;</p><p><b>　　return x;</b></p><p><b>　　}</b></p><p>　　exp(C,E,n) //蒙哥馬利冪模</p><p><b>　　{</b></p>

57、<p><b>　　D=R-n;</b></p><p>　　P=C*R mod n;</p><p><b>　　i=0;</b></p><p>　　while(true)</p><p><b>　　{</b></p><p>　　if

58、(E的當(dāng)前二進(jìn)制位Ei==1)D=M(D*P); //從低位到高位檢測(cè)二進(jìn)制位</p><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&

59、gt;</p><p>　　return D*R-1 (mod n);</p><p><b>　　}</b></p><p>　　在具體的實(shí)現(xiàn)中，對(duì)應(yīng)monty類的mul和exp方法。全局函數(shù)modexp初始化monty對(duì)象并調(diào)用其exp方法，使用的時(shí)候直接調(diào)用modexp即可。</p><p>　　3. 尋找素?cái)?shù)?E

60、ratosthenes篩選與Fermat素?cái)?shù)測(cè)試</p><p>　　首先要說(shuō)明的是，事實(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)題，生成密鑰的方式改為

61、隨機(jī)計(jì)算生成。這樣，短時(shí)間內(nèi)如果要得到一個(gè)100%準(zhǔn)確的大素?cái)?shù)是很困難的，只能以盡可能高的概率得到一個(gè)大素?cái)?shù)。</p><p>　　經(jīng)過(guò)2.2.1.1和2.2.1.2小節(jié)，所有的大數(shù)運(yùn)算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素?cái)?shù)的功能置于類Prime_factory_san之中。外部只要調(diào)用本類實(shí)例的成員vlong find_prime( vlong & start )就可以以大數(shù)start為起點(diǎn)，得到

62、一個(gè)數(shù)，這個(gè)數(shù)是素?cái)?shù)的概率很大。下面介紹尋找素?cái)?shù)的原理。</p><p>　　首先在需要尋找素?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ì)

63、應(yīng)的大數(shù)進(jìn)行比較確切的素?cái)?shù)測(cè)試即可，只要被測(cè)試的數(shù)是素?cái)?shù)概率達(dá)到一定門限，就判這個(gè)數(shù)為素?cái)?shù)。這樣做既保證了這段程序可以在短時(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值算法。首先，在類Prime_factory_san被構(gòu)造的時(shí)候，構(gòu)造函數(shù)中從2開始搜

64、尋一些小素?cái)?shù)，記錄在數(shù)組pl[]中，共記錄NP個(gè)。這些小素?cái)?shù)用來(lái)當(dāng)作因子，他們的倍數(shù)將被從大素?cái)?shù)搜索范圍內(nèi)剔除(即把數(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&

65、gt;<p>　　unsigned r = start % vlong(p);</p><p>　　if (r) r = p - r;</p><p>　　while ( r < SS )</p><p><b>　　{</b></p><p><b>　　b[r] = 0;</b&g

66、t;</p><p><b>　　r += p;</b></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)位置，將其剔除后，不斷

67、后移p個(gè)位置，將這個(gè)小素?cái)?shù)因子p在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖2-5所示。在完成對(duì)所有小素?cái)?shù)因子的類似操作后，他們的倍數(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ù)論

68、學(xué)家利用費(fèi)馬小定理研究出了多種素?cái)?shù)測(cè)試方法，本程序使用一種最簡(jiǎn)單的方式，直接應(yīng)用費(fèi)馬小定理。取一個(gè)與p互素的整數(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ù)的概率就比較大。按這種原理，我們編寫素?cái)?shù)測(cè)試函數(shù)如下。</p><p>　　int is_probable_prime_san( c

69、onst vlong &p )</p><p><b>　　{</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

70、<rep; i+=1 )</p><p>　　if ( modexp( any[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>&

71、lt;b>　　return 1;</b></p><p><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ò)一整天的生

72、成密鑰和加密操作，沒有發(fā)現(xiàn)失敗的密鑰， 所以本文暫沒有對(duì)這個(gè)問(wèn)題進(jìn)行討論。</p><p>　　實(shí)際得到素?cái)?shù)的流程：</p><p>　　先得到一個(gè)隨機(jī)的大整數(shù)N當(dāng)作尋找的起點(diǎn)．</p><p>　　確定一個(gè)尋找范圍的大小SS，把(N,N+SS)范圍內(nèi)的小素?cái)?shù)倍數(shù)去掉，即前面敘述的古希臘某人發(fā)明的篩選法．小素?cái)?shù)因子從２開始取，取幾百個(gè)(論文中將小素?cái)?shù)因子個(gè)數(shù)記為NP

73、)．</p><p>　　對(duì)范圍內(nèi)沒有去掉的數(shù)逐一進(jìn)行素?cái)?shù)測(cè)試，一個(gè)數(shù)如果通過(guò)測(cè)試次數(shù)達(dá)到一定標(biāo)準(zhǔn)，就判為素?cái)?shù)．</p><p>　　如果范圍內(nèi)沒找到素?cái)?shù)，就令N=N+SS，回到(2)繼續(xù)尋找．</p><p>　　用以上算法，直到以某成功概率得到素?cái)?shù)為止</p><p>　　綜上所述，總結(jié)素?cái)?shù)尋找的流程，如圖2-6所示。</p>

74、<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的情況下，求B的最小值，使得 (AB) mod M = 1。即相當(dāng)于求解B、N都是未知數(shù)

75、的二元一次不定方程 AB-MN=1的最小整數(shù)解。</p><p>　　而針對(duì)不定方程ax-by=1 的最小整數(shù)解，古今中外都進(jìn)行過(guò)詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國(guó)有秦九韶的“大衍求一術(shù)”。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說(shuō)明用歐幾里德算法求解二元一次不定方程的最小整數(shù)解。</p><p>　　給定不定方程11x-49y=1，求最小的x</p

76、><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><b>　　逆向代入：</b></p>

77、<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( const vlong &a, const vlong &m )

78、用來(lái)完成這種算法。對(duì)應(yīng)前面的敘述，參數(shù)a對(duì)應(yīng)A，參數(shù)m對(duì)應(yīng)M，函數(shù)返回值即為B的最小值。</p><p>　　5. RSA算法實(shí)現(xiàn)加密與解密</p><p>　　最后，類RSA_san基于前面的準(zhǔn)備工作，實(shí)現(xiàn)RSA密鑰生成和加解密的功能(算法在此不再贅述，RSA算法協(xié)議見（http://www.di-mgt.com.au/rsa_alg.html)。為了方便閱讀，整個(gè)類的源程序中，所使用的

79、變量字母均和RSA算法協(xié)議中一致。在類RSA_san的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對(duì)隨機(jī)密鑰的操作。之后可以直接使用類的其他成員進(jìn)行RSA加解密操作。類中各成員頻繁的用到字符串和vlong類型的轉(zhuǎn)換，因?yàn)榇髷?shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。所以，需要實(shí)現(xiàn)一系列的編碼轉(zhuǎn)換函數(shù)，比如將unsigned指針指向的一段空間里保存的一個(gè)大數(shù)，表示成十六進(jìn)制形式的字符串文本。編碼轉(zhuǎn)換通常是用C風(fēng)格的

80、指針操作和sprintf函數(shù)來(lái)完成。</p><p>　　需要加密和解密的數(shù)據(jù)也是通過(guò)字符串參數(shù)置入的。由于字符串的結(jié)尾字符“\0”實(shí)際上也可能是需要加密的數(shù)據(jù)，所以置入的串長(zhǎng)度并不能以“\0”來(lái)決定，程序里引入一個(gè)unsigned類型的參數(shù)來(lái)決定置入的串長(zhǎng)度，這樣就解決了加密連0數(shù)據(jù)時(shí)候被截?cái)嗟膯?wèn)題。</p><p>　　因?yàn)槭菍?duì)文件加密的軟件，需要加密的數(shù)據(jù)通常并不止幾字節(jié)，本軟件默認(rèn)

81、的分塊大小是1字節(jié)，即逐個(gè)字節(jié)作為參數(shù)，調(diào)用C++核心模塊中的方法。</p><p>　　加密解密流程均為標(biāo)準(zhǔn)RSA算法，具體過(guò)程見下圖：</p><p><b>　?、偕擅荑€：</b></p><p>　　圖2-7 隨機(jī)生成密鑰</p><p><b>　　相關(guān)代碼：</b></p>

82、<p>　　public static int GetRandomString()//實(shí)現(xiàn)隨機(jī)字串的獲得</p><p><b>　　{</b></p><p>　　Random rnd = new Random();</p><p>　　Byte[]b=new Byte[System.Math.Max(RSAprimeplen1

83、,RSAprimeplen2)];</p><p><b>　　s1="";</b></p><p><b>　　s2="";</b></p><p>　　for(int i=0;i<RSAprimeplen1;i++)</p><p><b>

84、;　　{</b></p><p>　　Byte tmp=System.Convert.ToByte(254.0*rnd.NextDouble());</p><p>　　if(tmp!=0)b[i]=tmp;else b[i]=1;}</p><p>　　s1=wujunjie_rsa.FromASCIIByteArray(b);</p>

85、;<p>　　for(int i=0;i<RSAprimeplen2;i++)</p><p><b>　　{</b></p><p>　　Byte tmp=System.Convert.ToByte(254.0*rnd.NextDouble());</p><p>　　if(tmp!=0)b[i]=tmp;else b[i

86、]=1;</p><p><b>　　}</b></p><p>　　s2=wujunjie_rsa.FromASCIIByteArray(b);</p><p>　　return 1;}</p><p><b>　?、诩用苓^(guò)程：</b></p><p>　　圖2-8 載入待

87、加密的文本</p><p>　　圖2-9 準(zhǔn)備加密文本</p><p>　　圖2-10加密后生成的文本</p><p>　　圖2-11加密過(guò)程完成</p><p><b>　　相關(guān)代碼：</b></p><p>　　private void menuItem10_Click(object send

88、er, System.EventArgs e)//公鑰加密</p><p><b>　　{</b></p><p>　　if(wujunjie_rsa.charlist.Count==0)</p><p><b>　　{</b></p><p>　　emptymsg em=new emptymsg(

89、this); </p><p>　　em.Show();</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　Stream myStream ;</p><p>　　SaveFileDialog saveFileDi

90、alog1 = new SaveFileDialog();</p><p>　　saveFileDialog1.Filter = "Hex text files (*.hextxt)|*.hextxt|All files (*.*)|*.*" ;</p><p>　　saveFileDialog1.FilterIndex = 1 ;</p><p&

91、gt;　　saveFileDialog1.RestoreDirectory = true ;</p><p>　　if(saveFileDialog1.ShowDialog() == DialogResult.OK)</p><p><b>　　{</b></p><p>　　if((myStream=saveFileDialog1.OpenF

92、ile()) != null)</p><p><b>　　{</b></p><p>　　textBox1.Text+="\r\n正在對(duì)讀入的文件進(jìn)行處理，請(qǐng)稍候：）\r\n";</p><p>　　System.Threading.Thread.Sleep(500);</p><p>　　High

93、ResolutionTimer timer = new HighResolutionTimer(); </p><p>　　timer.Start();</p><p>　　using (StreamWriter sw = new StreamWriter(myStream)) </p><p><b>　　{</b></p>&

94、lt;p>　　sw.WriteLine("# RSA.HexText");</p><p>　　sw.WriteLine("#___________________________________________");</p><p>　　Byte []b=new Byte[wujunjie_rsa.RSAstep];</p>&

95、lt;p>　　wujunjie_rsa.result_hexstrings.Clear();</p><p>　　progressBar1.Minimum=0;</p><p>　　progressBar1.Maximum=wujunjie_rsa.charlist.Count;</p><p>　　for(int i=0;i<wujunjie_rsa.

96、charlist.Count;i+=System.Convert.ToInt32(wujunjie_rsa.RSAstep))</p><p><b>　　{</b></p><p>　　for(int j=0;j<wujunjie_rsa.RSAstep;j++)</p><p><b>　　{</b></p

97、><p>　　b[j]=System.Convert.ToByte(wujunjie_rsa.charlist[i+j]);</p><p><b>　　}</b></p><p><b>　　string s;</b></p><p>　　wujunjie_rsa.RSA_san_en(b,wujun

98、jie_rsa.RSAstep);</p><p>　　s=wujunjie_rsa.get_result_hexstring();</p><p>　　wujunjie_rsa.result_hexstrings.Add(s);</p><p>　　progressBar1.Value=i+1;</p><p><b>　　}&l

99、t;/b></p><p>　　for(int i=0;i<wujunjie_rsa.result_hexstrings.Count;i++)</p><p><b>　　{</b></p><p>　　string hs=System.Convert.ToString(wujunjie_rsa.result_hexstrings[

100、i]);</p><p>　　if(hs==null||hs=="")sw.WriteLine("0");</p><p>　　else sw.WriteLine(hs);</p><p><b>　　}</b></p><p>　　sw.WriteLine("#____

101、_______________________________________");</p><p>　　sw.Write("# ");</p><p>　　sw.WriteLine(DateTime.Now);</p><p>　　wujunjie_rsa.result_hexstrings.Clear();</p>&

102、lt;p><b>　　}</b></p><p>　　myStream.Close();</p><p>　　timer.Stop(); </p><p>　　textBox1.Text+="\r\n消耗時(shí)間："+timer.ElapsedTime+"\r\n";</p><p&

103、gt;　　textBox1.Text+="\r\n處理完成，新生成文件\r\n"+saveFileDialog1.FileName+"\r\n";</p><p>　　progressBar1.Value=0;</p><p><b>　　}</b></p><p><b>　　}</b&

104、gt;</p><p><b>　　} </b></p><p><b>　?、劢饷苓^(guò)程：</b></p><p>　　圖2-12 載入加密后生成的文本</p><p>　　圖2-13解密已加密的文本</p><p>　　圖2-14 解密生成解密文件</p>&

105、lt;p>　　圖2-15 解密過(guò)程完成</p><p><b>　　相關(guān)代碼：</b></p><p>　　private void menuItem8_Click(object sender, System.EventArgs e)//私鑰解密</p><p><b>　　{</b></p><

106、p>　　if(wujunjie_rsa.hextxtlist.Count==0)</p><p><b>　　{</b></p><p>　　emptymsg em=new emptymsg(this); </p><p>　　em.Show();</p><p><b>　　return;</b&

107、gt;</p><p><b>　　}</b></p><p>　　Stream myStream ;</p><p>　　SaveFileDialog saveFileDialog1 = new SaveFileDialog();</p><p>　　saveFileDialog1.Filter = "Tex

108、t files (*.txt)|*.txt|All files (*.*)|*.*" ;</p><p>　　saveFileDialog1.FilterIndex = 2 ;</p><p>　　saveFileDialog1.RestoreDirectory = true ;</p><p>　　if(saveFileDialog1.ShowDial

109、og() == DialogResult.OK)</p><p><b>　　{</b></p><p>　　if((myStream=saveFileDialog1.OpenFile()) != null)</p><p><b>　　{</b></p><p>　　textBox1.Text+=

110、"\r\n正在對(duì)十六進(jìn)制文本進(jìn)行處理，請(qǐng)稍候：）\r\n";</p><p>　　System.Threading.Thread.Sleep(500);</p><p>　　HighResolutionTimer timer = new HighResolutionTimer(); </p><p>　　timer.Start(); </p

111、><p>　　using (BinaryWriter bn = new BinaryWriter(myStream))</p><p><b>　　{</b></p><p>　　progressBar1.Minimum=0;</p><p>　　progressBar1.Maximum=wujunjie_rsa.hextx

112、tlist.Count;</p><p>　　for(int i=0;i<wujunjie_rsa.hextxtlist.Count;i++)</p><p><b>　　{</b></p><p>　　wujunjie_rsa.RSA_san_dn_hexstring(System.Convert.ToString(wujunjie_r

113、sa.hextxtlist[i]));</p><p>　　for(uint j=0;j<wujunjie_rsa.RSAstep;j++)</p><p><b>　　{</b></p><p>　　bn.Write(wujunjie_rsa.get_result_byte(j));</p><p><b&

114、gt;　　}</b></p><p>　　progressBar1.Value=i+1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　myStream.Close();</p><p>　　timer.Sto

115、p(); </p><p>　　textBox1.Text+="\r\n消耗時(shí)間："+timer.ElapsedTime+"\r\n";</p><p>　　textBox1.Text+="\r\n處理完成，新生成文件\r\n"+saveFileDialog1.FileName+"\r\n";</p>

116、;<p>　　progressBar1.Value=0;}</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　6. 核心類庫(kù)綜述</b></p><p>　　綜上幾小節(jié)所述，實(shí)現(xiàn)RSA加密算法的C++核心

117、類庫(kù)由六個(gè)類組成，類名和對(duì)應(yīng)的功能描述總結(jié)如表2-1所示。各個(gè)類之間的關(guān)系如圖2-16所示。</p><p>　　表2-1 RSA加密算法的C++類庫(kù)中的類</p><p>　　圖2-16 C++核心功能類圖</p><p>　　另外需要說(shuō)明的是，程序中有幾個(gè)不屬于任何類的全局函數(shù)，比如應(yīng)用輾轉(zhuǎn)相除法求最大公約數(shù)的函數(shù)gcd、解同余方程的函數(shù)modinv等。按常規(guī)設(shè)

118、計(jì)模式來(lái)說(shuō)，不應(yīng)當(dāng)出現(xiàn)類之外的函數(shù)，但是因?yàn)檫@些函數(shù)使用頻繁，考慮到機(jī)器效率，直接置于全局，不再另行包裝。</p><p>　　2.2.2 封裝C++核心類庫(kù)的DLL組件</p><p>　　在Visual Studio當(dāng)前的解決方案中以VC++創(chuàng)建一個(gè)win32dll工程，將測(cè)試好的實(shí)現(xiàn)RSA加密算法的C++核心類庫(kù)中的所有文件加入到此工程下，新建一對(duì)cpp和h文件，把可能用到的功能全部

119、規(guī)劃為新文件中的全局函數(shù)，并以C接口導(dǎo)出，即__declspec(dllexport)。由于核心類庫(kù)的對(duì)外功能都使由RSA_san類提供的，所以在新cpp文件中全局的聲明一個(gè)RSA_san類的對(duì)象指針(RSA_san *WRSA)，全局函數(shù)int start_RSA_san()初始化*WRSA對(duì)象，在初始化成功后，其他全局函數(shù)通過(guò)調(diào)用*WRSA對(duì)象的公開方法實(shí)現(xiàn)各種功能，如加密、讀取密鑰等。在關(guān)閉上層引用程序以前，應(yīng)執(zhí)行int fini