《应用密码学第5章非对称密码体制课件》由会员分享，可在线阅读，更多相关《应用密码学第5章非对称密码体制课件（96页珍藏版）》请在金锄头文库上搜索。
1、,第5章非对称密码体制,5.1概述 5.2数学基础 5.3非对称密码体制概述 5.4RSA密码算法 5.5ElGamal密码算法 5.6椭圆曲线密码体制 5.7RSA、 ElGamal及椭圆曲线密码比较 5.8其他非对称密码体制简介,5.1概述通过前面的学习，我们对分组密码和序列密码都有了一定的了解。众所周知，两个用户在用对称密码体制进行保密通信时，必须要有一个双方共享的密钥。那么，如何才能让两个不在同一个地方的用户安全地拥有共享密钥呢？我们可能想到的方式有：（1）派一个人来传递；（2）通过邮件传递；（3）用电话或电报等方式传递。,首先我们要清楚，通过第三种方式传递是不安全的，因为在没有共享密
2、钥前，双方只能用明文的方式进行通信，显然是不安全的；第二种方式的时间需求比较大；第一种方式从时间和代价上来看，都难以符合需要。在非对称密码体制产生前，用得较多的解决办法就是第二种方式，但效率是比较低的。那么如何才能有效地解决这个问题，以用较小的代价、较高的效率实现通信双方的密钥传递呢？正是由于这个需求，促使了非对称密码体制的产生。,5.2数学基础,的解为：,例51韩信点兵。有兵若干，若列成5行纵队，则末行1人，若列成6行纵队，则末行5人，若列成7行纵队，则末行4人，若列成11行纵队，则末行10人，求兵数。解：由题意得,x1(mod 5)，x5(mod 6)，x4(mod 7)，x10(mod
3、11),5.2.2离散对数基于离散对数难题的密码学算法和应用比较多，从最开始的密钥交换算法DH(DiffieHellman)算法、ElGamal加密算法，到后来作为美国国家数字签名标准的DSA(DigitalSignatureAlgorithm)算法，后面介绍的Schnorr盲签名算法，以及很多特殊的签名算法，都是以离散对数难题为基础进行构造的。因此，掌握和理解离散对数的相关知识很重要。设p为奇素数，对于整数g，1gp，使得g?1(modp)成立的最小正整数如果是p-1,则g就是模p的原根。,5.2.4 勒让得符号设p为奇素数，a为整数，定义勒让得(Legendre)符号为：,若需对勒让得符号
4、的性质有更进一步的了解，读者可以参考其他有关初等数论的书籍。通过计算勒让得符号，容易判断二次方程x2a(modp)(p是奇素数)是否有解。,5.2.5素数的产生 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的拟素数。 由此可
5、知，如果对于整数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，使得1a
6、n-1bat(modn)ifb1(modn)then return(n是素数),结束fori=0tos-1if b-1(mod n)then return(n是素数),结束elsebb2(modn)return(n是合数),例54此例为判定合数为素数的例子，此处以n=25，a=7为例。取n=25，25-1=23*3，即s=3，t=3。由Miller-Rabin概率检测算法，得a=7318(mod 25)，i=0，b2=182-1(mod 25)输出：n是素数。实际上，25是合数。这时可以通过另选择一个a(1an-1)，(n，a)=1，如a=2，再次运行算法。,由Miller-Rabin概率检测
7、算法，得,b=238mod25 i=0, b2=82=6414(mod 25) i=1, b2=142=19621(mod 25) i=2, b2=212=44116(mod 25),循环完毕，输出：n是合数。 由此判断n肯定是个合数。 根据现有的研究成果，如果n是一个奇合数且能通过Miller-Rabin检测算法的概率不超过25%，可以通过多次选取a来运行算法，提高结果的准确性。对于奇数n，如果选择k个不同的a来运行算法，且返回的结果都是素数，则n是合数的可能性至多为4-k（即1/4k）。,5.2.6椭圆曲线由于椭圆曲线在因数分解上的应用，以及在椭圆曲线上建立的公钥密码系统的效率较基于因数分
8、解的RSA类和基于离散对数的ElGamal类的公钥算法要高，而且密钥长度短，因而受到了研究者的密切关注。,1椭圆曲线的定义椭圆曲线是指由Weierstrass方程：y2+a1xy+a3y=x3+a2x2+a4x+a6所确定的曲线。在公钥密码学中，主要用到两种椭圆曲线：（1）素域Fp(p3)上的椭圆曲线，可以表示为：,y2=x3+ax+b,其中a、b为整数，其判别式4a3+27b20。,（2）域F(2n)(n1)上的椭圆曲线，可以表示为：,y2+xy=x3+ax2+b,下面的介绍以第一种椭圆曲线为主。图51是y2=x3+x+6所表示的曲线，该图可以用MATLAB实现。显然该曲线关于x轴对称。,图
9、51y2=x3+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所示
10、。,设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。通过把直线方程代入椭圆曲线方程，可以求得第三个交点的坐
11、标，取第三个点关于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)由以下规则确定：,其中，,5.2.7有限域上的椭圆曲线有
12、限域GF(p)上的椭圆曲线是由方程：,定义的曲线，简单表示为Ep(a，b)。,其他的点可以按这个方式求出。由上可知，该椭圆曲线上一共有12个点。这12个点的分布如图53所示。图中左下标的起点是(0，0)点。对于同一条椭圆曲线y2=x3+ax+b，p取不同的值，点的分布也不同。通过比较y2=x3+x+6在平面上的曲线（见图51所示）和y2x3+x+6(mod11)在平面上的点（如图53所示），直观感觉没有太多的联系。对于同一条椭圆曲线，在不同的有限域上（即p取不同的值），点的个数是有差别的，当p很大时，虽然离散点的个数是确定的，但是离散点的分布情况看上去也没有什么规律。,图53y2x3+x+6(
13、mod11)在平面上的点,以y2x3+x+6(mod11)为例子，选取P=(2，7)，计算2P。首先计算：,k=(322+1)(27)-1 mod 118,于是,x3=82-2-2 mod 115 y3=8(2-5)-7 mod 112,因此，2P=(5，2)。,再计算,3P=2P+P=(5,2)+(2,7),首先计算,k=(7-2)(2-5)-1 （mod 11）2,于是，,x3=22-5-2 mod 118 , y3=2(5-8)-2 mod 113,因此，3P=(8，3)。 计算完毕后，可以通过把2P=(5，2)，3P=(8，3)代入到y2x3+x+6(mod11)中验证等式成立否，如果
14、不成立，则要检查计算过程的错误。,5.3非对称密码体制概述5.3.1非对称密码体制的原理在对称密码体制中，除了加密及解密算法是公开的外，一个重要的特点是加密算法与解密算法的密钥相同，或者容易从其中一个得到另一个，这要求通信双方要有共享的加密密钥。那么，可不可以出现下面的情况呢？,假设有一种挂锁，在没有锁上的情况下，任何人都可以轻松锁上。但锁上后，只有有该锁的钥匙的人，才可以用钥匙打开该锁。假设Alice把她的这种挂锁放到邮局，则任何想与她秘密通信的人都可以把消息放到一个箱子里，然后用挂锁锁上箱子，寄给Alice。由于只有Alice有开锁的钥匙，故只有Alice能打开箱子。这个流程可以用图54表
15、示。,图54Alice开锁示意图,图55非对称密码体制的模型图,根据图55所示的模型，利用非对称密码体制进行保密通信的过程可描述为：（1）主体B若需要其他主体利用非对称密码体制向他发送秘密消息，先要生成一对密钥，其中一个用于加密，另一个用于解密。用于加密的密钥在非对称密码体制中称为公开密钥，也称公开钥或公钥，是不需要保密的。B的公开密钥通常表示为PKB(PublicKeyofB)。用于解密的密钥称为秘密密钥，简称秘密钥或私钥，需要解密方严格保密。B的秘密密钥通常表示为SKB(SecretKeyofB)。在知道密码算法和公开密钥的情况下，要得到秘密密钥在计算上是不可行的。,（2）A若要向B发送秘
16、密消息m(message)，先要获取B的加密密钥，计算C=EPKB(m)，得到消息m对应的密文C(Cipher)，然后把C发送给B。其中C表示加密消息得到的密文，E(Encrypt)表示对消息进行加密的算法。EPKB(m)表示用加密算法E和公开密钥PKB对消息m进行加密。,5.3.2非对称密码体制的设计准则现在应用的非对称密码体制，其安全是指计算上是安全的。以著名的RSA算法所基于的大数分解难题为例，它假定n=pq是两个大素数的乘积，现在一般认为，p和q的长度都是512比特左右，则n的长度是1024比特左右。以人们现有的计算能力，在知道n的情况下，在短时间内是不能分解n的，也就是说，这在计算上是安全的。从理论上讲，如果有足够的计算能力，是可以分解n的。但如果分解n的时间超过了消息的保密期，或者投入的物力超过了消息本身的价值，对消息保密的目的就达到了。,一个密码算法要进入实用阶段，除了在理论上是安全的，在使用过程中，比如用到电子商务中，在投入上应该是商家能够接受的；对用户来说，接受商家的服务，无论是由于网络的原因，还是算法计算需要时间的
