rsa算法的實現——畢業(yè)論文

上傳人：奔*** IP屬地：河北更新時間：2024-03-02 格式：doc 頁數：38 大?。?92.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩37頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　RSA算法的實現　　摘要　　本文設計的是一套完整實用的RSA文件加密解決方案，并具體編碼實現。本文采用費馬小定理測試素數，使用Montgomery加快大數模乘運算，用C++實現RSA加密算法類庫，并在32位windows平臺封裝成組件。在.Net平臺引用

2、此組件，實現可以對任意文件進行RSA加密操作的窗體應用程序。經過加密的文件以及密鑰文件都是文本文件。本文首先給出關鍵類類圖、整個應用程序的結構描述文檔，然后對關鍵模塊流程圖、詳細的接口文檔進行闡述，并給出關鍵的實現代碼，最后對應用程序進行測試，對測試結果進行分析研究，進而對應用程序進行改進，對關鍵算法進行盡可能的優(yōu)化，最終得到一個在windows運行的可以用指定密鑰對任意文件進行RSA加密并可解密的完整應用程序，和一些相關的可移植組件。

3、　　關鍵詞： RSA；文件加密；Montgomery；費馬定理　　Implement of RSA Algorithm　　Abstract　　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 　　Key words: RSA ; File Encryption ; Montgomery ; Fermat　　目錄　　論文總頁數：35頁

7、1 引言1　　1.1課題背景1　　1.2 RSA算法介紹與應用現狀1　　1.3 RSA應用于文件加密的分析2　　1.3.1 文件加密使用RSA的可行性2　　1.

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

9、　　2.2.1 實現RSA加密算法的C++核心類庫5　　2.2.2 封裝C++核心類庫的DLL組件25　　2.2.3 引用DLL的.Net類與實現文件操作功能的窗體應用程序26　　3 軟件整體測試與分析改進27　　3.1 編寫測試各項性能需要

10、的精確計時類27　　3.2 測試數據與分析改進27　　3.2.1 密鑰生成測試27　　3.2.2 數據輸入輸出測試28　　3.2.3 加密解密測試29　　結論31</

11、p>　　參考文獻32　　附錄33　　致謝34　　聲明35&l

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

13、全性一直未能得到理論上的證明，但它經歷了各種攻擊，至今（2006年）未被完全攻破。隨著越來越多的商業(yè)應用和標準化工作，RSA已經成為最具代表性的公鑰加密技術。VISA、MasterCard、IBM、Microsoft等公司協力制定的安全電子交易標準（Secure Electronic Transactions，SET）就采用了標準RSA算法，這使得RSA在我們的生活中幾乎無處不在。網上交易加密連接、網上銀行身份驗證、各種信用卡使用的數字

14、證書、智能移動電話和存儲卡的驗證功能芯片等，大多數使用RSA技術。　　當今公鑰加密更廣泛應用于互聯網身份認證，本課題將公鑰加密算法RSA應用于小型文件加密。將任意文件加密成文本的解決方案，使其使用更加靈活。整個工程的分層設計，給引用移植和后續(xù)開發(fā)帶來便利。　　1.2 RSA算法介紹與應用現狀　　RSA算法可以簡單

15、敘述如下：　　<密鑰生成>　　取素數p，q，令n=p×q.　　取與(p-1)×(q-1)互素的整數e，　　由方程d×e=1 (mod (p-1)×(q-1))解出d，</p&g

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

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

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

19、戶曉的IE瀏覽器，自然也實現了SSL協議，集成了使用RSA技術的加密功能，結合MD5和SHA1，主要用于數字證書和數字簽名，對于習慣于使用網上購物和網上銀行的用戶來說，幾乎天天都在使用RSA技術。　　1.3 RSA應用于文件加密的分析　　1.3.1 文件加密使用RSA的可行性　　通過1.2節(jié)的論述，不難看出RSA

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

21、　雖然RSA加密運算的速度十分慢，但是在PC性能越來越好的今天，對于幾千字節(jié)的數據進行一次幾百位密鑰的RSA加密，所消耗的時間應該是可以接受的。下面結合大數運算程序的調試，從理論上簡單的分析消耗時間。在一臺普通配置的PC機上對一個整數進行冪模運算，因為公開密鑰的e通常取的較小，所以指數取一個小整數，比如C353，模一個70字節(jié)長的整數(140位十六進制，大數單元以線性組方式實現，對應到RSA算法中，這相當于約560bit的n)，調試一個

