现现代密学第10讲ECC课件

1、椭圆曲线(ECC)密码体制Elliptic Curve Cryptography2022/9/251椭圆曲线(ECC)密码体制Elliptic Curve Cr椭圆曲线椭圆曲线的曲线方程是以下形式的三次方程y2+axy+by=x3+cx2+dx+ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为O.2022/9/252椭圆曲线椭圆曲线的曲线方程是以下形式的三次方程2022/9/有限域上的椭圆曲线曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+b mod(p) (a,bGF(p),4a3+27b20 m

2、od 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. 2022/9/253有限域上的椭圆曲线曲线方程中的所有系数都是某一有限域GF(pGF(P)上ECC点的个数?个数越多,越安全.Hasse定理 如果E是定义在GF(p)域上的椭圆曲线，N是E上的点的个数，则： 28个点点集如何产生方法?对每一x(0 xp且x为整数），计算x3+ax+b mod p决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两

3、个平方根。除(4,0),对应每个x,都有2个点.2022/9/254GF(P)上ECC点的个数?个数越多,越安全.Hasse定理椭圆曲线加法的定义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/9/255椭圆曲线加法的定义Q+R: Q、 R连线与E交点关于x轴对称Ep(a,b)上加法O为加法单位元 P+O=PP (x,y)加法逆元-P(x,-y+p) P(x1,y1),Q= (x2,y2),P-Q, P+Q=

4、(x3,y3)x3=l2-x1-x2（mod p）y3=l(x1-x3)-y1 (mod p)例：E23(1,1)P=(3,10),Q(=9,7)2022/9/256Ep(a,b)上加法O为加法单位元 P+O=P例：E23(ECC上的密码应用Diffie-Hellman密钥交换Elgamal密码体制安全基础ECC上的离散对数问题是困难问题在ECC构成的交换群Ep(a,b)上考虑方程QkP，P,QEp(a,b),kp.由k和P求Q容易，由P,Q求k则是困难的。2022/9/257ECC上的密码应用2022/9/247Diffie-Hellman密钥交换攻击者如想获得K，必须由PA和G求出nA或P

5、B和G求出nBA秘钥nAB秘钥nB取Ep(a,b),生成元G(x1,y1) (p2180, |G|大素数)Ep(a,b)和G公开PA =nAGPB =nBGnAPBnBPA共享的秘钥K2022/9/258Diffie-Hellman密钥交换攻击者如想获得K，必须由Elgamal密码体制密钥产生选择一个素数p，g(g p), x(xp)私钥:x 公钥:(y,g,p )， ygx mod p加密选择随机数k，(k,p1)=1, M明文C1=g k mod p C2=Myk mod p 密文C=C1|C2。解密M=C2/C1x=My k/gkx=Mgxk/gkx mod p ECC实现Elgamal

6、密码体制密钥产生选取椭圆曲线Ep(a,b),生成元G ,nA 。私钥: nA 公钥: Ep(a,b), G, PA( PA=nAG) 加密选随机正整数k，将明文消息通过编码嵌入曲线上得到点pm?C1=kG C2= Pm+kPA 密文Cm=(C1, C2)解密 Pm =C2 -nA C1p，g, x, y指数关系Ep(a,b), G, nA, PA倍乘关系2022/9/259Elgamal密码体制密钥产生ECC实现Elgamal密码体明文嵌入(整数m点 Pm)选取K(大整数k，且满足(m+1)kp)令x=mk+j(m明文,j=0,1.k-1)判断x3+ax+b mod(p) 是否为平方剩余如果x

7、3+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;return q;2022/9/2513point multipy(point p, long m,椭圆曲线与离散对数密码体制比较安全性攻击离散对数问题运算复杂度 。 攻击ECC上离散对数问题运算复杂度 pmax是ECC形成的交换群的阶的最大素因子ECC上的密码体制更安全密钥量实现相同安全性条件下，ECC所需密钥量小的多灵活性ECC具有丰富的群结构和多选择性

8、(改变参数P,a,b)带宽要求2022/9/2514椭圆曲线与离散对数密码体制比较安全性密钥量2022/9/24ECC与RSA/DSA在同等安全条件下所需密钥长度RSA/DSA5127681024204821000ECC1061321602116002022/9/2515ECC与RSA/DSA在同等安全条件下所需密钥长度RSA/DECC的应用现在密码学界普遍认为它将替代RSA 成为通用的公钥密码算法.SET协议的制定者已把它作为下一代协议中缺省的公钥密码算法.在无线网络的安全解决方面有着广阔的前景大的主流厂商如Cisco Sybase 索尼等推出了相关的产品或解决方案.国内也有不少学者和公司在

9、作 相关的研发和应用.目前ECC 在无线局域网安全中的应用尚十分有限,原因可能有两个方面尚没有十分的迫切性,RSA 因其适用范围广,支持产品多,不可能很快由ECC 代替;ECC 本身还有许多需要研究提高的地方如高速ECC 密码算法芯片的研制等.2022/9/2516ECC的应用现在密码学界普遍认为它将替代RSA 成为通用的公ECC未来主要研究快速算法的研究ECC的离散对数问题ECC上编码方法的研究超椭圆曲线2022/9/2517ECC未来主要研究快速算法的研究2022/9/2417对ECC的 攻击至今没有发现比较有效的计算ECDLP 的方法,目前计算ECDLP 的最好算法仍然是指数时间的并行Pollard-rho 方法. ECDLP 是否存在亚指数时