有限域与离散对数问题

原文： Elliptic Curve Cryptography: finite fields and discrete logarithms

“整数对 p 取模“有限域（The field of integers modulo p）

有限域是什么？首先，它是一个包含有限个元素的集合。有限域最常见的例子是当 p 为素数时，整数对 p 取模，一般使用 \(\mathbb{Z}/p\), \(GF(p)\) 或者 \(\mathbb{F}_p\) 表示，下文中我们使用最后一种表示这个有限域。

有限域上定义了加法（+）和乘法（·）两种运算，运算满足封闭性、结合性和交换性。存在唯一的单位元（identity element），域中的每个元素存在唯一的逆元（inverse element）。最后，乘法对加法满足分配律（distributive）： \(x \cdot (y + z) = x \cdot y + x \cdot z\) 。

整数对 p 取模有限域中包含了从 \(0\) 到 \(p - 1\) 的所有整数，加法和乘法同 模运算（modular arithmetic） ，下面是 \(\mathbb{F}_{23}\) 的运算示例：

  • 加： \((18 + 9) \bmod 23 = 4\)

  • 减： \((7 - 14) \bmod 23 = 16\)

  • 乘： \((4 \cdot 7) \bmod 23 = 5\)

  • 加法逆元（Additive inverse）： \(-5 \bmod 23 = 18\)

    \((5 + (-5)) \bmod 23 = (5 + 18) \bmod 23 = 0\) ，正确。

  • 乘法逆元（Multiplicative inverse）： \(9^{-1} \bmod 23 = 18\)

    \(9 \cdot 9^{-1} \bmod 23 = 9 \cdot 18 \bmod 23 = 1\) ，正确。

如果上面的公式看不太明白，可以看下可汗学院的这个教程： What is Modular Arithmetic 。

注意： \(p\) 必须是一个素数。比如整数对 4 取模构成的集合就不是一个域：因为集合里的元素 2 没有乘法逆元，也就是说 \(2 \cdot x \bmod 4 = 1\) 无解。

模除(Division modulo p)

在 \(\mathbb{F}_p\) 中 \(x/y = x \cdot y^{-1}\) ，也就是说，\(x\) 除 \(y\) 等价于 \(x\) 乘上 \(y\) 的乘法逆元。

乘法逆元可以使用 扩展欧几里得算法（extended Euclidean algorithm） 很容易的计算得出，复杂度最差为 \(O(\log p)\)，用 p 的 bit 长度表示的话为 \(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\) 上的椭圆曲线（Elliptic curves in \(\mathbb{F}_p\)）

下面我们将椭圆曲线限定在 \(\mathbb{F}_p\) 上，前文提到实数域上的椭圆曲线公式如下：

\[\begin{split}\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}\end{split}\]

限定之后，公式变为：

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

其中 \(0\) 依然是无穷远点，\(a\) 和 \(b\) 是 \(\mathbb{F}_p\) 上的整数。

../_images/elliptic-curves-mod-p.png

曲线 \(y^2 \equiv x^3 - 7x + 10 (\bmod p)\) ，\(p = 19, 97, 127, 487\) 。每一个 x 对应两个点，并相对于 \(y = p/2\) 对称。

之前连续的曲线现在变成了 \(xy\) 平面上的离散点。我们可以证明，限定之后， \(\mathbb{F}_p\) 上的椭圆曲线依然构成一个阿贝尔群。

曲线上点的加法（Point addition）

我们需要稍微修改一下加法的定义，让其在 \(\mathbb{F}_p\) 上可以正常工作。在实数域上，我们说三个在一条直线上的点的和为零（\(P + Q + R = 0\)）。在 \(\mathbb{F}_p\) 上同理，只是这里的直线和实数域上的直线不太一样。\(\mathbb{F}_p\) 上的直线指的是满足 \(ax + by + c \equiv 0 (\bmod p)\) 的所有点 \((x, y)\) 的集合。

../_images/point-addition-mod-p.png