22、函數測試，按初等數論中的知識對程序進行算法優(yōu)化，最終在一臺配置為AMD Athron2800+，外頻333MHZ，物理內存512MB的PC上測試需要約45毫秒時間。如果按這種速度，逐字節(jié)對1KB的數據進行同樣的運算，所消耗的時間理論上為45毫秒的1024倍即約45秒。這個時間并不是非常長。　　其實從一個簡單的角度來說，既然RSA用于數字簽名可行，那就完全可以用于同樣大小的普通文件。對于較大的文件

23、，如果分成與數字簽名同樣大小的段(這里假設數字簽名較短，不分段一次計算加密完成)，分開的各段逐一進行加密運算，那所需要的時間也只是按文件大小線性的增長。通常數字簽名為幾十字節(jié)，加密運算并不需要很長的等待，這就說明對于幾百字節(jié)或一兩K字節(jié)大小的文件來說，如果進行RSA加密，并不會是非常漫長的工作。當然，如果文件更大，加密就顯得十分漫長了。比如按前面敘述的45毫秒大數運算程序推理，加密1M字節(jié)大小的文件需要約1天的時間。所以，要在普通PC用

24、幾百位以上的長密鑰RSA加密文件，文件不能過大，一般可以接受的上限是幾KB。如果要在較短時間內加密大文件，需要縮短密鑰長度以減小運算量，這將帶來安全性隱患。　　本文的第3章將根據實際調試好的軟件，測試給出具體的時間消耗數據。例如，在一臺配置為AMD Athron2800+，外頻333MHZ，物理內存512MB的PC上測試實現的軟件，以560bit的n逐字節(jié)加密一個1KB大小的文件需要55秒。通常

25、記錄如銀行帳號密碼等重要數據的文本文件大小不足百字節(jié)，加密只需要數秒鐘。所以對于小型文件，進行較長密鑰的RSA加密是完全可行的。　　1.3.2 文件加密使用RSA的意義　　如1.3.1節(jié)所述，小型文件加密可以使用RSA。比如，因擔心遺忘而用普通文本記錄的銀行帳號和密碼、不應被陌生人知道的重要電話號碼、幾千字節(jié)大的重要小圖片等。可行的方法未必是必要的，本小

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

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

28、的問題。只要大家都在這臺計算機或這臺計算機可以訪問到的地方，留下自己的公開密鑰，一切就變的容易解決了。張三要留給李四的文件，就用李四的公開密鑰加密，要留給王五的文件，就用王五的公開密鑰加密。李四和王五只要把留給自己的文件用自己的私　　綜上所述，使用前面敘述的方式加密文件有兩點重要意義：①應用非對稱密鑰加密任意文件，使非對稱密鑰的應用不僅僅局限于互聯網絡。②非對稱加密后的數據變換成文本，使得我們可

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

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

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

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

33、功能不斷擴充，任意一個層面的封裝都可以被直接應用到其他項目，比如在Web使用以前為某窗體程序寫的組件、給嵌入式設備交叉編譯算法庫等。但是每一層都需要依賴底層的所有組件。圖2-2形象的說明了分層設計給復用帶來的好處。　　圖2-2 綜合考慮復用性、可維護性和執(zhí)行效率的分層設計　　選用這種設計方案，上層使用C#，底層算法使用C++，可以由一個Visual St

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

35、p>　　2.2 各部分的設計與開發(fā)　　2.2.1 實現RSA加密算法的C++核心類庫　　1. 大數存儲和四則運算　　根據RSA算法的要求，為了實現大數的各種復雜運算，需要首先實現大數存儲和基本四則運算的功能。當今開源的大數運算C++類有很多，多用于數學分析、天文計算等，本文選用了一個流行的大數類型，并針對R

36、SA算法和本項目的具體需要對其進行了擴充和改進。下面簡單介紹大數存儲和四則運算的實現原理。　　最先完成的功能是大數的存儲，存儲功能由flex_unit類提供。和普通的類型一樣，每一個大數對應一個flex_unit的實例。類flex_unit中，用一個無符號整數指針unsigned * a指向一塊內存空間的首地址，這塊內存空間用來存儲一個大數，所以可以說，大數是被存儲在一個以unsigned為單元

37、的線性組中。在方法void reserve( unsigned x )中通過C++的new來給a開辟空間，當flex_unit的實例中被存入比當前存儲的數更大的數時，就會調用reserve來增加存儲空間，但是當flex_unit的實例中被存入比當前存儲的數更小的數時，存儲空間并不會自動緊縮，這是為了在運算的時候提高執(zhí)行效率。結合指針a，有兩個重要的無符號整數來控制存儲，unsigned z和unsigned n，z是被分配空間的單元數，

