密码学基础2：椭圆曲线密码学原理分析

首先要说明的一点是，椭圆曲线不是椭圆。椭圆方程是下面这样的：

而通常我们讨论的椭圆曲线的曲线方程是一个二元三次方程，它有多种形式，在椭圆曲线密码体系中，最常用的是如下的Weierstrass通用式(curve25519 等其他类型的椭圆曲线本文不讨论)：

之所以取名叫椭圆曲线，是因为该曲线方程跟求椭圆弧长的积分公式相似。从曲线方程和图像易知，椭圆曲线关于X轴对称。判定式不等于零是为了椭圆曲线不存在奇异点，即处处光滑可导，这样才能进行椭圆曲线上的加法运算。下面是一些适合用于加密的椭圆曲线，其中。

椭圆曲线加密算法涉及数学中的群论、有限域等内容，这节简要介绍下相关数学理论。亦可以跳过直接看第3节，遇到相关名词再查阅即可。

在讨论群之前，先说说集合。集合简单来说就是把一堆东西放在一起，如自然数集合。当然光有一堆东西还不够，东西之间相互作用才能更好的描述大千世界。于是，自然数集合通过加减运算衍生出整数集合、整数集合经过乘除又可以衍生出有理数，而后通过无理数的加入又衍生出实数集合、负数开方引入了复数集合。群则是集合和一个二元运算。

而如果再满足交换律，则该群就被称为是一个阿贝尔群。

根据群的定义，整数的加法运算就是一个群，而且还是一个阿贝尔群。而自然数的加法运算就不是一个群。整数加法运算构成群，因为它满足群的定义：整数加法的封闭性、结合律、交换律都成立。整数加法运算中单位元是 0。所有整数 n 都有加法逆元 -n。

在密码学中一般都需要一个有限的群，定义如下:

为了使一个结构同时支持四种基本算术(即加减乘除)，我们需要一个包含加法和乘法群的集合，这就是域。当一个集合为域的时候，我们就能在其中进行基本算术运算了。

所以域中元素只要形成加法群和乘法群并满足分配律就行，因为群中元素都有逆元，减法/除法可以转换为加/乘元素的逆元实现。实数集合是一个域，加法群中单位元是 0，每个实数都有加法逆元，乘法群中单位元是，每个非零实数都有乘法逆元。而整数集合就不是域，因为大部分元素没有乘法逆元，不能构成一个乘法群。

在密码学中，通常只对有限元素的域感兴趣，这种域称为有限域(Finite Field)。有限域中我们经常用到的是素数域，所谓素数域，就是阶为素数的有限域。 比如当 p 为素数时，整数环就是一个素数域，可以记作。在素数域中进行算术运算，需要遵守整数环的规则，即加法是模 p 加法，而乘法是模 p 乘法。

例如对于有：

椭圆曲线上的点经过一种特定的加法运算可以让椭圆曲线在实数域构成一个群。

无穷远点 ：定义一个无穷远点，即经过椭圆上任意一点的与X轴垂直的直线都经过该点。可能有人疑惑垂直于X轴的直线是平行线，为啥可以定义为都经过点？因为在非欧几何中，可认为平行线在无穷远处会交于一点。

椭圆曲线点加法 ：椭圆曲线上经过和两个点的直线与椭圆曲线的交点记作，根据定义有以及。继而定义椭圆曲线点加法：，即加法结果是经过点且与 X 轴垂直的直线与椭圆曲线的另外一个交点，简单来说，就是交点关于 X 轴的对称点。

椭圆曲线群：定义为椭圆曲线在实数域上的点集以及点加法

由此可知，椭圆曲线上的点在椭圆曲线加法运算上构成了一个阿贝尔群。增加了单位元后，椭圆曲线方程改为：

由定义可知，，所以，最终加法只需要计算交点的逆元即可。 几种特殊情况说明：

上一节定义了椭圆曲线几何上意义的点加法，需要转换为代数加法以方便计算。 要注意的是，这并不是两个点的坐标简单相加 。

假设直线 PQ 的斜率，然后将直线方程代入曲线可以得到： , 转换成标准式，根据韦达定理，即而可求得，想了解具体推导过程的可参见 [cubic-equations] 。

斜率计算需要区分两种情况，当 P=Q 时求椭圆曲线在 P 点的切线斜率(求导)即可：

可以简单验证，比如椭圆曲线是，通过参考资料1的 [可视化工具] 可得。容易验证，与代数加法公式计算结果一致。

对于特殊情况中有一个是切点的情况，如，计算方式不变，易得。而对于特殊情况，采用切线斜率亦可验证公式正确。

在实际加密算法中，我们通常需要多次通过椭圆曲线加法来实现一次加密，如下图所示：

图中打点的过程就是：

而在实际加密算法中，我们常常是使用一个点自己叠加，即初始直线变成椭圆曲线的切线即可，像下面这样：

