【文章內(nèi)容簡(jiǎn)介】 因?yàn)?Rmmn nn m o d39。 ???? ，故 t 為整數(shù)；同時(shí) nmtR mod? ，得 nmRt mod1?? 。由于 RnRnnm ???? ?0 ， M(m) 中 t結(jié)果范圍是 0≤ t2n，返回時(shí)如果 t 不小于 n，應(yīng)返回 tn。 本軟件程序中， RSA 核心運(yùn)算使用的乘模算法就是 M(A*B)。雖然 M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個(gè)乘模算法進(jìn)行計(jì)算了。 將上述乘模算法結(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)。 //從低位到高位檢測(cè)二進(jìn)制位 i+=1。 if(i==E 的 二進(jìn)制位數(shù) )break。 P=M(P*P)。 } return D*R1 (mod n)。 } 在具體的實(shí)現(xiàn)中，對(duì)應(yīng) monty 類的 mul 和 exp 方法。全局函數(shù) modexp 初始化 monty對(duì)象并調(diào)用其 exp 方法，使用的時(shí)候直接調(diào)用 modexp 即可。 3. 尋找素?cái)?shù) ?Eratosthenes 篩選與 Fermat 素?cái)?shù)測(cè)試 首先要說(shuō)明的是，事實(shí)上，當(dāng)今的計(jì)算機(jī)還不足以聰明到立刻計(jì)算生成一個(gè)很大的隨機(jī)素?cái)?shù)。一般來(lái)說(shuō)，要得到 100%準(zhǔn)確的大素?cái)?shù)，都是通過(guò)查已經(jīng)計(jì)算好的素 數(shù)表的方式。但是素?cái)?shù)表的方式給 RSA 的安全性帶來(lái)隱患，因?yàn)楣粽呷绻玫搅嗣荑€生成時(shí)所使用的素?cái)?shù)表，攻破 RSA 加密的難度將會(huì)大大降低。本程序起初使用素?cái)?shù)表的方式，后來(lái)考慮到安全性問(wèn)題，生成密鑰的方式改為隨機(jī)計(jì)算生成。這樣，短時(shí)間內(nèi)如果要得到一個(gè) 100%準(zhǔn)確的大素?cái)?shù)是很困難的，只能以盡可能高的概率得到一個(gè)大素?cái)?shù)。 經(jīng)過(guò) 和 小節(jié)，所有的大數(shù)運(yùn)算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素?cái)?shù)的功能置于類 Prime_factory_san 之中。外部只要調(diào)用本類實(shí)例的成員 vlong find_prime( vlong amp。 start )就可以以大數(shù) start 為起點(diǎn)，得到一個(gè)數(shù)，這個(gè)數(shù)是素?cái)?shù)的概率很大。下面介紹尋找素?cái)?shù)的原理。 首先在需要尋找素?cái)?shù)的整數(shù)范圍內(nèi)對(duì)整數(shù)進(jìn)行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構(gòu)造了一個(gè)數(shù)組 b[]，大小為一輪素?cái)?shù)搜索的范圍，記搜索范圍大小為 SS。 b[0]到 b[SS]分別對(duì)應(yīng)大數(shù) start 到 start+SS。 b[]中所有元素先初始化為 1，如果對(duì)應(yīng)的大數(shù)確定為合數(shù)，就將 b[]中對(duì)應(yīng)的元素置為 0。最后，只需對(duì)那些 b[]中為 1的元素對(duì)應(yīng)的大數(shù)進(jìn)行比較確切的素?cái)?shù)測(cè)試即可，只 要被測(cè)試的數(shù)是素?cái)?shù)概率達(dá)到一定門(mén)限，就判這個(gè)數(shù)為素?cái)?shù)。這樣做既保證了這段程序可以在短時(shí)間內(nèi)執(zhí)行完，又保證了可以以比較高的準(zhǔn)確度得到素?cái)?shù)。 函數(shù) find_prime 先把 b[]的所有元素賦值為 1，然后按參數(shù) start 給標(biāo)記數(shù)組 b[]的各元素賦 0 值。下面描述標(biāo)記數(shù)組 b[]的賦 0值算法。首先，在類 Prime_factory_san 被構(gòu)造的時(shí)候，構(gòu)造函數(shù)中從 2 開(kāi)始搜尋一些小素?cái)?shù)，記錄在數(shù)組 pl[]中，共記錄 NP 個(gè)。這些小素?cái)?shù)用來(lái)當(dāng)作因子，他們的倍數(shù)將被從大素?cái)?shù)搜索范圍內(nèi)剔除 (即把數(shù)組 b[]的對(duì)應(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 對(duì)各小素?cái)?shù)因子 p 求模的辦法，得到當(dāng)前 p 在素?cái)?shù)搜索范圍內(nèi)的最小倍數(shù)在 b[]中的對(duì)應(yīng)位置，將 其剔除后，不斷后移 p 個(gè)位置，將這個(gè)小素?cái)?shù)因子 p 在搜索范圍內(nèi)的所有倍數(shù)全部剔除，如圖 25所示。在完成對(duì)所有小素?cái)?shù)因子的類似操作后，他們的倍數(shù)在搜索范圍內(nèi)的位置標(biāo)記 b[r]被全部標(biāo)記為 0。實(shí)際上這就是 Eratosthenes 篩選法。 圖 25 在素?cái)?shù)搜索范圍內(nèi)剔除小素?cái)?shù)因子 p 的倍數(shù) 接下來(lái)，對(duì)可能為素?cái)?shù)的數(shù) (即標(biāo)記數(shù)組 b[]中值為 1 的元素對(duì)應(yīng)的數(shù) )進(jìn)行素?cái)?shù)測(cè)試。數(shù)論學(xué)家利用費(fèi)馬小定理研究出了多種素?cái)?shù)測(cè)試方法，本程序使用一種最簡(jiǎn)單的方式，直接應(yīng)用費(fèi)馬小定理。取一個(gè)與 p 互素的整數(shù) A，對(duì)于大素?cái)?shù) p 來(lái)說(shuō)應(yīng)該滿 足 Ap1mod p=1，但是我們把 p 代入一個(gè)大整數(shù)，滿足這個(gè)關(guān)系的數(shù)不一定是素?cái)?shù)。這時(shí)我們改變 A，進(jìn)行多次測(cè)試，如果多次測(cè)試都通過(guò)，這個(gè)數(shù)是素?cái)?shù)的概率就比較大。按這種原理，我們編寫(xiě)素?cái)?shù)測(cè)試函數(shù)如下。 int is_probable_prime_san( const vlong amp。p ) { const rep = 4。 //測(cè)試次數(shù) const unsigned any[rep] = { 2,3,5,7 }。 //測(cè)試用的底數(shù) for ( unsigned i=0。 irep。 i+=1 ) if ( modexp( any[i], pvlong(1), p ) != vlong(1) ) return 0。 //modexp 是冪模函數(shù)，按上一小節(jié)敘述的算法編碼。 //這里 modexp 計(jì)算 any[i]p1mod p。 return 1。 } 測(cè)試通過(guò)，程序就判定這個(gè)數(shù)為找到的素?cái)?shù)，將找到的素?cái)?shù)返回給上層程序使用。在這里其實(shí)有一個(gè)不可忽視的問(wèn)題，就是得到一個(gè)測(cè)試通過(guò)的合數(shù)。對(duì)于這種情況， RSA 算法加密解密是否還可以實(shí)現(xiàn)，是一個(gè)需要從數(shù)學(xué)角度論證的問(wèn)題。因?yàn)榈玫剿財(cái)?shù)的概率很高，經(jīng)過(guò)一整天 的生成密鑰和加密操作，沒(méi)有發(fā)現(xiàn)失敗的密鑰， 所以本文暫沒(méi)有對(duì)這個(gè)問(wèn)題進(jìn)行討論。 實(shí)際得到素?cái)?shù)的流程： (1) 先得到一個(gè)隨機(jī)的大整數(shù) N 當(dāng)作尋找的起點(diǎn)． (2) 確定一個(gè)尋找范圍的大小 SS，把 (N,N+SS)范圍內(nèi)的小素?cái)?shù)倍數(shù)去掉，即前面敘述的古希臘某人發(fā)明的篩選法．小素?cái)?shù)因子從２開(kāi)始取，取幾百個(gè) (論文中將小素?cái)?shù)因子個(gè)數(shù)記為 NP)． (3) 對(duì)范圍內(nèi)沒(méi)有去掉的數(shù)逐一進(jìn)行素?cái)?shù)測(cè)試，一個(gè)數(shù)如果通過(guò)測(cè)試次數(shù)達(dá)到一定標(biāo)準(zhǔn)，就判為素?cái)?shù)． (4) 如果范圍內(nèi)沒(méi)找到素?cái)?shù)，就令 N=N+SS，回到 (2)繼續(xù)尋找． 用以上算法，直到以某成功概率得到素?cái)?shù)為止 綜上所述，總結(jié)素?cái)?shù)尋找的流程，如圖 26 所示。 圖 26 函數(shù) find_prime 尋找素?cái)?shù)的流程框圖 得到了大素?cái)?shù)，即 RSA算法中的 p、 q，我們就可以計(jì)算出密鑰，進(jìn)行加密等操作了。 4. 二元一次不定方程 在 RSA 算法中，往往要在已知 A、 M 的情況下，求 B的最小值，使得 (AB) mod M = 1。即相當(dāng)于求解 B、 N 都是未知數(shù)的二元一次不定方程 ABMN=1 的最小整數(shù)解。 而針對(duì)不定方程 axby=1 的最小整數(shù)解，古今中外都進(jìn)行過(guò)詳盡的研究 ，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國(guó)有秦九韶的“大衍求一術(shù)”。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說(shuō)明用歐幾里德算法求解二元一次不定方程的最小整數(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 開(kāi)始 按 start 參數(shù)初始化標(biāo)記數(shù)組 b[SS] 。 i=0 計(jì)數(shù) iSS? b[i]==1? 判定為素?cái)?shù) ? start+=1。i+=1 結(jié)束 返回素?cái)?shù)尋找結(jié)果 start Yes Yes Yes No No No 逆向代入： 令 y=0 代入（ 3）得 x=1 令 x=1 代入（ 2）得 y=2 令 y=2 代入 （ 1）得 x=9 x=9。y=2 即為所求。 程序中，全局函數(shù) vlong modinv( const vlong amp。a, const vlong amp。m )用來(lái)完成這種算法。對(duì)應(yīng)前面的敘述，參數(shù) a對(duì)應(yīng) A，參數(shù) m對(duì)應(yīng) M，函數(shù)返回值即為 B的最小值。 5. RSA 算法實(shí)現(xiàn)加密與解密 最后，類 RSA_san基于前面的準(zhǔn)備工作，實(shí)現(xiàn) RSA密鑰生成和加解密的功能 (算法在此不再贅述， RSA算法協(xié)議見(jiàn)（ 整個(gè)類的源程序中，所使用的變量字母 均和 RSA算法協(xié)議中一致。在類 RSA_san的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對(duì)隨機(jī)密鑰的操作。之后可以直接使用類的其他成員進(jìn)行 RSA加解密操作。類中各成員頻繁的用到字符串和 vlong類型的轉(zhuǎn)換，因?yàn)榇髷?shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。所以，需要實(shí)現(xiàn)一系列的編碼轉(zhuǎn)換函數(shù)，比如將 unsigned指針指向的一段空間里保存的一個(gè)大數(shù)，表示成十六進(jìn)制形式的字符串文本。編碼轉(zhuǎn)換通常是用 C風(fēng)格的指針操作和 sprintf函數(shù)來(lái)完成。 需要加密和解密的數(shù)據(jù)也是通過(guò)字符串參數(shù)置入 的。由于字符串的結(jié)尾字符“ \0”實(shí)際上也可能是需要加密的數(shù)據(jù)，所以置入的串長(zhǎng)度并不能以“ \0”來(lái)決定，程序里引入一個(gè)unsigned類型的參數(shù)來(lái)決定置入的串長(zhǎng)度，這樣就解決了加密連 0數(shù)據(jù)時(shí)候被截?cái)嗟膯?wèn)題。 因?yàn)槭菍?duì)文件加密的軟件，需要加密的數(shù)據(jù)通常并不止幾字節(jié)，本軟件默認(rèn)的分塊大小是 1字節(jié)，即逐個(gè)字節(jié)作為參數(shù)，調(diào)用 C++核心模塊中的方法。 加密解密流程均為標(biāo)準(zhǔn) RSA算法，具體過(guò)程見(jiàn)下圖： ①生成密鑰： 圖 27 隨機(jī)生成密鑰 相關(guān)代碼： public static int GetRandomString()//實(shí)現(xiàn)隨機(jī)字串的獲得 { Random rnd = new Random()。 Byte[]b=new Byte[(RSAprimeplen1,RSAprimeplen2)]。 s1=。 s2=。 for(int i=0。iRSAprimeplen1。i++) { Byte tmp=(*())。 if(tmp!=0)b[i]=tmp。else b[i]=1。 } s1=(b)。 for(int i=0。iRSAprimeplen2。i++) { Byte tmp=(*())。 if(tmp!=0)b[i]=tmp。else b[i]=1。 } s2=(b)。 return 1。} ②加密過(guò)程： 圖 28 載入待加密的文本 圖 29 準(zhǔn)備加密文本 圖 210加密后生成的文本 圖 211加密過(guò)程完成 相關(guān)代碼： private void menuItem10_Click(object sender, e)//公鑰加密 { if(==0) { emptymsg em=new emptymsg(this)。 ()。 return。 } Stream myStream 。 SaveFileDialog saveFileDialog1 = new SaveFileDialog()。 = Hex text files (*.hextxt)|*.hextxt|All files (*.*)|*.* 。 = 1 。 = true 。 if(() == ) { if((myStream=()) != null) { +=\r\n正在對(duì)讀入的文件進(jìn)行處理，請(qǐng)稍候：） \r\n。 (500)。 HighResolutionTimer timer = new HighResolutionTimer()。 ()。 using (StreamWriter sw = new StreamWriter(myStream)) { ( )。 (___________________________________________)。 B