现现代密学-第10讲ECC课件.ppt

1、椭圆曲线椭圆曲线(ECC)密码体制密码体制Elliptic Curve Cryptography2022-10-4椭圆曲线椭圆曲线n椭圆曲线的曲线方程是以下形式的三次方程椭圆曲线的曲线方程是以下形式的三次方程y y2 2+axy+by=x+axy+by=x3 3+cx+cx2 2+dx+e+dx+ea,b,c,d,ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为称为无穷远点的元素，记为OO.2022-10-42有限域上的椭圆曲线有限域上的椭圆曲线n曲线方程中的所有系数都是某一有限域曲线方程中的所有系数都是某一有限域GF

2、(p)GF(p)中的元素中的元素(p(p为一大素数为一大素数)，最为常用的曲线方程为，最为常用的曲线方程为y2=x3+ax+b mod(p)(a,bGF(p),4a3+27b20 mod p)n例：例：p=23,a=b=1,4a4a3 3+27b+27b2 2=8=8 0 (mod23),n方程方程y2=x3+x+1 mod(p)记为记为Ep(a,b):表示表示ECC上点集上点集(x,y)|0 xp,0 yp,x,y)|0 xp,0 yp,且且x,yx,y均为整数均为整数并上并上O.2022-10-43GF(P)上上ECC点的个数点的个数?个数越多个数越多,越安全越安全.Hasse定理定理 n

