微機(jī)隨機(jī)大素數(shù)的概率生成與應(yīng)用

1、公開鑰密碼體制提出至今已有十多年的歷史，由于人們對信息安全的迫切要求和密碼學(xué)者不懈努力，這一體制已得到廣泛的應(yīng)用，在國內(nèi)外眾多的公開密鑰密碼方案中研究得比較充分而比較有名的首推美國的RSA。它的安全性是基于大數(shù)因子分解在數(shù)學(xué)上是一個 NP困難的問題，至今沒有有效的算法。無疑提高素數(shù)的位數(shù)將大大提高 RSA的安全性，同時大素數(shù)有實際的應(yīng)用領(lǐng)域。這促使我們對微機(jī)隨機(jī)大素數(shù)的概率生成應(yīng)用軟件的研制并提供實用。我們將這一軟件取名為386BIP-1。在微機(jī)上運行這個軟件，通常可在2-3小時內(nèi)得到一個概率為 1-(1/4) 的100位的隨機(jī)概率素數(shù)，這對于在微機(jī)上實現(xiàn)可用于實際的公鑰密碼系統(tǒng)，提供了可能。

2、此外,該軟件支持WINDOWS和網(wǎng)絡(luò)。 Center (一)設(shè)計要求與方案 根據(jù)實際應(yīng)用的需要，對386BIP-1的設(shè)計要求如下： (1) 用C(C+)語言編寫源程序. (2) 有好的用戶界面，方便的菜單選擇. (3) 從鍵盤輸入所要產(chǎn)生的隨機(jī)大素數(shù)的位數(shù)(100位以內(nèi)，100以上的只需稍加改動源程序中的數(shù)組大小即可)后，可自動產(chǎn)生所要求位數(shù)的大概率隨機(jī)大素數(shù)，且可進(jìn)一步進(jìn)行大概率驗證，并輸出大概率素數(shù)于屏幕，打印機(jī)或文件中. (4) 提供大素數(shù)在RSA中的具體應(yīng)用。 (5) 用于286,386,486微機(jī)；易于移植到大型機(jī)。 根據(jù)對軟件的設(shè)計要求，本軟件的主體由三個部份組成： (1) 隨機(jī)大

3、素數(shù)的概率生成：在本部份中，從鍵盤輸入所要產(chǎn)生的隨機(jī)大素數(shù)的位數(shù)，即可自動隨機(jī)產(chǎn)生大概率的大素數(shù)，并可輸出到屏幕，打印機(jī)或磁碟文件中。 (2) 大素數(shù)概率檢驗：在本部份中，從鍵盤或文件輸入一個位以內(nèi)的大整數(shù)，即可自動進(jìn)行概率檢驗，一次全部通過是素數(shù)的概率為1-(1/4) 。 (3) 大素數(shù)在RSA中的應(yīng)用：本部份中，可從鍵盤或文件輸入所產(chǎn)生的概率大素數(shù)，產(chǎn)生RSA加(解)密鑰；并提供加（解）密，輸出密（明）文于屏幕，打印機(jī)或磁盤文件中。 Center (二)設(shè)計分析 (1) 大整數(shù)及其四則運算的處理: 386BIA-1軟件包可在微機(jī)上直接輸入輸出1000位以內(nèi)的十進(jìn)制大整數(shù)進(jìn)行計算; 由于在C

4、語言中,十進(jìn)制整數(shù)的范圍僅為 -2 2 -1(不超出10位),因而首先要解決大整數(shù)的表示方法. 我們采取通常的用數(shù)組表示大整數(shù)的方法 ,因為在具體的程序設(shè)計語言(C語言)中考慮到基本運算的運算速度不一致(例如 ,除法比加、減、乘運算慢);同時,要盡可能地避免在程序運行中進(jìn)行變量類型轉(zhuǎn)換; 我們編程檢驗過,當(dāng)使用語言編程時,如果有字符型同數(shù)值型的類型轉(zhuǎn)換,則運算速度要下降十倍以上. 微機(jī)大整數(shù)運算,文獻(xiàn)中已使用了許多方法, 經(jīng)過反復(fù)研究,我們采用以眾不同的10000進(jìn)制方法,即任一整數(shù)a都表示為: a = ai*10000 (0ai9999,i非負(fù)整數(shù)); 這樣一方面可在微機(jī)上直接輸入輸出100

