4.7 椭圆曲线密码算法（ECC）

数学家对椭圆曲线的研究始于19 世纪中叶，积累了丰富而深厚的理论。1985 年，Neal Koblitz和Victor Miller分别独立地提出了椭圆曲线密码体制。多数公钥密码如RSA，Diffie-Hellman算法等都使用非常大的数或多项式，给密钥和信息的存储和处理带来很大的运算量。椭圆曲线是一个代替，可以用更小的尺寸得到同样的安全性，密钥长度为160 位的椭圆曲线密码系统可以具有与密钥长度为1024位的ElGamal或RSA密码系统相当的安全性。所以近年来，椭圆曲线密码系统在商业应用领域也开始得到越来越多的关注，ANSI，IEEE，ISO和NIST都制定了ECC标准草案。ElGamal密码体制能够在任何离散对数难处理的有限群中实现，ECC算法就是基于椭圆曲线群上的离散对数难题。

4.7.1 椭圆曲线的概念

域K上的椭圆曲线E由Weierstrass方程定义：

其中a1，a2，a3，a4，a6∈K且Δ≠0，Δ是E的判别式，具体定义此处省略。密码学上通常使用如下简化形式的椭圆曲线:

其中a，b∈K，曲线的判别式是Δ=-16（4a3+27b2），Δ≠0确保椭圆曲线是“光滑”的，即曲线的所有点都没有两个或两个以上不同的切线。图4.5给出两个实数域上椭圆曲线的例子。满足式（4.2）的所有点（x，y）和一个被称为无穷远点（point at infinity）或零点（zero point）的元素O组成点集E（a，b）。点集E（a，b）按照一定运算法则构成一个加法群，群上的加法规则可以用几何方法说明如下：

● 若曲线中的三点在一条直线上，则其和为O。

● O用做加法的单位元，因而O=-O，对于椭圆曲线上的任何一点P，P+O=P。

● 一条垂直的线与曲线相交于两个x坐标相同的点P1，P2，则P1+P2+O = O，于是P1 = -P2。因而一个点的逆元是与其有着相同x坐标和相反的y坐标的点，如图4.5（b）所示。

● 要对具有不同x坐标的两个点Q与R进行相加，先在它们之间画一条直线并求出第三个交点P1，容易看出这种交点是唯一的，除非这条直线在Q或者R处是曲线的切线，这时分别取P1=Q或者P1=R，那么注意到Q+R+P1=O，因此有Q+R=-P1，如图4.5（a）所示。

● 一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S。

显然，根据定义，前面定义的加法满足交换律和结合律。而一个点的倍乘定义为：

也称由P和k计算kP的运算为椭圆曲线多倍点运算（Point multiplication）或椭圆曲线标量乘法（Scalar multiplication）。

4.7.2 有限域上的椭圆曲线

密码学上关心的是一种受限形式的椭圆曲线，这种椭圆曲线定义在一个有限域上，不用实数域上的椭圆曲线做加密，原因是显而易见的，计算机本身是离散的，做实数运算会有舍入误差，而且可能溢出。椭圆曲线密码使用系数与变量定义在有限域的曲线，通常使用的有两类：定义在素数域GF（p）上的Ep（a，b）与定义在GF（2n）上的二元曲线E2n（a，b）。讨论较多的是定义在素数域GF（p）={0，1，2，…，p-1}上的椭圆曲线，此时变元和系数均在素数域GF（p）中取值，定义如下

其中p是奇素数，且4a3+27b2≠0mod p。

满足以上方程的小于p的非负整数对（x，y）加上无穷远点O组成集合Ep（a，b）。Ep（a，b）通过如下方式计算，针对所有的0≤x<p，计算x3+ax+b mod p，确定是否可以求出有效的y，如果是有效的y，则得到曲线上的点（x，y），其中x，y<p。对于任意点P，Q∈Ep（a，b），有如下运算规则：

● P+O=P

● 如果P=（x，y），则P+（x，-y）=O，（x，-y）点是P的逆元，记为-P，并且-P也在Ep（a，b）中。

● 如果P=（x1，y1），Q=（x2，y2），则P+Q=（x3，y3）为

x3=（λ2-x1-x2）mod p

y3=（λ（x1-x3）-y1）mod p

其中，如果P≠Q，则λ=（（y2-y1）/（x2-x1））mod p

如果P=Q，则λ=（（23x1 +a）/（2y1））mod p

● 乘法的定义为重复相加。如3P=P+P+P。

例如，取p=29，a=4，b=20，4a3+27b2=11056≠0mod p，定义在素数域GF（29）上的椭圆曲线y2=x3+4x+20在GF（29）上的解为：

（0，7），（0，22），（1，5），（1，24），（2，6），（2，23），（3，1），（3，28），（4，10），（4，19），

（5，7），（5，22），（6，12），（6，17），（8，10），（8，19），（10，4），（10，25），（13，6），（13，23），

（14，6），（14，23），（15，2），（15，27），（16，2），（16，27），（17，10），（17，19），（19，13），

（19，16），（20，3），（20，26），（24，7），（24，22），（27，2），（27，27）

这些点加上无穷远点O组成一个群E29（4，20）。

在E29（4，20）中，取点P1=（x1，y1）=（2，6），有-P1=（x1，-y1）=（2，-6），而-6mod29=23，因此-P1=（2，23），该点也在E29（4，20）中。