38、隨數字變大不斷增大，不會自己緊縮，而n是當前存儲的大數所占的單元數，組成一個大數的各unsigned單元的存入和讀出由set、get方法完成，變量n是只讀的。類型unsigned在32位機是32位的，所以對于flex_unit這個大數類來說，每個大數最大可　　圖2-3 flex_unit對大數的管理　　在flex_unit的存儲功能基礎上，將其派生，得到

39、vlong_value，在vlong_value中實現四則運算函數，并實現強制轉換運算符unsigned，以方便大數類型和普通整數的互相賦值。當大數被強制轉換為unsigned時，將取其最低四字節(jié)的值。四則運算實現的原理十分簡單，都是按最基本的算術原理實現的，四則運算過程的本質就是按一定數制對數字的計算，比如相加，就是低位單元對齊，逐單元相加并進位，減法同理。而乘除法和取余也都是按照豎式運算的原理實現，并進行了必要的優(yōu)化。雖然實現了四則

40、運算函數，但是若是程序里的運算都要調用函數，顯得煩瑣而且看起來不美觀，所以我們另寫一個類vlong，關聯(Associate，即使用vlong_value類型的對象或其指針作為成員)vlong_value，在vlong重載運算符。這樣，當我們操作vlong大數對象的時候，就可以像使用一個簡單類型一樣使用各種運算符號了。之所以將vlong_value的指針作為成員而不是直接構造的對象，也是為了提高執(zhí)行效率，因為大型對象的拷貝要消耗不少機器

41、時間。　　2. 大數冪模與乘模運算?Montgomery冪模算法　　在實現了vlong類型后，大數的存儲和四則運算的功能都完成了?？紤]到RSA算法需要進行冪模運算，需要準備實現這些運算的方法。所以寫一個vlong的友元，完成冪模運算功能。冪模運算是RSA 算法中比重最大的計算，最直接地決定了RSA 算法的性能，針對快速冪模運算這一課題，西方現代數學家提出

42、了很多的解決方案。經查閱相關數學著作，發(fā)現通常都是依據乘模的性質，先將冪模運算化簡為乘模運算。　　通常的分解習慣是指數不斷的對半分，如果指數是奇數，就先減去一變成偶數，然后再對半分，例如求D=，E=15，可分解為如下6個乘模運算。　　歸納分析以上方法，對于任意指數E，可采用如圖2-4的算法流程計算。　　圖2-4

43、冪模運算分解為乘模運算的一種流程　　按照上述流程，列舉兩個簡單的冪模運算實例來形象的說明這種方法。　?、偾蟮闹?lt;/b>　　開始D = 1P = 2 mod 17 = 2E = 15　　E奇數D = DP mod n

44、= 2P = PP mod n = 4E= (E-1)/2 =7　　E奇數D = DP mod n = 8P = PP mod n = 16E= (E-1)/2 =3　　E奇數D = DP mod n = 9P = PP mod n = 1E= (E-1)/2 =1　　E奇數D =

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

46、P = PP mod n = 4E = E/2 =4　　E偶數D = 1P = PP mod n = 3E = E/2 =2　　E偶數D = 1P = PP mod n = 9E = E/2 =1　　E奇數D = DP mod n = 9P = 不需要計算E

47、 = (E-1)/2 =0　　最終D = 9 即為所求。　　觀察上述算法，發(fā)現E根據奇偶除以二或減一除以二實際就是二進制的移位操作，所以要知道需要如何乘模變量，并不需要反復對E 進行除以二或減一除以二的操作，只需要驗證E 的二進制各位是0 還是1 就可以了。同樣是計算，下面給出從右到左掃描二進制位進行的冪模算法描述，設中間變量D,P,E的二進制各位下標從

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

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

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

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

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

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

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

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

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

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

58、(E的當前二進制位Ei==1)D=M(D*P); //從低位到高位檢測二進制位　　i+=1;　　if(i==E的二進制位數)break;　　P=M(P*P);　　}</b&

59、gt;　　return D*R-1 (mod n);　　}　　在具體的實現中，對應monty類的mul和exp方法。全局函數modexp初始化monty對象并調用其exp方法，使用的時候直接調用modexp即可。　　3. 尋找素數?E