5、0位以上的十進(jìn)制大整數(shù),另一方面,加法乘法皆不溢出;既易于表達(dá),亦易于運算.在進(jìn)行四則運算時,直接運用C語言中的基本運算,完全按一般的逐位對齊的辦法進(jìn)行運算,這來得十分方便簡捷,同時,在程序運行中完全避免了變量類型轉(zhuǎn)換,大幅度提高了運算速度. 例如: a,b的十進(jìn)制位數(shù)在800位以內(nèi)時;為在1000進(jìn)位制下表達(dá)a,b,可將它們寫成數(shù)組: Long int a200,b200; int la,lb; 這里的ai,bj是不超過4位的十進(jìn)制整數(shù), 即0ai,bj9999; la,lb 分別是a,b在 10000進(jìn)位制表示下的長,即la= Log a+1 ,lb= Log b+1 , 0ila-1,

6、0jlb-1; 這樣,十進(jìn)制整數(shù)a,b可分別表示為10000進(jìn)制數(shù): a= ai*(10000), b= bi*(10000). 由此可對800位以內(nèi)的大整數(shù)如下作加,減與乘法運算: a+b= (ai+bi)*(10000) ; a-b= (ai-bi)*(10000) ; a*b= (ai*bj)*(10000) 其中的ai+bj是兩個4位的十進(jìn)制整數(shù)相加,結(jié)果不超出一個5位的十進(jìn)制整數(shù),ai*bj是兩個4位的十進(jìn)制整數(shù)相乘,結(jié)果不超出一個8位的十進(jìn)制整數(shù); 因此可以直接使用微機(jī)C語言中的四則運算. 計算過程中尚須記錄進(jìn)位,借位; 以加法為例,可使用長整型變量 ssum,sumi,w及整型變

7、量ls, 其中ssum存放每四位相加的結(jié)果,w記錄進(jìn)位sumi是經(jīng)過處理后的結(jié)構(gòu)如同整數(shù)a,b一樣的最后結(jié)果,ls記錄和所用數(shù)組的最大下標(biāo).如此,加法函數(shù)如下: struct aadd long int result200; int lr; ; struct aadd add(long int a200,long int b200,int la,int lb) struct aadd a; long int ssum,w; int i; w=0; if(la=lb) a.lr=lb-1; for(i=0;i=la&ilb) ssum=bi+w; a.sumi=ssum%10000; w=ssu

8、m/10000; i=i+1; else a.lr=la-1; for(i=0;ilb;i+) ssum=ai+bi+w; a.sumi=ssum%10000; w=ssum/10000; for(i=lb;ila;i+) ssum=ai+w; a.sumi=ssum%10000; w=ssum/10000; if(w!=0) a.lr=a.lr+1; a.suma.lr=w; return(a); 乘法是直接利用C語言中的乘法指令和求和函數(shù)實現(xiàn)的,兩個100位大整數(shù)相乘只需C語言中的基本指令乘法625次,加法625次即可完成. 除法是直接利用C語言中的除法指令及求積函數(shù)和求差函數(shù)實現(xiàn)的,方法

9、是采用高位試商的辦法進(jìn)行,與通常筆算中方試相類似.不難看出,我們的做法與通常四則運算相同,一個算法如果是快速的,則在我們軟件包的四則運算實現(xiàn)下來仍然是快速的! (2) 大數(shù)的偽隨機(jī)數(shù)發(fā)生器: 在眾多的偽隨機(jī)數(shù)產(chǎn)生方法中,選取了線性同余偽隨機(jī)數(shù)產(chǎn)生器,即 Xn =D*Xn+C mod M 其中:X 為初始值,D,C為常數(shù),M=10000. 輸入初始值Seed和迭代次數(shù)rnum之后,運行偽隨機(jī)數(shù)產(chǎn)生器產(chǎn)生rnum個偽隨機(jī)數(shù),選取這rnum個偽隨機(jī)數(shù)中的第rnum個偽隨機(jī)數(shù)為rdm(1),以rdm(1)作為第二次偽隨機(jī)數(shù)產(chǎn)生器的初值(此時的兩個偽隨機(jī)產(chǎn)生器參數(shù)可改變),如此連續(xù)產(chǎn)生所需的m個偽隨機(jī)數(shù)

