咖说 | 大白话椭圆曲线加密算法（上）

"

收集一众行业大咖观点，探索区块链商业及应用。百家争鸣、百花齐放，说理、解密、预测和八卦，了解行业内幕，看咖说就够了！

投稿请联系 ：[email protected]

本文作者：虞双齐，区块链技术 CTO，登录学院合伙人。

"

你应该听过 ECC，ECDH 或者 ECDSA。ECC 是椭圆曲线加密算法（Elliptic curve cryptography）的简称，后面两个是基于它的算法实现。

在数字货币加密技术中，不得不谈 ECC，它是数字货币的安全基石。本文不涉及 ECC 中复杂的数学知识，笔者将努力使用简单通俗的语言来解释 ECC 是如何提供与保障加密安全的。 

整篇文章，先讲解所涉及的理论基础知识，然后讲解 ECC 的定义，再通过实例来讲解 ECC 的加密解密原理和 ECDSA 的签名原理。对理论基础不了解的读者，请务必掌握理论基础后再继续往下看，不推荐跳读。 

 1. 椭圆曲线理论基础 

1.1 定义 什么是椭圆曲线？

在数学上，它是下方方程所有点的集合。

下图是不同 a，b 得到的不同图形的椭圆曲线。可以看到椭圆曲线的形状，并非椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程，故得此名。

随着 a，b 的不同，椭圆曲线也会在平面上呈现不同的形状。辨识度很高，可以看到椭圆曲线始终是关于 x 轴对称的。

方程后面的判别式（如下图）是来保障曲线的光滑（非奇异），也就是说在曲线里面不能有尖点、自相交点和孤立点。从而保证椭圆曲线上所有的点都有切线。

上方曲线中他们的判别式均为0。左曲线带尖点；右曲线曲线自相交。他们都不是有效的椭圆曲线。

 1.2 四则运算 

不同于代数几何中的四则运算，在椭圆曲线中有定义自有四则运算。  

1.2.1 加法运算 

已知椭圆曲线上的点 P 和 Q，求 P+Q。  

首先在曲线上标出点 P 和点 Q。再做经过点 P 和 Q 的直线，与曲线相交于第三点 R。继续做点 R 关于 X 轴的对称点 -R。这个 -R 点就是点 P 和 Q 相加得到的点，记作 P+Q=-R。

因椭圆曲线是关于 X 轴对称的，-R 是点 R 的对称点， 点 -R 必然也在椭圆曲线上，换句话说 P+Q 也在椭圆曲线上。   

点 R 的存在对于 -R 至关重要。在大多数情况下直线一定将和椭圆曲线相交于第三点。如果直线和椭圆曲线没有第三个交叉点时，即点 R 不存在时，就无法按上面方法求 P+Q。以下情况中，点 R 不存在。  

当 P = -Q 时，直线将与 Y 轴平行，没有第三个交点。假设 P+Q=O，此时 P +Q =P+(-P)=O。移项得到 P + O = P。 

这意味着点 P 加上一个点 O 后还是自身点 P。我们把这个点 O 作为加法的单位元，曲线上的任意点与单位元相加不会改变其值。实际上点 O 表示平行线的相交点，称为无穷远点 O∞。可以理解为所有平行于 y 轴的直线交于 O 点。  

当 P=Q 时，只能以点 P 作为切点做一条关于椭圆曲线的切线，切线将与椭圆曲线相加与另一点，记做点 R。同样，做点 R 的关于 X 轴的对称点 -R。这个 -R 点就是点 P 和 P 相加得到的点，记作 P+P=2P=-R。

在图像上，我们可以非常便捷的找到 P+Q 点。而在数学上，该如何计算呢？可以通过代数算法来计算 P+Q，但这里不展开讲解，本文将借助网页工具《Elliptic Curve point addition (ℝ)》来进行求解。

1.2.2 减法运算

已知椭圆曲线上的点 P 和 Q，求 P-Q。 

