应用密码学第5章非对称密码体制

单击此处编辑母版标题样式,第5章非对称密码体制,第5章非对称密码体制,5.1概述,5.2数学根底,5.3非对称密码体制概述,5.4RSA密码算法,5.5ElGamal密码算法,5.6椭圆曲线密码体制,5.7RSA、 ElGamal及椭圆曲线密码比较,5.8其他非对称密码体制简介,5.1概述通过前面的学习，我们对分组密码和序列密码都有了一定的了解。众所周知，两个用户在用对称密码体制进行保密通信时，必须要有一个双方共享的密钥。那么，如何才能让两个不在同一个地方的用户平安地拥有共享密钥呢？我们可能想到的方式有：1派一个人来传递；2通过邮件传递；3用 或电报等方式传递。,首先我们要清楚，通过第三种方式传递是不平安的，因为在没有共享密钥前，双方只能用明文的方式进行通信，显然是不平安的；第二种方式的时间需求比较大；第一种方式从时间和代价上来看，都难以符合需要。在非对称密码体制产生前，用得较多的解决方法就是第二种方式，但效率是比较低的。那么如何才能有效地解决这个问题，以用较小的代价、较高的效率实现通信双方的密钥传递呢？正是由于这个需求，促使了非对称密码体制的产生。,5.2数学根底,的解为：,例51韩信点兵。有兵假设干，假设列成5行纵队，那么末行1人，假设列成6行纵队，那么末行5人，假设列成7行纵队，那么末行4人，假设列成11行纵队，那么末行10人，求兵数。解：由题意得,x,1(mod 5)，,x,5(mod 6)，,x,4(mod 7)，,x,10(mod 11),离散对数基于离散对数难题的密码学算法和应用比较多，从最开始的密钥交换算法DH(DiffieHellman)算法、ElGamal加密算法，到后来作为美国国家数字签名标准的DSA(DigitalSignatureAlgorithm)算法，后面介绍的Schnorr盲签名算法，以及很多特殊的签名算法，都是以离散对数难题为根底进行构造的。因此，掌握和理解离散对数的相关知识很重要。设p为奇素数，对于整数g，1gp，使得g?1(modp)成立的最小正整数如果是p-1,那么g就是模p的原根。,5.2.4 勒让得符号,设,p,为奇素数，,a,为整数，定义勒让得(Legendre)符号为：,假设需对勒让得符号的性质有更进一步的了解，读者可以参考其他有关初等数论的书籍。通过计算勒让得符号，容易判断二次方程x2a(modp)(p是奇素数)是否有解。,素数的产生 1.Miller-Rabin概率检测算法Miller-Rabin概率检测算法的理论根底是费尔马定理，即设n是正奇整数，如果n是素数，由费尔马定理，对于任意整数b(1bn-1)，有bn-11(mod n)。如果n是素数，该等式一定成立；如果n不是素数，该等式一般不成立。如果n不是素数而又使得该等式成立，称n为对于基b的拟素数。拟素数表示不是素数，而是合数。整数63是合数，当b=8时，该等式成立，称整数63是对于基b=8的拟素数。 由此可知，如果对于整数b(1bn-1)，(n,b)=1,使得 bn-11(modn)不成立，那么n是一个合数。,由上面的讨论可知，判断一个正奇整数是不是合数，可以通过尝试找整数b(1bn-1)，(n,b)=1,看bn-11(modn)成立与否。如果不成立，那么n是一个合数，如果成立，那么n可能是素数，可以通过再找别的整数b(1bn-1)进行尝试。根据上面的论述，Miller-Rabin概率检测算法的实现思路可以描述为：计算n-1=2st，那么有,根据这个原理，Miller-Rabin概率检测算法可描述如下：MillerRabin(n)/把n-1写成n-1=2 st，其中t是一个奇数，选取随机整数a，使得1an-1bat(modn)ifb1(modn)then return(n是素数),结束fori=0tos-1if b-1(mod n)then return(n是素数),结束,elsebb,2,(modn),return(n是合数),例54,此例为判定合数为素数的例子，此处以n=25，a=7为例。取,n,=25，25-1=2,3,*3，即,s,=3，,t,=3。由Miller-Rabin概率检测算法，得,a,=7,3,18(mod 25)，,i,=0，,b,2,=18,2,-1(mod 25)输出：,n,是素数。实际上，25是合数。这时可以通过另选择一个,a,(1,a,3)上的椭圆曲线，可以表示为：,y,2,=,x,3,+,ax,+,b,其中,a,、,b,为整数，其判别式4,a,3,+27,b,2,0。,2域F(2n)(n1)上的椭圆曲线，可以表示为：,y,2,+,xy,=,x,3,+,ax,2,+,b,下面的介绍以第一种椭圆曲线为主。图51是,y,2,=,x,3,+,x,+6所表示的曲线，该图可以用MATLAB实现。显然该曲线关于,x,轴对称。,图51,y,2,=,x,3,+,x,+6所表示的曲线,2椭圆曲线的加法现在定义椭圆曲线的加法。在椭圆曲线所在的平面上，定义一个称为无穷远点的元素，记为O，把它定义为加法的单位元。也即椭圆曲线上的点P和它相加：P+O=P。椭圆曲线的加法定义如下：如果椭圆曲线上的3个点位于同一直线上，那么这三个点的和为O。 设P和Q是椭圆曲线上x坐标不同的两个点，R=P+Q定义为：画一条通过P, Q的直线与椭圆曲线交于P1, 由加法的定义：P +Q+ R1=O。那么P+Q =- R1=R，参看示意图5-2。点P的倍点定义为：过P点做椭圆曲线的切线，设与椭圆曲线交于R1, 那么P+P+ R1=O, 故2P=-R1=R。参看示意图5-2所示。,设P和Q是椭圆曲线上x坐标不同的两个点，R=P+Q定义为：画一条通过P、Q的直线与椭圆曲线交于R1，由加法的定义：P+Q+R1=O，那么P+Q=-R1=R，参看示意图52(a)。点P的倍点定义为：过P点做椭圆曲线的切线，设与椭圆曲线交于R1，那么P+P+R1=O，故2P=-R1=R。参看示意图52(b)。 对于上述加法，可以通过以下方式理解。设椭圆曲线的方程为y2=x3+ax+b，椭圆曲线上有点P(x1，y1)，Q(x2，y2)，如图52(a)所示。那么过P和Q点的直线的斜率为k=(y2-y1)/(x2-x1)，该直线可以表示为y=kx+c。通过把直线方程代入椭圆曲线方程，可以求得第三个交点的坐标，取第三个点关于x轴的对称点即为所求。,对于倍点运算，那么通过P(x1，y1)点做椭圆曲线的切线，如图52(b)所示，该切线的斜率可以用如下方法求得。对y2x3+ax+b两边求导数得：,通过,P,点的椭圆曲线的切线就可以表示为,y,=,kx,+,c,，通过把直线方程代入椭圆曲线方程，可以求得直线与椭圆曲线的另一个交点的坐标，取该点关于,x,轴的对称点即为所求。,图52,椭圆曲线的加法示意图,通过以上推导，可以得出椭圆曲线y2=x3+ax+b上的点的加法运算规那么，这个规那么可以定义为： 设P=(x1,y1)，Q=(x2,y2)，P-Q，那么P+Q=R(x3,y3)由以下规那么确定：,x,3,k,2,-,x,1,-,x,2,y,3,k,(,x,1,-,x,3,)-,y,1,其中，,有限域上的椭圆曲线,有限域GF(,p,)上的椭圆曲线是由方程：,定义的曲线，简单表示为,E,p,(,a,，,b,)。,其他的点可以按这个方式求出。由上可知，该椭圆曲线上一共有12个点。这12个点的分布如图53所示。图中左下标的起点是(0，0)点。对于同一条椭圆曲线y2=x3+ax+b，p取不同的值，点的分布也不同。通过比较y2=x3+x+6在平面上的曲线见图51所示和y2x3+x+6(mod11)在平面上的点如图53所示，直观感觉没有太多的联系。对于同一条椭圆曲线，在不同的有限域上即p取不同的值，点的个数是有差异的，当p很大时，虽然离散点的个数是确定的，但是离散点的分布情况看上去也没有什么规律。,图53,y,2,x,3,+,x,+6(mod11)在平面上的点,以,y,2,x,3,+,x,+6(mod11)为例子，选取,P,=(2，7)，计算2,P,。首先计算：,k,=(322+1)(27)-1 mod 118,于是,x,3,=8,2,-2-2 mod 115,y,3,=8(2-5)-7 mod 112,因此，2,P,=(5，2)。,再计算,3,P,=2,P,+,P,=(5,2)+(2,7),首先计算,k=(7-2)(2-5)-1 mod 112,于是，,x,3,=22-5-2 mod 118 ,y,3,=2(5-8)-2 mod 113,因此，3P=(8，3)。,计算完毕后，可以通过把2P=(5，2)，3P=(8，3)代入到y2x3+x+6(mod11)中验证等式成立否，如果不成立，那么要检查计算过程的错误。,5.3非对称密码体制概述,非对称密码体制的原理,在对称密码体制中，除了加密及解密算法是公开的外，一个重要的特点是加密算法与解密算法的密钥相同，或者容易从其中一个得到另一个，这要求通信双方要有共享的加密密钥。那么，可不可以出现下面的情况呢？,假设有一种挂锁，在没有锁上的情况下，任何人都可以轻松锁上。但锁上后，只有有该锁的钥匙的人，才可以用钥匙翻开该锁。假设Alice把她的这种挂锁放到邮局，那么任何想与她秘密通信的人都可以把消息放到一个箱子里，然后用挂锁锁上箱子，寄给Alice。由于只有Alice有开锁的钥匙，故只有Alice能翻开箱子。这个流程可以用图54表示。,图54Alice开锁示意图,图55非对称密码体制的模型图,根据图55所示的模型，利用非对称密码体制进行保密通信的过程可描述为：1主体B假设需要其他主体利用非对称密码体制向他发送秘密消息，先要生成一对密钥，其中一个用于加密，另一个用于解密。用于加密的密钥在非对称密码体制中称为公开密钥，也称公开钥或公钥，是不需要保密的。B的公开密钥通常表示为PKB(PublicKeyofB)。用于解密的密钥称为秘密密钥，简称秘密钥或私钥，需要解密方严格保密。B的秘密密钥通常表示为SKB(SecretKeyofB)。在知道密码算法和公开密钥的情况下，要得到秘密密钥在计算上是不可行的。,2A假设要向B发送秘密消息m(message)，先要获取B的加密密钥，计算C=EPKB(m)，得到消息m对应的密文C(Cipher)，然后把C发送给B。其中C表示加密消息得到的密文，E(Encrypt)表示对消息进行加密的算法。EPKB(m)表示用加密算法E和公开密钥PKB对消息m进行加密。,非对称密码体制的设计准那么现在应用的非对称密码体制，其平安是指计算上是平安的。以著名的RSA算法所基于的大数分解难题为例，它假定n=pq是两个大素数的乘积，现在一般认为，p和q的长度都是512比特左右，那么n的长度是1024比特左右。以人们现有的计算能力，在知道n的情况下，在短时间内是不能分解n的，也就是说，这在计算上是平安的。从理论上讲，如果有足够的计算能力，是可以分解n的。但如果分解n的时间超过了消息的保密期，或者投入的物力超过了消息本身的价值，对消息保密的目的就到达了。,一个密码算法要进入实用阶段，除了在理论上是平安的，在使用过程中，比方用到电子商务中，在投入上应该是商家能够接受的；对用户来说，接受商家的效劳，无论是由于网络的原因，还是算法计算需要时间的原因，所等待的时间是要可以容忍的，密码算法的使用是透明的，因为不可能每个用户都去掌握密码理论。只有这样，这个算法投入商业使用才会有市场。,非对称密码体制的分类经过三十多年的研究和应用，非对称密码体制的研究取得了很大的进展，研究者们创立了多种不同的密码算法。通常，对非对称密码体制的分类，是根据其所基于的数学根底的不同，主要分成如下几类。1基于大数分解难题的，包括RSA密码体制、Rabin密码等。在理论上，RSA的平安性取决于大数因子分解的困难性，但在数学上至今还未证明分解模n就是攻击RSA的最正确方法，也未证明分解大整数就是NP问题，可能有尚未发现的多项式时间分解算法。以大数分解难题为数学根底的密码理论应用，还包括后面要提到的RSA数字签名、RSA盲签名以及FiatShamir身份认证方案等。,2基于离散对数难题的，如ElGamal密码，有限域上的离散对数问题的难度和大整数因子分解问题的难度相当。基于离散对数难题的最著名的算法是NIST于1994年通过的数字签名标准(DSS)中使用的数字签名算法DSA，它是ElGamal签名的变形。3基于椭圆曲线离散对数的密码体制，严格说来，可以归于基于离散对数难题的密码体制中。不过由于有限域上的椭圆曲线有它的一些特殊性，故人们往往把它单独归为一个类别。,另外，颇受关注的还有NTRU，它是建立在网格中寻找最短向量的数学难题的根底上的，而且具有一些比较好的性质。目前，美国IEEE标准化组织正在起草专门针对NTRU的标准P1363.1，并取得了较大的进展。除了上述的公钥密码体制外，人们研究的还有基于背包问题的MH背包体制，基于代数编码理论的MeEliece体制，基于有限自动机理论的公钥密码体制，基于双线性配对技术的公钥密码体制等。从目前看，这些密码体制还没有投入广泛使用。,5.4RSA密码算法 RSA开展简史1976年，Diffie和Hellman发表了非对称密码的奠基性的论文密码学的新方向，建立了公钥密码的概念。1978年，麻省理工学院的Rivest、Shamir和Adleman在他们的论文“获得数字签名和公钥密码系统的一种方法中，实现了Diffie和Hellman提出的思想的一种算法，简称RSA算法，即为三个人的名字的首字母的缩写。据英国政府声称，他们在切尔特汉姆的政府通信总部很早就创造了公开密钥密码术。这个最高机密的密码术是由战后的布莱切里庄园的余部创造的。在那里，Ellis于1969年提出了与Diffie和Hellman相类似的非对称密码的思想，1973年，Cocks提出了与RSA算法一致的公钥密码体制。,从RSA算法的产生到现在，密码学家对算法的平安性进行了广泛的研究和讨论，并在实践中有了广泛的应用。后面介绍的数字签名算法和身份认证算法中，基于大数分解难题的算法也是以RSA算法为根底的。,2加密如果发送方想发送需要保密的消息m给Bob，就选择Bob的公钥e，n，然后计算Cmemodn，最后把密文C发送给接收方Bob。,3解密,接收方Bob收到密文C，根据自己掌握的私钥计算,m,C,d,(mod,n,)。所得结果,m,即为发送方欲发送的消息。把该算法放入保密通信模型中，可以有如图56所示的保密通信示意图。,图56保密通信示意图,对算法的几点说明如下：1对算法的理解要放到保密通信模型中去。开始学习时，读者容易陷入去记忆和理解算法而无视了算法应用的背景。2按现在的计算能力，大素数p和q的大小按二进制计算长度应该在512比特左右，且p和q只相差几个比特。关于这一点，后面还有说明。3大素数p和q是奇数，(n)=(p-1)(q-1)是偶数，故e一定是奇数。4因为满足gcd(n)，e)=1，即(n)与e互素，故e模(n)的逆一定存在，可以通过扩展欧几里德算法求得。,5加密的时候，要求明文m要小于n。因假设mn，由于计算时使用了模运算，那么不能通过解密算法正确求得明文m，只能得到比n小且与mmodn同余的整数。6至于密钥生成过程中的p、q、(n)，一般的说法是平安地销毁。由孙子定理，p、q也可用于提高RSA算法的解密速度。7这里介绍的只是理论上的RSA，在实践中使用RSA算法时，还有一些本卷须知，请关注后面的讨论。8在公钥密码体制中，通常认为公钥具有较长的使用周期，如一年或者三五年，就像学生证或者工作证一样，在一定时间内可以认为代表了公钥持有者的身份。,RSA算法举例例56在RSA算法密钥产生过程中，设p=13，q=23，取公钥e29，那么私钥d可以用欧几里德扩展算法求出。由可得,n=pq=13*23=299,(n)=(p-1)(q-1)=12*22=264,264=29*9+329=3*9+23=2+11=3-2 =3-(29-3*9) =3*10-29 =(264-29*9)*10-29 =264*10-29*91 =-91173(mod264)由欧几里德扩展算法可得：d为173。,1加密过程：设RSA算法的参数选择如上所述，那么消息m=9时所对应的密文的计算过程为929(mod299)211。2解密过程：211173(mod 299)9。这个过程可以采用平方乘算法或者模重复平方算法进行运算。在完成算法运算的过程中，要把这个过程放到保密通信模型中去理解如图57所示，清楚加密方发送方知道哪些信息，解密方接受方知道哪些信息，这有助于对算法的理解，以及对公钥密码体制的理解。读者刚开始学习算法时，容易对那么大的计算量产生畏惧心理，从而无视了把算法放到保密通信模型中去理解它的应用。实际上，用任何一种编程语言比方C语言去实现上面的计算，都是非常简单的事情。,图57保密通信模型例如,RSA算法的平安性及常用攻击通过对RSA算法的学习，我们可以看到，因为e，n为公开密钥，破解RSA算法最直接的方法就是分解n，计算n=pq，(n)=(p-1)(q-1)，通过de1(mod(n)求出d。所以说，RSA算法的平安性是基于分解大整数的难题的。随着科学技术的不断开展和人类计算能力的提高，大整数分解的理论和实现也取得了很大进展。RSA155即n为155位的十进制，约512比特于1999年8月被成功分解，得到两个78位的十进制素数。因此在使用RSA的时候，要注意密钥的大小，现在使用的RSA的n的长度一般是1024比特，估计在未来一段比较长的时间里，n的长度为2048比特是平安的。,除此之外，为保证算法的平安性，还有一些要求。1p与q的差值要大。比方要求n为1024比特时，p与q的大小都为512比特左右，最好相差几个比特，如p取508比特，q取516比特。下面给出证明以较小的整数为例，说明为什么p与q的差值要大。设q-p=k，那么,(,q,+,p,),2,-(,q,-,p,),2,=4,pq,=4,n,，,(,q,+,p,),2,= (,q,-,p,),2,+4,n,=,k,2,+4,n,如果k的值小，由于n的值，那么可以容易找到这样的k，使得k2+4n是一个完全平方数，从而得出q+p和q-p的值，联立求解可得到q和p。,RSA算法的实现在RSA算法的实现过程中，参考文献，需要考虑以下的问题：(1)如何判定一个大的整数是不是素数，产生素数困难吗？(2)指定长度的素数个数是有限的，当有很多人使用RSA算法时会不会发生两个人使用同一个素数的情况？(3)从RSA算法可以看到，算法中的主要运算都集中在指数运算以及模运算上。如何有效提高这两种运算，以加快算法的加解密速度。另外，具体实现RSA算法时，还要参考RSA的加密标准(PKCS#1，IEEEP1363)，可以提高算法加密的平安性。,定理52小于n的素数的总数近似为n/(ln n)，这个结论称为素数个数定理。1答复大整数是否为素数的判定，及产生素数是否困难的问题。大整数是否为素数的判定可以参考节。由素数个数定理，如果在1N之间任取一个数，其为素数的概率为1/ln N，如果取N2512，约为10160，那么1/lnN约为1/355，如果再去掉2、3、5、7等的倍数，尝试的次数就不会很多了。,2答复大素数个数的估计问题。通过一个简单的例子，可以明白大素数的个数是十分庞大的资源，不用担忧会被用完。,例58小于10,100,的素数个数,x,大概为多少？由素数个数定理，,因,ln10,100,log,2,10,100,=100*log,2,10100*4=400,可以看到，这是非常可观的数量。事实上，素数的分布是数字越大越稀，所以没有上面估计的这么乐观，但也没有必要杞人忧天到去担忧是不是会用完的这种状况。,3加速运算的方法问题。在实现RSA算法时，在提高指数运算速度上，可以采用模重复平方计算法，或者平方乘算法。在具体实现时，还常采用蒙哥马利算法来提高模乘运算的速度。由于蒙哥马利算法不容易理解，这里从略。模重复平方计算法和平方乘算法这两种算法的实现思路、时间和空间代价等相似，这里只介绍平方乘算法。 求am可如下进行，其中a、m是正整数：将m表示为二进制形式bkbk-1b0，即,因此,例5-9：,求9726,3533,mod11413,解：,3533,2,计算过程如下：,由上表可以看到，在计算过程中，如果使用简单循环来实现，需要执行3533次循环，即3533次乘法和模运算。用平方乘算法，循环的次数只有12次，最多只需要执行12次平方、12次乘法和模运算，计算量大大减少。在上面的例子中，由于9726的平方是在现在计算机能够表示的范围内，所以用任何编程语言可以轻松完成。在实际使用时，RSA算法中模数n的大小，我们前面提到过，大约有1024位，十进制大约为300位。有的编程语言比方Java提供了大整数的相关函数，实现比较容易，但如果使用C语言，完全自己编程实现，那就要麻烦许多。,5.5ElGamal密码算法,对于刚涉及密码学理论的读者需要注意的是，不同书籍中的Shanks算法表述略有不同，应适当注意其中的差异，但本质都是一样的。我们来理解一下为什么这个算法称为大步小步法。序列(yr，r)，r=0，1，s-1“走的是小步，从y处开始“走，紧邻的两步的比值为，“走的总长度为s；而序列(ts，s)，t=1，2，s“走的是大步，从0点开始“走，紧邻的两步的比值为s。在经过适当的步数后，两个序列会“踩在同一个“脚印上，由此可以解出x的值。不过我们也应该看到，这个算法的代价还是很高的，因为两个序列的循环次数都是p0.5。实践应用中，p的取值通常都是512比特左右，所以用这个算法对于离散对数问题构不成威胁。,5.6椭圆曲线密码体制椭圆曲线密码体制简介椭圆曲线密码体制在1985年提出。从1998年起，一些国际标准化组织开始了对椭圆曲线密码的标准化工作，1998年IEEEP1363工作组正式将椭圆曲线密码写入了当时正在讨论制定的“公钥密码标准的草稿。椭圆曲线密码算法在与RSA算法相同平安性的情况下，其密钥较短，160比特长的密钥相当于RSA算法密钥长为1024比特的平安性，因而有利于容量受限的存储设备如智能卡等在平安领域的使用。,椭圆曲线上的ElGamal密码体制下面描述在椭圆曲线上实现ElGamal密码系统的算法。先由系统选取一条椭圆曲线，该椭圆曲线上的点形成了循环群E，GE是椭圆曲线上的一个点，N是点G在循环群E的阶，即NG=OO为单位元。用户选择一个整数a，0aN，计算=aG，a保密，但将公开。即a，G是私钥，G是公钥，所选择的椭圆曲线也是公开的。,假定把明文消息m嵌入到群E的点Pm上。当消息发送者欲向A发送m，可求得一对数偶(C1 , C2)，其中C1= kG , C2= Pm+k,k是随机产生的整数。A收到(C1 , C2)后，计算C2-aC1得到消息Pm，因为C2-aC1=(Pm+k)a(kG)= Pm.可以看到，如同ElGamal密码体制一样，它也是一个不确定性算法，对于一个消息m，加密过程中k的选取不一样，那么加密所得的密文也不同。另外，该密码体制也有密文“信息扩展问题。可以看到，如同ElGamal密码体制一样，它也是一个不确定性算法，对于一个消息m，加密过程中k的选取不一样，那么加密所得的密文也不同。另外，该密码体制也有密文“信息扩展问题。,于是,x,3,=8,2,-2-2 mod 115,y,3,=8(2-5)-7 mod 112,因此，2,r,=(5，2)。,再计算3,r,=2,r,+,r,=(5，2)+(2，7)，首先计算：,k,=(7-2)(2-5)-1 mod 112,于是,x,3,=22-5-2 mod 118,y,3,=2(5-8)-2 mod 113,因此，3,r,=(8，3)。,类似地，还可以计算出,nr,，,n,1，计算结果如下：,因此，,r,=(2，7)是E的生成元，,E,是一个循环群。,由上面的讨论，可以确定,E,中的所有点，但这只是在例题中，实际应用中，由于给定的椭圆曲线上的点数太多，无法完全列举E中所有的点，也没有必要列举E中所有的点。,例513,假设选取,r,=(2，7)，B的私钥是7，有,=7,r,=(7，2)。加密运算是：,解密运算是：,d,(,c,1,c,2,)=,c,2,-7,c,1,假设,A,要加密明文,m,=(10，9)(这是E上的一个点)，如果随机选择,k,=3，A计算,c,1,=3,r,=3(2,7)=(8,3),c,2,=m+3=(10,9)+3(7,2)= (10,9)+(3,5),=9r+8r=17r=4r=(10,2),于是恢复了明文。,5.7RSA、ElGamal及椭圆曲线密码比较RSA密码体制是基于大数分解难题的，出现的时间是20世纪70年代，到现在已经30多年了。经过比较长时间的使用和学者们的研究，从算法和计算角度看是平安的，只是随着人类计算能力的提高，RSA算法中选取的参数(p，q)越来越大，现在普遍认为，n=pq的取值为2048比特是平安的，这相当于600位的十进制整数。这也导致了加解密的运算量和存储空间的增加，影响了其在便携产品如 、PDA等中的使用。,国际上一些标准化组织ISO、ITU及SWIFT等均已接受RSA体制作为标准。在Internet中所采用的PGP中也将RSA作为传送会话密钥和数字签字的标准算法。由于RSA是简单且比较成熟的一种公钥密码体制，故许多公司及研究团体都对它进行了实现。ElGamal密码体制是基于离散对数难题的，很多密码算法如著名的密钥交换算法DH(DiffieHellman)，以及后面学到的美国的数字签名标准DSA就是基于离散对数问题的。ElGamal密码体制在加密的时候要完成两次模幂运算，密文的长度是消息长度的两倍，这在一定程度上影响了其广泛使用。,椭圆曲线密码是ElGamal密码体制在椭圆曲线上的应用，优点是在同等平安程度下，其密钥比RSA和ElGamal要短得多。由现有的资料可知，ECC的密钥长度为160比特时的平安强度与RSA的密钥长度为1024比特时相当，这对于存储和通信带宽受限时的应用是一个很重要的优点，比方PDA、IC卡、无线设备等，而且160比特的ECC的运算速度比1024比特的模运算快。基于椭圆曲线离散对数的加密算法和签名算法被很多标准采用。,5.8其他非对称密码体制简介除了前面介绍的基于大数分解难题的RSA密码算法、基于离散对数难题的ElGamal密码算法和基于椭圆曲线离散对数难题的椭圆曲线密码算法外，在密码学的开展历史上，还有一些其他的非对称密码算法，对于非对称密码体制的开展产生了重大影响。1背包算法。公钥密码体制的第一个算法是由Mercle和Hellman开发的背包算法，其平安性基于背包难题，这是一个NP完全问题。尽管这个算法后来发现是不平安的，但由于它证明了如何将NP完全问题用于公钥密码学，故在公钥密码学的开展史上有过重大的影响。,2Rabin算法。这个方案的平安性基于求合数的模平方根的难度，等价于因子分解问题。3McEliece算法。该算法由McEliece在1978年提出，是一种基于代数编码理论的公开密钥密码系统。其思想是构造一个Goppa码并将其伪装成普通的线性码。不过该算法的公开密钥太庞大，加密后的密文长度为明文的两倍，这在一定程度上影响了它的广泛应用，故而研究的人也比较少。 4基于有限自动机的公钥密码算法。这是由中国密码学家陶仁冀提出的，该算法基于有限自动机理论。如同分解两个大素数的乘积很困难一样，要分解两个有限自动机的合成也很困难。,除了这些公钥密码算法外，近年来，学者们又相继提出了其他的非对称密码体制。如NTRU、基于辫群的密码体制、量子密码体制等，也受到了研究者们的广泛关注。由于NTRU有非常多的优点，故研究者对NTRU甚为亲睐。关于量子密码体制，请参看本书后面章节，这里只是简单介绍NTRU。NTRU(NumberTheoryResearchUnit)算法是一种新的公钥密码体制，它是在1996年的美洲密码学会上由Brown大学数学系的三位美国数学家JeffreyHoffstein、JillPipher和JosephH.Silverman提出的。,经过十多年的迅速开展与完善，该算法在密码学领域受到了高度的重视。自2000年开始，美国IEEE标准化组织起草专门针对NTRU的标准P1363.1。NTRU算法的平安性基于多项式、不同模混合运算的相互作用和从一个非常大的维数格中寻找最短向量的困难性。对现有的RSA、DSA等公钥密码体制而言，由于涉及到大数的模幂运算，此运算所需存储空间大、速度慢。NTRU只使用了简单的模乘法和模求逆运算，因而它具有密钥产生容易，加、解密速度快等特点。就目前来说，NTRU的平安性和目前最有影响的RSA算法、椭圆曲线密码体制(ECC)等算法是一样平安的，且具有与RSA同等程度的平安性，能抵抗量子运算攻击。,