椭圆曲线密码学（2）：有限域和离散对数（译）

英文原文地址

作者：Andrea Corbellini

翻译：Hantao Sun

这是椭圆曲线密码学系列的第二篇文章

椭圆曲线密码学系列文章链接：

上一篇：实数域上的椭圆曲线和群法则

在上一篇文章中，我们知道椭圆曲线如何在实数域上定义群。尤其是定义了点的加法法则：给定三个共线的点，它们的和等于0( $P + Q + R = 0$ )。并且推导出计算点加法的几何方法和代数方法。

下面我们介绍一下数乘( $nP = P + P + \cdots + P$ ) ，并且给出了一个“简单”算法：倍数相加

现在，我们要将实数域上的椭圆曲线限制在有限域上，看看有什么变化。

模 $p$ 的有限域

有限域首先是有限数字的集合。例如：模 $p$ 的有限域， $p$ 必须是素数（以下“素数域”等同于”有限域”），它通常表示为 $\mathbb{Z}/p$ ， $GF(p)$ 或者 $\mathbb{F}_p$ ，我们使用后者来标记。

在 $\mathbb{F}_p$ 中有两个二元操作符加法（+）和乘法（ $\cdot$ ），他们是封闭的、满足交换律和结合律。对于这两个操作符，都存在一个唯一的元素和逆元素。最后，乘法对加法满足分配律： $x \cdot (y + z) = x \cdot y + x \cdot z$ 。

模 $P$ 的整数集合由 $0$ 到 $p - 1$ 的所有整数组成。加法和乘法都需要进行模运算（也称作“时钟算术”）。下面是关于 $\mathbb{F}_{23}$ 的例子：

加法： $(18 + 9) \bmod{23} = 4$
减法： $(7 - 14) \bmod{23} = 16$
乘法： $4 \cdot 7 \bmod{23} = 5$
加法逆元： $-5 \bmod{23} = 18$
算法： $(5 + (-5)) \bmod{23} = (5 + 18) \bmod{23} = 0$
乘法逆元： $9^{-1} \bmod{23} = 18$
算法： $9 \cdot 9^{-1} \bmod{23} = 9 \cdot 18 \bmod{23} = 1$

如果您不熟悉这些公式，可以通过可汗学院来获取模运算的相关知识。

我们之前说过，模 $p$ 的整数是个域，可以满足上面的所有公式。请注意， $p$ 必须是一个素数。模4的整数集合不是一个域：2没有乘法逆元。（ $2 \cdot x \bmod{4} = 1$ 无解）

模 $p$ 的除法

我们稍后会定义在 $\mathbb{F}_p$ 上的椭圆曲线，但在这之前我们要搞清楚 $x / y$ 在 $\mathbb{F}_p$ 上表示什么含义。公式： $x / y = x \cdot y^{-1}$ ，即 $x$ 除以 $y$ 表示 $x$ 乘以 $y$ 的乘法逆元。 $x / y$ 的解法是：找到 $y$ 的逆元，再做一次乘法。

计算乘法逆元可以用扩展欧几里得算法来计算，最坏的情况时间复杂度是 $O(\log p)$ （或者 $O(k)$ ，如果考虑位长）。

在这里不讨论扩展欧几里得算法的细节，下面是Python的实现：

def extended_euclidean_algorithm(a, b):
    """
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t


def inverse_of(n, p):
    """
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p

在 $\mathbb{F}_p$ 上的椭圆曲线

我们已经具备了 $\mathbb{F}_p$ 上定义椭圆曲线的条件. 在上一篇椭圆曲线的点集：

$\begin{array}{rcl} \left\{(x, y) \in \mathbb{R}^2 \right. & \left. | \right. & \left. y^2 = x^3 + ax + b, \right. \\ & & \left. 4a^3 + 27b^2 \ne 0\right\}\ \cup\ \left\{0\right\} \end{array}$

改为:

$\begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. & \left. | \right. & \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ & & \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\}\ \cup\ \left\{0\right\} \end{array}$

$0$ 仍然是无限远点， $a$ 和 $b$ 是 $\mathbb{F}_p$ 上任意整数。

Fp上的奇异曲线 — 曲线 $y^2 \equiv x^3 \pmod{29}$ 是奇异的，在 $(0, 0)$ 上有三个解，它不是一个有效的曲线

之前的图像是一个连续的曲线，而现在是不连贯的点。但我们仍然可以证明 $\mathbb{F}_p$ 上的椭圆曲线满足阿贝尔群。

点相加

很显然，我们要稍微修改一下加法的定义，使它可以在 $\mathbb{F}_p$ 上工作。在实数域上，我们定义三个共线的点之和等于0（ $P + Q + R = 0$ ）。我们保留这个定义，那么在 $\mathbb{F}_p$ 上三点共线意味者什么？

我们可以说三点共线表示三个点在一条直线上，但是在 $\mathbb{F}_p$ 上的直线和 $\mathbb{R}$ 上的直线不一样。简单的说， $\mathbb{F}_p$ 上的直线上的点集 $(x, y)$ 满足 $ax + by + c \equiv 0 \pmod{p}$ （这是标准直线公式，再加上” $(\text{mod}\ p)$ ”）

