椭圆曲线密码学（1）：介绍（译）

作者：Andrea Corbellini

翻译：Hantao Sun

知道公钥加密的人或许听说过ECC，ECDH，ECDSA。ECC是椭圆曲线密码学的缩写，而另外的两个是基于它的算法。

如今，ECC应用于TLS，PGP，SSH。这些都是当前web和IT世界的基础技术，更不要说Bitcoin和其他数字加密货币。

在ECC流行之前，几乎所有的公钥加密算法都是基于RSA，DSA和DH，这类基于模运算的替换式密码系统。RSA系列在现今仍然非常重要，经常和ECC一起使用。RSA的原理和实现都比较容易理解，粗略的实现也比较容易，但是ECC的基础对于大多数人来说仍然很神秘。

我将用一系列的博文向大家介绍椭圆曲线加密。我的目标不是提供一份ECC的详尽指南（网络上已经有很多关于这个主题的信息），而是一份关于“ECC是什么”，“为什么它是安全的“等问题的概述，这样不会浪费时间在大量的数学证明和无聊的实现细节。同时我将给出有帮助的图例和脚本。

具体来说，我会涉及这几个主题：

为了理解这些，你需要了解一些集合论的基础知识、几何和模运算，以及对称和非对称加密。最后，你需要明确什么是“简单”的问题，什么是“困难”的问题，以及它们在密码学中的角色。

准备好了吗？我们开始吧！

椭圆曲线

首先：什么是椭圆曲线？Wolfram MathWorld给出了优秀、精确的定义。简单来说，一个椭圆曲线可以描述成为下列等式中点的集合：

$y^2 = x^3 + ax + b$

其中$4a^3 + 27b^2 \ne 0$（这个保证了曲线是非奇异的）。上面的等式被称作椭圆曲线的Weierstrass标准形式。

奇点类型：左边是曲线$(y^2 = x^3)$，右边是自相交曲线$(y^2 = x^3 - 3x + 2)$。它们都不是有效的椭圆曲线

对于不同的 $a$ 和 $b$，椭圆曲线呈现不同的形状。可以很轻易的证明：椭圆曲线是 $x$ 轴对称的。

我们还需要在曲线中加入一个无限远点（也被称为理想点）。从现在开始，我们用符号0来表示这个无限远点。

如果我们精确考虑无限远点，需要改进椭圆曲线的定义：

$\{(x,y)\in\Re |y^2 = x^3 + ax + b,4a^3 + 27b^2 \ne 0\} \cup \{0\}$

群

一个群是一个集合，并在其上定义一个二元运算符（我们称之为“加法”，用符号 $+$ 表示）。如果称一个集合 $\mathbb{G}$ 是群，“加法”需要有如下性质：

封闭性：如果 $a$ 和 $b$ 属于 $\mathbb{G}$，那么 $a+b$ 也属于 $\mathbb{G}$
结合律：$(a+b)+c=a+(b+c)$
零元：存在一个元素 $0$，使得任意的 $a\in\mathbb{G}$ ，有 $a + 0 = 0 + a = a$
逆元：对于任意的 $a\in\mathbb{G}$，都存在 $b\in\mathbb{G}$，使得 $a + b = 0$

如果 $\mathbb{G}$ 满足：

交换律：$a + b = b + a$

那么就称之为阿贝尔群。

对于通常意义的加法，整数集合 $\mathbb{Z}$ 是一个群（也是阿贝尔群）。自然数集合 $\mathbb{N}$ 不是一个群，因为它不满足第四条性质。

如果我们通过这四条性质证明一个集合是群的话，还可以推出其他的性质。比如：零元是唯一的；逆元也是唯一的（对于任意的 $a\in\mathbb{G}$ ，有且仅有一个 $b\in\mathbb{G}$，满足 $a + b = 0$）。这些性质在将来都非常重要。

椭圆曲线的群法则

我们可以在椭圆曲线上定义一个群，满足：

群的元素就是椭圆曲线上的点
零元是无穷远点
$P$ 的逆元是关于x轴的对称点
加法规则：给定三个共线的非 $0$ 点 $P$、$Q$、$R$，他们的和 $P + Q + R = 0$

对于加法规则，只需要三个共线的非 $0$ 点，它们可以以任意的顺序相加。也就是说，如果 $P$、$Q$、$R$ 共线，那么 $P + (Q + R) = Q + (P + R) = R + (P + Q) = … = 0$。这样，我们可以直观的看到，加法规则满足交换律和结合律：我们构造了一个阿贝尔群。

太棒了！但是我们该如何计算两点之和呢？

几何加法

