椭圆曲线加密算法

椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为 ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别提出的。

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA 加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长

1.椭圆曲线

在数学上，椭圆曲线（英语：Elliptic curve，缩写为EC）为一代数曲线，被下列式子所定义

y2=x3+ax+b

其是无奇点的；亦即，其图形没有尖点或自相交。

满足此条件的a b满足：4a3+27b2≠0

图1

在基础上需要定义一个无穷远的点，将此点作为零点：此时椭圆曲线定义为：{(x,y)∈ℝ2|y2=x3+ax+b,4a3+27b2≠0}∪{0}

在椭圆曲线中的群的运算律：

1. 所有的点都在椭圆曲线上

2. 0点作为群上的单元点即

P+0=P

3. P点关于X轴的对称点为P点的逆即

P+(−P)=04.对于位于同一条直线上的三个点P,Q,R.则有

P+Q+R=0

图2

P+Q+R=0（无限远点

P Q R三个点的位置是任意的，他们满足加法的结合律，因为这个群是一个阿贝尔群。

2.椭圆曲线加法

当P和Q不相等时(x P≠x Q)

由于是在阿贝尔群上可以将P+Q+R=0改写为P+Q=−R所以在椭圆曲线上的加法定义为P Q 两点加法为P,Q两点连线与曲线的交点R的关于X轴对称点−R

图2-3

P+Q=-R

P Q两点的直线的斜率为：

m=y P−y Q x P−x Q

这条线与曲线的交点为：R=(x R,y R)

x R=m2−x P−x Q

y R=y P+m(x R−x P)

因此(x P,y P)+(x Q,y Q)=(x R,−y R)如果在图上表示即为上述的P+Q=−R

当P 和Q 不相等时(x P =x Q )( y P =−y q )

因为p +(−p )=0

图 3 P Q 两点相同时

直线的斜率为

m =3x P 2+a 2y P 经计算的

m =3x P 2+a 2y P x R =m 2−x P −x Q y R =y P +m(x R −x P )

图 4

通过上面的加法运算我们可以得出其标量乘法运算可以得出

nP=P+P+⋯+P

⏟

n times

从上式可以看出当我们计算nP的时候需要做n次加法，如果n有k位那么的计算时间复杂度变为O(2k),这显然不是快捷的方式。

其中一种加快计算的方式是将这些加法运算的次数减少，我们将n写成2进制形式，然后我们按每位计算，每次复用上一次的结果如当n=151时，其二进制位100101112所以

151=1⋅27+0⋅26+0⋅25+1⋅24+0⋅23+1⋅22+1⋅21+1⋅20 =27+24+22+21+20

所以如果运用在上面的标量乘法时，其运算可以简化为：

151⋅P=27P+24P+22P+21P+20P

4.离散空间椭圆曲线

我们将曲线上的点全部局限于F p上此时离散形式的椭圆曲线变为：{(x,y)∈(F p)2 | y2≡x3+ax+b(modp),4a3+27b2≢0(modp)}∪{0}

0仍然为无穷远点，a,b 为整数Array

图5y2≡x3−7x+10(modp)p=19,97,127,487的图示

在离散椭圆图上的加法和曲线上的加法的定义类似，在离散的椭圆曲线中，直线的方程变为ax+by+c≡0(modp)，点P，Q两点的加法的操作也是基于这个定义上下图展示了y2≡x3−x+3(mod127)曲线上P=(16,20)和Q= (41,120)两点之间的加法直线y≡4x+83(mod127)在此空间上是一组距离相等的平行线

图6

5.离散椭圆曲线代数加法

对照曲线上的加法，离散空间椭圆曲线加法公式可以写作

x R=(m2−x P−x Q)modp

y R=[y P+m(x R−x P)]modp

=[y Q+m(x R−x Q)]modp

如果P≠Q，此时的m的值的形式为

m=(y P−y Q)(x P−x Q)−1modp

如果P=Q时：

m=(3x P2+a)(2y P)−1modp

在离散型的椭圆空间里面我们知道点的数目是有限的，而这些点的个数我们称为椭圆曲线群的阶数

同样的在离散空间，对于曲线上的点同样满足标量加法的法则nP=P+P+⋯+P

⏟

n times

但是在离散空间椭圆曲线加法会有一个有趣的现象，对一个点进行有限次的加法，存在一个是n使得nP=P例如在曲线y2≡x3+2x+3(mod97)的一点P=(3,6),计算其的标量乘法，计算结果如下：

图7

可以看出P=(3,6)经过6次加法后又回到本身，也即是5P=0

所以对于P的加法可以写作kP=(k mod 5)P

可以证明的是一个点的加法所构成的子集是一个循环的子集

首先一个点的加法所得到的点一定是有限的，因为加法所获得的点全部都在父

集上的，父集的大小是有限的，所以经过有限次的加法后所获得的结果必定会

重复，那么结果就会重复下去。只需证明第一个重复的值是P即可。

假设第一个重复的值不是P，而是kP,那么后面的结果也必然是kP的倍数，假设

重复的次数为n,

如果(n,k)不为1，那么存在使得km mod n=0即kmP=0即(km+1)P=P

与假设矛盾

如果(n,k)=1那么kmP=(m mod n) kP那么存在一个数使得mk mod n=1即mkP=(mk mod n)P=P与假设矛盾。

在一个循环子集中将P称之为生成点或者基点，其子集的点的大小n称之为子集

的阶即nP=0

由拉格朗日定理可知子群的阶n是全集阶N的因子

例如y2=x3−x+3在F37上N=42它的子集大小只能n=1,2,3,6,7,14,21,42为基点P=(2,3),因为P≠0，2P≠0…7P=0所以构成的子集的大小为7

