【文章內(nèi)容簡介】 的存儲，存儲功能由flex_unit類提供。和普通的類型一樣，每一個大數(shù)對應(yīng)一個flex_unit的實例。類flex_unit中，用一個無符號整數(shù)指針unsigned * a指向一塊內(nèi)存空間的首地址，這塊內(nèi)存空間用來存儲一個大數(shù)，所以可以說，大數(shù)是被存儲在一個以unsigned為單元的線性組中。在方法void reserve( unsigned x )中通過C++的new來給a開辟空間，當(dāng)flex_unit的實例中被存入比當(dāng)前存儲的數(shù)更大的數(shù)時，就會調(diào)用reserve來增加存儲空間，但是當(dāng)flex_unit的實例中被存入比當(dāng)前存儲的數(shù)更小的數(shù)時，存儲空間并不會自動緊縮，這是為了在運算的時候提高執(zhí)行效率。結(jié)合指針a，有兩個重要的無符號整數(shù)來控制存儲，unsigned z和unsigned n，z是被分配空間的單元數(shù)，隨數(shù)字變大不斷增大，不會自己緊縮，而n是當(dāng)前存儲的大數(shù)所占的單元數(shù)，組成一個大數(shù)的各unsigned單元的存入和讀出由set、get方法完成，變量n是只讀的。類型unsigned在32位機(jī)是32位的，所以對于flex_unit這個大數(shù)類來說，每個大數(shù)最大可以達(dá)到 個字節(jié)長，這已經(jīng)超過了32位機(jī)通常的最大內(nèi)存容量，所以是足夠進(jìn)行RSA所需要的各種運算的。圖32形象的說明了大數(shù)存儲類flex_unit對大數(shù)的管理。 *a unsigned類型的指針大數(shù)占n個單元開辟了z個單元大的內(nèi)存內(nèi)存空間圖32 flex_unit對大數(shù)的管理在flex_unit的存儲功能基礎(chǔ)上，將其派生，得到vlong_value，在vlong_value中實現(xiàn)四則運算函數(shù)，并實現(xiàn)強(qiáng)制轉(zhuǎn)換運算符unsigned，以方便大數(shù)類型和普通整數(shù)的互相賦值。當(dāng)大數(shù)被強(qiáng)制轉(zhuǎn)換為unsigned時，將取其最低四字節(jié)的值。四則運算實現(xiàn)的原理十分簡單，都是按最基本的算術(shù)原理實現(xiàn)的，四則運算過程的本質(zhì)就是按一定數(shù)制對數(shù)字的計算，比如相加，就是低位單元對齊，逐單元相加并進(jìn)位，減法同理。而乘除法和取余也都是按照豎式運算的原理實現(xiàn)，并進(jìn)行了必要的優(yōu)化。雖然實現(xiàn)了四則運算函數(shù)，但是若是程序里的運算都要調(diào)用函數(shù)，顯得煩瑣而且看起來不美觀，所以我們另寫一個類vlong，關(guān)聯(lián)(Associate，即使用vlong_value類型的對象或其指針作為成員)vlong_value，在vlong重載運算符。這樣，當(dāng)我們操作vlong大數(shù)對象的時候，就可以像使用一個簡單類型一樣使用各種運算符號了。之所以將vlong_value的指針作為成員而不是直接構(gòu)造的對象，也是為了提高執(zhí)行效率，因為大型對象的拷貝要消耗不少機(jī)器時間。在實現(xiàn)了vlong類型后，大數(shù)的存儲和四則運算的功能都完成了?？紤]到RSA算法需要進(jìn)行冪模運算，需要準(zhǔn)備實現(xiàn)這些運算的方法。所以寫一個vlong的友元，完成冪模運算功能。冪模運算是RSA 算法中比重最大的計算，最直接地決定了RSA 算法的性能，針對快速冪模運算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了很多的解決方案。經(jīng)查閱相關(guān)數(shù)學(xué)著作，發(fā)現(xiàn)通常都是依據(jù)乘模的性質(zhì)，先將冪模運算化簡為乘模運算。通常的分解習(xí)慣是指數(shù)不斷的對半分，如果指數(shù)是奇數(shù)，就先減去一變成偶數(shù)，然后再對半分，例如求D=，E=15，可分解為如下6個乘模運算。 歸納分析以上方法，對于任意指數(shù)E，可采用如圖33的算法流程計算 。開始D=1。P=C mod nE0?E為奇數(shù)?E=E1E為偶數(shù)?E=E/2YesNoResult=D結(jié)束YesYesNoNo圖33 冪模運算分解為乘模運算的一種流程按照上述流程，列舉兩個簡單的冪模運算實例來形象的說明這種方法。① 求的值開始 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 P = 2 mod 17 = 2 E = 8E偶數(shù) D = 1 P = PP mod n = 4 E = E/2 =4E偶數(shù) D = 1 P = PP mod n = 3 E = E/2 =2E偶數(shù) D = 1 P = PP mod n = 9 E = E/2 =1E奇數(shù) D = DP mod n = 9 P = 不需要計算 E = (E1)/2 =0最終D = 9 即為所求。觀察上述算法，發(fā)現(xiàn)E根據(jù)奇偶除以二或減一除以二實際就是二進(jìn)制的移位操作，所以要知道需要如何乘模變量，并不需要反復(fù)對E 進(jìn)行除以二或減一除以二的操作，只需要驗證E 的二進(jìn)制各位是0 還是1 就可以了。同樣是計算，下面給出從右到左掃描二進(jìn)制位進(jìn)行的冪模算法描述，設(shè)中間變量D,P,E的二進(jìn)制各位下標(biāo)從左到右為u,u1,u2,…,0。Powmod(C,E,n) { D=1。 P=C mod n。 for i=0 to u do { if(Ei=1)D=D*P(mod n)。 　　 P=P*P(mod n)?！　? }　　 return D。}選擇與模數(shù)n互素的基數(shù)R=2k，n滿足2k－1≤n2k， n應(yīng)為奇數(shù)。并且選擇R1及n’，滿足0 R1n, 0 n’n,使得 RR1nn’＝1。對于0≤mRn的任意整數(shù),Montgomery給出求模乘法mR1 mod n 的快速算法M(m):M(m){ if (t≥n) return (tn)。 else return t。}因為，故t為整數(shù)；同時，得。由于，M(m) 中t結(jié)果范圍是0≤t2n，返回時如果t不小于n，應(yīng)返回tn。本軟件程序中，RSA核心運算使用的乘模算法就是 M(A*B)。雖然M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個乘模算法進(jìn)行計算了。本軟件起初未使用Montgomery 乘模算法時，加密速度比使用Montgomery乘模算法慢，但速度相差不到一個數(shù)量級。將上述乘模算法結(jié)合前面敘述的冪模算法，構(gòu)成標(biāo)準(zhǔn)Montgomery冪模算法，即本軟件所使用的流程，敘述如下。M(m){k = ( m * n’ ) mod R。x = (m + k*n ) / R。 if (x=n) x = n。 return x。}exp(C,E,n) { D=Rn。 P=C*R mod n。 i=0。 while(true) { if(E的當(dāng)前二進(jìn)制位Ei==1)D=M(D*P)。 //從低位到高位檢測二進(jìn)制位 i+=1。 if(i==E的二進(jìn)制位數(shù))break。 　　 P=M(P*P)?！　　　 return D*R1 (mod n)。}在具體的實現(xiàn)中，對應(yīng)monty類的mul和exp方法。全局函數(shù)modexp初始化monty對象并調(diào)用其exp方法，使用的時候直接調(diào)用modexp即可。首先在需要尋找素數(shù)的整數(shù)范圍內(nèi)對整數(shù)進(jìn)行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構(gòu)造了一個數(shù)組b[]，大小為一輪素數(shù)搜索的范圍，記搜索范圍大小為SS。b[0]到b[SS]分別對應(yīng)大數(shù)start到start+SS。b[]中所有元素先初始化為1，如果對應(yīng)的大數(shù)確定為合數(shù)，就將b[]中對應(yīng)的元素置為0。最后，只需對那些b[]中為1的元素對應(yīng)的大數(shù)進(jìn)行比較確切的素數(shù)測試即可，只要被測試的數(shù)是素數(shù)概率達(dá)到一定門限，就判這個數(shù)為素數(shù)。這樣做既保證了這段程序可以在短時間內(nèi)執(zhí)行完，又保證了可以以比較高的準(zhǔn)確度得到素數(shù)。函數(shù)find_prime先把b[]的所有元素賦值為1，然后按參數(shù)start給標(biāo)記數(shù)組b[]的各元素賦0值。下面描述標(biāo)記數(shù)組b[]的賦0值算法。首先，在類Prime_factory_san被構(gòu)造的時候，構(gòu)造函數(shù)中從2開始搜尋一些小素數(shù)，記錄在數(shù)組pl[]中，共記錄NP個。這些小素數(shù)用來當(dāng)作因子，他們的倍數(shù)將被從大素數(shù)搜索范圍內(nèi)剔除(即把數(shù)組b[]的對應(yīng)元素標(biāo)記為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求模的辦法，得到當(dāng)前p在素數(shù)搜索范圍內(nèi)的最小倍數(shù)在b[]中的對應(yīng)位置，將其剔除后，不斷后移p個位置，將這個小素數(shù)因子p在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖34所示。在完成對所有小素數(shù)因子的類似操作后，他們的倍數(shù)在搜索范圍內(nèi)的位置標(biāo)記b[r]被全部標(biāo)記為0。實際上這就是Eratosthenes篩選法。數(shù)軸素數(shù)搜索范圍start到start+SS小素數(shù)因子p搜索起點start 對應(yīng)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中對應(yīng)元素標(biāo)記為0設(shè)在剛執(zhí)行到while時r0 x=r圖34 在素數(shù)搜索范圍內(nèi)剔除小素數(shù)因子p的倍數(shù)接下來，對可能為素數(shù)的數(shù)(即標(biāo)記數(shù)組b[]中值為1的元素對應(yīng)的數(shù))進(jìn)行素數(shù)測試。取一個與p互素的整數(shù)A，對于大素數(shù)p來說應(yīng)該滿足Ap1mod p=1，但是我們把p代入一個大整數(shù)，滿足這個關(guān)系的數(shù)不一定是素數(shù)。這時我們改變A，進(jìn)行多次測試，如果多次測試都通過，這個數(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ù)學(xué)角度論證的問題。因為得到素數(shù)的概率很高，經(jīng)過一整天的生成密鑰和加密操作，沒有發(fā)現(xiàn)失敗的密鑰， 所以本文暫沒有對這個問題進(jìn)行討論。綜上所述，總結(jié)素數(shù)尋找的流程，如圖35所示。 開始按start參數(shù)初始化標(biāo)記數(shù)組b[SS] 。 i=0計數(shù)iSS?b[i]==1?判定為素數(shù)?start+=1。i+=1結(jié)束返回素數(shù)尋找結(jié)果startYesYesYesNoNoNo圖35 函數(shù)find_prime尋找素數(shù)的流程框圖得到了大素數(shù)，即RSA算法中的p、q，我們就可以計算出密鑰，進(jìn)行加密等操作了。最后，類RSA_san基于前面的準(zhǔn)備工作，實現(xiàn)RSA密鑰生成和加解密的功能為了方便閱讀，整個類的源程序中，所使用的變量字母均和RSA算法協(xié)議中一致。在類RSA_san的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對隨機(jī)密鑰的操作。之后可以直接使用類的其他成員進(jìn)行RSA加解密操作，也可以載入以前保存的密鑰或再次隨機(jī)生成密鑰。類中各成員頻繁的用到字符串和vlong類型的轉(zhuǎn)換，因為大數(shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。所以，需要實現(xiàn)一系列的編碼轉(zhuǎn)換函數(shù)，比如將unsigned指針指向的一段空間里保存的一個大數(shù)，表示成十六進(jìn)制形式的字符串文本。編碼轉(zhuǎn)換通常是用C風(fēng)格的指針操作和sprintf函數(shù)來完成。需要加密和解密的數(shù)據(jù)也是通過字符串參數(shù)置入的。由于字符串的結(jié)尾字符“\0”實際上也可能