《现现代密学第10讲ECCppt课件》由会员分享，可在线阅读，更多相关《现现代密学第10讲ECCppt课件（18页珍藏版）》请在金锄头文库上搜索。
1、椭圆曲线椭圆曲线(ECC)密码体制密码体制Elliptic Curve Cryptography2024/9/171.椭圆曲线椭圆曲线n椭圆曲线的曲线方程是以下形式的三次方程椭圆曲线的曲线方程是以下形式的三次方程ny2+axy+by=x3+cx2+dx+ey2+axy+by=x3+cx2+dx+ena,b,c,d,ea,b,c,d,e是满足某些简单条件的实数。定义中包含是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为一个称为无穷远点的元素，记为O.O.2024/9/172.有限域上的椭圆曲线有限域上的椭圆曲线n曲线方程中的所有系数都是某一有限域曲线方程中的所有系数都是某一有限域
2、GF(p)GF(p)中的元素中的元素(p(p为一大素数为一大素数) )，最为常用的曲线方程为，最为常用的曲线方程为ny2=x3+ax+b mod(p) (a,bGF(p),4a3+27b20 mod y2=x3+ax+b mod(p) (a,bGF(p),4a3+27b20 mod p)p)n例：例：p=23,a=b=1, 4a3+27b2=8 0 (mod23),p=23,a=b=1, 4a3+27b2=8 0 (mod23),n方程方程y2=x3+x+1 mod(p) y2=x3+x+1 mod(p) 记为记为Ep(a,b):Ep(a,b):表示表示ECCECC上点集上点集(x,y)|0x
3、p,0 yp,(x,y)|0xp,0 yp,且且x,yx,y均为整数均为整数 并上并上O. O. 2024/9/173.GF(P)上上ECC点的个数点的个数?个数越多个数越多,越安全越安全.Hasse定理定理 n如果如果E是定义在是定义在GF(p)域上的椭圆曲线，域上的椭圆曲线，N是是E上的点的个数，那么：上的点的个数，那么： 28个点个点点集如何产生方法点集如何产生方法?n对每一x(0xp且x为整数），计算x3+ax+b mod pn决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两个平方根。n除(4,0),对应每个x,都有2个点.2024/9/17
4、4.椭圆曲线加法的定义椭圆曲线加法的定义Q+R: Q、 R连线与连线与E交点关于交点关于x轴对称点轴对称点Q+R=-PO为加法单位元为加法单位元 P+O=PP (x,y)加法逆元加法逆元-P(x,-y) P+(-P)=O当当4a3+27b20 mod p Ep(a,b)构成加法交换群构成加法交换群 否则导致加否则导致加法运算无意法运算无意义义2024/9/175.Ep(a,b)Ep(a,b)上加法上加法nO为加法单位元为加法单位元 P+O=PnP (x,y)加法逆元加法逆元-P(x,-y+p) nP(x1,y1),Q= (x2,y2),P-Q,n P+Q= (x3,y3)nx3=l2-x1-x
5、2mod p）ny3=l(x1-x3)-y1 (mod p)例：例：E23(1,1)nP=(3,10),Q(=9,7)2024/9/176.ECCECC上的密码上的密码n应用应用nDiffie-HellmanDiffie-Hellman密钥交换密钥交换nElgamalElgamal密码体制密码体制n安全基础安全基础nECCECC上的离散对数问题是困难问题上的离散对数问题是困难问题n在在ECCECC构成的交换群构成的交换群Ep(a,b)Ep(a,b)上考虑方上考虑方程程Q QkPkP，P,QEp(a,b),kp.P,QEp(a,b),kp.由由k k和和P P求求Q Q容易，由容易，由P,QP,
6、Q求求k k则是困难的。则是困难的。2024/9/177.Diffie-HellmanDiffie-Hellman密钥交换密钥交换n攻击者如想获得攻击者如想获得K K，必须由，必须由PAPA和和G G求出求出nAnA或或PBPB和和G G求出求出nBnBA秘钥nAB秘钥nBn取取Ep(a,b),Ep(a,b),生成元生成元G(x1,y1) (p2180, |G|G(x1,y1) (p2180, |G|大素数大素数) )nEp(a,b)Ep(a,b)和和G G公开公开PA =nAGPB =nBGnAPBnBPA共享的秘钥共享的秘钥K2024/9/178.ElgamalElgamal密码体制密码体
7、制n密钥产生密钥产生n选择一个素数选择一个素数p p，g(g p), x(xp)g(g p), x(xp)n私钥私钥:x :x 公钥公钥:(y,g,p ):(y,g,p )， y y gx gx mod pmod pn加密加密n选择随机数选择随机数k k，(k,p(k,p1)=1, M1)=1, M明文明文nC1=g k mod pC1=g k mod pn C2=Myk mod p C2=Myk mod pn 密文密文C=C1|C2C=C1|C2。n解密解密nM=C2/C1x=My k/gkx=Mgxk/gkx M=C2/C1x=My k/gkx=Mgxk/gkx mod p mod p E
8、CCECC实现实现ElgamalElgamal密码体制密码体制n密钥产生密钥产生n选取椭圆曲线选取椭圆曲线Ep(a,b),Ep(a,b),生成生成元元G ,nA G ,nA 。n私钥私钥: nA : nA 公钥公钥: Ep(a,b), : Ep(a,b), G, PA( PA=nAG)G, PA( PA=nAG)n 加密加密n选随机正整数选随机正整数k k，将明文消息，将明文消息通过编码嵌入曲线上得到点通过编码嵌入曲线上得到点pm?pm?nC1=kG C2= Pm+kPAC1=kG C2= Pm+kPAn 密文密文Cm=(C1, C2)Cm=(C1, C2)n解密解密n Pm =C2 -nA
9、C1 Pm =C2 -nA C1p，g, x, y指数关系指数关系Ep(a,b), G, nA, PA倍乘关系倍乘关系2024/9/179.明文嵌入明文嵌入( (整数整数mm点点 Pm) Pm)选取选取K(大整数大整数k，且满足，且满足(m+1)kp)令令x=mk+j(m明文明文,j=0,1.k-1)判断判断x3+ax+b mod(p) 是否为平是否为平方剩余方剩余如果如果x3+ax+b mod(p) 有平方根有平方根y,则则Pm=（x,y）;否则否则j=j+1,返返回回2如果如果j=k;则嵌入失败。则嵌入失败。失败概率失败概率1/2k解密点解密点 Pmx,y） 整数整数m =x/ky2=x3
10、+2x+7mod(179) m=5选选K=10(满足满足(5+1)101;nnreturn q;n2024/9/1713.椭圆曲线与离散对数密码体制比较椭圆曲线与离散对数密码体制比较n安全性安全性n攻击离散对数问题运算复杂度攻击离散对数问题运算复杂度 。 n攻击攻击ECCECC上离散对数问题运算复杂度上离散对数问题运算复杂度n pmax pmax是是ECCECC形成的交换群的阶的最大素因子形成的交换群的阶的最大素因子nECCECC上的密码体制更安全上的密码体制更安全n密钥量密钥量n实现相同安全性条件下，实现相同安全性条件下，ECC所需密钥量小的所需密钥量小的多多n灵活性灵活性nECC具有丰富的
11、群结构和多选择性具有丰富的群结构和多选择性(改变参数改变参数P,a,b)n带宽要求带宽要求2024/9/1714.ECCECC与与RSA/DSARSA/DSA在同等安全条件下所需在同等安全条件下所需密钥长度密钥长度RSA/DSA5127681024204821000ECC1061321602116002024/9/1715.ECCECC的应用的应用n现在密码学界普遍认为它将替代现在密码学界普遍认为它将替代RSA RSA 成为通用的公钥密码算成为通用的公钥密码算法法.SET.SET协议的制定者已把它作为下一代协议中缺省的公钥密协议的制定者已把它作为下一代协议中缺省的公钥密码算法码算法. .n在无
12、线网络的安全解决方面有着广阔的前景在无线网络的安全解决方面有着广阔的前景n大的主流厂商如大的主流厂商如Cisco Sybase Cisco Sybase 索尼等推出了相关的产品或解索尼等推出了相关的产品或解决方案决方案. .国内也有不少学者和公司在作国内也有不少学者和公司在作 相关的研发和应用相关的研发和应用. .n目前目前ECC ECC 在无线局域网安全中的应用尚十分有限在无线局域网安全中的应用尚十分有限, ,n原因可能有两个方面原因可能有两个方面n尚没有十分的迫切性尚没有十分的迫切性,RSA ,RSA 因其适用范围广因其适用范围广, ,支持产品多支持产品多, ,不可不可能很快由能很快由EC
13、C ECC 替代替代; ;nECC ECC 本身还有许多需要研究提高的地方如高速本身还有许多需要研究提高的地方如高速ECC ECC 密码算法密码算法芯片的研制等芯片的研制等. .2024/9/1716.ECCECC未来主要研究未来主要研究n快速算法的研究快速算法的研究nECCECC的离散对数问题的离散对数问题nECCECC上编码方法的研究上编码方法的研究n超椭圆曲线超椭圆曲线2024/9/1717.对对ECCECC的的 攻击攻击n至今没有发现比较有效的计算至今没有发现比较有效的计算ECDLP ECDLP 的方法的方法, ,目前计算目前计算ECDLP ECDLP 的最好算法仍然是指数时间的的最好算法仍然是指数时间的并行并行Pollard-rho Pollard-rho 方法方法. .n ECDLP ECDLP 是否存在亚指数时间攻击是否存在亚指数时间攻击? ? 这一问题这一问题的回答是肯定的的回答是肯定的, ,因为从理论上证明因为从理论上证明ECDLP ECDLP 不不存在亚指数时间攻击已是不可能的了存在亚指数时间攻击已是不可能的了. . n寻找寻找ECDLP ECDLP 的亚指数时间甚至多项式时间攻击的亚指数时间甚至多项式时间攻击是非常重要和有意义的是非常重要和有意义的, ,这需要更高深的数学这需要更高深的数学和更天才的技巧和更天才的技巧. . 2024/9/1718.