曲线构成群，所以曲线上点的加法依然满足前面说的各种群特性。

  • \(Q + 0 = 0 + Q = 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\) （根据逆元的定义）。

代数加法（Algebraic sum）

公式和前面实数域上的代数加法一样，只是每个公式的最后需要追加一个“\(\bmod p\)”。给定 \(P = (x_P, y_P)\), \(Q = (x_Q, y_Q)\) 和 \(R = (x_R, y_R)\) ，我们如下计算 \(P + Q = -R\) ：

\[\begin{split}\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}\end{split}\]

如果 \(P \ne Q\)，斜率 \(m\) 为：

\[m = (y_P - y_Q)(x_P - x_Q)^{-1} \bmod p\]

否则：

\[m = (3 x_P^2 + a)(2 y_P)^{-1} \bmod{p}\]

离散点加法可视化工具

椭圆曲线群的序（The order of an elliptic curve group）

有限域上的椭圆曲线群的集合中包含有限个数的点，这些点的个数称为该群的序（order）。

我们可以从 \(0\) 到 \(p - 1\) 遍历 \(x\) 的所有可能值来计算得到点的个数，计算复杂度为 \(O(p)\) ，如果 \(p\) 非常大的话，性能会很低下。

还好，存在高效算法 Schoof’s algorithm 可以快速计算一个群的序。具体细节我们可以不用关注，只需要知道其可以多项式时间内计算完成就行。

乘法和循环子群（Scalar multiplication and cyclic subgroups）

有限域上的乘法和实数域上一样，还是：

\[nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}\]

我们依然可以使用 double and add 算法来高效完成乘法运算。

乘法可视化演示工具

\(\mathbb{F}_p\) 上的椭圆曲线上的点的乘法有一个非常有意思的特性。以曲线 \(y^2 \equiv x^3 + 2x + 3 (\bmod 97)\) 和点 \(P = (3, 6)\) 为例：

../_images/cyclic-subgroup.png

  • \(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)\)

  • ……

首先，\(nP\) 所有可能的值只有 5 个。第二，这些值循环出现。所以，对于所有的整数 \(k\) ：

  • \(5kP = 0\)

  • \((5k + 1)P = P\)

  • \((5k + 2)P = 2P\)

  • \((5k + 3)P = 3P\)

  • \((5k + 4)P = 4P\)

使用取模运算我们可以将上面 5 个公式进一步简化为： \(kP = (k \bmod 5)P\) 。

不仅如此，我们还可以证明这 5 个点的加法是封闭的。也就是说 \(0\) 、\(P\)、\(2P\)、\(3P\)、\(4P\) 任意相加，最终的结果还是这 5 个点之一。

以上规律并不限于 \(P = (3, 6)\) 这个点，而是对曲线上所有的点都成立。假设 \(P\) 是曲线上任意一点：

\[nP + mP = \underbrace{P + \cdots + P}_{n\ \text{times}} + \underbrace{P + \cdots + P}_{m\ \text{times}} = (n + m)P\]

也就是说：两个 \(P\) 的倍乘数相加，它们的和还是 \(P\) 的倍乘数。也就证明了 \(nP\) 的可能值构成的集合是一个椭圆曲线的循环子群。

通过点 \(P\) 我们可以获得这个循环子群里的所有元素，所以 \(P\) 又被称为这个循环子群的 生成元（generator） 或者 基点（base point） 。

循环子群是椭圆曲线加密以及其它一些加密系统的基石。

子群的序（Subgroup order）

Schoof’s algorithm 只能计算椭圆曲线群的序，不能用于计算点 \(P\) 生成的子群的序，那么这个子群的序怎么来计算呢？

在解决这个问题之前，我们先做一点铺垫：

  • 前面，我们定义一个群的序为这个群里元素的个数。不过对于循环子群，我们可以给出另外一个等价的定义：\(P\) 的序为满足 \(nP = 0\) 的最小正整数 \(n\) 。例如前面包含 5 个点的子群，我们可以看到 \(5P = 0\) 。

  • 根据 拉格朗日定理（Lagrange’s theorem） ，子群的序是其父群的一个约数（divisor）。也就是说，如果椭圆曲线群的序为 \(N\)，子群的序为 \(n\)，那么 \(n\) 是 \(N\) 的一个约数。

