【文章內(nèi)容簡介】 　　 P=M(P*P)。　　}　　 return D*R1 (mod n)。}在具體的實現(xiàn)中，對應monty類的mul和exp方法。全局函數(shù)modexp初始化monty對象并調(diào)用其exp方法，使用的時候直接調(diào)用modexp即可。3. 尋找素數(shù)?Eratosthenes篩選與Fermat素數(shù)測試首先要說明的是，事實上，當今的計算機還不足以聰明到立刻計算生成一個很大的隨機素數(shù)。一般來說，要得到100%準確的大素數(shù)，都是通過查已經(jīng)計算好的素數(shù)表的方式。但是素數(shù)表的方式給RSA的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所使用的素數(shù)表，攻破RSA加密的難度將會大大降低。本程序起初使用素數(shù)表的方式，后來考慮到安全性問題，生成密鑰的方式改為隨機計算生成。這樣，短時間內(nèi)如果要得到一個100%準確的大素數(shù)是很困難的，只能以盡可能高的概率得到一個大素數(shù)。，所有的大數(shù)運算功能都準備完畢，在此基礎(chǔ)上，本工程將尋找素數(shù)的功能置于類Prime_factory_san之中。外部只要調(diào)用本類實例的成員vlong find_prime( vlong amp。 start )就可以以大數(shù)start為起點，得到一個數(shù)，這個數(shù)是素數(shù)的概率很大。下面介紹尋找素數(shù)的原理。首先在需要尋找素數(shù)的整數(shù)范圍內(nèi)對整數(shù)進行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構(gòu)造了一個數(shù)組b[]，大小為一輪素數(shù)搜索的范圍，記搜索范圍大小為SS。b[0]到b[SS]分別對應大數(shù)start到start+SS。b[]中所有元素先初始化為1，如果對應的大數(shù)確定為合數(shù)，就將b[]中對應的元素置為0。最后，只需對那些b[]中為1的元素對應的大數(shù)進行比較確切的素數(shù)測試即可，只要被測試的數(shù)是素數(shù)概率達到一定門限，就判這個數(shù)為素數(shù)。這樣做既保證了這段程序可以在短時間內(nèi)執(zhí)行完，又保證了可以以比較高的準確度得到素數(shù)。函數(shù)find_prime先把b[]的所有元素賦值為1，然后按參數(shù)start給標記數(shù)組b[]的各元素賦0值。下面描述標記數(shù)組b[]的賦0值算法。首先，在類Prime_factory_san被構(gòu)造的時候，構(gòu)造函數(shù)中從2開始搜尋一些小素數(shù)，記錄在數(shù)組pl[]中，共記錄NP個。這些小素數(shù)用來當作因子，他們的倍數(shù)將被從大素數(shù)搜索范圍內(nèi)剔除(即把數(shù)組b[]的對應元素標記為0)，剔除的程序代碼如下。 for (i=0。inp。i++) { unsigned p = pl[i]。 unsigned r = start % vlong(p)。 if (r) r = p r。 while ( r SS ) { b[r] = 0。 r += p。 } }這里利用start對各小素數(shù)因子p求模的辦法，得到當前p在素數(shù)搜索范圍內(nèi)的最小倍數(shù)在b[]中的對應位置，將其剔除后，不斷后移p個位置，將這個小素數(shù)因子p在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖25所示。在完成對所有小素數(shù)因子的類似操作后，他們的倍數(shù)在搜索范圍內(nèi)的位置標記b[r]被全部標記為0。實際上這就是Eratosthenes篩選法。數(shù)軸素數(shù)搜索范圍start到start+SS小素數(shù)因子p搜索起點start 對應b[0]距離start：p(start mod p)b[x]b[x+p]b[x+2p]b[x+3p]b[x+4p]b[x+5p]：剔除。 b中對應元素標記為0設(shè)在剛執(zhí)行到while時r0 x=r圖25 在素數(shù)搜索范圍內(nèi)剔除小素數(shù)因子p的倍數(shù)接下來，對可能為素數(shù)的數(shù)(即標記數(shù)組b[]中值為1的元素對應的數(shù))進行素數(shù)測試。數(shù)論學家利用費馬小定理研究出了多種素數(shù)測試方法，本程序使用一種最簡單的方式，直接應用費馬小定理。取一個與p互素的整數(shù)A，對于大素數(shù)p來說應該滿足Ap1mod p=1，但是我們把p代入一個大整數(shù)，滿足這個關(guān)系的數(shù)不一定是素數(shù)。這時我們改變A，進行多次測試，如果多次測試都通過，這個數(shù)是素數(shù)的概率就比較大。按這種原理，我們編寫素數(shù)測試函數(shù)如下。int is_probable_prime_san( const vlong amp。p ){ const rep = 4。 //測試次數(shù) const unsigned any[rep] = { 2,3,5,7 }。 //測試用的底數(shù) for ( unsigned i=0。 irep。 i+=1 )if ( modexp( any[i], pvlong(1), p ) != vlong(1) ) return 0。 //modexp是冪模函數(shù)，按上一小節(jié)敘述的算法編碼。//這里modexp計算any[i]p1mod p。 return 1。}測試通過，程序就判定這個數(shù)為找到的素數(shù)，將找到的素數(shù)返回給上層程序使用。在這里其實有一個不可忽視的問題，就是得到一個測試通過的合數(shù)。對于這種情況，RSA算法加密解密是否還可以實現(xiàn)，是一個需要從數(shù)學角度論證的問題。因為得到素數(shù)的概率很高，經(jīng)過一整天的生成密鑰和加密操作，沒有發(fā)現(xiàn)失敗的密鑰， 所以本文暫沒有對這個問題進行討論。綜上所述，總結(jié)素數(shù)尋找的流程，如圖26所示。 開始按start參數(shù)初始化標記數(shù)組b[SS] 。 i=0計數(shù)iSS?b[i]==1?判定為素數(shù)?start+=1。i+=1結(jié)束返回素數(shù)尋找結(jié)果startYesYesYesNoNoNo圖26 函數(shù)find_prime尋找素數(shù)的流程框圖得到了大素數(shù)，即RSA算法中的p、q，我們就可以計算出密鑰，進行加密等操作了。4. 二元一次不定方程在RSA 算法中，往往要在已知A、M的情況下，求B的最小值，使得 (AB) mod M = 1。即相當于求解B、N都是未知數(shù)的二元一次不定方程 ABMN=1的最小整數(shù)解。而針對不定方程axby=1 的最小整數(shù)解，古今中外都進行過詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說明用歐幾里德算法求解二元一次不定方程的最小整數(shù)解。給定不定方程11x49y=1，求最小的x（1） 11 x 49 y = 1 49 mod 11 = 5（2） 11 x 5 y = 1 11 mod 5 = 1（3） x 5 y = 1 5 mod 1 = 0逆向代入：令y=0 代入（3）得x=1令x=1 代入（2）得y=2令y=2 代入（1）得x=9x=9。y=2即為所求。程序中，全局函數(shù)vlong modinv( const vlong amp。a, const vlong amp。m )用來完成這種算法。對應前面的敘述，參數(shù)a對應A，參數(shù)m對應M，函數(shù)返回值即為B的最小值。5. 按常規(guī)RSA算法實現(xiàn)加密與解密最后，類RSA_san基于前面的準備工作，實現(xiàn)RSA密鑰生成和加解密的功能(算法在此不再贅述，RSA算法協(xié)議見)。為了方便閱讀，整個類的源程序中，所使用的變量字母均和RSA算法協(xié)議中一致。在類RSA_san的構(gòu)造函數(shù)里，執(zhí)行準備一對隨機密鑰的操作。之后可以直接使用類的其他成員進行RSA加解密操作，也可以載入以前保存的密鑰或再次隨機生成密鑰。類中各成員頻繁的用到字符串和vlong類型的轉(zhuǎn)換，因為大數(shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。所以，需要實現(xiàn)一系列的編碼轉(zhuǎn)換函數(shù)，比如將unsigned指針指向的一段空間里保存的一個大數(shù)，表示成十六進制形式的字符串文本。編碼轉(zhuǎn)換通常是用C風格的指針操作和sprintf函數(shù)來完成。需要加密和解密的數(shù)據(jù)也是通過字符串參數(shù)置入的。由于字符串的結(jié)尾字符“\0”實際上也可能是需要加密的數(shù)據(jù)，所以置入的串長度并不能以“\0”來決定，程序里引入一個unsigned類型的參數(shù)來決定置入的串長度，這樣就解決了加密連0數(shù)據(jù)時候被截斷的問題。因為是對文件加密的軟件，需要加密的數(shù)據(jù)通常并不止幾字節(jié)，這時由上層程序?qū)?shù)據(jù)按用戶的設(shè)置分塊，分別加密或解密。本軟件默認的分塊大小是1字節(jié)，即逐個字節(jié)作為參數(shù)，調(diào)用C++核心模塊中的方法。加密解密流程均為標準RSA算法，具體過程和使用方法參見源程序和接口文檔。6. 核心類庫綜述綜上幾小節(jié)所述，實現(xiàn)RSA加密算法的C++核心類庫由六個類組成，類名和對應的功能描述總結(jié)如表21所示。各個類之間的關(guān)系如圖27所示。表21 RSA加密算法的C++類庫中的類class flex_unit大數(shù)運算和存儲最基本的類，主要實現(xiàn)超大整數(shù)的存儲和索引管理。class vlong_value是flex_unit的派生類，在靈活大數(shù)存儲的基礎(chǔ)上實現(xiàn)四則運算函數(shù)。class vlong以vlong_value為基礎(chǔ)(將一個vlong_value指針作成員)，重載運算符。class monty為RSA準備大數(shù)求冪模運算的函數(shù)，vlong的友元。class Prime_factory_san素數(shù)工廠，尋找大素數(shù)的類。class RSA_san在前5個類的基礎(chǔ)上，實現(xiàn)RSA核心算法的類。圖27 C++核心功能類圖另外需要說明的是，程序中有幾個不屬于任何類的全局函數(shù)，比如應用輾轉(zhuǎn)相除法求最大公約數(shù)的函數(shù)gcd、解同余方程的函數(shù)modinv等。按常規(guī)設(shè)計模式來說，不應當出現(xiàn)類之外的函數(shù)，但是因為這些函數(shù)使用頻繁，考慮到機器效率，直接置于全局，不再另行包裝。 封裝C++核心類庫的DLL組件在Visual Studio當前的解決方案中以VC++創(chuàng)建一個win32dll工程，將測試好的實現(xiàn)RSA加密算法的C++核心類庫中的所有文件加入到此工程下，新建一對cpp和h文件，把可能用到的功能全部規(guī)劃為新文件中的全局函數(shù)，并以C接口導出，即__declspec(dllexport)。由于核心類庫的對外功能都使由RSA_san類提供的，所以在新cpp文件中全局的聲明一個RSA_san類的對象指針(RSA_san *WRSA)，全局函數(shù)int start_RSA_san()初始化*WRSA對象，在初始化成功后，其他全局函數(shù)通過調(diào)用*WRSA對象的公開方法實現(xiàn)各種功能，如加密、讀取密鑰等。在關(guān)閉上層引用程序以前，應執(zhí)行int finish_RSA_san()來釋放WRSA，該函數(shù)執(zhí)行delete WRSA的操作。其他接口函數(shù)的使用見DLL接口文檔。另外，DLL組件可以自己在全局函數(shù)中實現(xiàn)一些其他功能，作為對核心類庫功能的補充。C接口的DLL組件可以被諸如VB、Delphi等開發(fā)環(huán)境方便的引用。 在C，使用特性[DllImport()]引用C接口的DLL組件。類中接口DLL的函數(shù)都以靜態(tài)成員的方式對外公開。在類庫中還提供了任意長度隨機串的生成函數(shù)，此函數(shù)用于生成尋找素數(shù)的大數(shù)起點。一般因為文件操作十分簡單，用流輸入輸出的方式包裝完成，程序中將文件操作直接放在菜單項關(guān)聯(lián)的事件處理函數(shù)中。窗體等圖形操作界面直接由Visual Studio的所見即所得的方式完成，不需要編碼實現(xiàn)。最終實現(xiàn)的應用程序，結(jié)構(gòu)如圖28所示。圖28 本軟件的Visual Studio解決方案第3章 軟件整體測試與分析改進 編寫測試各項性能需要的精確計時類，無法勝任軟件性能測試的工作，這里使用Windows API 函數(shù)QueryPerformanceCounter和QueryPerformanceFrequency進行精確計時。功能被封裝在C類HighResolutionTimer中，使用時只需構(gòu)造一個此類的對象，在計時開始的時候調(diào)用其Start方法，計時結(jié)束時調(diào)用其Stop方法，然后訪問其ElapsedTime屬性，就可以得到一個以秒為單位的float型精確的計時值了。API 函數(shù)QueryPerformanceCounter和QueryPerformanceFrequency是靠查詢CPU的高精度計時器來計時的，所以可以輕松的精確到毫秒級計時。附錄中給出了這個類的源代碼。 測試數(shù)據(jù)與分析改進 密鑰生成測試生成密鑰運算最費時的工作是尋找素數(shù)。，尋找素數(shù)是一項頗為復雜的工作，其速度可能受以下變量的影響：RSA加密需要的n的位數(shù)（尋找素數(shù)的整數(shù)起點大小start）、大素數(shù)測試時底數(shù)A的個數(shù)（針對一個整數(shù)的素數(shù)測試次數(shù)）、小素數(shù)因子p的個數(shù)NP、一輪尋找遍歷的整數(shù)個數(shù)SS等。其中最具影響力的因素顯然是RSA加密需要的n的位數(shù)。以下對各變量分別進行測試，暫且忽略操作系統(tǒng)調(diào)度對測試的影響。1. 測試加密使用的n的位數(shù)對耗時的影響即 在固定A、NP、SS等變量的情況下，改變加密位數(shù)n，測試密鑰生成的時間消耗情況。測試時，A取4個值，分別為7，NP取200，SS取1000。測試PC配置為CPU ，下文測試中，未說明PC配置的也都在同一PC完成，不再重復。統(tǒng)計數(shù)據(jù)如表31所示。表中各項對應的全部測試數(shù)據(jù)見，包括兩個作為素數(shù)搜索起點的隨機數(shù)和生成的素數(shù)p、q以及e、d、n。表31 RSA加密模數(shù)n與密鑰生成耗時的關(guān)系加密位數(shù)n (bit)對應的搜索起點字節(jié)數(shù)測試5次獲得隨機密鑰消耗的時間(秒)平均時間消耗(秒)第一次第二次第三次第四次第五次256163842451232640407684889656102464115272128080不同顏色的單元格表示每行中的最大值和最小值這種顏色代表行中最大