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

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

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

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

4、語(yǔ)言中,十進(jìn)制整數(shù)的范圍僅為 -2 2 -1(不超出10位),因而首先要解決大整數(shù)的表示方法. 我們采取通常的用數(shù)組表示大整數(shù)的方法 ,因?yàn)樵诰唧w的程序設(shè)計(jì)語(yǔ)言(C語(yǔ)言)中考慮到基本運(yùn)算的運(yùn)算速度不一致(例如 ,除法比加、減、乘運(yùn)算慢);同時(shí),要盡可能地避免在程序運(yùn)行中進(jìn)行變量類型轉(zhuǎn)換; 我們編程檢驗(yàn)過,當(dāng)使用語(yǔ)言編程時(shí),如果有字符型同數(shù)值型的類型轉(zhuǎn)換,則運(yùn)算速度要下降十倍以上. 微機(jī)大整數(shù)運(yùn)算,文獻(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á),亦易于運(yùn)算.在進(jìn)行四則運(yùn)算時(shí),直接運(yùn)用C語(yǔ)言中的基本運(yùn)算,完全按一般的逐位對(duì)齊的辦法進(jìn)行運(yùn)算,這來得十分方便簡(jiǎn)捷,同時(shí),在程序運(yùn)行中完全避免了變量類型轉(zhuǎn)換,大幅度提高了運(yùn)算速度. 例如: a,b的十進(jìn)制位數(shù)在800位以內(nèi)時(shí);為在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)位制表示下的長(zhǎng),即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). 由此可對(duì)800位以內(nèi)的大整數(shù)如下作加,減與乘法運(yùn)算: a+b= (ai+bi)*(10000) ; a-b= (ai-bi)*(10000) ; a*b= (ai*bj)*(10000) 其中的ai+bj是兩個(gè)4位的十進(jìn)制整數(shù)相加,結(jié)果不超出一個(gè)5位的十進(jìn)制整數(shù),ai*bj是兩個(gè)4位的十進(jìn)制整數(shù)相乘,結(jié)果不超出一個(gè)8位的十進(jìn)制整數(shù); 因此可以直接使用微機(jī)C語(yǔ)言中的四則運(yùn)算. 計(jì)算過程中尚須記錄進(jìn)位,借位; 以加法為例,可使用長(zhǎng)整型變量 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語(yǔ)言中的乘法指令和求和函數(shù)實(shí)現(xiàn)的,兩個(gè)100位大整數(shù)相乘只需C語(yǔ)言中的基本指令乘法625次,加法625次即可完成. 除法是直接利用C語(yǔ)言中的除法指令及求積函數(shù)和求差函數(shù)實(shí)現(xiàn)的,方法

9、是采用高位試商的辦法進(jìn)行,與通常筆算中方試相類似.不難看出,我們的做法與通常四則運(yùn)算相同,一個(gè)算法如果是快速的,則在我們軟件包的四則運(yùn)算實(shí)現(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之后,運(yùn)行偽隨機(jī)數(shù)產(chǎn)生器產(chǎn)生rnum個(gè)偽隨機(jī)數(shù),選取這rnum個(gè)偽隨機(jī)數(shù)中的第rnum個(gè)偽隨機(jī)數(shù)為rdm(1),以rdm(1)作為第二次偽隨機(jī)數(shù)產(chǎn)生器的初值(此時(shí)的兩個(gè)偽隨機(jī)產(chǎn)生器參數(shù)可改變),如此連續(xù)產(chǎn)生所需的m個(gè)偽隨機(jī)數(shù)

10、 rdm(m),由此構(gòu)成大隨機(jī)數(shù) rdm = rdm(i)*10000 選取足夠大的m,就可獲得足夠大的偽隨機(jī)數(shù). (3) 素?cái)?shù)概率檢驗(yàn): Wilson定理給出了一個(gè)判別素?cái)?shù)的充分必要條件:P為素?cái)?shù)當(dāng)且僅當(dāng)(P-1)! -1 MOD P.由于其極高的計(jì)算復(fù)雜性,無法實(shí)用. Fermat定理給出P為素?cái)?shù)的必要條件:a a mod p, 則 p不是素?cái)?shù), 可用于檢驗(yàn)素?cái)?shù),但效果不佳. 我們使用Rabin素?cái)?shù)檢驗(yàn)法. 定義 設(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檢驗(yàn),其中h是某個(gè)

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

16、Borland C+(3.1)下開發(fā)研制的，與通常程序設(shè)計(jì)完全一樣，由于源程序很長(zhǎng)，這里就不再附入。下面主要介紹隨機(jī)大素?cái)?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檢驗(yàn) i:i+1 i10 結(jié)束 Center (四) 計(jì)算的具體例子 下面兩個(gè)100位的隨機(jī)大概率素?cái)?shù)就是用此軟件在AST 486/33 微機(jī)上用不到3個(gè)小時(shí)產(chǎn)生出來的. 參考文獻(xiàn): Center 參 考 文 獻(xiàn) 1 葉頂峰,常伊群,呂述望 基于微機(jī)386的公鑰密碼體制,第四屆通信保密現(xiàn)狀研討會(huì), 1993. 2 D,Knuth, The art of Comouter Programming,Vol,2,Reading MA:A