综上，我们可以得到如下计算子群的序的算法：

  1. 使用 Schoof’s algorithm 计算得到椭圆曲线群的序 \(N\)。

  2. 找出 \(N\) 的所有约数。

  3. 对于 \(N\) 的每一个约数 \(n\)，计算 \(nP\) 。

  4. 满足 \(nP = 0\) 的最小 \(n\) ，就是基点为 \(P\) 的子群的序。

例如，\(\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\) 。

另外一个例子：\(\mathbb{F}_{29}\) 上的椭圆曲线群 \(y^2 = x^3 - x + 3\) 的序为 \(N = 37\)，是一个素数，所以它的子群的序 \(n\) 只能为 1 或者 37。当 \(n = 1\) 时，子群里只有无穷远点，当 \(n = N\) 时，子群包含了椭圆曲线群里的所有点。

寻找基点（Finding a base point）

对于椭圆曲线加密算法，我们需要一个序比较高的子群。具体来说，我们需要选择一个椭圆曲线，计算它的序 \(N\)，选择 \(N\) 的一个比较大的约数作为子群的序 \(n\)，最后找到这个序对应的基点。这里我们不是先选基点再计算它的序，而是反过来：先选定序再寻找其对应的基点。那么在知道序的情况下如何找到其对应的基点呢？

我们需要再引入一个概念。根据拉格朗日定理可知 \(h = N/n\) 必然是一个整数 （\(n\) 是 \(N\) 的约数）。这个 \(h\) 叫做 子群的 cofactor 。

对于椭圆曲线上的任意点，都有 \(NP = 0\)，因为 \(N\) 是所以 \(n\) 的公倍数，根据 cofactor 的定义，我们可以得到：

\[n(hP) = 0\]

假设 \(n\) 是一个素数（具体理由后面会解释）。从上面的公式我们可以知道：点 \(G = hP\) 生成一个序为 \(n\) 的子群（除非 \(G = hP = 0\)，它生成的群的序为 1）。

据此，我们得到以下算法：

  1. 计算椭圆曲线的序 \(N\) 。

  2. 选择子群的序 \(n\)， \(n\) 是素数并且是 \(N\) 的约数。

  3. 计算 cofactor \(h = N/n\)。

  4. 取曲线上随机一点 \(P\) 。

  5. 计算 \(G = hP\) 。

  6. 如果 \(G\) 是 \(0\)，回第 4 步，否则 \(G\) 就是我们要找的基点（序为 \(n\)，cofactor 为 \(h\) ）。

注意，算法可以工作的前提是 \(n\) 是一个素数，如果不是，\(G\) 的序可能是 \(n\) 的一个约数。

离散对数（Discrete logarithm）

如果知道 \(P\) 和 \(Q\)，如何找到 \(k\) 使得 \(Q = kP\) 呢？

这个问题前面已经说了，叫做 离散对数问题 。到目前为止，还没有一个算法可以在多项式时间内解决。

这个问题同 DSA 算法、 Diffie-Hellman (D-H) 密钥交换以及 ElGamal 算法中使用的离散对数问题类似，区别只在于这些算法使用的是幂次而不是乘法运算，这些算法中的离散对数问题是这样的：如果知道 \(a\) 和 \(b\)，如何找到 \(k\) 使得 \(b = a^k \bmod p\) 。

因为这些问题都是限定在有限域上的，所以它们是“离散”的，因为它们和普通的对数运算类似，所以叫做对数问题。

椭圆曲线有意思的地方在于：比起其它的加密算法，它的离散对数问题似乎更难解决。这意味着我们可以使用较少 bit 的 \(k\) 就获得和其它加密系统同样的安全等级。