双钥密码体制(二)精读.pptx

网络安全—技术与实践（第2版）刘建伟王育民编著清华大学出版社普通高等教育“十一五”国家级规划教材教育部2011年精品教材课件制作人声明本课件总共有17个文件，版权属于刘建伟所有，仅供选用此教材的教师和学生参考。本课件严禁其他人员自行出版销售，或未经作者允许用作其他社会上的培训课程。对于课件中出现的缺点和错误，欢迎读者提出宝贵意见，以便及时修订。课件制作人：刘建伟2012年2月8日双钥密码体制（第2讲）椭圆曲线密码体制双钥密码体制（第2讲）椭圆曲线密码体制一、Diffie-Hellman密钥交换1976年Diffie和Hellman发明了DH算法，该算法是一个公开密钥算法，其安全性源于在有限域上计算离散对数比计算指数更为困难。DH算法用于密钥分配，但不能用于加密或解密。DH算法已经申请美国和加拿大的专利，目前该专利已经到期。DH算法容易受到中间人攻击。Diffie-Hellman密钥分配方案两个通信主体Alice和Bob，希望在公开信道上建立共享密钥选择一个大素数p(～200digits)一个生成元aAlice选择一个秘密钥(privatekey)xApBob选择一个秘密钥(privatekey)xBpAliceandBob计算他们的公开密钥:yA=axAmodp，yB=axBmodpAlice,Bob分别公开yA,yB共享密钥的生成计算共享密钥：KAB=axA.xBmodp=(yAxB)modp(whichBcancompute)=(yBxA)modp(whichAcancompute)KAB可以用于对称加密密钥不能用于加密任意消息；可以建立共享密钥基于有限域上的指数问题安全性是基于计算离散对数的困难性Diffie-Hellman应用的问题双钥密码体制（第2讲）椭圆曲线密码体制二、Rabin公钥密码体制1979年，Rabin利用合数模下求解平方根的困难性构造了一种安全的公钥体制。Rabin公钥体制已经被证明：对该体制的破译的难度等价于大整数分解。Rabin体制是RSA的一种特例，它有以下两个特点：RSA中选取的公开钥e满足1＜e＜φ(n)，且gcd(e,φ(n))=1。而Rabin体制则选择e=2。2.1密钥的产生2.随机选择两大素数p,q1.Rabin体制则选择e=24.n,e作为公钥5.p,q为私钥3.计算：n=p×q满足p≡q≡3mod4即这两个素数的形式为：4k+3（k为整数）2.2Rabin加密过程2.3Rabin解密过程A解密就是求c的模n平方根，即解x2≡cmodn；由中国剩余定理可知，解以上方程等价于解方程组：由于p≡q≡3mod4，可以很容易求出方程组的解：经过组合可以得到4个同余方程组：2.3Rabin解密过程（续）可见：由中国剩余定理解出的每一方程组的解有4个，即每一密文对应的明文不是唯一的。解决办法：为了有效地确定唯一的明文，发送者可以在明文消息m中加入某些信息，如发送者的身份号、接收者的身份号、日期、时间等。双钥密码体制（第2讲）椭圆曲线密码体制三、椭圆曲线密码体制ECC1985年，Koblitz和Miller独立将椭圆曲线（EllipticCurve）引入密码学中，成为构造双钥体制的有力工具。目前，对这种椭圆曲线离散对数密码体制研究已经有16年的历史，尚未发现明显的弱点。目前，大多数的产品和标准均使用RSA。为了保证RSA的安全性，近年来所采用的密钥长度不断增加，这直接导致了RSA计算量的增加。ECC对RSA提出了巨大的挑战。在公钥密码的标准化过程中，IEEEP1363标准已经采用了ECC。与RSA相比，ECC的主要优点是可以使用比RSA更短的密钥获得相同水平的安全性。3.1实数域上椭圆曲线的概念实数域上的椭圆曲线可以定义为满足方程 y2=x3+ax+b的点(x,y)的集合实数域椭圆曲线上加法:P+Q实数域椭圆曲线上加法:P+(-P)实数域椭圆曲线上加法：2P3.2有限域Fq上的椭圆曲线有限域Fq上的椭圆曲线y2=x3+ax+b，其点集(x,y)构成有限域上的Abel群。条件为：4a3+27b2≠0modq设P=(x1,y1),Q=(x2,y2),P+Q=(x3,y3)，那么：举例说明—F23的椭圆曲线取p=23,a=b=1,则椭圆曲线方程为：y2=x3+x+1把满足上式的所有点(x,y)和元素O所组成的点集记为E23(1,1)对于E23(1,1)，只关心满足模p方程的、从(0,0)到(p-1,p-1)的象限中的非负整数。下表列出E23(1,1)若干点(O点除外)。(0,1)(6,4)(12,19)(0,22)(6,19)(13,7)(1,7)(7,11)(13,16)(1,16)(7,12)(17,3)(3,10)(9,7)(17,20)(3,13)(9,16)(18,3)(4,0)(11,2)(