[译] 椭圆曲线密码学: 有限域和离散对数

本文翻译自爱尔兰AWS工程师 ANDREA CORBELLINI 关于椭圆曲线密码学四篇博客中的第二篇, 原文采用 CC-BY 4.0 协议 进行授权
原文链接 : https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/
原作者: ANDREA CORBELLINI
译者: chxj1992

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

前一篇文章中, 我们知道了如何在实数域上的椭圆曲线上定义一个群. 具体来说, 我们定义了点加的规则: 找到位于一条直线上的三个点, 三点之和为零($P + Q + R = 0$). 我们推导了求解点加的几何方法代数方法.

我们还介绍了标量乘法($nP = P + P + \cdots + P$) 并且我们找到了一种用于计算标量乘法的"简单"算法: 倍加法.

现在我们将要把椭圆曲线限制在有限域而非所有实数的集合上, 让我们来看看这会产生怎样的变化.

以p为模的整数域

有限域, 简单来说是指一个包含有限个元素的集合. 整数对质数 p 取模的集合就是有限域的一个例子, 一般用 $\mathbb{Z}/p$, $GF(p)$ 或者 $\mathbb{F}_p$ 表示. 这里我们采用最后一种表示方法.

在域上存在二元运算: 加法(+)和乘法(·), 他们都满足封闭性, 结合律和交换律. 对这两种操作都存在一个唯一的单位元, 并且对每个元素都有且仅有一个逆元. 最后, 乘法还满足分配率: $x \cdot (y + z) = x \cdot y + x \cdot z$

这个集合由从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$

    译者注: 利用扩展的欧几里得算法(也叫扩展的辗转相除法)可以快速地求出某个数的逆元. 除此之外, 根据费马小定理也可知 $9^{22} \bmod{23} = 1$, 所以 $9^{-1} \bmod{23} = 9^{-1+22} \bmod{23} = 18$

如果这些等式看起来很陌生那么你需要先了解一点关于模运算的基本知识, 可以看看 Khan Academy的这篇教程

正如我们所言, 以p为模的整数是一个域, 它具备上述所有的特征. 需要注意的是p必须是一个质数! 以4为模的整数不是一个域: 2没有乘法逆元(等式 $2 \cdot x \bmod{4} = 1$ 没有解)

以p为模的除法运算

我们将会定义 $\mathbb{F}_p$ 上的椭圆曲线, 但在那之前我们需要对 $\mathbb{F}_p$ 上的 $x / y$ 是什么意思有一个清晰的认识. 根据 $x / y = x \cdot y^{-1}$, 或者简单地说, x 除以 y 等于 x 乘以 y 的乘法逆元. 这很容易理解, 并且它为我们提供了一种计算除法的基本方法: 找到这个数的乘法逆元再用计算乘法的方法来计算它

借助扩展欧几里得算法计算乘法逆元是比较"容易"完成, 在最坏的情况下, 算法的复杂度为 $O(\log p)$ (或者按位长来算, $O(k)$). 我们不会详细讲解扩展的欧几里得算法, 因为这不是本文要讨论的, 不过这里有一份Python版的实现代码:

译者注: 扩展欧几里得算法 也叫 扩展的辗转相除法, 该算法在译者的之前的博客 读跨越千年的RSA算法 一文中曾有讲到, 有兴趣的读者可以前往阅读

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$ 上的两个整数.

以上是当 p = 19, 97, 127, 487 时, 曲线 $y^2 \equiv x^3 - 7x + 10 \pmod{p}$ 的图形. 注意, 在每个 x 坐标上最多有2个点, 且整个图形关于 $y = p / 2$ 水平对称.

曲线 $y^2 \equiv x^3 \pmod{29}$ 是奇异的并且在有三个点落在 (0,0) 上. 这样的曲线就不是有效的椭圆曲线

之前连续的曲线现在变成了xy平面上一些离散的点的集合. 然而我们还是能证明, 即使我们限制了曲线的域, 这个在 $\mathbb{F}_p$ 上的椭圆曲线仍然是一个阿贝尔群

点加