Fp上点的加法 — 曲线 $y^2 \equiv x^3 - x + 3 \pmod{127}$ ，其中点 $P = (16, 20)$ ，点 $Q = (41, 120)$ 。注意连接 $P$ 和 $Q$ 的直线 $y \equiv 4x + 83 \pmod{127}$ 在平面中重复。

在群中，我们保留了加法的属性：

$Q + 0 = 0 + Q = Q$ （集合元素的定义）
给定非0点 $Q$ ，它的逆元 $-Q$ 是横坐标相同而纵坐标相反的点，也可以表示为 $-Q = (x_Q, -y_Q \bmod{p})$ 。例如，如果曲线在 $\mathbb{F}_{29}$ 上有点 $Q = (2, 5)$ ，它的逆元是 $-Q = (2, -5 \bmod{29}) = (2, 24)$ 。
当然， $P + (-P) = 0$ （逆元定义）

代数和

计算点之和与上一篇一样，只是要注意在每一个算式后面添加“ $\text{mod}\ p$ ”。因此，假设 $P = (x_P, y_P)$ ， $Q = (x_Q, y_Q)$ ， $R = (x_R, y_R)$ ，我们可以计算 $P + Q = -R$ ：

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

如果 $P \ne Q$ ，斜率 $m$ ： $m = (y_P - y_Q)(x_P - x_Q)^{-1} \bmod{p}$ 如果 $P = Q$ ： $m = (3 x_P^2 + a)(2 y_P)^{-1} \bmod{p}$

等式没有发生改变。实际上，这些等式在任何域中都成立，有限域或无限域（ $\mathbb{F}_2$ 和 $\mathbb{F}_3$ 除外）。困难是这个证明需要很复杂的数学概念，幸好我找到了只使用基本概念的证明方法Stefan Friedl证明。如果您对“为什么这个公式在每个域都成立”感兴趣，可以读一读。

我们没有定义它的几何方法，因为这存在一些困难。比如在上一篇我们计算 $P + P$ 时需要画 $P$ 点的切线。但是对于非连续的点，“切线”是没有意义的。我们可以解决这个问题，但是纯粹的几何方法在这里是非常复杂、没有意义的。

您可以使用可视化工具来直观感受点的加法。

椭圆曲线群的阶

我们说在有限域上椭圆曲线包含有限个点。那么有一个重要的问题：到底有多少个点？

首先，让我们称群上点的数量为群的阶

尝试从 $0$ 到 $p - 1$ 所有的 $x$ 对应的点是不可行的，当 $p$ 很大时，需要 $O(p)$ 次计算是很“困难”的。

幸好，Schoof算法可以很快算出来，这里就不延伸到算法的细节了。

数乘和循环子群

在实数域上，数乘定义为： $n P = \underbrace{P + P + \cdots + P}_{n\ \text{times}}$ 同样的，我们可以用倍数相加算法去计算（时间复杂度为 $O(\log n)$ 或者 $O(k)$ ， $k$ 表示 $n$ 的位数)）。这是数乘的可视化工具。

在 $\mathbb{F}_p$ 上的椭圆曲线点的数乘有一个有趣的特性。假设有曲线 $y^2 \equiv x^3 + 2x + 3 \pmod{97}$ 和其上的点 $P = (3, 6)$ ，计算 $P$ 的数乘：

循环子群 — $P = (3, 6)$ 的数乘只有五个点（ $0$ ， $P$ ， $2P$ ， $3P$ ， $4P$ ），并在其上重复。很容易发现数乘和带模运算的加法有相似性。

$0P = 0$
$1P = (3, 6)$
$2P = (80, 10)$
$3P = (80, 87)$
$4P = (3, 91)$
$5P = 0$
$6P = (3, 6)$
$7P = (80, 10)$
$8P = (80, 87)$
$9P = (3, 91)$
…

可以发现两个结论： $P$ 的数乘只有五个结果，其他的点都没有出现；结果是循环重复的。我们可以写成：

$5kP = 0$
$(5k + 1)P = P$
$(5k + 2)P = 2P$
$(5k + 3)P = 3P$
$(5k + 4)P = 4P$

五个等式可以合成为一个 $kP = (k \bmod{5})P$ 。

同时，我们可以证明这五个点在加法下是封闭的。也就是说，当这五个点中的任意数量点相加，结果还是在五个点上。曲线上的其他点不会出现在结果中。

这个结论对任意的点都成立，假设有点 $P$ ： $nP + mP = \underbrace{P + \cdots + P}_{n\ \text{times}} + \underbrace{P + \cdots + P}_{m\ \text{times}} = (n + m)P$

这意味着：如果两个 $P$ 的数乘相加，可以得到一个 $P$ 的数乘（ $P$ 的数乘在加法下是封闭的）。这就可以证明 $P$ 的数乘结果是椭圆群的一个子群。

“子群”是另一个群的子集。“循环子群”表示元素是循环的，就像上面的例子。点 $P$ 被称作循环子群的基点。

循环子群是ECC和其他加密系统的基础。在下一篇文章中我们会解释其原因。

