微机随机大素数的概率生成与应用

1、公开钥密码体制提出至今已有十多年的历史，由于人们对信息安全的迫切要求和密码学者不懈努力，这一体制已得到广泛的应用，在国内外众多的公开密钥密码方案中研究得比较充分而比较有名的首推美国的RSA。它的安全性是基于大数因子分解在数学上是一个 NP困难的问题，至今没有有效的算法。无疑提高素数的位数将大大提高 RSA的安全性，同时大素数有实际的应用领域。这促使我们对微机随机大素数的概率生成应用软件的研制并提供实用。我们将这一软件取名为386BIP-1。在微机上运行这个软件，通常可在2-3小时内得到一个概率为 1-(1/4) 的100位的随机概率素数，这对于在微机上实现可用于实际的公钥密码系统，提供了可能。

2、此外,该软件支持WINDOWS和网络。 Center (一)设计要求与方案 根据实际应用的需要，对386BIP-1的设计要求如下： (1) 用C(C+)语言编写源程序. (2) 有好的用户界面，方便的菜单选择. (3) 从键盘输入所要产生的随机大素数的位数(100位以内，100以上的只需稍加改动源程序中的数组大小即可)后，可自动产生所要求位数的大概率随机大素数，且可进一步进行大概率验证，并输出大概率素数于屏幕，打印机或文件中. (4) 提供大素数在RSA中的具体应用。 (5) 用于286,386,486微机；易于移植到大型机。 根据对软件的设计要求，本软件的主体由三个部份组成： (1) 随机大

3、素数的概率生成：在本部份中，从键盘输入所要产生的随机大素数的位数，即可自动随机产生大概率的大素数，并可输出到屏幕，打印机或磁碟文件中。 (2) 大素数概率检验：在本部份中，从键盘或文件输入一个位以内的大整数，即可自动进行概率检验，一次全部通过是素数的概率为1-(1/4) 。 (3) 大素数在RSA中的应用：本部份中，可从键盘或文件输入所产生的概率大素数，产生RSA加(解)密钥；并提供加（解）密，输出密（明）文于屏幕，打印机或磁盘文件中。 Center (二)设计分析 (1) 大整数及其四则运算的处理: 386BIA-1软件包可在微机上直接输入输出1000位以内的十进制大整数进行计算; 由于在C

4、语言中,十进制整数的范围仅为 -2 2 -1(不超出10位),因而首先要解决大整数的表示方法. 我们采取通常的用数组表示大整数的方法 ,因为在具体的程序设计语言(C语言)中考虑到基本运算的运算速度不一致(例如 ,除法比加、减、乘运算慢);同时,要尽可能地避免在程序运行中进行变量类型转换; 我们编程检验过,当使用语言编程时,如果有字符型同数值型的类型转换,则运算速度要下降十倍以上. 微机大整数运算,文献中已使用了许多方法, 经过反复研究,我们采用以众不同的10000进制方法,即任一整数a都表示为: a = ai*10000 (0ai9999,i非负整数); 这样一方面可在微机上直接输入输出100

5、0位以上的十进制大整数,另一方面,加法乘法皆不溢出;既易于表达,亦易于运算.在进行四则运算时,直接运用C语言中的基本运算,完全按一般的逐位对齐的办法进行运算,这来得十分方便简捷,同时,在程序运行中完全避免了变量类型转换,大幅度提高了运算速度. 例如: a,b的十进制位数在800位以内时;为在1000进位制下表达a,b,可将它们写成数组: Long int a200,b200; int la,lb; 这里的ai,bj是不超过4位的十进制整数, 即0ai,bj9999; la,lb 分别是a,b在 10000进位制表示下的长,即la= Log a+1 ,lb= Log b+1 , 0ila-1,