由于我们拥有了阿贝尔群，所以我们可以用 $P + Q = -R$ 来表示 $P + Q + R = 0$。这样我们可以用几何方法来计算出 $P$ 和 $Q$ 两点之和：如果我们画一条经过 $P$ 和 $Q$ 的直线，相交于曲线上第三个点 $R$ （这和 $P$、$Q$、$R$ 共线是一致的）。然后再找到 $R$ 的逆元 $-R$，这就是 $P + Q$ 的结果。

画直线穿过P和Q，交曲线于R — 画直线穿过 $P$ 和 $Q$，交曲线于 $R$。该点关于 $x$ 轴的对称点 $-R$ 就是 $P + Q$ 的结果

几何的方法虽然有效，但我们要更精确一些。需要回答以下问题：

如果 $P = 0$ 或 $Q = 0$ 会发生什么？当然，我们无法画出线（$0$ 不在 $xy$ 平面上）。但由于我们已经定义了零元，那么对于任意的 $P$ 或 $Q$，有 $P + 0 = P$，$0 + Q = Q$
如果 $P = -Q$ 呢？在这种情况下，这条线和 $y$ 轴垂直，不经过其他的点。但如果 $P$ 是 $Q$ 的逆元，根据逆元的定义有 $P + Q = P + (-P) = 0$
如果 $P = Q$ 呢？那会有无限多的线通过这个点，这样事情就变得复杂了。考虑点 $Q’ \ne P$，当 $Q’$ 趋近于 $P$ 的时候发生了什么？

当 $Q’$ 趋近于 $P$ ，经过 $P$ 和 $Q$ 的线趋近于曲线的切线。正因如此，我们说 $P + P = -R$，$R$ 是经过 $P$ 点的切线与曲线的交点。

当 $P \ne Q$ 时，什么情况 $R$ 不存在？这个问题和上一条很类似。实际上，当穿过 $P$ 和 $Q$ 的线正好是曲线切线时，不存在 $R$

假设 $P$ 是切点，在上一条中，我们写出 $P + P = -Q$，现在等式变成了 $-P$。另一方面，如果 $Q$ 是切点，那么等式就是 $P + Q = -Q$

通过几何方法可以对椭圆曲线上任意一点做加法。如果你想尝试，我已经做了一个椭圆曲线的加法可视化工具

代数加法

如果想应用于计算机，我们需要将几何方法转变成代数方法。转变上述规则为一系列的方程式看起来很直接，但要解三次方程，这真的很乏味。因此我只给出结论。

首先，我们抛弃一些烦人的细枝末节。由于已知 $P + (-P) = 0$ 和 $P + 0 = 0 + P = P$，所以我们只考虑两个不为 $0$，不对称的点 $P = (x_P, y_P)$ 和 $Q = (x_Q, y_Q)$

如果 $x_P \ne x_Q$，通过 $PQ$ 直线的斜率是：

$m = \frac{y_P - y_Q}{x_P - x_Q}$

这条线和椭圆曲线的第三个交点 $R=(x_R, y_R)$ ：

$\begin{array}{rcl} x_R & = & m^2 - x_P - x_Q \\ y_R & = & y_P + m(x_R - x_P) \end{array}$

或者等价于：

$y_R = y_Q + m(x_R - x_Q)$

于是 $(x_P, y_P) + (x_Q, y_Q) = (x_R, -y_R)$（谨记 $P + Q = -R$）。

如果需要检验结果的正确性，需要检验 $R$ 是否在曲线上，而且 $P$，$Q$，$R$ 共线。检验三点共线很容易，而检验R是否属于曲线需要解三次方程，很繁琐。

让我们使用可视化工具举个例子：设置 $P = (1, 2)$，$Q = (3, 4)$，在曲线 $y^2 = x^3 - 7x + 10$ 上，他们的和是 $P + Q = -R = (-3, 2)$。让我们检验下上面的等式是否正确：

$\begin{array}{rcccccr} m & = & \frac{y_P - y_Q}{x_P - x{Q}} & = & \frac{2 - 4}{1 - 3} & = & 1 \\ x_R & = & m^2 - x_P - x_Q & = & 1^2 - 1 - 3 & = & -3 \\ y_R & = & y_P + m(x_R - x{P}) & = & 2 + 1*(-3 - 1) & = & -2 \\ y_R & = & y_Q + m(x_R - x{Q}) & = & 4 + 1*(-3 - 3) & = & -2 \end{array}$

正确！

注意到当** $P$ 或 $Q$ 任意一个是切点**，等式依然成立。设置 $P = (-1, 4)$，$Q = (1, 2)$

$\begin{array}{rcccccr} m & = & \frac{y_P - y_Q}{x_P - x{Q}} & = & \frac{4 - 4}{-1 - 1} & = & -1 \\ x_R & = & m^2 - x_P - x_Q & = & (-1)^2 - (-1) - 1 & = & 1 \\ y_R & = & y_P + m(x_R - x{P}) & = & 4 + (-1)*(1 - (-1)) & = & 2 \end{array}$