10、 rdm(m),由此構(gòu)成大隨機(jī)數(shù) rdm = rdm(i)*10000 選取足夠大的m,就可獲得足夠大的偽隨機(jī)數(shù). (3) 素數(shù)概率檢驗: Wilson定理給出了一個判別素數(shù)的充分必要條件:P為素數(shù)當(dāng)且僅當(dāng)(P-1)! -1 MOD P.由于其極高的計算復(fù)雜性,無法實用. Fermat定理給出P為素數(shù)的必要條件:a a mod p, 則 p不是素數(shù), 可用于檢驗素數(shù),但效果不佳. 我們使用Rabin素數(shù)檢驗法. 定義 設(shè)p是正整數(shù),p-1= 2 *m,其中k是非負(fù)整數(shù),m是正奇數(shù).若存在正整數(shù)a,使得 a 1 mod p 或 a -1 mod p 則稱p關(guān)于a通過Miller檢驗,其中h是某個

11、非負(fù)整數(shù),0hk-1. 定理 若p是素數(shù),a是正整數(shù), (p,a)=1,則p關(guān)于a通過Miller檢驗. 定理 若p是正奇合數(shù),則最多只有(p-1)/4個數(shù)a,1ap-1,關(guān)于它們p通過Miller檢驗.(有關(guān)證明見文獻(xiàn)4). Rabin素數(shù)檢驗法: 若p是正整數(shù),隨機(jī)取k個小于p的不同整數(shù),若這k個數(shù)的Miller檢驗全部通過,則 p為合數(shù)的概率為(1/4) . Rabin檢驗法不能完全肯定一數(shù)一定是素數(shù),然而當(dāng)k相當(dāng)大時可以相當(dāng)高的可靠性任可其素性. 在我們的軟件里,主要函數(shù)是判斷一個與a互素的大整數(shù)p關(guān)于a是否通過miller檢驗,其程序如下設(shè)計: struct aadd long in

12、t sum110; int lensum; ; struct mminus long int minu110; int lenminu,h; ; struct divi long int quo110,rem110; int lenquo,lenrem; ; struct mmult2 long int numa110; int lena; ; char miller(long int nump110,long int numa110,int lenp,int lena) struct aadd da,add(long int ,long int ,int,int); struct mminu

13、s mm,minus(long int ,long int ,int,int); struct divi di,zm,div2(long int ,int),pmo(long int ,long int ,long int ,int,int,int); struct mmult2 ma,mult2(long int ,int); long int numc2,numd2; int i,j=0,h,lenc=0,lend=0; numc0=1; numd0=2; mm=minus(nump,numc,lenp,lenc); for(i=0;imm.lenminu;i+) di.quoi=mm.m

14、inui; di.lenquo=mm.lenminu; do di=div2(di.quo,di.lenquo); j+; while(di.rem0=0); ma=mult2(di.quo,di.lenquo); da=add(ma.numa,numc,ma.lena,lenc); zm=pmo(numa,nump,da.sum,lena,lenp,da.lensum); if(zm.rem0=1&zm.lenrem=0) return(y); else if(zm.lenrem=mm.lenminu) i=0; while(zm.remi=mm.minui&i=zm.lenrem) i=i

15、+1; if(i=zm.lenrem+1) return(y); for(h=1;h=j-2;h+) zm=pmo(zm.rem,nump,numd,zm.lenrem,lenp,lend); if(zm.lenrem=mm.lenminu) i=0; while(zm.remi=mm.minui&i=zm.lenrem) i=i+1; if(i=zm.lenrem+1) return(y); return(n); 這里的add是求和函數(shù),minus是求差函數(shù),div2是除以2求商和余數(shù)函數(shù),mult2是乘以2求積函數(shù),pmo是冪模函數(shù)。 Center (三)程序設(shè)計 386BIP-1軟件是在

16、Borland C+(3.1)下開發(fā)研制的，與通常程序設(shè)計完全一樣，由于源程序很長，這里就不再附入。下面主要介紹隨機(jī)大素數(shù)的概率生成框圖: 隨機(jī)數(shù)發(fā)生器產(chǎn)生 100位的大整數(shù) p; i:=0 隨機(jī)數(shù)發(fā)生器產(chǎn)生 100位以內(nèi)的整數(shù)a 判斷 p,a 是否互素 判斷p關(guān)于a是否 通過miller檢驗 i:i+1 i10 結(jié)束 Center (四) 計算的具體例子 下面兩個100位的隨機(jī)大概率素數(shù)就是用此軟件在AST 486/33 微機(jī)上用不到3個小時產(chǎn)生出來的. 參考文獻(xiàn): Center 參 考 文 獻(xiàn) 1 葉頂峰,常伊群,呂述望 基于微機(jī)386的公鑰密碼體制,第四屆通信保密現(xiàn)狀研討會, 1993. 2 D,Knuth, The art of Comouter Programming,Vol,2,Reading MA:A