如果在F29上，其阶为N=37 所以其子集大小只能为n=1或者 37

对于ECC（椭圆加密算法），需要找到一个具有高阶子集，一般情况下选择一个椭圆曲线并计算他的阶，然后找到一个数字大的因子n作为子集的阶，如果这个子集的基点为P则nP=Np=0

给定n和P，那么需要计算n次计算出Q=nP,如果只给出P,Q如何计算出n这就是所谓的对数问题。这个问题也就是椭圆曲线的离散对数问题而求解这个对数问题是非常困难的，而正是由于这种困难使得我们使用椭圆加密算法变得更加可靠

与其他类似的加密算法相比，破解椭圆加密算法更加困难，这也意味着更少位数的秘钥k可以达到同类算法同样的安全强度

6.椭圆加密算法ECDH 和ECSDA

椭圆加密算法是基于有限域的离散型的椭圆曲线的循环子集上，定义一个这样的子集需要以下参数，

●有限域的大小素数P

●椭圆曲线方程a和b

●用于生成子集的基点G

●子集的阶n

●子集的辅因子 h

总的来说一个椭圆加密算法基于(p,a,b,G,n,ℎ)参数上

(1)ECDH

同其他非对称加密算法一样，需要计算私钥和公钥，

在ECC中私钥是一个随机数d来自于{1,…,n−1}(n是子集的阶)

公钥是曲线上的一个点H=dG（G是子集的基点）

如果我们知道d和G，找到公钥H是很容易的，但是如果只知道H和G找到私钥d是及其困难的，这等同有在做离散对数问题，上文有提到这个问题在现在来说还没有有效的算法，所以是很困难的。

ECDH是迪夫赫尔曼算法的一个变种，它实际上是一个秘钥共识协议，ECDH协议定义了秘钥的如何产生以及如何交换秘钥。

如果Alice和Bob需要交换秘钥，中间人Hack可以在两者之间监听

1.Alice和Bob使用同样参数的椭圆曲线，并且随机产生各自的秘钥d A和d B,并

且计算出各自的公钥H A=d A G和H B=d B G,

2.他们彼此交换各自的公钥H A和H B,而中间人也将他们的公钥截获，但是他们

都不能从这些信息中计算出他们的私钥

3.Alice计算出S=d A H B，Bob计算出S=d A H B，明显的是他们各自计算出的结

果是一致的。

S=d A H B=d A(d B G)=d B(d A G)=d B H A

而中间人不能从公钥中计算出S，所以Alice和Bob共享了密码S,这也正是迪夫赫尔曼所要解决的问题。

当Alice和Bob获得了共同的秘钥S，他们就可以使用对称加密算法如AES，3DES来加密他们的信息了。

(2)ECSDA签名算法

在比特币的交易中，一笔交易会在整个区块链网络中传播，每个节点需要验证一笔交易的有效性，通过交易中解锁脚本去验证交易中的输入是否是有效的。这其中正是使用了ECDSA算法来验证。

假如Alice需要对一个信息进行签名，Bob需要使用Alice的公钥来验证这个信息。Alice和Bob都使用的是同一个参数相同的椭圆曲线函数。ECDSA作用在的是信息的hash值上的，且这个值是被截取后的使得其大小与这个曲线的子集的阶一致。将这个截取后的hash值定义为 z

图8

算法的流程是

1.Alice随机选择一个随机数k (k2.计算s=k−1(z+rd A)modn，d A是Alice使用的私钥，k−1是k关于n的模逆，

如果s为0则重新选择k再次计算。将(r,s)作为签名信息

3.Bob此时有了Alice的公钥H A和签名信息(r,s)，首先计算

u1=s−1zmodn

u2=s−1rmodn

4.然后在计算

P=u1G+u2H A

如果r=x P modn，则可以判定这个信息是来自于Alice的

（3）算法的正确性证明

从验证的步骤往前回溯有

P=u1G+u2H A

=u1G+u2d A G

=(u1+u2d A)G

将u1和u2的等式带入得到

P=(u1+u2d A)G

=(s−1z+s−1rd A)G

=s−1(z+rd A)G

因为对于基点G来说它的阶为n,因此为了简洁，可以省去mod n

由模逆运算的性质可以将s=k−1(z+rd A)modn改写为k=s−1(z+rd A)modn 于是有

P=s−1(z+rd A)G

=kG

可以看出此式正是通过随机数k生成点P的运算，回溯到了最开始的计算，可以验证算法的正确性

（4）算法的漏洞

在Console Hacking 2010大会上，黑客披露了一个Sony PS3的关于ECSDA的一个破解方式。造成这个漏洞的原因在于PS3 在ECSDA算法中未随机的选择数字k

用来生成点P,从而造成私钥泄露。

在此处键入公式。

假设我们有两笔使用相同k值签名的信息，这两笔信息的hash为(z1,z2)，他们的签名信息为(r1,s1)和(r2,s2)

●首先他们的r1=r2，因为k值相同

●考虑(s1−s2)modn=k−1(z1−z2)modn

●将两边同时乘以k，k(s1−s2)modn=(z1−z2)modn

●两边同时除以(s1−s2)得到k=(z1−z2)(s1−s2)−1modn 上面的最后一个式子我们可以计算得到k，从这个确定的k可以计算得出私钥s=k−1(z+rd S)modn⇒d S=r−1(sk−z)modn

从上述分析可以看出相同k是可以导致私钥泄露的

所以随机数k在ECSDA算法中扮有重要角色，如果在比特币的交易中