我们得到结果 $P + Q = (1, -2)$，这和可视化工具显示的结果一致。

当 $P = Q$ 时，情况稍微不一样： $x_R$ 和 $y_R$ 的等式不变。如果 $x_P = x_Q$，需要一个不同的斜率方程：

$m = \frac{3x_p^2 + a}{2y_p}$

正如我们预期的那样，m的表达式是曲线方程的一阶导数：

$y_P = \pm \sqrt{x_P^3 + ax_p + b}$

为了证明这个结果，需要检查R在曲线上，并且经过 $P$ 和 $R$ 的直线和曲线只有两个交点。当然，我们依然不去证明，试试一个例子：$P = Q = (1, 2)$

$\begin{array}{rcl} m & = & \frac{3x_P^2 + a}{2y_P} = \frac{3 \cdot 1^2 - 7}{2 \cdot 2} = -1 \\ x_R & = & m^2 - x_P - x_Q = (-1)^2 - 1 - 1 = -1 \\ y_R & = & y_P + m(x_R - x_P) = 2 + (-1) \cdot (-1 - 1) = 4 \end{array}$

这和工具算出来的结论一致！

虽然推到的过程比较繁琐，但我们的方程非常紧凑。这要归功于Weierstrass标准形式，如果没有它方程将非常复杂。

数乘

除了加法，我们还可以定义另一个运算符号：数乘：

$nP = \underbrace{P + P + ... + P}_{n\ times}$

其中，$n$ 是一个自然数。我也写了一个数乘的可视化工具

写成这种形式，看起来 $nP$ 需要 $n$ 个 $P$ 相加。如果 $n$ 表示成 $k$ 位二进制数字，那么算法时间复杂度是 $O(2_k)$，这是非常耗时的。我们有更快的算法。

一种方法是倍数相加算法，通过一个例子可以更好的解释它。设 $n = 151$，它的二进制表示是 $10010111_2$，这个二进制表示可以转化为 $2$ 的幂之和：

$\begin{array}{rcl} 151 & = & 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \\ & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0 \end{array}$

（我们取 $n$ 的每个二进制位和2的幂相乘）

因此，可写出方程：

$151 \cdot P = 2^7P + 2^4P + 2^2P + 2^1P + 2^0P$

算法流程：

获取 $P$
计算 $P + P$ 得到 $2P$
计算 $2P + P$（这样我们就得到了 $2^1P + 2^0P$）
计算 $2P + 2P$ 得到 $2^2P$
再将 $2^2P$ 加到结果中（得到 $2^2P + 2^1P + 2^0P$）
计算 $2^2P + 2^2P$ 得到 $2^3P$
对于 $2^3P$ 不做任何处理
计算 $2^3P + 2^3P$ 得到 $2^4P$
再将 $2^4P$ 加到结果中（得到 $2^4P + 2^2P + 2^1P + 2^0P$）
…

最终，我们通过 $7$ 次倍数相加得到了 $151 \cdot P$

如果这样描述不清楚，这里有一份Python脚本实现了这个算法：

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(logn)$（如果按二进制长度的话就是 $O(k)$）。真是个好算法，比最初的 $O(n)$ 算法要强多了。

对数

已知 $n$ 和 $P$，我们现在至少有一个多项式时间算法来计算 $Q = nP$。但是另一方面呢，如果已知 $P$ 和 $Q$，该如何计算 $n$？这个问题属于对数问题（指数时间问题）。使用“对数”而不是“除法”是为了符合其他的密码系统（用指数代替乘法）。

在对数问题上，我不清楚有什么“简单”的算法。然而对于数乘是比较容易获取一些模式的。比如，在曲线 $y^2 = x^3 - 3x + 1$ 上，取点 $P = (0, 1)$。可以立即验证出：如果 $n$ 是奇数，$nP$ 在曲线的左部分；如果 $n$ 是偶数，$nP$ 在曲线的右部。当试验的更多，我们或许能找到更多的模式，最终引导我们编写出一种算法，可以有效的计算该曲线上的对数。

但是存在一个对数问题的变种：离散对数问题。我们将在下一章看到，如果减少椭圆曲线的域，数乘仍然是“容易”的，可是离散对数问题却是一个“困难”的问题。这种二元性就是椭圆曲线密码学的关键。

下周见

今天非常感谢大家，希望大家喜欢这篇文章！下周我们将探索有限域和离散对数问题，以及例子和工具。如果这些知识您很感兴趣，请继续关注！

下一篇：有限域上的椭圆曲线和离散对数问题

椭圆曲线

群

椭圆曲线的群法则

几何加法

代数加法

数乘

对数

下周见

下周见