椭圆曲线密码学简介（一）：实数域的椭圆曲线及其群运算规则

Posted on In Views: Disqus:
本文对在加密货币当中大量使用的椭圆曲线密码学进行介绍。

经过前面几篇文章的介绍，相信对公钥密码学有所了解的各位应该已经听说过ECC，ECDH和ECDSA，ECC是椭圆密码学的简称，后面两个是基于椭圆密码学的具体算法。

目前我们可以在当前web和IT世界当中的三大主要技术TSL，PGP，SSH当中都可以找到椭圆曲线密码系统，更不用说Bitcoin以及其它加密货币了。

在ECC开始流行之前，几乎所有的公钥加密算法都是基于RSA，DSA以及DH，底层的加密系统对应的数学难题是模运算。RSA系列算法依然很重要，常常和ECC一同使用。考虑到RSA系列算法背后的原理比较简单，也很容易解释清楚，而ECC却依然蒙着神秘的面纱，本文将提供一个关于ECC的综述，并解释其安全背后的机理，也一并给出一些具体的例子。文章主要包含以下几个方面的内容：

  • 基于群论在实数域定义的椭圆曲线
  • 基于有限域的椭圆曲线和离散对数问题
  • 密钥对的生成和两个ECC算法：ECDH和ECDSA
  • ECC破解算法，与RSA算法安全性比较

在开始之前，你需要对集合论、几何学以及模运算有所了解，并且对对称加密和非对称加密比较熟悉，关于秘密学当中对“easy”问题和“hard”问题的定位也要有清晰的认识。

椭圆曲线（Elliptic Curves）

首先，什么是椭圆曲线，Wolfram MathWorld给出了完整的定义。而ECC算法所采用的椭圆曲线是一类可用Weierstrass公式加以描述的椭圆曲线EE，即：

E={(x,y)∣y2+A1y=x3+A2x2+A3x+A4}E=\{(x,y)|y^2+A_1 y=x^3+A_2 x^2 +A_3x + A_4\}

其中参数A1A_1至 A2A_2的不同取值决定椭圆曲线在坐标系中的形状。实际常用的形式是一类称为Weierstrass Normal Form（WNF）的的简化形式，即：

E={(x,y)∣y2=x3+ax+b}E=\{(x,y)|y^2=x^3+ax + b\}

由于ECC算法运算过程中需要使用WMF曲线的切线，因此为了使WNF曲线没有奇异点，即处处光滑可导，需要满足其判别式不为零，即：

Δ=4a3+27b2≠0\Delta=4a^3+27b^2\neq 0

同时，定义射影平面上的无穷远点，记为0.无穷远点是所有曲线在无穷远处的交点，也被称为理想点。因此，下面的论述当中所采用的完整的WNF椭圆曲线公式为：

E={(x,y)∈R2∣y2=x3+ax+b,Δ=4a3+27b2≠0}∪{0}E=\{(x,y) \in \mathbb{R}^2 | y^2=x^3+ax+b,\Delta=4a^3+27b^2\neq0\}\cup\{0\}

当令b=1b=1， aa从2递减1到-3的椭圆曲线如下所示：

下面我们再来看两条存在奇异点的曲线，如下图所示：

左边这条曲线的方程为y2=x3y^2=x^3，右边的这条曲线方程为y2=x3−3x+2y^2=x^3-3x+2，两者都不是合格可用的椭圆曲线。另外，不难发现，所有的椭圆曲线都是关于xx轴对称的。

群论（Groups）

从数学的角度，一个群是由一种集合以及定义在该群上的一个二元运算所组成，且符合“群公理”。具体完整的定义如下：假设G\mathbb{G}是一个非空集合，++是它的一个二元运算，如果满足以下条件，则G\mathbb{G}和 ++构成一个群。

  • 封闭性（closure）：若aa和 bb是集合G\mathbb{G}的成员，则存在唯一确定的c∈Gc \in \mathbb{G}，使得c=a+bc=a+b
  • 结合律（associativity）：即对G\mathbb{G}中任意元素a,b,ca,b,c，都有(a+b)+c=a+(b+c)(a+b)+c=a+(b+c)
  • 单位元（identify element）：存在G\mathbb{G}中的一个元素ee ，对任意所有的G\mathbb{G}中的元素aa，总有等式e+a=a+e=ae+a=a+e=a。则将ee称为单位元，也称幺元
  • 逆元（inverse）：对于G\mathbb{G}任意一个aa，存在G\mathbb{G}中的一个元素bb，使得总有a+b=b+a=ea+b=b+a=e（ee为单位元），则称aa与 bb 互为逆元素，简称逆元。bb 记作a−1a^{-1}