3、如果如果E是定义在是定义在GF(p)域上的椭圆曲线，域上的椭圆曲线，N是是E上的点的个数，则：上的点的个数，则：ppN2)1(28个点个点点集如何产生方法点集如何产生方法?n对每一x(0 xp0 xp且且x x为整数），计算为整数），计算x x3 3+ax+b mod p+ax+b mod pn决定求出的值在模决定求出的值在模p下是否有平方根，如果没有则椭下是否有平方根，如果没有则椭圆曲线上没有与这一圆曲线上没有与这一x对应的点；如果有，则求出两对应的点；如果有，则求出两个平方根。个平方根。n除除(4,0),对应每个对应每个x,都有都有2个点个点.2022-10-44椭圆曲线加法的定义椭圆曲线

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)构成加法交换群构成加法交换群 否则导致加否则导致加法运算无意法运算无意义义2022-10-45E Ep p(a,b)(a,b)上加法上加法nO为加法单位元为加法单位元 P+O=PnP(x,y)加法逆元加法逆元-P(x,-y+p)nP P(x(x1 1,y,y1 1),Q=(x),Q=(x2 2,y,y2 2),P),P-Q,P+Q=(x(x3 3,y,y3 3)x

5、x3 3=l l2 2-x-x1 1-x-x2 2（mod pmod p）y y3 3=l l(x(x1 1-x-x3 3)-y)-y1 1(mod p)(mod p)QPyaxQPxxyy121121223l例：例：E23(1,1)nP=(3,10),Q(=9,7),(mod)(modmod:),(),(mod)(modmod1272231234107362373033623641205102133211201723201641017311231710993112311222216339107323223323PyxPEQPyxll2022-10-46ECCECC上的密码上的密码n应用应用n

6、Diffie-HellmanDiffie-Hellman密钥交换密钥交换nElgamalElgamal密码体制密码体制n安全基础安全基础nECCECC上的离散对数问题是困难问题上的离散对数问题是困难问题n在在ECCECC构成的交换群构成的交换群E Ep p(a,b)(a,b)上考虑方程上考虑方程QQkPkP，P,QEP,QEp p(a,b),kp.(a,b),kp.由由k k和和P P求求QQ容易，由容易，由P,QP,Q求求k k则是困难的。则是困难的。2022-10-47Diffie-HellmanDiffie-Hellman密钥交换密钥交换n攻击者如想获得攻击者如想获得K K，必须由，必须

7、由P PA A和和G G求出求出n nA A或或P PB B和和G G求出求出n nB BA秘钥秘钥nAB秘钥秘钥nBn取取E Ep p(a,b),(a,b),生成元生成元G(xG(x1 1,y,y1 1)(p2)(p2180,180,|G|G|大素数大素数)nE Ep p(a,b)(a,b)和和G G公开公开PA=nAGPB=nBGnAPBnBPA共享的秘钥共享的秘钥K2022-10-48ElgamalElgamal密码体制密码体制n密钥产生密钥产生 选择一个素数选择一个素数p p，g g(g g p p),x(),x(x x p p)私钥私钥:x :x 公钥公钥:(:(y,g,py,g,p

8、 )，y y g gx x mod mod p pn加密加密 选择随机数选择随机数k k，(k,pk,p1)=1,1)=1,MM明文明文 C C1 1=g g k k mod mod p p C C2 2=MyMyk k mod mod p p 密文密文C C=C=C1 1|C|C2 2。n解密解密MM=C=C2 2/C/C1 1x x=MyMy k k/g gk kx x=MgMgx xk k/g/gk kx x mod mod p p ECCECC实现实现ElgamalElgamal密码体制密码体制n密钥产生密钥产生 选取椭圆曲线选取椭圆曲线E Ep p(a,b),(a,b),生成元生成元

9、G,nG,nA A 。私钥私钥:n:nA A 公钥公钥:E:Ep p(a,b),(a,b),G,G,P PA A(P PA A=n=nA AG)G)n 加密加密 选随机正整数选随机正整数k k，将，将明文消息明文消息通过通过编码编码嵌入嵌入曲线上得到点曲线上得到点p pm m?C C1 1=kG kG C C2 2=P Pm m+kP+kPA A 密文密文C Cm m=(=(C C1 1,C C2 2)n解密解密 P Pm m =C C2 2 -n nA A C C1 1p，g,x,y指数关系指数关系Ep(a,b),G,nA,PA倍乘关系倍乘关系2022-10-49明文嵌入明文嵌入(整数整数m

10、m点点 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解密点解密点 Pm（x,y）整数整数m=x/ky2=x3+2x+7mod(179)m=5选选K=10(满足满足(5+1)101;nnreturn q;n2022-10-413椭圆曲线椭圆曲线与与离散对数离散对数密码体制比较密码体制比较n

11、安全性安全性攻击离散对数问题运算复杂度攻击离散对数问题运算复杂度 。攻击攻击ECCECC上离散对数问题运算复杂度上离散对数问题运算复杂度 p pmaxmax是是ECCECC形成的交换群的阶的最大素因子形成的交换群的阶的最大素因子ECCECC上的密码体制更安全上的密码体制更安全32)log)(log(log(expppO)(exp(logmaxpOn密钥量密钥量n实现相同安全性条件下，实现相同安全性条件下，ECC所需密钥量小的多所需密钥量小的多n灵活性灵活性nECC具有丰富的群结构和多选择性具有丰富的群结构和多选择性(改变参数改变参数P,a,b)带宽要求带宽要求2022-10-414ECCECC

12、与与RSA/DSARSA/DSA在同等安全条件下所在同等安全条件下所需密钥长度需密钥长度RSA/DSA5127681024204821000ECC1061321602116002022-10-415ECCECC的应用的应用n现在密码学界普遍认为它将替代现在密码学界普遍认为它将替代RSA RSA 成为通用的公钥密码算成为通用的公钥密码算法法.SETSET协议的制定者已把它作为下一代协议中缺省的公钥密协议的制定者已把它作为下一代协议中缺省的公钥密码算法码算法.n在无线网络的安全解决方面有着广阔的前景在无线网络的安全解决方面有着广阔的前景n大的主流厂商如大的主流厂商如Cisco Sybase Cis

13、co Sybase 索尼等推出了相关的产品或解决方案索尼等推出了相关的产品或解决方案.国国内也有不少学者和公司在作内也有不少学者和公司在作 相关相关的的研发和应用研发和应用.n目前目前ECC ECC 在无线局域网安全中的应用尚十分有限在无线局域网安全中的应用尚十分有限,n原因可能有两个方面原因可能有两个方面n尚没有十分的迫切性尚没有十分的迫切性,RSA RSA 因其适用范围广因其适用范围广,支持产品多支持产品多,不可能很快由不可能很快由ECC ECC 代替代替;nECC ECC 本身还有许多需要研究提高的地方如高速本身还有许多需要研究提高的地方如高速ECC ECC 密码算法芯片的研密码算法芯片

14、的研制等制等.2022-10-416ECCECC未来主要研究未来主要研究n快速算法的研究快速算法的研究nECCECC的离散对数问题的离散对数问题nECCECC上编码方法的研究上编码方法的研究n超椭圆曲线超椭圆曲线2022-10-417对对ECCECC的的 攻击攻击n至今没有发现比较有效的计算至今没有发现比较有效的计算ECDLP ECDLP 的方法的方法,目前计算目前计算ECDLP ECDLP 的最好算法仍然是指数时间的的最好算法仍然是指数时间的并行并行Pollard-rho Pollard-rho 方法方法.n ECDLP ECDLP 是否存在亚指数时间攻击是否存在亚指数时间攻击?这一问题的这一问题的回答是肯定的回答是肯定的,因为从理论上证明因为从理论上证明ECDLP ECDLP 不存不存在亚指数时间攻击已是不可能的了在亚指数时间攻击已是不可能的了.n寻找寻找ECDLP ECDLP 的亚指数时间甚至多项式时间攻击的亚指数时间甚至多项式时间攻击是非常重要和有意义的是非常重要和有意义的,这需要更高深的数学和这需要更高深的数学和更天才的技巧更天才的技巧.2022-10-418