【文章內容簡介】 數(shù)，用普通的除法求模而進行乘模運算是不能滿足速度的要求的。為此，Montgomery在1983年提出了一種模加右移的乘模算法（主要著作發(fā)表于1985年），從而避免了通常求模算法中費時的除法步驟。本軟件僅僅是應用Montgomery(蒙哥馬利)算法，算法的具體推導證明需要頗多數(shù)論知識，不在本文的討論范圍內，如需了解可參見蒙哥馬利的相關著作。下面簡單描述RSA中常用的Montgomery(蒙哥馬利)算法供參考理解源程序。選擇與模數(shù)n互素的基數(shù)R=2k，n滿足2k－1≤n2k， n應為奇數(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結果范圍是0≤t2n，返回時如果t不小于n，應返回tn。本軟件程序中，RSA核心運算使用的乘模算法就是 M(A*B)。雖然M(A*B)并不是乘模所需要的真正結果，但只要在冪模算法中進行相應的修改，就可以調用這個乘模算法進行計算了。將上述乘模算法結合前面敘述的冪模算法，構成標準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的當前二進制位Ei==1)D=M(D*P)。 //從低位到高位檢測二進制位 i+=1。 if(i==E的二進制位數(shù))break。 　　 P=M(P*P)?！　　　 return D*R1 (mod n)。}在具體的實現(xiàn)中，對應monty類的mul和exp方法。全局函數(shù)modexp初始化monty對象并調用其exp方法，使用的時候直接調用modexp即可。3. 尋找素數(shù)?Eratosthenes篩選與Fermat素數(shù)測試首先要說明的是，事實上，當今的計算機還不足以聰明到立刻計算生成一個很大的隨機素數(shù)。一般來說，要得到100%準確的大素數(shù)，都是通過查已經(jīng)計算好的素數(shù)表的方式。但是素數(shù)表的方式給RSA的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所使用的素數(shù)表，攻破RSA加密的難度將會大大降低。本程序起初使用素數(shù)表的方式，后來考慮到安全性問題，生成密鑰的方式改為隨機計算生成。這樣，短時間內如果要得到一個100%準確的大素數(shù)是很困難的，只能以盡可能高的概率得到一個大素數(shù)。，所有的大數(shù)運算功能都準備完畢，在此基礎上，本工程將尋找素數(shù)的功能置于類Prime_factory_san之中。外部只要調用本類實例的成員vlong find_prime( vlong amp。 start )就可以以大數(shù)start為起點，得到一個數(shù)，這個數(shù)是素數(shù)的概率很大。下面介紹尋找素數(shù)的原理。首先在需要尋找素數(shù)的整數(shù)范圍內對整數(shù)進行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構造了一個數(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ù)。這樣做既保證了這段程序可以在短時間內執(zhí)行完，又保證了可以以比較高的準確度得到素數(shù)。函數(shù)find_prime先把b[]的所有元素賦值為1，然后按參數(shù)start給標記數(shù)組b[]的各元素賦0值。下面描述標記數(shù)組b[]的賦0值算法。首先，在類Prime_factory_san被構造的時候，構造函數(shù)中從2開始搜尋一些小素數(shù)，記錄在數(shù)組pl[]中，共記錄NP個。這些小素數(shù)用來當作因子，他們的倍數(shù)將被從大素數(shù)搜索范圍內剔除(即把數(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ù)搜索范圍內的最小倍數(shù)在b[]中的對應位置，將其剔除后，不斷后移p個位置，將這個小素數(shù)因子p在搜索范圍內的所有倍數(shù)全部剔除，如圖25所示。在完成對所有小素數(shù)因子的類似操作后，他們的倍數(shù)在搜索范圍內的位置標記b[r]被全部標記為0。實際上這就是Eratosthenes篩選法。接下來，對可能為素數(shù)的數(shù)(即標記數(shù)組b[]中值為1的元素對應的數(shù))進行素數(shù)測試。數(shù)論學家利用費馬小定理研究出了多種素數(shù)測試方法，本程序使用一種最簡單的方式，直接應用費馬小定理。取一個與p互素的整數(shù)A，對于大素數(shù)p來說應該滿足Ap1mod p=1，但是我們把p代入一個大整數(shù)，滿足這個關系的數(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)失敗的密鑰， 所以本文暫沒有對這個問題進行討論。實際得到素數(shù)的流程：(1) 先得到一個隨機的大整數(shù)N當作尋找的起點．(2) 確定一個尋找范圍的大小SS，把(N,N+SS)范圍內的小素數(shù)倍數(shù)去掉，即前面敘述的古希臘某人發(fā)明的篩選法．小素數(shù)因子從２開始取，取幾百個(論文中將小素數(shù)因子個數(shù)記為NP)．(3) 對范圍內沒有去掉的數(shù)逐一進行素數(shù)測試，一個數(shù)如果通過測試次數(shù)達到一定標準，就判為素數(shù)．(4) 如果范圍內沒找到素數(shù)，就令N=N+SS，回到(2)繼續(xù)尋找．用以上算法，直到以某成功概率得到素數(shù)為止綜上所述，總結素數(shù)尋找的流程，如圖26所示。 開始按start參數(shù)初始化標記數(shù)組b[SS] 。 i=0計數(shù)iSS?b[i]==1?判定為素數(shù)?start+=1。i+=1結束返回素數(shù)尋找結果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ù)解，古今中外都進行過詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉相除法，中國有秦九韶的“大衍求一術”。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說明用歐幾里德算法求解二元一次不定方程的最小整數(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 )用來完成這種算法。對應前