随机预言模型下的RSA公钥密码体制及其快速实现

随机预言模型下的RSA公钥密码体制及其快速实现 随机预言模型下的RSA公钥密码体制及其 快速实现 58 第25卷第6期 2007年l2月 凯里学院 JournalofKailiUniversity Vo1.25No.6 Dec.2007 随机预言模型下的RSA公钥密码体制 及其快速实现 邓从政,谈光涛 (1.凯里学院数学与计算机科学系,贵州凯里556000}2.孝昌第二中学,湖北孝昌432900) [摘要]RSA公钥密码体制是当今最流行的公钥密码体制,在实际应用中由于它的代数性质,攻击者易于积累有效 信息,在加密大量消息的情况下加解密速度非常慢.针对这2个缺陷,提出了一种加载随机预言模型的RSA公钥密码体 制.运用Rabin-Miller算法 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 素数并成功生成2个大素数之后,再运用欧几里德算法在默认公钥的前提下求得私钥,然 后运用公钥和私钥进行加密与解密,大大降低了攻击者对信息的积累,提高了加解密的效率,在公钥加密 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 和电子商业 中被广泛应用. [关键词]随机预言;公钥密码体制;Rabin一/Vliller算法;扩展欧几里德算法 [中图分类号]TP311.56[文献标识码]A[文章编号]1673—9329(2007)06—0058—03 0引言 随着计算机技术和网络的发展和普及.安全问题越来 越弓f起人们的关注.尤其当传送一些比较机密或是不想被 他人知道的文件时,人们就不得不考虑加密技术.在现代的 信息安全技术当中现在流行的两种密码体制是公钥密码 体制和私钥密码体制,相对私钥密码体制而言,公钥密码体 制的保密性更强,形式更简单.而且也适合密钥的管理.使 用更广泛.RSA是一种比较经典和实用的加密算法.既能 用于数据加密.又能用于数字签名,而且其可靠性与所用密 钥的长度有很大关系.从RSA的保密性来看,敌手试图攻 破RSA得到私钥,这几乎是不可能的,但是在实际应用中, 攻击者的目标也许并没有这么大的野心,他虽然不能得到 私钥.但是仍可以获得很多信息.RSA是确定性的密码体 制.具有很强的代数性质,容易让攻击者积累信息.当积累 的信息比较多的时候.攻击者就有机可图了.假如有人找到 一 种很快的分解因子算法.那么用RSA加密的信息的可靠 性肯定会极度下降.事实证明,随着密钥长度的增加.因子 分解的难度也相应增加.其安全性也可以得到进一步的保 证,因而我们需要小心地选择RSA的密钥大小.从目前的 计算机技术看来,一个1024到2048比特的密钥大小应该 比较合理.另外.RSA最大的缺点就是加密和解密的效率 低.本文针对这两大缺点.提出了一种加载随机预言模型 的RSA公钥密码体制.并运用Rabin—Miller算法检测素数 并成功生成两个大素数之后,再运用欧几里德算法在默认 公钥的前提下求得私钥,来快速地实现RSA的加解密. 1加载随机预言模型的RSA公钥密码体制 1.1随机预言模型简介 随机预言模型是Hash函数某种理想化的数学模型.通 过这种模型可以得到一个理想化的Hash函数,由Ballare 和Rogaway引入的随机预言模型提供了这种数学模型.在 这个模型中.随机的从Hash函数族中选出一个Hash函数 h,我们仅允许预言器访问函数h.这意味着不会给出一个 公式或者算法来计算函数^()的值,因此计算函数^(z) 值的唯一方法是询问预言器.这可以想象成在一本巨大的 关于随机数的 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 中查询^()的值,对于每一个x,有一个 完全随机值与h(X)相对应.例如,在RSA加密后总会带有 很强的代数性质.如果能在加密前将明文随机化.那么加密 后就会避开了RSA所带来的代数性质了,也就是说不会让 攻击者得到有效的消息了.因此加载随机预言模型在RSA 数字签名体制的实际应用中有很大的安全性. 1.2RSA公钥密码体制及其缺陷 RSA公钥密码体制:设/'l一加,其中P和g是两个不同 的大素数(户,g大于1024bits).定义参数系统为 K一((,户,g,口,6):ab1(mode(n))) 其中(,6)组成公钥,(户,g,n)组成私钥.对于参数系统K = (.P,g,口,6),消息z?Z,定义加密函数为:ek(z)一 modn,解密函数为:d^()一yaroodn. RSA体制是这样实现的.假设Bob先建立了RSA体 制,得到了参数(,P.q.n.6)并公开了.Alice想秘密传送明 文消息给Bob,Alice首先将明文消息分成若干数据块.每块 消息z?,计算y一()一mod.然后将密文Y传 送给Bob.Bob收到密文后,计算()一mod,由此恢 复明文z一以(v). 在实际应用中.RSA存在两大缺陷.其一.对于一般攻 击者来说.RSA公钥密码体制是安全的.但是对于一些主 动攻击者来说.他们并没有直接求出私钥而攻破此体制, [收稿日期]2007—09—18 [作者简介]邓从政(1969一),男,湖北孝感人,凯里学院讲师,主要从事信息安全,密 码与编码等方面的研究 第6期邓从政,谈光涛:随机预言模型下的RSA公钥密码体制及其快速实现59 RsA公钥密码体制是确定性的密码体制,加密后不可避免 的带来了很多代数性质,这样就为攻击者带来了很多有效 信息的积累,当信息积累到了一定程度的时候,攻击者就可 以有很大机会分辨出明密文对,并将之破译了.其二,从加 解密中可以看出,RSA公钥密码体制是先对明文分块,然 后对每一块进行加密.其中要进行大整数的模幂乘法运算. 而大整数的模乘运算的效率本来就比较低,如果要加密的 明文很多的时候,进行大整数模乘运算的次数就更多,这样 就大大地降低了加解密的效率.用软件实现时,这一缺陷更 加明显. 1.3加载随机预言模型的RSA公钥密码体制 这种算法是基于RSA算法基础上改进的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,其安全 性也是依赖大整数分解的困难性.然而它与传统RsA体制 相比,它引人了随机预言模型. (1)选择2个不同的大素数P和q(P,q大于l 024Bits),使得n=加;(2)计算"一,声(n)一(P—1)(q — 1);(3)选择a,gcd(口,声(n))一l,计算bamod;(4) 设H:{0,i)一{0,i)为一个随机预言,令明文x?{0, i);(5)加密明文消息:随机选择r?{0,1),定义P(z)一 (1,2)一(modn,H(r)?z);(6)解密密文消息:d(yl, 2)一H(y1"roodn)?2,1?{0,1),2?{0,1).其中 (n,6)组成公钥,(户,qm)组成私钥;(7)验证:d(y1,2)一 H(y1"modn)?y2=H(()modn)2一H(rmodn)y2 x. 假设Bob先建立了RSA体制,得到了n,6,a,P和q,并 公开了n和b.假设Alice想秘密传送明文给Bob,Alice首先 将明文分成长度相等的数据块,其中每个数据块的长度为 m:/7l?[1og一1],若最后一块的长度小于m,则用特殊字 符进行填充.随机选择r,r?{0,1),对每一数据块x,计 算P(z)=(1.Y2)一(modn,H(r)0z).其中H是随机 预言H:r?{0,1)一{0,1).最后将密文P(z)=(1,2) 传给Bob.Bob收到密文后,对每一组(,yz),计算d(y, Y2)=H(y1modn)?y2,y1?{0.1),2?{0,1),这样即 可以恢复明文了. 算法通过计算H(r)?z),先将明文随机化.减少了攻 击者进行消息积累的可能性.从加密变换中可以看出,要想 恢复明文x.就必须计算H(r)oz)而H(r)是一个随机预 言的值,根据随机预言模型的性质,只有知道'r才能求得 H(r);而要想知道r(仅知道r的一部分信息是不够的,要计 算H(r)就必须知道r全部的信息),由于攻击者不知道陷 门,无法得到a,所以就不能在多项式时问内求得r.从RSA 公钥密码体制中可以看出,它在加解密的运算时,都是先将 信息进行分块,然后对每个分块分别进行一次大整数的模 乘运算.RSA算法的最大缺点就是在加解密的速度上,当 明文很大的时候,那么速度慢的问题就更加明显了,因为要 进行很多次的大整数模乘运算.而加载随机预言模型的 RSA公钥密码体制就很有效的鸸决了这个问题.它在加解 密当中,只需分别进行一次大整数的模乘运算,而将原来体 制中的多次大整数的模乘运算改为了效率很高的异或运 算.即计算H(r)0z),这样通过减少大整数的模乘运算, 有效的提高了加解密的效率.特别是在软件实现中,更能提 高该体制的可用性. 3随机预言模型下RSA公钥密码体制的快速实现 3.1素性检测 要快速实现加载随机预言模型的RSA公钥密码体制, 就要涉及到素数的生成.一个简单的想法就是先随机生成 一 个奇数,然后检测这个奇数是不是素数.一个比较高效和 流行的检测素性的方法是Rabin--Miller法,其核心算法称 为wITNESS.具体描述如下: WITNESS(a,n) 令6.…60为(n—1)的二进制 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 d.卜_l: for.卜_kdownto0: dox.卜_d; d一(×)modn; ifd—landx?1andx?n一1;thenretumTRUE; ifbf—l; thend.卜_(×amodn; ifd?l; therreturnTRUE; returnFAISE WITNESS的输人是要测试的数n或小于n的某个整 数,算法的目的是检测n是否为素数.如果WITNESS返回 TRUE,如果]modn返回FALSE,表明n可能是素数. 在实际中,我们用以下随机递增法寻找素数: (1)生一个(n一1)位的随机数P;(2)设高位位和低位 位为1以确保该素数达到要求的长度;(3)检测以确保P不 能被任何小素数(如3,5.7,11等等)整除.这里先将此数用 2000以内的素数除,初步检测其素性;(4)对随机数a运行 Rabin--Miller测试.如果P通过测试,则另外产生一个随机 数a.再重新进行测试.选取较小的a值,以保证较快的计算 速度. 用同样的方法生成另外一个素数q后,我们就可以着 手于密钥的生成了.在国际标准中,所用的公钥固定为素数 65537,密钥的生成就是根据公钥和欧拉函数的值计算私钥 的过程,而私钥是利用欧几里德算法寻求公钥对于欧拉函 数的乘法逆元.欧几里德算法是数论的一项基本技术,它通 过一个简单的过程来确定两个正整数的最大公因子.扩展 的欧几里德算法不仅能确定两个正整数的最大公因子,如 果这两个数互素,还能确定它们各自的乘法逆元,扩展的欧 几里德算法如下. ExtendedEuclideanAlgorithm(d,,)算法 (1)(1.,x3)一(1,0,,),(1,Y2.Y3)一(1,0,); (2)if弘一0returnx3一gcd(d.,);noinverse (3)if弘一lretumya—gcd(d,;一d—lm.d,; (4)Q—Ix3/y3]; (5)(T1.r,2,)一(z1一Qy1,x2一Qy2,z3一@3); (6)(Xl,,x3).卜_(yl,Yz,); (7)(1,2,弘)一(T1,r,2,);(8)go1o(2) 3.2算法的实现 扩展的欧几里德算法的实现过程就是用C++语言定 义一个特殊的大数.并对运算中需要的各个运算符进行重 载,再实现这个特殊的大数的各项运算.假定A.B是参加 运算的两个大素数,其下标范围分别为,C是运算结果的数 值,其下标范围为. 1.加法 A=Data[/一n1downto0](A[]*0xl0000i) B:Data[-/一n2downtoO](B[]*0xl0000i)nl?n: C:Data[-/一ndownto0](c[]*0xl0~000i)= A+B 显然,c[]不是简单地等于A[-i]+B[]因为若c[] >Oxffff,则需要进位.当然,计算c[—1]时也可能产生 60凯里学院2007年l2月 了进位,故计算C[]时还要加上上次的进位值.若用c,fEi] 记录每次的进位.则有C[]一A[i]+B[]+cf[i—1]一 f/'[]*0xl0000.其中[一1]=0,.若A[]+B[]+cf[ — 1]>Oxfff.则[]一l;反之,则[=o.若[7J] 一 o.则"一,zl;反之,则71一"l+1. 2.减法 A—Data[i—mdownto0](A[]*0xl0000i) B=Data[i—mdownto0](B[]*0xl0000i)n】??t2 C—Data[i一"downto0](C[*0xl0000i)一A— B 显然,c[]不是简单地等于A[]一B[],因为若A[]< ]就需要借位.当然.计算cE;一1]时也可能产生了借 位,故计算c[i,1]时还要减去上次的借位值.若用cf[] 录每次的借位.则有:C[]一A[]一B[]一c_厂[i—1]+ []*0xl0000.其中,[一1]一0. 若Ab]>B[],则[]一o;反之,则cf[]一1.若 f[m]一o.则l,t—Hl—l;反之则:1. 3.乘法 A:Data[i—downto0](A[]*OxlO000i) B:Data[/:=2downtoO](B[i]*0xl0000i)l?y/2 C—Data[i一,zdownto0](c[]*0xl0000i)一 A*B 显然C—Data[/一ldownto0] (A*B[i]*0xl0000i),而 (A*B[]*0xl0000i)=Data[j—mdowntoO] (A[力*B[*0xl0000i(i+j)) 故C[]=Data[j=啦downtoO](一力)*B[力+ [)*0xl0000.其中,一1]一0, []=(Data[j—2downto0](A[i—])*B[力+c_厂[ — lJ)/*0xl0000,=l+啦一1. 若[]>0,则一+l,C[]=cf. 4.除法 A=Data[i—1downto0](AEi]*0xl0000i) B—Data[i—n2downto0](B[]*0xl0000i)nl?也 C=Data[/一"downto0](c[]*0xl0000i)一A/B 因无法将B对A"试商",我们只能转换成B[]对A[nj 的试商以得到一个近似值,故我们不能直接计算C.但是. 我们可以一步一步地逼近c.显然 (A[1]/13[-2]一1)*OxlO000(l一"2)<c 令X一0,重复:A=A一邶,z=z+(A[]/B[] 一 1)*0xl0000(1一,z2),直至0A<B,则有x=C. 注意:由于大救可理解为0xl0000进制.所以任意大数 A*0xl0000k都等价于将A的数组中的各元索左移位. 不必计算;类似的.除法则等价于右移若干位. 5.取模 A—Data[/一nldownto0](A[]*0xl0000i) B:Data[/=n2downtoO](B[]*0xl0000i)n1?,l2 C:Data[i="downto0](c[]*0xl0000i)一 AB 求模与求商的过程一一致,只是不需要记录商.故更加简 单.求模的具体过程如下:重复A=A一(A[瑚]/B[n], 1)*0xl0000(,,】一.)*B,直到A<B.则有A—C. 6.求逆元运算 RSA算法,常要在已知A,M的情况下,求B,使得 (A*B)M—1.这相当于求解B,N都是未知数的二元一 次不定方程A*B—M*N—l的最小整数解.而对于 一 by—l的最小整数解,有着名的欧几里德算法,即辗转 相除法可以实现,它是一种递归算法.比较容易理解. 7.Rabin-Miller算法 Rabin--Miller算法是目前检测素数最快的方法,具体 如下: (1)算奇数M,使得N一2M+l;(2)选择随机数A< M;(3)对于任意i<r.若A*2rMmodN=N—l,则N通 过随机数的测试;(4)或者,取AMmodN=l,则N通过随 机数的测试;(5)让A取不同的值对N进行5次测试,若全 部通过则判定N为素数. 若N通过一次测试,则N不是素数的概率为25%.若 N通过t次测试,则N不是素数的概率为l/4.事实上.取t 为5时,N不是素数的概率为1/128,N为素数的概率已经 超过了99.99%.在实际应用中.可首先用300,500个小 素数对N进行测试,以提高Rabin--MiLLer测试通过的概 率,从而提高测试速度.而在生成随机数时,选取的随机数 最好让r为0,则可省去上述步骤(3)的测试,进一步提高测 试速度. 8.加载随机预言模型 使用加载随机预言模型的RSA公钥密码体制,至此就 可以方便快速地使用上述算法使RSA密钥自动生成,并利 用公钥和私钥进行加密和解密了. ..结束语 本文提出了一种加载随机预言模型的RSA公钥密码 体制.这种体制有效地防止了攻击者的信息积累,而且提高 了加解密的效率,特别在加密大量消息的效率上更加明显, 这种方案在应用中有很大的实际意义.使用RSA算法进行 加密的关键在于找到两个足够大的素数,这样才能保证对 信息进行加密后的安全性.本文通过对素数生成和检测的 研究,找到了一种可以生成l000比特以上的密钥算法,使 RSA密钥的破解更具难度且可以快速实现.从而更有利于 RSA算法在电子商业中的广泛应用. 参考文献: [1]斯廷森(加).密码学原理与实践[M].2版.冯登国,译.北京: 电子工业出版社,2003. [2]杨明.密码编码学与网络安全一原理与实践[M].北京:电子工 业出版社,200.1. [3]BALLAREMandROGAWAYP.Randomoraclesarepracti— cal:aparadigmfordesigningefficientprotocols[C]//First ACMconferenceoncomputerandcommunications~ecurity. ACMPress,1993. [4]HWANGRj,SUFF,YEHYS,eta1.Anefficientdecryption methodforRSAcry【)IosysIemfJ].IEEECNF,2005,1. Is]ELSHENAWYH,SHABANK.ExtendedRSAcryptosystem anddigitalsignatureschemesinthedomainofgaussianinte? gers[J].IEEECNF,2002(1). [责任编辑:孟立霞]