《第10章 椭圆曲线密码.ppt》由会员分享，可在线阅读，更多相关《第10章 椭圆曲线密码.ppt（24页珍藏版）》请在三一文库上搜索。
1、返回总目录,第10章 椭圆曲线密码,教学目的,了解椭圆曲线密码 了解椭圆曲线 了解ECCp-109挑战 了解并行Pollard Rho法, 椭圆曲线,本章内容, 椭圆曲线（mod p）, 加权投影坐标, 定义在Galois域的椭圆曲线, 密码安全曲线, 将信息转化为椭圆曲线代码,本章内容, 椭圆曲线公开密钥密码算法, 椭圆曲线因数分解, ECCp-109挑战, 并行Pollard Rho法,椭圆曲线的安全度,椭圆曲线,10.1 椭圆曲线,定义,椭圆曲线即三次平滑代数平面曲线（Smooth Algebraic Plane Curve），可在适当的坐标下，表达成Weierstrass方程式,除了特
2、殊系数，一般而言，可在适当的坐标下，表示成,在系数K上的平面图形，其中E也包括无限远点O。,椭圆曲线加法律,定义椭圆曲线加法律,在椭圆曲线定义“加法”如下：,（1）视无限远点O为“加法单位素”。,（2）点P的“加法反元素”即点-P，定义为点P对x轴的镜像。,（3）一般而言，三次曲线与直线相交于三点（需计算重数（Multiplicity），若相切时，重数为2，如图所示，P、Q、-（P+Q）共线，点(P+Q)即点-(P+Q)对x轴的镜像，依此定义“加法”。,椭圆曲线加法律,（4）加法坐标计算：令 、 ，欲求 其中可分为三种情形：,：取通过P、Q截线的斜率 。,、 ：即P=Q，取通过P切线的斜率 。
3、,、 ：此时 。,除第3种情形外，,椭圆曲线,定理,为交换群（Abelian Group），其中加法“+”，如上所定，无限远点O为加法单位素。,定义,令P为椭圆曲线E上一点。对自然数n，可定义“乘法”,定理Mordell-Weil,令椭圆曲线E定义在有理数上 ， 为曲线上所有x、y坐标皆为有理数的点所成的集合（也包含无穷远点O），则,椭圆曲线（mod p）,10.2 椭圆曲线（mod p）,定理,令P3为质数。令定义在整数 上的椭圆曲线,其中a、 系数、均为整数且满足,则,为定义在FP上的椭圆曲线。,椭圆曲线（mod p）,定义椭圆曲线离散对数问题,定理,令E为定义在FP上的椭圆曲线，则E(F
4、P)的个数满足,其中误差项,定理,令椭圆曲线 (mod p)，则,加权投影坐标,10.3 加权投影坐标,性质,令椭圆曲线,令 ， 为E上的点（加权投影坐标表达式）。而点,若P1、P20，且P1P2，则加法公式为,若P1=P2，则 的公式为,定义在Galois域的椭圆曲线,10.4 定义在Galois域的椭圆曲线,定义,定义在特征值为2的Non-Supersingular椭圆曲线，可在适当的坐标系选取下表示成,加法律”可定义如下：,：,PQ：,密码安全曲线,10.5 密码安全曲线,例：,令p3为质数、b为整数，且p|b。令椭圆曲线,则E为Supersingular曲线。,证明：,考虑乘法群的Ho
5、momorphism：,故由Lagrange定理，可得,将信息转化为椭圆曲线代码,10.6 将信息转化为椭圆曲线代码,而信息m将对应到E(FP)之某点的x坐标值。然而，m3+am+b为完全平方数的概率为0.5，因此可添加若干位在m上，即,使得x3+ax+b为完全平方数，如此便可对应到E(FP)上的一点；而失败的概率，即m无法对应到的概率是为2-K，其中(m+1)KP。,而接收方收到信息Pm=(x,y)只需计算,椭圆曲线公开密钥密码算法,10.7 椭圆曲线公开密钥密码算法,质数曲线简例,选取一条20-bit质数曲线,（2）随机取整数,（1）随机取一个20-bit质数 p=681899,且,（3）
6、因为p小，可利用Legendre符号公式计算,（4）质因数分解g，得,（5）计算,故点P(1,65537)的秩为,椭圆曲线版的Diffie-Hellman密钥交换,算法椭圆曲线版的Diffie-Hellman密钥交换,Alice与Bob要用椭圆曲线密码共同约定密钥。,（曲线参数约定）约定 (E/Fq,P)。,Alice选择一正整数A，计算PA=AP，将点PA传送给Bob。,Bob选择一正整数B，计算PB=BP，将点PB传送给Alice。,Alice收到PB，计算PK=APB，PK即共同约定的密钥。,Bob收到PA，计算PK=BPA，PK即共同约定的密钥。,椭圆曲线版的ElGamal密码,算法椭
7、圆曲线版的ElGamal密码,Alice欲加密明文Pm代码成密文PC传送给Bob。,（曲线参数约定）约定 (E/Fq,P)。,（密钥产生）Bob随机选取一个整数B且B与g互质，即gcd(B,g)=1，计算PB=BP。公开密钥为(E/Fq,P,PB) ，私钥为B。,（加密）明文代码 。Alice取得Bob的公开密钥(E/Fq,P,PB) ，随机选取整数A，计算PA=AP，计算PC=Pm+APB，密文为(PA,PC)，传送给Bob。,（解密）Bob收到密文(PA,PC) ，计算Pm=PC-BPA得明文代码。,椭圆曲线的ElGamal数字签名,算法椭圆曲线的ElGamal数字签名,Alice要将信息
8、m数字签名成s传送给Bob，其中m为整数且 。,（曲线参数约定）约定 (E/Fq,P)。,（密钥产生）Alice随机选取一个整数A，计算PA=AP。公开密钥为(E/Fq,P,PA) ，私钥为A,数字签名,（1）Alice随机选取一整数k使得gcd(k,g)=1。,（2）计算R=kP。,（3）计算 ，其中x(R)为点R的x坐标。,（4）将数字签名 传送给Bob。,验证,（1）Bob收到数字签名，并取得Alice的公钥。,（2）计算,（3）若V1=V2则验收，否则拒绝。,椭圆曲线版的DSA，ECDSA,算法椭圆曲线版的DSA，ECDSA,椭圆曲线因数分解,10.8 椭圆曲线因数分解,算法椭圆曲线因
9、数分解,ECFactor(n) if(g=gcd(n,6)1) return g; m=n; for(r=2;m=2;r+) m=n(1/r); if(isInteger(m) return m; ; /判断n是否与6互质或n非某整数m的r次幂 Point: px=RandomInteger(1,n); py=RandomInteger(1,n); /P=(px,py)=px,py,1为椭圆曲线的点 newCurve: a=RandomInteger(1,n); b=py2-px3-a*px(mod n);,椭圆曲线因数分解,/E:y2=x3+a*x+b Discriminant: g=gcd
10、(4*a3+27*b2,n); if(g=n) goto newCurve; else if(1k; /选取适当的k值 compute: x,y,z=px,py,1; factor=1; for(B=2;B=k;B+), x,y,z=Bx,y,z (mod n); /以加权投影坐标公式计算 factor=gcd(n,z); if(1factorn) return factor; else if(factor=0) goto newCurve; else /factor=1 continue; ; if(factor=1) goto new;,ECCp-109挑战,10.9 ECCp-109挑战,ECCp-x代表随机的质数曲线，x代表x-bit的质数。 ECC2-m代表随机的二元曲线，m代表秩为2m的Galois域。 ECCk-m代表一种特殊的二元曲线，称之为Koblitz曲线，而m代表秩2m为的 Galois域。,并行Pollard Rho法,10.10 并行Pollard Rho法,