因 P -Q = P +(-Q)，求 P-Q 就是点 P 与点 -Q 的加法运算。而点 -Q 就是点 Q 对称点，在运算中称 -Q 是 Q 的负元，Q(x,y) 的负元是 (x,-y)。综上，可得 P-Q 的计算公式如下： 

1.2.3 乘法运算

已知椭圆曲线上的点 P 和数值 n，求 nP。  

前面已计算出 P+P，同理可以继续计算出 P+P+P=2P+P。  

重复 n 次加法运算就可以得到 n 次点 P 相加的结果，记为 nP 。我们把这个过程叫做 P 的自累。  

这就是乘法运算，比如 3P=P+P+P，通过进行 3 次加法运算就可以得到 3P 的值。思考：如果 n 相当大，如何提高加法运算效率？  

1.2.4 除法运算

已知椭圆曲线上的点 P 和数值 r，求 r-1P。  

注意，这里的 r-1 并不是表示 r 的负一次方。在椭圆曲线中有如下定义。  

当已知 r 和单位元 O 的值即可求解出 r-1，从而使用乘法求解 r-1P。 

假设已知椭圆曲线上的点 P(1,4) 和 r=4，椭圆曲线单位元为 8。则有 4•r-1=8，得 r-1=2，r-1P=2P。 

 1.3 有限域GF(p) 

有限域是指有限个元素的域，记做 GF(p)，其中 p 是质数，有{0,1,2,3...,p-1}共 p 个元素。例如GF(7)={0,1,2,3,4,5,6}。

GF(p) 中的四则运算都是基于取模运算的，就是小学学过的带余除法的余数。例如：12 除以7，商为1，余数为5，记做 12 mod 7 =5 。 

如果两个不同的数 a，b 除以同一个数 p 之后余数相同，称之为 a，b 模 p 同余，记 a mod p = b mod p。为了简便，我们把“mod p”统一写到最后面，并且为了防止与“a=b”混淆，使用恒等符号“≡”，记 a ≡ b (mod p)。 

而椭圆曲线（如 y2=x3+x+1）是定义在实数域上的，实数是连续的，导致了椭圆曲线的连续（右图）。这种连续性，使它并不合适用于安全加密。所以，可以把椭圆曲线定义在有限域上，使得曲线变成离散的点。下图是椭圆曲线取 p 为 2 所形成的离散的点。  

 1.4 有限域椭圆曲线 

如前面所述，在有限域 Fp 上的椭圆曲线，可用于加密。按下定义有限域椭圆曲线：

1.选择满足条件 4a3+27b2 ≠ 0 (mod p)，且小于p的两个非负整数 a、b。

2.满足方程 y2=x3+ax+b (mod p) 的所有点 (x,y)，再加上无穷远点 O∞，构成一条椭圆曲线。其中 x，y 属于 0 到 p-1 间的整数。

我们把这条椭圆曲线记为 Ep(a,b)，比如 E23(1,1) 方程如下，它的离散点如下图所示。          

 1.5 有限域椭圆曲线点的阶  

如果椭圆曲线 Ep(a,b) 上一点 P，存在最小的正整数 n 使得 nP≡O∞,则将 n 称为 P 的阶。 

若 n 不存在，则 P 是无限阶的。下图是 E23(1,1) 和 P(3,10) 各个阶的结果。从图可以明显看出，点的分布和顺序都是杂乱无章的。

  

计算可得 27P=-P=(3,13)，所以 28P=27P+P=-P+P=O∞，因此 E23(1,1) 上点 P(3,10) 的阶为 29。

 结语 

椭圆曲线加密算法是一种非对称加密算法，比 RSA 具有更高的效率和更短私钥。有效解决“提高安全强度必须增加**长度”的工程实现问题。且已得到广泛的支持和使用。使用 ECC 作为加密算法已成为首选项。

 参考资料 

· 掘金《椭圆曲线加密原理与应用》

· 掘金《椭圆曲线机密算法》

· 博客园-ECC椭圆曲线详解

END

了解最新动态