第10章 椭圆曲线密码.ppt
返回总目录,第10章 椭圆曲线密码,教学目的,了解椭圆曲线密码了解椭圆曲线 了解ECCp-109挑战 了解并行Pollard Rho法,椭圆曲线,本章内容,椭圆曲线（mod p）,加权投影坐标,定义在Galois域的椭圆曲线,密码安全曲线,将信息转化为椭圆曲线代码,本章内容,椭圆曲线公开密钥密码算法,椭圆曲线因数分解,ECCp-109挑战,并行Pollard Rho法,椭圆曲线的安全度,椭圆曲线,10.1 椭圆曲线,定义,椭圆曲线即三次平滑代数平面曲线（Smooth Algebraic Plane Curve），可在适当的坐标下，表达成Weierstrass方程式,除了特殊系数，一般而言，可在适当的坐标下，表示成,在系数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种情形外，,椭圆曲线,定理,为交换群（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(FP)的个数满足,其中误差项,定理,令椭圆曲线(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曲线。,证明：,考虑乘法群的Homomorphism：,故由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）因为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密码,算法椭圆曲线版的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要将信息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 椭圆曲线因数分解,算法椭圆曲线因数分解,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+bDiscriminant:g=gcd(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=1continue;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法,