显然, 为了让加法在 $\mathbb{F}_p$ 上仍然有效, 我们需要稍微调整一下定义. 在实数域上, 我们说位于一条直线上的三点之和为0($P + Q + R = 0$). 我们可以保留这个定义, 但是在 $\mathbb{F}_p$ 上三点连成一线是什么意思呢?

我们说当有一条直线能将三个点连起来时, 三点就位于一条直线上. 当然, $\mathbb{F}_p$(有限域)上的直线和$\mathbb{R}$(实数域)上的直线是不一样的. 通俗的说, $\mathbb{F}_p$ 上的直线是指满足方程 $ax + by + c \equiv 0 \pmod{p}$ 的所有点 $(x, y)$ 的集合(即加上 "$(\text{mod}\ p)$" 的标准直线方程).

上图为曲线 $y^2 \equiv x^3 - x + 3 \pmod{127}$ 上 点$P = (16, 20)$ 和 点$Q = (41, 120)$ 的加法. 看看直线$y \equiv 4x + 83 \pmod{127}$是如何通过在平面上不断"重复"出现将这些点连接起来的.

既然我们在一个群里, 那么点加就具有以下这些我们已知的属性:

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

代数求和

这里计算点加的方程与在前一篇文章里讲的完全一样, 除了我们需要再每个方程末尾加上 $\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 逐个尝试所有可能的值显然是不切实际的, 这样需要经过 $O(p^2)$ 次尝试, 如果 p 是一个非常大的质数, 这样做的将会很"困难".

幸好, 我们还有一种更快的算法来计算群的阶: Schoof's 算法. 我们不会深入介绍这个算法的细节 -- 我们只需要知道, 这个算法的时间复杂度为多项式级别.

标量乘法和循环子群

在实数域中, 乘法可以通过如下方式定义: $$ n P = \underbrace{P + P + \cdots + P}_{n\ \text{times}} $$ 然后, 我们可以通过倍加法通过 $O(\log n)$ 步(或者 $O(k)$, k为数字的位长)得出结果. 这里也有一个计算标量乘法的交互式工具.

离散域 $\mathbb{F}_p$ 上的椭圆曲线乘法有一个有趣的属性, 当已知曲线 $y^2 \equiv x^3 + 2x + 3 \pmod{97}$ 和 点 $P = (3, 6)$, 现在计算点 P 的(标量)乘积.