取点P1=（x1，y1）=（2，6），P2=（x2，y2）=（4，10），P1+P2=（x3，y3）可计算如下：

λ=（（y2-y1）/（x2-x1））mod p=（（10-6）/（4-2））mod29=（4/2）mod29=2mod29

x3=（λ2-x1-x2）mod p=（22-2-4）mod29=27mod29

y3=（λ（x1-x3）-y1）mod p=（2×（2-27）-6）mod29=2mod29

因此，P1+P2=（27，2）。

取点P1=（x1，y1）=（2，6），2P1=（x3，y3）可计算如下：

λ=（（23x1 +a）/（2y1））mod29=（（3×22+4）/（2×6））mod29

=（16/12）mod 29 =（4/3）mod 29 = 11mod 29

x3=（λ2-x1-x1）mod29=（112-2-2）mod29=1mod29

y3=（λ（x1-x3）-y1）mod29=（11×（2-1）-6）mod29=5mod29

因此，2P1=（1，5）。

4.7.3 椭圆曲线密码算法

4.7.3.1 椭圆曲线群上的离散对数难题

ECC是基于椭圆曲线离散对数难题（Discrete logarithm problem on elliptic curve，ECDLP）的密码体制。我们对有限域GF（p）的乘法群上的离散对数难题（Discrete logarithm problem，DLP）和ECDLP进行了一些比较，如表4.4所示，可以把ECC的加类比于模乘，ECC的重复相加类比于模幂，定义与GF（p）的乘法群上离散对数类似的ECDLP难题：

定义于有限域上的椭圆曲线对于加法构成了一个群Ep（a，b），G是Ep（a，b）一个阶为素数n的点，令Q=kG，其中Q，G属于Ep（a，b），0<k<n，

给定k，G，容易计算Q

给定Q，G，难以解出k

实际应用中，k的值非常大，从而使穷举攻击不可行。

4.7.3.2 基于ECDLP的D-H密钥交换

利用椭圆曲线可以进行类似的D-H密钥交换。首先选择一曲线Ep（a，b），其次，选择Ep（a，b）中的元素G=（x1，y1），使得G的阶n是一个大素数，G的阶是指满足nG=O的最小n值。用户A和B之间的密钥交换过程如下：

（1）A和B分别选取一个小于n的整数KRA<n和KRB<n作为私钥。

（2）然后分别计算其公钥：KUA=KRA×G，KUB=KRB×G。

（3）A和B分别秘密地计算其共享密钥：K=KRA×KUB，K=KRB×KUA。

两种计算结果是相同的，A和B获得了同样的密钥K=KRA× kRB×G。

取p=211，Ep（0，-4），这等价于曲线y2=x3-4，G=（2，2），可以算得241G=O。

A的私钥是KRA=121，因此A的公钥是KUA=121（2，2）=（115，48）。B的私钥是KRB=203，因此B的公钥是KUB =203（2，2）=（130，203）。它们共享的密钥是121（130，203）=203（115，48）=（161，169）。

4.7.3.3 基于ECDLP的加解密

基于ECDLP的加解密方法有多种，这里介绍一种最简单的基于ECDLP的加解密方法。首先选择一曲线Ep（a，b），其次，选择Ep（a，b）中的元素G，使得G的阶n是一个大素数，G的阶是指满足nG=O的最小n值。用户A和B之间的加解密过程如下：

（1）密钥计算：用户A秘密选择整数nA，计算KUA = nAG，然后公开（p，a，b，G，KUA），KUA为公钥，nA为私钥。

（2）加密：用户B要把消息M发给A，先把消息M变换成为Ep（a，b）中一个点Pm，然后，选择随机数r，计算密文Cm={rG，Pm + rKUA}，如果r使得rG或者rKUA为O，则要重新选择r。

（3）解密：用户A对密文Cm解密，（Pm+rKUA）-nA（rG）=Pm+rnAG-nArG =Pm。

与有限域GF（p）上的ElGamal加密算法相同，加密信息有扩张。

取p=751，Ep（-1，188），这等价于曲线y2=x3-x+188，G=（0，376）。假设B希望发送一个报文给A，这个报文被编码为椭圆曲线的点Pm=（562，201），B选择随机数r=386，A的公开密钥是KUA=（201，5），我们有rG=386（0，376）=（676，558），Pm+rKUA=（562，201）+386（201，5）=（385，328）。因此B发送密文{（676，558），（385，328）}。

4.7.3.4 椭圆曲线密码体制的安全性

经过密码学研究人员20多年的努力，椭圆曲线密码已经得到了长足的发展。各种基于椭圆曲线的加密算法和密钥交换机制被提出并实现，椭圆曲线密码算法的标准化工作也正在进行中。IEEE的P1363定义了椭圆曲线的公钥系统。无线通信的WAP协议中的WTLS层，也可以选择使用椭圆曲线密码系统。RSA和椭圆曲线密码分别基于不同的数学难题，相对来说，椭圆曲线密码能用更少的密钥位来获得更高的安全性，而且加密速度比RSA要快，使它在许多计算资源受限制的环境里得到广泛的应用。目前已知求解椭圆曲线离散对数问题的最快方法为Pollard rho方法，表4.5 比较了这种方法与使用扩展数域筛法（GNFS）分解整数来破解RSA算法的效率。两者都可以用于加解密，密钥交换和数字签名。