第10章椭圆曲线密码学

10.３椭圆曲线算术椭圆曲线理论是一个古老而深奥的数学分支，已有100多年的历史，一直作为一门纯理论学科被少数数学家掌握。它被广大科技工作者了解要归功于20世纪80年代的两件重要的工作。第一，Weil应用椭圆曲线理论证明了著名的费尔玛大定理。第二，NealKoblitz和V.S.Miller把椭圆曲线群引入公钥密码理论中，提出了基于椭圆曲线的公钥密码体制ECC（EllipticCurvesCryptosystem），取得了公钥密码理论和应用的突破性进展。20世纪90年代，最通用的公钥密码体制是RSA公钥密码体制和DH公钥密码交换算法。其密钥长度一般为512比特。1999年8月22日RSA-512被攻破，所以，这些公钥不得不被加长。为了达到对称密钥128比特的安全水平，NIST推荐使用3072比特的RSA密钥。显然这种密钥长度的增长，对本来计算速度缓慢的RSA来说，无疑是雪上加霜。ECC的提出改变了这种状况，实现了密钥效率的重大突破。大有以强大的短密钥优势取代RSA成为新一代公钥标准（事实标准）之势。ECC的安全性和优势得到了业界的认可和广泛的应用：（1）1998年ECDSA（椭圆曲线数字签名算法）被确定为ISO/IEC数学签名标准ISO14888-3;（2）1999年2月ECDSA被ANSI确定为数字签名标准ANSIX9.62-1998，ECDH（椭圆曲线Diffie-Hellman）被确定为ANSIX9.63;（3）2000年2月ECDSA被确定为IEEE标准IEEE1363-2000，同期，NIST确定其为联邦数字签名标准FIPS186-2。1.椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似，一般来计，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e(1)其中a,b,c,d,e是满足某些简单条件的实数。其中包括称为无穷远点的元素。密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式（1）中，所有系数都是某一有限域GF（p）中的元素（其中p为一大素数）。其中最为常用的是由方程y2≡x3+ax+b(modp)定义的曲线。（a,b∈GF(p),4a2+27b3≠0modp）椭圆曲线上的加法运算定义如下：（1）设L是通过P和Q的直线。L交E于P和Q，容易看出，L还交E于第三点，记作R’。对x轴反射R’，得到一点R,定义P+Q=R。见图1和图2.图2中的P点和Q点重合。（2）o为加法单位元（无穷远点），即对椭圆曲线上任一点P，有P+o=o+P=P.（3）P=(x,y)是椭圆曲线上的一点，它的加法逆元定义为-P=(x,-y)P+（-P）=o下面给出一个计算R的代数公式。椭圆曲线E上的两点P=（x1,y1）和Q=（x2,y2）可以PQR’RL图1EPR’R图2EL按照下面的规则相加：(1)如果x2=x1,y2=-y1,则P+Q=o;否则P+Q=（x3,y3）,其中x3≡λ2-x1-x2(modp)y3≡λ(x1-x3)-y1(modp)其中λ是直线L的斜率，λ≡(y2-y1)(x2-x1)-1modp当P≠Q时λ≡(3x12+a)（2y1）-1modp当P=Q时举例：设E是Z11上的椭圆曲线y2≡x3+x+6。请确定E上的点。解：从y2≡x3+x+6看出，a=1,b=6,则4a3+27b2≡8≠0mod11所以该椭圆曲线可用于密码体制。（1）当x=0时y2≡6mod11（2）现在求解方程（2），首先根据legendre符号来判断方程（2）有没有解：112113116而1323111131112可见1112113116方程（2）无解。（2）当x=1时，方程变为y2≡8mod11（3）现判断方程(3)有没有解。1111211833所以方程（3）也无解。（3）当x=2时，方程变为y2≡5mod11（4）151511115方程（4）有解，其解为y≡±5(11+1)/4≡±53≡±4(mod11)即有两个点（2，4），（2，-4）（4）当x=3时，y2≡3mod11（5）因为132311113所以方程（5）有解，其解为：y≡±3(11+1)/4≡±33≡±5(mod11)即有两个点（3，5），（3，-5）同理可以算出：当x=4,5,6,7,8,9,10时各方程解。结果如下表所示：xX3+x+6mod11是否为二次剩余y06否18否25是4，733是5，648否54是2，968否74是2，989是3，897否104是2，9可见E有13点（包括无穷远点o）.假设取p=（2，7）,计算2P:2P=P+Pλ≡(3x12+a)（2y1）-1modp≡(3╳22+1)(2╳7)-1mod11≡2╳3-1mod11≡8mod11x3≡λ2-x1-x2(modp)≡82-2-2≡5mod11y3≡λ(x1-x3)-y1(modp)≡8(2-5)-7≡2mod11所以2P=（5，2）下面计算3P3P=2P+P=(5,2)+（2,7）λ≡(y2-y1)(x2-x1)-1modp≡(7-2)（2-5）-1modp≡5╳（-3）-1modp≡5╳8-1≡2mod11x3≡λ2-x1-x2(modp)≡22-5-2≡8mod11y3≡λ(x1-x3)-y1(modp)≡2(5-8)-2≡3mod11可见3P=（8，3）如此继续下去，其余的乘积计算结果如下：P=（2，7）2P=（5，2）3P=（8，3）4P=（10，2）5P=（3，6）6P=（7，9）7P=（7，2）8P=（3，5）9P=（10，9）10P=（8，8）11P=（5，9）12P=（2，4）2.椭圆曲线上的密码体制（1）ElGamal密码体制设p是一个素数，g是Zp*的一个生成元（也叫原根）。明文空间P=Zp*，密文空间C=Zp*╳Zp*，选定0ap，计算b≡gamodp。私钥：a公钥：b加密算法：设明文为m，0≤mp，随机地选择一个正整数k，0≤kp，计算：y1≡gkmodp,y2≡mbkmodp密文c=(y1,y2)解密算法：m≡y2y1-amodp(2)基于椭圆曲线的ElGamal密码体制首先选取一条满足4a3+27b2≠0modp的椭圆曲线Ep（a,b），将明文消息通过编码嵌入到曲线上得点Pm，再对点Pm做加密变换。取Ep（a,b）上的一个点,Ep（a,b）和G作为公开参数用户选nA作为秘密钥，并以PA=nAG作为公开密钥。任一用：1)加密：用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下密文对：Cm={kG，Pm+kPA}={C1,C2}2）解密：C2-nAC1=Pm+kPA-nAkG=Pm+knAG-nAkG=Pm举例：利用上例的椭圆曲线y2≡x3+x+6。取G=（2，7）,私钥nA=7,则公钥为PA=nAG=7（2，7）=（7，2）若明文Pm=（10，9），取随机数k=3,加密：C1=kG=3（2，7）=（8，3）C2=Pm+kPA=(10,9)+3(7，2)=(10,2)解密：Pm=C2-nAC1=(10,2)-7（8，3）=(10,2)-（3，5）=(10,2)+（3，6）=（10，9）3.椭圆曲线密码算法的优点ECC与RSA比较，有很多技术优点：（1）安全性能更高安全性能占绝对优势，ECC在计算复杂度上目前是完全指数级的，而RSA是亚指数级。（2）计算量小和处理速度快。（3）存储空间小。160bit的ECC与1024bit的RSA具有相同的安全强度210bit的ECC与2048bit的RSA具有相同的安全强度。意味着它所占的存储空间要小得多。这对于加密算法在资源受限环境上（如智能卡等）的应用具有特别重要的意义。（4）带宽要求低。习题：求出椭圆曲线E：y2≡x3-2mod7上的点，并：（1）在E上找到（3，2）+（6，5）的和。（2）在E上找到（3，2）+（3，2）的和。