6、0jlb-1; 这样,十进制整数a,b可分别表示为10000进制数: a= ai*(10000), b= bi*(10000). 由此可对800位以内的大整数如下作加,减与乘法运算: a+b= (ai+bi)*(10000) ; a-b= (ai-bi)*(10000) ; a*b= (ai*bj)*(10000) 其中的ai+bj是两个4位的十进制整数相加,结果不超出一个5位的十进制整数,ai*bj是两个4位的十进制整数相乘,结果不超出一个8位的十进制整数; 因此可以直接使用微机C语言中的四则运算. 计算过程中尚须记录进位,借位; 以加法为例,可使用长整型变量 ssum,sumi,w及整型变

7、量ls, 其中ssum存放每四位相加的结果,w记录进位sumi是经过处理后的结构如同整数a,b一样的最后结果,ls记录和所用数组的最大下标.如此,加法函数如下: 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语言中的乘法指令和求和函数实现的,两个100位大整数相乘只需C语言中的基本指令乘法625次,加法625次即可完成. 除法是直接利用C语言中的除法指令及求积函数和求差函数实现的,方法

9、是采用高位试商的办法进行,与通常笔算中方试相类似.不难看出,我们的做法与通常四则运算相同,一个算法如果是快速的,则在我们软件包的四则运算实现下来仍然是快速的! (2) 大数的伪随机数发生器: 在众多的伪随机数产生方法中,选取了线性同余伪随机数产生器,即 Xn =D*Xn+C mod M 其中:X 为初始值,D,C为常数,M=10000. 输入初始值Seed和迭代次数rnum之后,运行伪随机数产生器产生rnum个伪随机数,选取这rnum个伪随机数中的第rnum个伪随机数为rdm(1),以rdm(1)作为第二次伪随机数产生器的初值(此时的两个伪随机产生器参数可改变),如此连续产生所需的m个伪随机数

10、 rdm(m),由此构成大随机数 rdm = rdm(i)*10000 选取足够大的m,就可获得足够大的伪随机数. (3) 素数概率检验: Wilson定理给出了一个判别素数的充分必要条件:P为素数当且仅当(P-1)! -1 MOD P.由于其极高的计算复杂性,无法实用. Fermat定理给出P为素数的必要条件:a a mod p, 则 p不是素数, 可用于检验素数,但效果不佳. 我们使用Rabin素数检验法. 定义 设p是正整数,p-1= 2 *m,其中k是非负整数,m是正奇数.若存在正整数a,使得 a 1 mod p 或 a -1 mod p 则称p关于a通过Miller检验,其中h是某个

11、非负整数,0hk-1. 定理 若p是素数,a是正整数, (p,a)=1,则p关于a通过Miller检验. 定理 若p是正奇合数,则最多只有(p-1)/4个数a,1ap-1,关于它们p通过Miller检验.(有关证明见文献4). Rabin素数检验法: 若p是正整数,随机取k个小于p的不同整数,若这k个数的Miller检验全部通过,则 p为合数的概率为(1/4) . Rabin检验法不能完全肯定一数一定是素数,然而当k相当大时可以相当高的可靠性任可其素性. 在我们的软件里,主要函数是判断一个与a互素的大整数p关于a是否通过miller检验,其程序如下设计: 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是求和函数,minus是求差函数,div2是除以2求商和余数函数,mult2是乘以2求积函数,pmo是幂模函数。 Center (三)程序设计 386BIP-1软件是在

16、Borland C+(3.1)下开发研制的，与通常程序设计完全一样，由于源程序很长，这里就不再附入。下面主要介绍随机大素数的概率生成框图: 随机数发生器产生 100位的大整数 p; i:=0 随机数发生器产生 100位以内的整数a 判断 p,a 是否互素 判断p关于a是否 通过miller检验 i:i+1 i10 结束 Center (四) 计算的具体例子 下面两个100位的随机大概率素数就是用此软件在AST 486/33 微机上用不到3个小时产生出来的. 参考文献: Center 参 考 文 献 1 叶顶峰,常伊群,吕述望 基于微机386的公钥密码体制,第四届通信保密现状研讨会, 1993. 2 D,Knuth, The art of Comouter Programming,Vol,2,Reading MA:A