群运算的次序很重要，把元素aa 与元素bb结合，所得到的结果不一定与把元素bb与元素aa结合相同；亦即，a+b=b+aa+b=b+a（交换律）不一定恒成立。满足交换律的群称为交换群（阿贝尔群，以尼尔斯·阿贝尔命名），不满足交换律的群称为非交换群（非阿贝尔群）。

如果我们将加法作为集合的二元运算，那么加上整数集合Z\mathbb{Z}将得到一个群，且是一个阿贝尔群。而自然数集合N\mathbb{N}因为不满足逆元，则无法与加法构成一个群。

群的奇妙之处在于如果你能够上述四个性质，那么你可以获得一些其它有趣的性质。

比如，单位元是独一无二的，逆元也是独一无二的。对于任何一个aa，有且仅有一个bb满足a+b=0a+b=0。

椭圆曲线的群法则（The group law for elliptic cirves）

我们可以基于特定的椭圆曲线定义一个群，作如下规定：

  • 群的元素是椭圆曲线上面的点的集合
  • 单位元是在无穷远处的点，记为0
  • 一个元素点PP的逆元是其关于xx轴对称的点
  • 二元远算操作规则定义如下：在曲线上面找到对齐的在一条直线上面的三个非零的点：P,Q,RP, Q, R，三者之和为0，即P+Q+R=0P+Q+R=0

对于最后一点，我们的要求仅仅是一条直线上面对齐的三个点，而对齐本身与顺序是无关的，因此，如果P,Q,RP, Q, R是对齐的，则有P+(Q+R)=Q+(P+R)=R+(P+Q)=...=0P+(Q+R)=Q+(P+R)=R+(P+Q)=...=0，如此这般，我们也顺带证明了我们所定义的二元操作符是能够同时满足结合律和交换律的，我们在椭圆曲线上面定义的群还是一个阿贝尔群。

几何加法（Geometric addition）

庆幸我们是在一个阿贝尔群当中，我们可以将P+Q+R=0P+Q+R=0写成P+Q=−RP+Q=-R。这个形式的方程，可以让我们得到一种计算两个点PP和 QQ相加之和的几何方法：如果我们画一条直线通过PP和 QQ，那么直线会与曲线相交与第三个点RR。那么该点的逆元−R-R即为P+QP+Q的结果。

几何方法一目了然，但是还需要回答一些边界条件：

  • P=0 or Q=0P=0 \, or\, Q=0：考虑到无穷远点本身并不在这个平面上面，线是画不出来的，但是我们已经定义了0为单位元，对于任意PP和 QQ，都有P+0=P和0+Q=QP+0=P和0+Q=Q
  • P=−QP=-Q：经过这两个点的直线是一条垂直线，与椭圆曲线不会有第三个交点。但是PP是 QQ的逆元，根据逆元的定义有P+Q=P+(−P)=0P+Q=P+(-P)=0
  • P=QP=Q：会有无数条线经过这个点，情况会有一些复杂。令Q′≠PQ'\neq P，如果我们让Q′Q'无限得接近PP，则经过它们的直线会变成椭圆曲线的切线，此时有P+P=−RP+P=-R，其中RR是切线与椭圆曲线的交点。如下图所示：

  • P≠QP \neq Q，且找不到第三点RR：这个情况与上面的情况非常类似，此时过P,QP,Q的线就是椭圆曲线的切线。假设PP就是切点，在前面的一个情况当中，P+P=−QP+P=-Q，这个方程现在变成P+Q=−PP+Q=-P。反过来，如果QQ是这个切点，则有P+Q=−QP+Q=-Q。如下图所示：