点 $P = (3, 6)$ 的乘积总共只有 5 个点(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的乘积只有5个值, 曲线上其他任何点都没有出现. 其二, 这些点反复循环出现. 我们可以写成:

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

上面5个方程实际上还可以压缩成一个, 多亏有模运算: $kP = (k \bmod{5})P$

不仅如此, 我们还可以验证到这五个点在加法运算下是封闭的. 这意味着: 无论我把 0, P, 2P, 3P, 4P 怎么加, 得到的结果总是这五个点之一. 再次强调, 椭圆曲线上其他任何的点都不会出现在结果中.

不仅仅是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 的另一个乘积 (P的乘积在加法运算下是封闭的). 这足以证明P的乘积的集合是椭圆曲线群的一个循环子群.

"子群"是指另一个群的子集构成的群. 而"循环子群"是指群里的元素反复循环出现的子群, 正如前面的例子中所展示的. 点 P 则叫做这个循环子群的 生成点基点.

循环子群是 ECC 以及其他密码学系统的基础, 在下一篇文章中我们将看到其中的原因.

子群的阶

我们可以问自己, 从 P 点生成的子群的阶是多少(或者说, P 的阶是多少). Schoof's 算法不能帮助我们回答这个问题, 因为这个算法只在整个椭圆曲线上是有效的, 在子群上则不行. 在进入这个问题之前, 我们需要了解一些点:

  • 到目前为止, 我们将一个群里点的数量定义为这个群的阶, 这个定义仍然是有效的, 但是在一个循环子群中我们可以给出一个新的等效的定义: P的阶是使 nP = 0 成立的最小正整数. 事实上, 如果你再看看前面的例子, 我们的子群包含5个点, 5P = 0 成立.
  • P 的阶与椭圆曲线的阶是通过拉格朗日定理, 其中有关于子群的阶是其父群的阶的因数的阐述. 换句话说, 如果一个椭圆曲线包含 N 个点且它的某个子群包含 n 个点, 则有 n 是 N 的一个因数.

以上两个信息给我们提供了一个找到基于P点的子群的阶的方法:

  1. 通过 Schoof's 算法找出椭圆曲线的阶 N
  2. 找出 N 所有的因数
  3. 用 N 的每个因数 n 计算出 nP
  4. 其中使 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, 而这并不是这个子群的阶, 而是它的某个倍数.

再看一个例子: $\mathbb{F}_{29}$ 上的椭圆曲线 $y^2 = x^3 - x + 1$ 的阶 N = 37, 这是一个质数. 那么其子群的阶 n 只有可能为 1 或 37. 正如你所猜, 当 n = 1, 这个子群将只包含一个无穷远处的点, 而当 n = N 时, 子群将包含这个椭圆曲线上所有的点.

找到一个基点

为了实现 ECC 算法, 我们需要一个高阶子群. 所以总的来说我们要选择一条椭圆曲线, 计算出它的阶(N), 从中选出一个较大因数作为子群的阶(n)并最终找到一个合适的基点. 这就是说: 我们并非先找到一个基点再计算它的阶, 而是反过来: 我们先找到一个足够好的阶然后再找出合适的基点. 那么我们要怎么做呢?

首先, 我们需要再介绍一个术语. 拉格朗日定理揭示了数字 $h = N / n$ 总是一个整数(因为n是N的因数). 数字 h 有一个名字: 叫做这个子群的余子式.

现在设想对于椭圆曲线上的每个点都有 NP = 0 成立. 之所以有上述结论因为 N 总是任何候选 n 的倍数. 通过余子式的定义, 我们可以写出: $$ n(hP) = 0 $$ 现在假设 n 是质数(我们选择质数作为阶的原因将会在下篇文章中解释). 将方程写作上面的形式, 实际上告诉我们点 $G = hP$ 可以生产一个n阶的子群(除了当 $G = hP = 0$ 时, 其子群的阶为1).

据此提示, 我们可以写出下面的算法:

  1. 计算出椭圆曲线的阶 N
  2. 选择子群的阶 n, 为了让算法可行, 这个数字必须是一个质数并且是 N 的因数
  3. 计算出余子式 $h = N / n$
  4. 在曲线上随机选择一点 P
  5. 计算出 G = hP
  6. 如果 G 为 0, 则返回第4步. 否则我们就成功找出了这个n阶子群的生成点和其余子式h

需要注意的是, 此算法只有当n为质数时成立. 如果n不为质数, 那么G的阶则可能是n的一个因数.

离散对数

正如处理连续椭圆曲线时所做的那样, 我们现在将要讨论一个问题: 如果我们已知 P 和 Q, 使 Q = kP 成立的k是多少?

这个问题就是所谓的椭圆曲线上的离散对数难题, 我们相信这是一个"困难"问题, 因为到目前为止我们还没有找到任何一个可以在经典计算机上运行且能在多项式时间内解决这个问题的算法. 然而, 上述结论实际上也并没有经过数学上的证明.

和其他密码系统如 DSA, DH 以及 ElGamal算法一样, 这个问题也可以类推为离散对数难题 -- 这并不是一个巧合. 两者区别在于, 其他的那些算法使用的并非标量乘法而是指数模运算. 它们的离散对数难题可以表述为: 已知 a 和 b, 求使 $b = a^k \bmod{p}$ 成立的k是多少?

上述两类问题都是"离散的"是因为它们都在作用与有限的集合(更准确地说, 应该是循环子群). 它们都叫"对数"因为类推为普通对数问题.

让 ECC 更有吸引力的是, 在今天, 椭圆曲线上的离散对数难题似乎相比于其他密码学系统的离散对数难题要更加"困难"一些. 这意味着我们只用提供更少位数的整数k就能够达到与其他密码系统相同的安全级别, 关于此结论的细节我们将在第四篇也是最后一篇文章中进行讨论.

未完待续

今天的内容就到这里了! 希望你能喜欢这篇文章或在评论区写下你的观看法. 下周我将发布这个系列的第三篇文章, 是关于 ECC算法: 秘钥对的生成, ECDH 和 ECDSA. 这将会是这个系列文章中最有趣的一个部分. 千万别错过哦!

Show Comments