《第6章椭圆曲线密码体制ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章椭圆曲线密码体制ppt课件.ppt（44页珍藏版）》请在三一办公上搜索。
1、公钥密码,一、椭圆曲线公钥密码ECC(Elliptic Curve Cryptography)二、McEliece公钥密码,椭圆曲线公钥密码ECC,1.简要历史椭圆曲线(Elliptic curve)作为代数几何中的重要问题已有100多年的研究历史1985年，N.Koblitz和V.Miller独立将其引入密码学中，成为构造双钥密码体制的一个有力工具。利用有限域GF(2n)上的椭圆曲线上点集所构成的群上定义的离散对数系统，可以构造出基于有限域上离散对数的一些双钥体制-椭圆曲线离散对数密码体制(ECDLC)，如Diffie-Hellman，ElGamal，Schnorr，DSA等。10余年的研究
2、，尚未发现明显的弱点。,研究现状,椭圆曲线密码是除RSA算法以外最重要的公钥密码之一。与RSA算法相比它也有很多独特的优点。出于国家安全战略考虑，国内学术界和管理部门一直希望能够在国内一些应用场合使用椭圆曲线密码。在推广和使用椭圆曲线密码的过程中，相应的芯片是必不可少的。然而，由于椭圆曲线密码算法是一种很复杂的数学算法，如何将椭圆曲线密码算法芯片化，国内外没有成熟技术。,椭圆曲线加密算法,背景RSA中用到了因子分解的困难性，而为了增加困难得加大数的位数，从而导致计算速度变慢。ECC可以用较小的密钥长度达到较高的计算难度获得同样的安全性，密钥长度较RSA短得多被IEEE公钥密码标准P1363采用
3、,椭圆曲线公钥密码ECC,椭圆曲线上一个点P的k倍表示表示P+P+（k个点P“相加”），记为kP。椭圆曲线上一个点P的所有倍数点组成了椭圆曲线的子集，该子集是该椭圆曲线关于该“加法”的循环子群。给定“椭圆曲线”上的点P，给定整数k，计算“kP=？”是容易的。（折半相加）给定“椭圆曲线”上的两个点P和Q，求整数“？P=Q”是困难的。这个问题称为椭圆曲线上的离散对数问题。,椭圆曲线方程,Elliptic Curvey2axybyx3cx2dxe 其中a、b、c、d、e是满足某个简单条件的实数另有O点被定义为无穷点/零点,椭圆曲线的定义,1.1椭圆曲线的定义设F是域，F-是F的代数闭包。椭圆曲线的一
4、般定义为F-上亏格为1的光滑的代数曲线。这个定义涉及很多代数几何中的概念。实际上，定义在F上的椭圆曲线可等价地看作由方程y2+a1xy+a3xy=x3+a2x2+a4x+a6(1)刻划的F-上曲线再添加上一点O，其中aiF且满足判别式不为零。椭圆曲线的有理点即为点O及坐标在F中的点(x，y)。方程(1)称为该椭圆曲线的Weierstrass方程。当F的特征不是2或3时，这个方程可化为特别简单的形式y2=x3+ax+b并要求判别式=4a3+27b20,椭圆曲线密码示意图,椭圆曲线密码介绍,运算定义：若曲线三点在一条直线上,则其和为OO用作加法的单位：O=-O;P+O=P一条竖直线交X轴两点P1、
5、P2，则P1+P2+O=O，于是P1=-P2如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S,椭圆曲线加法的定义,Q,R是ECC上x坐标不同的两点，Q+R定义为：画一条通过Q,R的直线与ECC交于P1(交点是唯一的，除非做的Q,R点的切线，此时分别取P1=Q或P1=R)。由Q+R+P1=O,得Q+R=-P1点Q的倍数定义如下：在Q点做ECC的一条切线，设切线与ECC交于S,定义2Q=Q+Q=-S。类似可定义3Q=Q+Q+Q,上述加法满足加法的一般性质，如交换律、结合律等,
6、椭圆曲线上不同坐标点相加,椭圆曲线上相同坐标点相加,椭圆曲线上一坐标点与无穷远点相加,椭圆曲线上两对称点相加,AB=A+(-A)=O,B,EC：PQR,素域上的EC,在有限域Zp上的简化ECy2x3axb mod p 其中4a327b2 mod p 0（这是一个离散点的集合）举例y2x318x15 mod 23 y2x317x15 mod 23http:/,EC1,EC2,有限域上的椭圆曲线,曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+b mod(p)(a,bGF(p),4a3+27b20 mod p)例：p=23,a=b=1,4
7、a3+27b2=8 0(mod23),方程为y2=x3+x+1 mod(p)，图形为连续图形。我们感兴趣的是在第一象限的整数点。设Ep(a,b)表示ECC上点集(x,y)|0 xp,0 yp,且x,y均为整数并上O.,有限域上的椭圆曲线点集产生方法,对每一x(0 xp且x为整数），计算x3+ax+b mod p决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两个平方根。,Ep(a,b)上加法,如果P,Q Ep(a,b)P+O=P如果P(x,y),则(x,y)+(x,-y)OP(x1,y1),Q=(x2,y2),P-Q,P+Q=(x3,y3)x3=l2-
8、x1-x2（mod p）y3=l(x1-x3)-y1(mod p),例：E23(1,1),P=(3,10),Q(=9,7),EC上的离散对数问题,QkP中的k计算也是极其困难的kP表示k个P相加：P+P+P在DH密钥交换中使用了ygx mod p中x的计算困难性同样在ECC中将使用QkP中计算k的困难性有两个应用密钥交换 加密解密,在有限域上的椭圆曲线运算,在此椭圆曲线上可以能出现的点有(0,1)、(0,4)、(2,1)、(2,4)、(3,1)、(3,4)、(4,2)、(4,3)、(,)任取椭圆曲线上两点，无论作加法、減法或乘法，其結果永远为上述坐标点中的一点.椭圆曲线中的离散对数难题：给定一
9、参数K及一点A，要求得另一点B，使得B=KA是很容易的。例如：5A=A+A+A+A+A但若給定A及B要求得K則很困難,ECC上的密码,ECC上的离散对数问题在ECC构成的交换群Ep(a,b)上考虑方程QkP，P,QEp(a,b),kp.由k和P求Q容易，由P,Q求k则是困难的。由ECC上离散对数问题可以构造Diffie-Hellman密钥交换和ElGamal密码体制,椭圆曲线用于加密,找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选
10、择整数r，计算P=kG，然后公开(p,a,b,G,P)，P为公钥保密k,用EC的加解密,准备曲线参数p、a、b、G，y2x3axb mod p A有自己的私钥Na，并产生公钥PaNaGB有自己的私钥Nb，并产生公钥PbNbG加密（A要给B发送消息）对明文m的编码点Pm，选择随机数k，密文CC1，C2 kG，PmkPb解密：编码点PmC2NbC1，因为(PmkPb)NbkG PmkNbGNbkG Pm,类ElGamal,用EC的加解密,原理先是通过kPb掩盖Pm(即m)，又通过kG掩盖k知道陷门Nb则可以轻松恢复之分析攻击者解C1kG中的k困难性,橢圓曲線的公開金鑰加密機制,椭圆曲线的数字签名,
11、Diffie-Hellman密钥交换,取一素数p2180,两个参数a,b,得到Ep(a,b).取Ep(a,b)的一个生成元G(x1,y1),要求G的阶是一个非常大的素数。(阶是满足nG=O的最小正整数n).Ep(a,b)和G公开，A和B密钥交换过程如下A选小于n的整数nA作为秘密钥，并有PA=nAG作为公钥B类似选取自己的秘密钥nB和公开钥PBA和B分别由K=nAPB和KnBPA产生共享的秘密钥攻击者如想获得K，必须由PA和G求出nA或PB和G求出nB,ElGamal密码体制,密钥产生过程选择一个素数p，以及g(g p),xp,计算公钥 ygx mod p,(y,g,p)为公钥，x为秘密钥加密
12、过程M是发送明文组，选择随机数k，且(k,p1)=1，计算：C1=g k mod p(随机数k被加密)C2=Myk mod p(明文被随机数k和公钥加密)密文由C1、C2级连构成，即密文C=C1|C2。解密过程M=C2/C1x=My k/gkx=Mgxk/gkx mod p,ECC实现ElGamal密码体制,选取一条椭圆曲线，得到Ep(a,b)。将明文消息通过编码嵌入曲线上得到点pm取Ep(a,b)的生成元G，Ep(a,b)和G为公开参数用户选取nA为秘密钥，PA=nAG为公开钥。加密：选随机正整数k，密文为Cm=(kG,Pm+kPA)解密：Pm+kPA-nAkG=Pm,椭圆曲线公钥密码ECC
13、,根据这个数学难题，可以构造丰富的公钥密码体制，称为椭圆曲线公钥密码（ECC，略）。Certicom 公司对ECC和RSA进行了对比，在实现相同的安全性下，ECC 所需的密钥量比RSA少得多，如下表所示。其中MIPS表示用每秒完成100万条指令的计算机所需工作的年数，m表示ECC的密钥由2 m点构成。以40 MHz的钟频实现155 bits的ECC，每秒可完成40,000次椭园曲线运算，其速度比1024 bits的DSA和RSA快10倍。,关于速度,速度在密钥长度相等的情况下，RSA和ECC的速度相当；但是在相同的安全强度要求下，ECC可以使用较少的位数就可以；故ECC较好适合嵌入式设备中,椭
14、圆曲线公钥密码ECC,因此ECC与RSA相比，更加简洁快速。具体地说，实现具有相同安全性的同类体制，ECC具有更小规模的软、硬件。,ECC的密钥长度m RSA的密钥长度 MIPS-年,160 1024 1012 320 5120 1036 600 21000 1078 1200 120000 10168,椭圆曲线密码的安全性,难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECC RSA*Pollard rho分析方法,椭圆曲线算法与RSA算法的比较,椭圆曲线公钥系统是代替RSA的强有力的竞争者。椭圆曲线加密方法与RSA方法相比，有以下的优点：（1）安全性能更高
15、如160位ECC与1024位RSA、DSA有相同的安全强度。（2）计算量小，处理速度快在私钥的处理速度上（解密和签名），ECC远 比RSA、DSA快得多。（3）存储空间占用小ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，所以占用的存储空间小得多。（4）带宽要求低使得ECC具有广泛得应用前景。,椭圆曲线密码体制的优点,密钥量小实现相同安全性条件下，ECC所需密钥量远下雨有限域上离散对数问题的公钥体制的密钥量灵活性好通过改变参数可以获得不同的曲线，具有丰富的群结构和多选择性ECC的这些特点使它必将取代RSA，成为通用的公钥加密算法。比如SET协议的制定者已把它作为下一代SET协议中缺省的
16、公钥密码算法。,椭圆曲线公钥密码ECC,在安全性设计方面，Menezes，Okamoto和Vanstone 指出应避免选用超奇异曲线，否则椭圆曲线群上的离散对数问题退化为有限域低次扩域上的离散对数问题，从而能在“多项式时间”上可解。他们还指出，若所用循环子群的阶数达2160，则可提供足够的安全性。,练习1,椭圆曲线加密/解密方案中，这个密码系统的参数是E11(1,6)和G=(2,7)。B的秘密密钥是nB=7。（要求有计算点的详细过程，不能直接给答案，否则算错）（1）求B的公开密钥PB;（5分）（2）A希望解密报文Pm=(10,9)，并选择随机数k=3，确定密文Cm.（6分）（3）给出B用来从C
17、m中恢复Pm的计算过程（即证明是可逆的）。（4分）,练习2,考虑一个其共享素数q=71，而一个原根为7的ElGamal方案。（1）如果B有一个公开密钥为3而A选择了随机整数2，M=30对应的密文是什么？（2）如果现在A选择一个不同的k值以便将M=30加密为C=(59,C2)，整数C2是什么？,练习3,假定用户A和B使用Diffie-Hellman密钥交换协议来确定一个共同的密钥k，他们使用的素数为p=11，Zp的生成元为g=2，如果用户A选择的秘密随机数为rA=5，用户B选择的秘密随机数为rB=7，试问k是多少？,练习4,考虑下列B用来加密发给A的报文的方案。A选择两个素数P和Q，它们与(P-1)和(Q-1)互素；A公布N=PQ作为它的公开密钥；A计算P与Q使得 PP 1mod(Q-1),QQ 1mod(P-1)成立；B加密报文M为CMN modN A通过解M1C(P)modQ和MM1(Q)modP求出M.问：1）解释这个方案工作的原理；2）它与RSA有何不同。,