我们定义对一个点 P 进行 n 次加法得到 nP，称之为标量乘法。如前面例子中。

不过，当 n 很大时，执行 n 次加法需要时间，效率有问题。 因为椭圆曲线点加法在实数域构成阿贝尔群，满足交换律和结合律，于是可以通过 [Double-and-add] 算法进行优化 。比如，其二进制表示为，通过优化只要7次倍乘和4次加法计算即可，时间复杂度降到。这是一个很好的单向函数，正向计算容易，而反向和蛮力计算复杂。

令，则 Q 作为公钥，n 为私钥。如果要破解该密钥，问题就是 "Q = nP，如果已知 P 和 Q，如何求解 n"? 这个问题是比较困难的。不过由于在实数域上曲线连续，可能会更容易找到一些规律进行破解。而且实数域上数值大小没有限制、浮点数等问题而导致计算效率问题，在实际应用中常将椭圆曲线限制到一个有限域内，将曲线变成离散的点，这样即方便了计算也加大了破解难度。

前面提到为了安全性和便于实现，需要将椭圆曲线限制到一个有限域内，通常用的是素数域 (即对于点为素数)。于是破解就会变成一个离散对数问题，这比连续曲线上的对数问题会难很多。素数域下椭圆曲线定义如下：

下面是曲线和的图像。可以发现，椭圆曲线变成了离散的点，且关于对称。

定义上椭圆曲线点加法如下，公式跟实数域上相比只是多了模操作。

斜率 m 计算同样分两种情况：

椭圆曲线在素数域上的点加法依然构成阿贝尔群。单位元依旧是无穷远点，元素的逆元变成。而交换律、结合律、封闭性则可以通过素域上的模加法、模乘法来证明。实数域的椭圆曲线点加法定义是有明确几何意义的，从几何上好证明。而椭圆曲线在就没有明显的几何意义了，观察可发现三点满足，群律的证明过于繁琐，略去(其实是没有找到一个简易的证明)。

以前面曲线为例，，则有，且和都在椭圆曲线上。从图形上看，在直线上。

在有限域下，椭圆曲线加法群的元素是有限的，元素数目就是群的阶。

如椭圆曲线，其在素数域中元素有，阶为24(23个素数域中的点 + 1个无穷远点)，如果 p 很大的话，则通过蛮力计算阶是很难的，好在使用 [Schoof算法] 可以在多项式时间内计算出群的阶。计算椭圆曲线在有限域上点的数目可以参见 [Counting points on elliptic curves] 。

Schoof算法运用了 Hasses 定理。Hasses定理给出了椭圆曲线在的阶的范围，可以看出，当 p 很大时，阶跟 p 的值是比较接近的。

跟实数域一样，在素数域里面也是选取一个点 P，然后计算倍乘 nP 作为公钥。还是以为例，，我们采用素数域下新的计算公式计算。

可以发现，即 P 的标量乘法得到的点集是原椭圆曲线群的一个子集，则它是原椭圆曲线群的一个子群，而且是循环子群。子群中元素个数称为子群的阶(示例子群的阶为8)，点 P 称为该子群的基点或者生成元。循环子群是椭圆曲线密码体系的基础，我们期望子群中元素越多越好，如何找到一个合适的子群尤为重要。

首先要解决一个问题，就是已知下的椭圆曲线上的点 P，如何求得 P 的倍乘运算后生成的子群的阶? 根据拉格朗日的群论定理，子群的阶是父群的阶的约数。求解曲线上点 P 生成的子群的阶可以用下面方法：

以示例曲线为例，父群的阶是，则以曲线上的点生成的子群的阶只能是。对于点，故其生成的子群的阶就是 8，而点生成的子群的阶则正好等于父群的阶24。

在加密算法中，我们期望找到一个阶高的子群。不过，通常不是先去找个基点，然后计算子群的阶，因为这样过于不确定，算法上不好实现。相反地，先选择一个大的子群阶，然后再找生成该子群的一个基点就容易多了。

前面提到，子群的阶 n 是父群的阶 N 的约数，即有，h 是一个整数，我们称之为子群的余因子(cofactor)。因为，所以有:

通常会选择一个素数作为子群的阶，即 n 是素数。可以发现，点生成了阶为 n 的子群( 除外，因为这个子群的阶为1)，不等于的点就是我们寻找的基点。具体步骤如下：

需要注意，上面算法里的 n 必须是素数，否则计算的基点 G 生成的子群的阶可能是 n 的约数而不是 n，不符合要求 。以曲线为例，，我们选择，则，随机选取一个点，计算，恰好满足要求。

如前所述，椭圆曲线加密算法工作在素数域下的椭圆曲线循环子群中，需要的域参数(Domain Parameter)包括：

如比特币用来做数字签名中采用的椭圆曲线 [secp256k1] 的域参数如下：