【正文】 直接由Visual Studio的所見即所得的方式完成，不需要編碼實(shí)現(xiàn)。類中接口DLL的函數(shù)都以靜態(tài)成員的方式對外公開。C接口的DLL組件可以被諸如VB、Delphi等開發(fā)環(huán)境方便的引用。其他接口函數(shù)的使用見DLL接口文檔。由于核心類庫的對外功能都使由RSA_san類提供的，所以在新cpp文件中全局的聲明一個(gè)RSA_san類的對象指針(RSA_san *WRSA)，全局函數(shù)int start_RSA_san()初始化*WRSA對象，在初始化成功后，其他全局函數(shù)通過調(diào)用*WRSA對象的公開方法實(shí)現(xiàn)各種功能，如加密、讀取密鑰等。按常規(guī)設(shè)計(jì)模式來說，不應(yīng)當(dāng)出現(xiàn)類之外的函數(shù)，但是因?yàn)檫@些函數(shù)使用頻繁，考慮到機(jī)器效率，直接置于全局，不再另行包裝。class RSA_san在前5個(gè)類的基礎(chǔ)上，實(shí)現(xiàn)RSA核心算法的類。class monty為RSA準(zhǔn)備大數(shù)求冪模運(yùn)算的函數(shù)，vlong的友元。class vlong_value是flex_unit的派生類，在靈活大數(shù)存儲的基礎(chǔ)上實(shí)現(xiàn)四則運(yùn)算函數(shù)。各個(gè)類之間的關(guān)系如圖27所示。加密解密流程均為標(biāo)準(zhǔn)RSA算法，具體過程和使用方法參見源程序和接口文檔。因?yàn)槭菍ξ募用艿能浖枰用艿臄?shù)據(jù)通常并不止幾字節(jié)，這時(shí)由上層程序?qū)?shù)據(jù)按用戶的設(shè)置分塊，分別加密或解密。需要加密和解密的數(shù)據(jù)也是通過字符串參數(shù)置入的。所以，需要實(shí)現(xiàn)一系列的編碼轉(zhuǎn)換函數(shù)，比如將unsigned指針指向的一段空間里保存的一個(gè)大數(shù)，表示成十六進(jìn)制形式的字符串文本。之后可以直接使用類的其他成員進(jìn)行RSA加解密操作，也可以載入以前保存的密鑰或再次隨機(jī)生成密鑰。為了方便閱讀，整個(gè)類的源程序中，所使用的變量字母均和RSA算法協(xié)議中一致。對應(yīng)前面的敘述，參數(shù)a對應(yīng)A，參數(shù)m對應(yīng)M，函數(shù)返回值即為B的最小值。a, const vlong amp。y=2即為所求。下面舉例說明用歐幾里德算法求解二元一次不定方程的最小整數(shù)解。而針對不定方程axby=1 的最小整數(shù)解，古今中外都進(jìn)行過詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。4. 二元一次不定方程在RSA 算法中，往往要在已知A、M的情況下，求B的最小值，使得 (AB) mod M = 1。 i=0計(jì)數(shù)iSS?b[i]==1?判定為素?cái)?shù)?start+=1。綜上所述，總結(jié)素?cái)?shù)尋找的流程，如圖26所示。對于這種情況，RSA算法加密解密是否還可以實(shí)現(xiàn)，是一個(gè)需要從數(shù)學(xué)角度論證的問題。}測試通過，程序就判定這個(gè)數(shù)為找到的素?cái)?shù)，將找到的素?cái)?shù)返回給上層程序使用。//這里modexp計(jì)算any[i]p1mod p。 i+=1 )if ( modexp( any[i], pvlong(1), p ) != vlong(1) ) return 0。 //測試用的底數(shù) for ( unsigned i=0。p ){ const rep = 4。按這種原理，我們編寫素?cái)?shù)測試函數(shù)如下。取一個(gè)與p互素的整數(shù)A，對于大素?cái)?shù)p來說應(yīng)該滿足Ap1mod p=1，但是我們把p代入一個(gè)大整數(shù)，滿足這個(gè)關(guān)系的數(shù)不一定是素?cái)?shù)。 b中對應(yīng)元素標(biāo)記為0設(shè)在剛執(zhí)行到while時(shí)r0 x=r圖25 在素?cái)?shù)搜索范圍內(nèi)剔除小素?cái)?shù)因子p的倍數(shù)接下來，對可能為素?cái)?shù)的數(shù)(即標(biāo)記數(shù)組b[]中值為1的元素對應(yīng)的數(shù))進(jìn)行素?cái)?shù)測試。實(shí)際上這就是Eratosthenes篩選法。 } }這里利用start對各小素?cái)?shù)因子p求模的辦法，得到當(dāng)前p在素?cái)?shù)搜索范圍內(nèi)的最小倍數(shù)在b[]中的對應(yīng)位置，將其剔除后，不斷后移p個(gè)位置，將這個(gè)小素?cái)?shù)因子p在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖25所示。 while ( r SS ) { b[r] = 0。 unsigned r = start % vlong(p)。inp。這些小素?cái)?shù)用來當(dāng)作因子，他們的倍數(shù)將被從大素?cái)?shù)搜索范圍內(nèi)剔除(即把數(shù)組b[]的對應(yīng)元素標(biāo)記為0)，剔除的程序代碼如下。下面描述標(biāo)記數(shù)組b[]的賦0值算法。這樣做既保證了這段程序可以在短時(shí)間內(nèi)執(zhí)行完，又保證了可以以比較高的準(zhǔn)確度得到素?cái)?shù)。b[]中所有元素先初始化為1，如果對應(yīng)的大數(shù)確定為合數(shù)，就將b[]中對應(yīng)的元素置為0。程序中構(gòu)造了一個(gè)數(shù)組b[]，大小為一輪素?cái)?shù)搜索的范圍，記搜索范圍大小為SS。下面介紹尋找素?cái)?shù)的原理。外部只要調(diào)用本類實(shí)例的成員vlong find_prime( vlong amp。這樣，短時(shí)間內(nèi)如果要得到一個(gè)100%準(zhǔn)確的大素?cái)?shù)是很困難的，只能以盡可能高的概率得到一個(gè)大素?cái)?shù)。但是素?cái)?shù)表的方式給RSA的安全性帶來隱患，因?yàn)楣粽呷绻玫搅嗣荑€生成時(shí)所使用的素?cái)?shù)表，攻破RSA加密的難度將會大大降低。3. 尋找素?cái)?shù)?Eratosthenes篩選與Fermat素?cái)?shù)測試首先要說明的是，事實(shí)上，當(dāng)今的計(jì)算機(jī)還不足以聰明到立刻計(jì)算生成一個(gè)很大的隨機(jī)素?cái)?shù)。}在具體的實(shí)現(xiàn)中，對應(yīng)monty類的mul和exp方法。 　　 P=M(P*P)。 if(i==E的二進(jìn)制位數(shù))break。 if(E的當(dāng)前二進(jìn)制位Ei==1)D=M(D*P)。 while(true) P=C*R mod n。 return x。x = (m + k*n ) / R。將上述乘模算法結(jié)合前面敘述的冪模算法，構(gòu)成標(biāo)準(zhǔn)Montgomery冪模算法，即本軟件所使用的流程，敘述如下。雖然M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個(gè)乘模算法進(jìn)行計(jì)算了。由于，M(m) 中t結(jié)果范圍是0≤t2n，返回時(shí)如果t不小于n，應(yīng)返回tn。 else return t。并且選擇R1及n’，滿足0 R1n, 0 n’n,使得 RR1nn’＝1。下面簡單描述RSA中常用的Montgomery(蒙哥馬利)算法供參考理解源程序。為此，Montgomery在1983年提出了一種模加右移的乘模算法（主要著作發(fā)表于1985年），從而避免了通常求模算法中費(fèi)時(shí)的除法步驟。提高乘模運(yùn)算的速度是提高模冪運(yùn)算速度的關(guān)鍵。在本軟件的代碼中采用直接掃描vlong二進(jìn)制各位的辦法?！　? }　　 return D。 for i=0 to u do { if(Ei=1)D=D*P(mod n)。Powmod(C,E,n) { D=1。觀察上述算法，發(fā)現(xiàn)E根據(jù)奇偶除以二或減一除以二實(shí)際就是二進(jìn)制的移位操作，所以要知道需要如何乘模變量，并不需要反復(fù)對E 進(jìn)行除以二或減一除以二的操作，只需要驗(yàn)證E 的二進(jìn)制各位是0 還是1 就可以了。① 求的值開始 D = 1 P = 2 mod 17 = 2 E = 15E奇數(shù) D = DP mod n = 2 P = PP mod n = 4 E = (E1)/2 =7E奇數(shù) D = DP mod n = 8 P = PP mod n = 16 E = (E1)/2 =3E奇數(shù) D = DP mod n = 9 P = PP mod n = 1 E = (E1)/2 =1E奇數(shù) D = DP mod n = 9 P = PP mod n = 1 E = (E1)/2 =0最終D = 9 即為所求。開始D=1。通常的分解習(xí)慣是指數(shù)不斷的對半分，如果指數(shù)是奇數(shù)，就先減去一變成偶數(shù)，然后再對半分，例如求D=，E=15，可分解為如下6個(gè)乘模運(yùn)算。冪模運(yùn)算是RSA 算法中比重最大的計(jì)算，最直接地決定了RSA 算法的性能，針對快速冪模運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了很多的解決方案。考慮到RSA算法需要進(jìn)行冪模運(yùn)算，需要準(zhǔn)備實(shí)現(xiàn)這些運(yùn)算的方法。之所以將vlong_value的指針作為成員而不是直接構(gòu)造的對象，也是為了提高執(zhí)行效率，因?yàn)榇笮蛯ο蟮目截愐牟簧贆C(jī)器時(shí)間。雖然實(shí)現(xiàn)了四則運(yùn)算函數(shù)，但是若是程序里的運(yùn)算都要調(diào)用函數(shù)，顯得煩瑣而且看起來不美觀，所以我們另寫一個(gè)類vlong，關(guān)聯(lián)(Associate，即使用vlong_value類型的對象或其指針作為成員)vlong_value，在vlong重載運(yùn)算符。四則運(yùn)算實(shí)現(xiàn)的原理十分簡單，都是按最基本的算術(shù)原理實(shí)現(xiàn)的，四則運(yùn)算過程的本質(zhì)就是按一定數(shù)制對數(shù)字的計(jì)算，比如相加，就是低位單元對齊，逐單元相加并進(jìn)位，減法同理。 *a unsigned類型的指針大數(shù)占n個(gè)單元開辟了z個(gè)單元大的內(nèi)存內(nèi)存空間圖23 flex_unit對大數(shù)的管理在flex_unit的存儲功能基礎(chǔ)上，將其派生，得到vlong_value，在vlong_value中實(shí)現(xiàn)四則運(yùn)算函數(shù)，并實(shí)現(xiàn)強(qiáng)制轉(zhuǎn)換運(yùn)算符unsigned，以方便大數(shù)類型和普通整數(shù)的互相賦值。類型unsigned在32位機(jī)是32位的，所以對于flex_unit這個(gè)大數(shù)類來說，每個(gè)大數(shù)最大可以達(dá)到 個(gè)字節(jié)長，這已經(jīng)超過了32位機(jī)通常的最大內(nèi)存容量，所以是足夠進(jìn)行RSA所需要的各種運(yùn)算的。在方法void reserve( unsigned x )中通過C++的new來給a開辟空間，當(dāng)flex_unit的實(shí)例中被存入比當(dāng)前存儲的數(shù)更大的數(shù)時(shí)，就會調(diào)用reserve來增加存儲空間，但是當(dāng)flex_unit的實(shí)例中被存入比當(dāng)前存儲的數(shù)更小的數(shù)時(shí)，存儲空間并不會自動(dòng)緊縮，這是為了在運(yùn)算的時(shí)候提高執(zhí)行效率。和普通的類型一樣，每一個(gè)大數(shù)對應(yīng)一個(gè)flex_unit的實(shí)例。下面簡單介紹大數(shù)存儲和四則運(yùn)算的實(shí)現(xiàn)原理。 各部分的設(shè)計(jì)與開發(fā) 實(shí)現(xiàn)RSA加密算法的C++核心類庫1. 大數(shù)存儲和四則運(yùn)算根據(jù)RSA算法的要求，為了實(shí)現(xiàn)大數(shù)的各種復(fù)雜運(yùn)算，需要首先實(shí)現(xiàn)大數(shù)存儲和基本四則運(yùn)算的功能。整個(gè)工程分四層，實(shí)現(xiàn)RSA加密算法的C++核心類庫、封裝C++核心類庫的DLL組件、。圖22形象的說明了分層設(shè)計(jì)給復(fù)用帶來的好處。這種開發(fā)方式，核心功能集中在最底層，在不斷的封裝中針對具體環(huán)境對組件功能不斷擴(kuò)充，任意一個(gè)層面的封裝都可以被直接應(yīng)用到其他項(xiàng)目，比如在Web使用以前為某窗體程序?qū)懙慕M件、給嵌入式設(shè)備交叉編譯算法庫等。核心的RSA算法由C++類庫實(shí)現(xiàn)，針對用戶所在的操作系統(tǒng)封裝成本地化組件。這種開發(fā)方式比起前兩種，缺點(diǎn)就是設(shè)計(jì)開發(fā)模式陳舊，代碼煩瑣，不方便維護(hù)；。但是對于非PC設(shè)備，只能方便的移植到運(yùn)行Windows嵌入式操作系統(tǒng)的設(shè)備，向其他操作系統(tǒng)移植困難，需要重新編寫大量代碼。其他各功能的設(shè)計(jì)開發(fā)，如文件操作、數(shù)據(jù)編碼轉(zhuǎn)換和圖形界面等，可以使用ATL、MFC或Windows API實(shí)現(xiàn)。 Framework的環(huán)境運(yùn)行，在Windows操作系統(tǒng)，.Net Framework的機(jī)器效率好于java平臺，但是相比于本地化的代碼，還是十分拖沓的。但是缺點(diǎn)也很明顯，如果想把核心算法和功能應(yīng)用到非PC設(shè)備(例如嵌入式手持設(shè)備)，則要求設(shè)備上有支持前面提及的加密類庫的CVM；對于在PC上運(yùn)行，JVM的數(shù)據(jù)運(yùn)算速度要遠(yuǎn)遠(yuǎn)落后于本地化代碼在PC上的運(yùn)算速度，本軟件需要進(jìn)行大量運(yùn)算，這一點(diǎn)不適合由java完成。因?yàn)橛袕?qiáng)大的標(biāo)準(zhǔn)庫支持，文件的讀取和保存操作、各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換、圖形操作界面的實(shí)現(xiàn)也很簡單( 等包)，如果結(jié)合一種快速開發(fā)的IDE，比如JBuilder，整個(gè)軟件可以在很短的時(shí)間內(nèi)編碼完成。1. 整個(gè)工程使用java平臺實(shí)現(xiàn)RSA密鑰生成、RSA加密解密的功能實(shí)現(xiàn)十分簡單，因?yàn)闃?biāo)準(zhǔn)庫中集成幾乎所有功能，不需要從RSA算法出發(fā)進(jìn)行編碼。圖21 本項(xiàng)目的 Use Case和Statechart根據(jù)以上分析，一般來說，需要進(jìn)行編碼的程序有 ①RSA密鑰生成 ②RSA加密解密 ③任意文件的讀取和保存操作 ④各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換 ⑤圖形操作界面。④ 可以裝載加密過的文件，并用指定的密鑰解密還原出原文件。② 可以保存密鑰和裝載密鑰，密鑰保存為純文本。②非對稱加密后的數(shù)據(jù)變換成文本，使得我們可以通過幾乎任何方式安全傳遞任意文件，比如在只有的環(huán)境使用xml方式。為了適合前面敘述的在公共BBS與特定的某人交流重要保密信息的情況，加密生成的數(shù)據(jù)應(yīng)該是文本，這樣可以方便復(fù)制粘貼。這樣，我們自己維護(hù)自己的私有密鑰，利用簡單并且公開的方式，可以安全傳送任意小型數(shù)據(jù)，包括一切二進(jìn)制文件。例如，我們可以將任意一個(gè)文件用某人的公開密鑰加密變換成一段可以復(fù)制粘貼的文本，然后粘貼在公眾互聯(lián)網(wǎng)上，對方只需把需要解密的文本復(fù)制保存成一個(gè)文本文件，在本地機(jī)用自己的私有密鑰解密即可。在這種情況下，我們需要使用公開密鑰方式，并自己維護(hù)私有密鑰。②如果發(fā)送郵件，雖然傳送過程是加密的，但是密碼畢竟是由郵件服務(wù)器維護(hù)，所以系統(tǒng)管理員通常也有辦法看到內(nèi)容。這種情況要保證安全，在當(dāng)今互聯(lián)網(wǎng)絡(luò)上是比較棘手的。一種更實(shí)際的情況是，我們想通過Internet上的公眾論壇或郵件發(fā)送重要保密信息給某人。李四和王五只要把留給自己的文件用自己的私有密鑰解密，就可以得到留給自己的文件了。只要大家都在這臺計(jì)算機(jī)或這臺計(jì)算機(jī)可以訪問到的地方，留下自己的公開密鑰，一切就變的容易解決了。如果需要在這臺公共計(jì)算機(jī)上留十個(gè)文件給不同的人，自己就要記和十個(gè)人