现在几何加法已经能够覆盖所有的情况了，你只需要尺规就可以在椭圆曲线上面进行各种加法计算了。如果有兴趣也可以看看本文主要参考资料作者提供的图形化工具，这个工具提供了在实数域和离散有限域上面的加法和乘法实现，可以直观的看出这两者的区别，便于对文章的理解。

代数加法（Algebraic addition）

如果要使用计算机进行具体的加法远算，那么要从几何方法切换到代数方法。将以上所描述的规则转化为方程组是直截了当的办法，但是因为涉及到求解三次方程，会非常麻烦，这里仅仅给出最终结果，具体的求解和推导过程可以查阅相关资料，比如wiki百科等。

首先，对于简单的边界条件先排除掉，我们已经知道P+(−P)=0P+(-P)=0，以及P+0=0+P=PP+0=0+P=P。因此，我们只需要考虑两个非零且不对称的点P=(xP,yP),Q=(xQ,yQ)P=(x_P,y_P),Q=(x_Q,y_Q)。

如果PP和 QQ不相等，则通过这两个点的直线的斜率为：

m=yP−yQxP−xQm=\frac{y_P-y_Q}{x_P-x_Q}

则直线与椭圆曲线的第三个交点R(xR,yR)R(x_R,y_R)的坐标如下：

或者，等价于：

yR=yQ+m(xR−xQ)y_R=y_Q+m(x_R-x_Q)

因此有：(xP,yP)+(xQ,yQ)=(xR,−yR)(x_P,y_P)+(x_Q,y_Q)=(x_R,-y_R)，需要注意yRy_R的负号。

为了验证结果的正确性，需要验证以下两点：

  • RR是否在这条曲线上面
  • P,Q,RP,Q,R是否共线

验证三点是否共线相对简单，而验证一个点是否在椭圆曲线上面则相对复杂一些，需要求解三次方程。这里我们还是借助前面提到的图形化工具，在曲线y2=x3−7x+10y^2=x^3-7x+10上面取两点P=(1,2),Q=(3,4)P=(1,2),Q=(3,4)，得到P+Q=−R=(−3，2)P+Q=-R=(-3，2)，我们由此验证下前面的代数表达式是否正确：

m=yP−yQxP−xQ=2−41−3=1\begin{aligned} m &= \frac{y_P-y_Q}{x_P-x_Q} \\ &= \frac{2-4}{1-3} \\ &= 1 \end{aligned}

xR=m2−xP−xQ=12−1−3=−3\begin{aligned} x_R &= m^2-x_P-x_Q \\ &= 1^2-1-3 \\ &= -3 \end{aligned}

yR=yP+m(xR−xP)=2+1×(−3−1)=−2=yQ+m(xR−xQ)=4+1×(−3−3)=−2\begin{aligned} y_R &= y_P+m(x_R-x_P) \\ &= 2+1 \times(-3-1) \\ &= -2 \\ &= y_Q+m(x_R-x_Q) \\ &= 4+1 \times(-3-3) \\ &= -2 \end{aligned}

另外，当PP或者QQ其中之一是切点的时候，上述方程依然正确，具体读者可以自行验证。

而当P=QP=Q时，情况会稍微复杂一些：因为xP=xQx_P=x_Q，所以关于斜率我们需要采用另外一个不同的方程：

m=3xP2+a2yPm=\frac{3x^2_P+a}{2y_P}

不难发现，正如我们期望的那样，上述mm的表达式就是下式的一阶导数：

yP=±xP3+axP+by_P=\pm \sqrt{x^3_P+ax_P+b}

为了证明这一结果的有效性，只需检查RR在这条椭圆曲线上，以及经过RR和 PP的直线与椭圆曲线只有两个交点。当然，具体证明还是交给相关专业的数学教材，这里只举一个具体的例子：P=Q=(1，2)P=Q=(1，2)。

m=3xP2+a2yP=3×12−72×2=−1\begin{aligned} m &= \frac{3x^2_P+a}{2y_P} \\ &= \frac{3\times 1^2-7}{2\times 2} \\ &= -1 \end{aligned}

xR=m2−xP−xQ=(−1)2−1−1=−1\begin{aligned} x_R &= m^2-x_P-x_Q \\ &= (-1)^2-1-1 \\ &= -1 \end{aligned}

