【学习课件】第19讲EIGamal体制

1、EIGamal体制与椭圆曲线(ECC)密码体制数学基础本原元：设p为素数，若存在一个整数a，使得a，a2，a3，ap1，关于模p互不同余，则称模p的本原元。离散对数问题：Y=logaX X计算Y是容易的，至多需要2log2p次运算就可以。但是根据Y计算X就是困难的，利用目前最好的算法，对于小心选择的p将至少需要p1/2次以上的运算，只要p足够的大，求解离散 对数就是相当困难的。编辑pptEIGamal公钥密码体制设计过程:Step1 选取大素数p,再选取 的一个本原元a,并将p和a公开.Step2 随机选取整数 ,并计算出 并将 作为公开的加密密钥,将d作为保密的脱密密钥.编辑ppt加脱密变换

2、 加密变换: ,秘密选择一个整数, 则密文为其中脱密变换: 对任意密文明文为编辑ppt实例P=2597,取a2，秘密密钥为765，可以计算出公开密钥为y2765 mod 2597949。取明文M1299，随机数k853，则 C12853 mod 2597435， C21299949853 mod 25972396 所以密文为: （C1，C2）（435，2396） 解密时计算: M2396(435765)-1 mod 25971299编辑ppt特点(1) 密文长度扩展1倍;(2) 只利用了有限域的乘法群的性质,即只使用了乘法运算和求乘法逆的运算 为何密文需要扩展1倍? 这涉及其设计思想问题.编辑

3、ppt安全性分析因为该算法是基于离散对数问题的，所以p的选取必须足够的大，为150位以上的十进制数，且p1有大素因子为了加密和签名的安全k必须是一次性的编辑ppt设计思想(1) 利用Diffie-Hellman密钥交换协议生成双方加密用的密钥.此时不同之处在于已将 作为公开密钥公布,不需每次发送.(2) 采取了一次一密的加密思想.将 作为双方交换的密钥,利用它对明文进行加脱密.编辑ppt问题为什么要求 ?答案: 因为 的周期为 p-1 ,即备注:(1) 参数可以全网公用,也可一人一套;(2) 加密不同的明文分组时选用独立的随机数,但秘密的脱密密钥需和其版本号一起长期不变.编辑ppt实现方法(1

4、) 大素数的选择与构造将大素数p选为安全素数,即使p=2q+1且q为素数.实验表明,平均100个随机数中可选出1个素数, 平均100素数中可选出1个安全素数.编辑ppt(2)安全素数条件下本原元的判断方法由Fermat定理知 ,即因而如果则有w 整除p-1=2q,因而由q是素数知,w只能是2或q.此时是本原元等价于 且 编辑ppt安全素数条件下本原元的构造方法 在 ( p=2q+1)中随机选择一个 ,若 且 ,则判定 是安全素数;否则再随机选择另一个进行检验.编辑ppt问题:容易找到本原元吗?答案:容易,至少在安全素数条件下容易.编辑ppt椭圆曲线(ECC)密码体制Elliptic Curve

5、 Cryptography概述获得同样的安全性，密钥长度较RSA短得多被IEEE公钥密码标准P1363采用编辑ppt椭圆曲线椭圆曲线的曲线方程是以下形式的三次方程y2+axy+by=x3+cx2+dx+ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为O.编辑ppt椭圆曲线加法的定义如果其上的3个点位于同一直线上，那么它们的和为O。O为加法单位元，即对ECC上任一点P,有P+O=P设P1=(x,y)是ECC上一点，加法逆元定义为P2=-P1=(x,-y)P1,P2连线延长到无穷远，得到ECC上另一点O,即P1,P2,O三点共线，所以P1+P2+O=O, P1+

6、P2=O, P2=-P1OOO,O=-O编辑ppt椭圆曲线加法的定义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,上述加法满足加法的一般性质，如交换律、结合律等编辑ppt有限域上的椭圆曲线曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+b mod(p) (a,bGF(p)

7、,4a3+27b20 mod p)例：p=23,a=b=1, 4a3+27b2=8 0 (mod23),方程为y2=x3+x+1 mod(p)，图形为连续图形。我们感兴趣的是在第一象限的整数点。设Ep(a,b)表示ECC上点集(x,y)|0 xp,0 yp,且x,y均为整数并上O. 编辑ppt有限域上的椭圆曲线点集产生方法对每一x(0 xp且x为整数），计算x3+ax+b mod p决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两个平方根。编辑pptEp(a,b)上加法如果P,Q Ep(a,b)P+O=P如果P(x,y),则(x,y)+(x,-y)O

8、P(x1,y1),Q= (x2,y2),P-Q,P+Q= (x3,y3)x3=l2-x1-x2（mod p）y3=l(x1-x3)-y1 (mod p)编辑ppt例：E23(1,1)P=(3,10),Q(=9,7)编辑pptECC上的密码ECC上的离散对数问题在ECC构成的交换群Ep(a,b)上考虑方程QkP，P,QEp(a,b),kp.由k和P求Q容易，由P,Q求k则是困难的。由ECC上离散对数问题可以构造Diffie-Hellman密钥交换和Elgamal密码体制编辑pptECC实现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编辑ppt椭圆曲线密码体制的优点安全性高攻击有限域上的离散对数可用指数积分法，运算复杂度为 。 对ECC上离散对数攻击并不有效。攻击ECC上离散对数问题的方法只有大步小步法，复杂度为 。pmax是ECC形成的交换群的阶的最大素因子，因此ECC上的密码体制比基于有限域上离散对数问题的公钥体制更安全编辑ppt椭圆曲线密码体制的优点密钥量小实现相同安全性条件下，EC