子群的阶

我们提出一个问题：由基点 $P$ 生成的子群的阶是多少（或者说基点 $P$ 的阶是多少）？这个问题不能通过Schoof算法来计算，因为Schoof算法只能作用于整个曲线。我们需要一些准备工作：

到现在为止，我们定义阶为群中点的个数。这个定义依旧有效，但是在循环子群中，我们给出一个等价定义： $P$ 的阶表示为一个最小的正整数 $n$ ，使得 $nP = 0$ 。在上面的例子中，子群包含5个点，得出 $5P = 0$ 。
$P$ 的阶和曲线的阶可以通过拉格朗日定理联系起来：子群的阶能被其父群的阶整除，换句话说，如果椭圆曲线包含 $N$ 个点，它的一个子群包含 $n$ 个点，那么 $n$ 能被 $N$ 整除。

结合上面的两点，我们可以得出以 $P$ 为基点的子群的阶的计算方法：

用Schoof算法计算椭圆曲线的阶 $N$ 。
找到 $N$ 所有的约数。
对于约数集合中任意的 $n$ ，计算 $nP$ 。
找到最小的 $n$ ，使得 $nP = 0$ ，则 $n$ 就是子群的阶。

举例：在有限域 $\mathbb{F}_{37}$ 上的曲线 $y^2 = x^3 - x + 3$ 的阶 $N = 42$ 。它的子群可能的阶为 $n = 1$ ， $2$ ， $3$ ， $6$ ， $7$ ， $14$ ， $21$ 或 $42$ 。如果尝试 $P = (2, 3)$ ，我们可以发现 $P \ne 0$ ， $2P \ne 0$ ，…， $7P = 0$ ，因此 $P$ 的阶是 $n = 7$ 。

值得注意的是，阶一定选取最小的满足条件的值，而不是随机的。如果我们随机取值，上面的例子可能取 $n = 14$ ，这不是 $P$ 的阶。

再举例：在有限域 $\mathbb{F}_{29}$ 上的曲线 $y^2 = x^3 - x + 1$ 的阶 $N = 37$ ，是一个素数。它的子群的阶只能是 $n = 1$ 或 $37$ 。当 $n = 1$ 时，子群只包含一个无限远点；当 $n = N$ 时，子群包含曲线的所有点。

计算基点

在实际的ECC算法中，我们需要子群拥有很高的阶。通常我们先选择一个椭圆曲线，计算它的阶。然后选择一个比较大的约数作为子群的阶。最后找到对应的基点。这就意味着，并不是先拥有了基点再计算子群的阶，而是反过来：我们先确定一个阶，再计算对应的基点。那么怎么做呢？

首先，介绍一下更多的属于。根据拉格朗日定理 $h = N / n$ 总是一个整数。称 $h$ 为子群的辅因子。

对于曲线上的任意一点 $P$ 都有 $NP = 0$ ，因为 $N$ 是任意 $n$ 的倍数。使用辅因子： $n(hP) = 0$

假设 $n$ 是一个素数（在下一篇解释原因），这个等式表示点 $G = hP$ 生成了阶 $n$ 的子群（除非 $G = hP = 0$ ，那么子群的阶为1）

由此，算法概述如下；

计算椭圆曲线的阶 $N$ 。
选择子群的阶 $n$ ，这个值必须是素数而且能被 $N$ 整除。
计算辅因子 $h = N / n$ 。
随机选择曲线上的任意一点 $P$ 。
计算 $G = hP$ 。
如果 $G$ 等于0，从第4步开始重复。否则，就找到了一个阶为 $n$ 且辅因子为 $h$ 的子群。

注意： $n$ 必须是素数，否则G的阶有可能是 $n$ 的一个约数。

离散对数

和我实数域上连续的椭圆曲线一样，我们也需要讨论一个问题：如果我们知道了点 $P$ 和点 $Q$ ，能否找到值 $k$ ，使得 $Q = kP$ ？

这个问题成为椭圆曲线上的离散对数问题，是公认的“困难”问题。虽然不能从数学上证明，但至今没有一种在经典计算机上的多项式时间解决办法。（译者注：这个问题不抗量子计算）

这个问题和其他密码学的离散对数问题一样，比如数字签名算法（DSA）、Diffie-Hellman交换key算法（DH）以及ElGamal加密算法。区别是，其他算法使用模幂来代替数乘，也就是说：如果我们知道了 $a$ 和 $b$ ，如何找到 $k$ 使得 $b = a ^ k \bmod{P}$ ？

这些算法被称为“离散”的，是因为它们涉及有限集合（更准确的说，是循环子群）。而“对数”是因为它们类似普通的对数形式。

对于ECC而言，它的离散对数问题比其他加密算法更“难”。这意味着可以使用更少的比特来达到与其他加密算法相同的安全级别，关于这部分将在最后一篇详解。

下周内容

希望大家喜欢这篇文章。

下周将涉及ECC的算法：密钥对的生成，ECDH和ECDSA。这是本系列中最有趣的部分，不要错过！

模pp的有限域

模pp的除法

在Fp\mathbb{F}_p上的椭圆曲线

点相加

代数和