yR=yP+m(xR−xP)=2+(−1)×(−1−1)=4\begin{aligned} y_R &= y_P+m(x_R-x_P) \\ &= 2+(-1) \times(-1-1) \\ &= 4 \end{aligned}

这里我们有P+P=−R=(−1,−4)P+P=-R=(-1,-4)，结果正确。

标量乘法（Scalar multiplication）

除了加法，我们可以定义另外一个操作：标量乘法，具体如下：

nP=P+P+...+P⏟n timesnP=\underbrace{P+P+...+P}_{n\,times}

其中nn是一个自然数。这里我们依然可以借助前面提到的图形化工具对标量乘法进行演示。

从上面的形式可以看出，计算标量乘法nPnP需要进行nn次的加法。如果nn有 kk个二进制位的话，那么我们的算法复杂度将是O(2k)O(2^k)，不过，对于乘法的计算有现成的更为优化的多项式级别复杂度的算法。

其中一个比较著名的是**加倍累加（double and add ）**算法。我们用一个具体的例子来解释其原理。不妨取n=151n=151，其二进制表示形式为：100101112{10010111}_2。而将二进制转化为十进制的过程可以用2的不同次方的累加表示如下：

从这个角度，我们可以改写上述变量乘法公式：

151×P=27×P+24×P+22×P+21×P+20×P151\times P=2^7\times P+2^4\times P+2^2\times P + 2^1\times P+2^0\times P

这样，标量乘法可以表示为多项式乘法类似的算法，具体步骤如下：

  • 得到PP
  • 翻倍PP，得到2P2P
  • 将2P2P加到PP（得到21×P+20×P2^1\times P+2^0\times P的结果）
  • 翻倍2P2P，得到22×P2^2\times P
  • 将翻倍的22×P2^2\times P加到上一次的结果当中得到22×P+21×P+20×P2^2\times P+2^1\times P+2^0\times P
  • 翻倍22×P2^2\times P，得到23×P2^3\times P
  • 不对23×P2^3\times P进行任何操作
  • 翻倍23×P2^3\times P，得到24×P2^4\times P
  • 将翻倍的24×P2^4\times P加到上一次的结果当中得到24×P+22×P+21×P+20×P2^4\times P+2^2\times P+2^1\times P+2^0\times P
  • …

最后，我们仅需要7次的翻倍计算和4次的加法计算就可以得到151×P151\times P的结果。

如果这个过程不够清晰，这里有一段实现了这个算法的python脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def bits(n):
    """
    Generates the binary digits of n, starting
    from the least significant bit.

    bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
    """
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    """
    Returns the result of n * x, computed using
    the double and add algorithm.
    """
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result += addend
        addend *= 2

    return result

这里我们分析下这个算法的时间复杂度。如果翻倍和加法都是O(1)O(1)的话，那么这个算法就是O(log⁡n)O(\log n)，比起之前的O(n)O(n)，算法时间复杂度大大简化。

对数（Logarithm）

给定nn和 PP，我们有一个至少是多项式时间复杂度的算法来计算Q=nPQ=nP。但是，如果反过来呢？比如已知QQ和 PP来计算nn呢？通常将这种问题叫作对数问题（logarithm problem）。之所以用对数来代替除法是为了与其它的加密系统保持一致。

对于对数问题我们不知道是否有可以称之为“简单”的算法，但是通过一些乘法实验还是很容易看出一些规律的。比如，以椭圆曲线y2=x3−3x+1y^2=x^3-3x+1和点P=(0,1)P=(0,1)为例。我们可以立刻确认，如果nn是奇数，nPnP将会在曲线的左半部分；如果nn是偶数，nPnP将会在曲线的右半部分。如果我们做更多的实验，我们可以发现更多的规律，最终可以指引我们写出一个基于特定曲线的求解对数问题的特定算法。

当然，对数问题也有一些衍生：离散对数问题。这个将在下一篇文章当中进行讨论，如果我们减小椭圆曲线的域，变量乘法依然“简单”，但是离散对数却变成一个“难题”，这个双重特性是椭圆曲线密码学的基石。

参考资料