60、ratosthenes篩選與Fermat素數測試　　首先要說明的是，事實上，當今的計算機還不足以聰明到立刻計算生成一個很大的隨機素數。一般來說，要得到100%準確的大素數，都是通過查已經計算好的素數表的方式。但是素數表的方式給RSA的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所使用的素數表，攻破RSA加密的難度將會大大降低。本程序起初使用素數表的方式，后來考慮到安全性問題，生成密鑰的方式改為

61、隨機計算生成。這樣，短時間內如果要得到一個100%準確的大素數是很困難的，只能以盡可能高的概率得到一個大素數。　　經過2.2.1.1和2.2.1.2小節(jié)，所有的大數運算功能都準備完畢，在此基礎上，本工程將尋找素數的功能置于類Prime_factory_san之中。外部只要調用本類實例的成員vlong find_prime( vlong & start )就可以以大數start為起點，得到

62、一個數，這個數是素數的概率很大。下面介紹尋找素數的原理。　　首先在需要尋找素數的整數范圍內對整數進行篩選，把所有確知為合數的整數排除出去。程序中構造了一個數組b[]，大小為一輪素數搜索的范圍，記搜索范圍大小為SS。b[0]到b[SS]分別對應大數start到start+SS。b[]中所有元素先初始化為1，如果對應的大數確定為合數，就將b[]中對應的元素置為0。最后，只需對那些b[]中為1的元素對

63、應的大數進行比較確切的素數測試即可，只要被測試的數是素數概率達到一定門限，就判這個數為素數。這樣做既保證了這段程序可以在短時間內執(zhí)行完，又保證了可以以比較高的準確度得到素數。　　函數find_prime先把b[]的所有元素賦值為1，然后按參數start給標記數組b[]的各元素賦0值。下面描述標記數組b[]的賦0值算法。首先，在類Prime_factory_san被構造的時候，構造函數中從2開始搜

64、尋一些小素數，記錄在數組pl[]中，共記錄NP個。這些小素數用來當作因子，他們的倍數將被從大素數搜索范圍內剔除(即把數組b[]的對應元素標記為0)，剔除的程序代碼如下。　　for (i=0;i<np;i++)　　{　　unsigned p = pl[i];</p&

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

66、t;　　r += p;　　}　　}　　這里利用start對各小素數因子p求模的辦法，得到當前p在素數搜索范圍內的最小倍數在b[]中的對應位置，將其剔除后，不斷

67、后移p個位置，將這個小素數因子p在搜索范圍內的所有倍數全部剔除，如圖2-5所示。在完成對所有小素數因子的類似操作后，他們的倍數在搜索范圍內的位置標記b[r]被全部標記為0。實際上這就是Eratosthenes篩選法。　　圖2-5 在素數搜索范圍內剔除小素數因子p的倍數　　接下來，對可能為素數的數(即標記數組b[]中值為1的元素對應的數)進行素數測試。數論

68、學家利用費馬小定理研究出了多種素數測試方法，本程序使用一種最簡單的方式，直接應用費馬小定理。取一個與p互素的整數A，對于大素數p來說應該滿足Ap-1mod p=1，但是我們把p代入一個大整數，滿足這個關系的數不一定是素數。這時我們改變A，進行多次測試，如果多次測試都通過，這個數是素數的概率就比較大。按這種原理，我們編寫素數測試函數如下。　　int is_probable_prime_san( c

69、onst vlong &p )　　{　　const rep = 4; //測試次數　　const unsigned any[rep] = { 2,3,5,7 }; //測試用的底數　　for ( unsigned i=0; i

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

71、lt;b>　　return 1;　　}　　測試通過，程序就判定這個數為找到的素數，將找到的素數返回給上層程序使用。在這里其實有一個不可忽視的問題，就是得到一個測試通過的合數。對于這種情況，RSA算法加密解密是否還可以實現，是一個需要從數學角度論證的問題。因為得到素數的概率很高，經過一整天的生

72、成密鑰和加密操作，沒有發(fā)現失敗的密鑰，所以本文暫沒有對這個問題進行討論。　　實際得到素數的流程：　　先得到一個隨機的大整數N當作尋找的起點．　　確定一個尋找范圍的大小SS，把(N,N+SS)范圍內的小素數倍數去掉，即前面敘述的古希臘某人發(fā)明的篩選法．小素數因子從２開始取，取幾百個(論文中將小素數因子個數記為NP

73、)．　　對范圍內沒有去掉的數逐一進行素數測試，一個數如果通過測試次數達到一定標準，就判為素數．　　如果范圍內沒找到素數，就令N=N+SS，回到(2)繼續(xù)尋找．　　用以上算法，直到以某成功概率得到素數為止　　綜上所述，總結素數尋找的流程，如圖2-6所示。

74、　　圖2-6 函數find_prime尋找素數的流程框圖　　得到了大素數，即RSA算法中的p、q，我們就可以計算出密鑰，進行加密等操作了。　　4. 二元一次不定方程　　在RSA 算法中，往往要在已知A、M的情況下，求B的最小值，使得 (AB) mod M = 1。即相當于求解B、N都是未知數

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

76、>　　（1） 11 x - 49 y = 1 49 mod 11 = 5　?。?） 11 x - 5 y = 1 11 mod 5 = 1　?。?）x - 5 y = 1 5 mod 1 = 0　　逆向代入：

77、　　令y=0 代入（3）得x=1　　令x=1 代入（2）得y=2　　令y=2 代入（1）得x=9　　x=9;y=2即為所求。　　程序中，全局函數vlong modinv( const vlong &a, const vlong &m )

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

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

80、指針操作和sprintf函數來完成。　　需要加密和解密的數據也是通過字符串參數置入的。由于字符串的結尾字符“\0”實際上也可能是需要加密的數據，所以置入的串長度并不能以“\0”來決定，程序里引入一個unsigned類型的參數來決定置入的串長度，這樣就解決了加密連0數據時候被截斷的問題。　　因為是對文件加密的軟件，需要加密的數據通常并不止幾字節(jié)，本軟件默認

81、的分塊大小是1字節(jié)，即逐個字節(jié)作為參數，調用C++核心模塊中的方法。　　加密解密流程均為標準RSA算法，具體過程見下圖：　?、偕擅荑€：　　圖2-7 隨機生成密鑰　　相關代碼：

82、　　public static int GetRandomString()//實現隨機字串的獲得　　{　　Random rnd = new Random();　　Byte[]b=new Byte[System.Math.Max(RSAprimeplen1

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

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

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

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

87、加密的文本　　圖2-9 準備加密文本　　圖2-10加密后生成的文本　　圖2-11加密過程完成　　相關代碼：　　private void menuItem10_Click(object send

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

89、this); 　　em.Show();　　return;　　}　　Stream myStream ;　　SaveFileDialog saveFileDi

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

91、gt;　　saveFileDialog1.RestoreDirectory = true ;　　if(saveFileDialog1.ShowDialog() == DialogResult.OK)　　{　　if((myStream=saveFileDialog1.OpenF

92、ile()) != null)　　{　　textBox1.Text+="\r\n正在對讀入的文件進行處理，請稍候：）\r\n";　　System.Threading.Thread.Sleep(500);　　High

93、ResolutionTimer timer = new HighResolutionTimer(); 　　timer.Start();　　using (StreamWriter sw = new StreamWriter(myStream)) 　　{&

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

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

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

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

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

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

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

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

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

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

104、gt;　　} 　　③解密過程：　　圖2-12 載入加密后生成的文本　　圖2-13解密已加密的文本　　圖2-14 解密生成解密文件&

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

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

107、gt;　　}　　Stream myStream ;　　SaveFileDialog saveFileDialog1 = new SaveFileDialog();　　saveFileDialog1.Filter = "Tex

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

109、og() == DialogResult.OK)　　{　　if((myStream=saveFileDialog1.OpenFile()) != null)　　{　　textBox1.Text+=

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

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

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

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

114、gt;　　}　　progressBar1.Value=i+1;　　}　　}　　myStream.Close();　　timer.Sto

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

116、;　　progressBar1.Value=0;}　　}　　}　　6. 核心類庫綜述　　綜上幾小節(jié)所述，實現RSA加密算法的C++核心

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

118、計模式來說，不應當出現類之外的函數，但是因為這些函數使用頻繁，考慮到機器效率，直接置于全局，不再另行包裝。　　2.2.2 封裝C++核心類庫的DLL組件　　在Visual Studio當前的解決方案中以VC++創(chuàng)建一個win32dll工程，將測試好的實現RSA加密算法的C++核心類庫中的所有文件加入到此工程下，新建一對cpp和h文件，把可能用到的功能全部

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

rsa算法的實現——畢業(yè)論文

文檔簡介

溫馨提示

最新文檔

評論

rsa算法的實現——畢業(yè)論文

文檔簡介

溫馨提示

最新文檔

評論

免費下載