# 椭圆曲线密码学：有限域和离散对数
>原文[地址](https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/)，DAOC DAO进行翻译整理
[在上一篇文章中](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/)，我们了解了如何使用实数上的椭圆曲线来定义群。具体来说，我们定义了一个点加法规则：给定三个对齐的点，它们的和为零（$P + Q + R = 0$）我们推导出了计算点加法的几何方法和代数方法。
然后我们引入了标量乘法（$nP = P + P + \cdots + P$），我们发现了一种计算标量乘法的“简单”算法：翻倍加和。
现在我们将把椭圆曲线限制在有限域内，而不是实数集，看看情况如何变化。
## 模$p$整数域
首先，有限域是具有有限个元素的集合。有限域的一个例子是模$p$的整数集，其中$p$是素数，通常表示为$\mathbb{Z}/p$，$GF(p)$或者$\mathbb{F}_p$。我们将使用后一种符号。
在域中，我们有两个二元运算：加法 ($+$) 和乘法 ($·$)。两者都是封闭的、结合的和交换的。对于这两种运算，都存在一个唯一的恒等元素，并且对于每个元素都有一个唯一的逆元素。最后，乘法对加法是分配的：
$$x \cdot (y + z) = x \cdot y + x \cdot z$$
模$p$整数集的元素由$0$到$p-1$构成。加法和乘法的工作方式与[取模运算](http://en.wikipedia.org/wiki/Modular_arithmetic)（也称为“时钟运算”）相同。以下是一些运算示例$\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$
如果您对这些等式不熟悉，并且需要模运算的入门知识，请查看[可汗学院](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic)。
正如我们已经说过的，模$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 实现：
```
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$上定义椭圆曲线的所有必要元素。在[之前文章](https://hackmd.io/@daoc-dao/Skf9sdbcJx)中定义的点集：
$$
\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$上的两个整数。
>曲线$y^2 \equiv x^3 - 7x + 10 \pmod{p}$和$p = 19, 97, 127, 487$。注意，对于每一个$x$，最多有两个点，还要注意关于$y = p / 2$对称。
>曲线$y^2 \equiv x^3 \pmod{29}$是奇异的，并且有三重点$(0,0)$，它不是有效的椭圆曲线。
以前连续的曲线现在变成了一组在$xy$平面不相交的点。但我们可以证明，即使我们约束了我们的域，椭圆曲线在$\mathbb{F}_p$仍然形成一个阿贝尔群。
## 点加法
显然，我们需要稍微改变一下加法的定义，才能让它在$\mathbb{F}_p$发挥作用。对于实数，我们说三个对齐点的总和为零（$P + Q + R = 0$）我们可以保留这个定义，但是在$\mathbb{F}_p$上三个点对齐是什么意思呢？
如果有一条线连接所有点，我们可以说这三个点是对齐的。但显然，$\mathbb{F}_p$上的线和$\mathbb{R}$上的线是不一样的。我们可以非正式的说，$\mathbb{F}_p$上的一条线是满足$ax + by + c \equiv 0 \pmod{p}$的点集$(x,y)$。（标准方程加上$(modp)运算$）
>当$P = (16, 20)$和$Q = (41, 120)$时，在曲线$y^2 \equiv x^3 - x + 3 \pmod{127}$上的加法。注意，$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$（来自逆元的定义）
## 代数和
计算点加法的公式与上一篇文章完全相同，只是我们需要在表达式的末尾添加$(\bmod(p))$。因此，给定$P = (x_P, y_P)$，$Q = (x_Q, y_Q)$和$R = (x_R, y_R)$，我们可以计算$P + Q = -R$如下：
$$
\begin{align*}
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{align*}
$$
如果$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 的证明](https://arxiv.org/pdf/1710.00214)只使用了基本概念。如果你对这些方程在（几乎）每个领域都适用的原因感兴趣，请阅读它。
回到我们——我们不会定义几何方法：事实上，这样做存在一些问题。例如，在上一篇文章中，我们说要计算$P + P$我们需要取曲线的切线$P$。但是如果没有连续性，“切线”这个词就没有任何意义。我们可以解决这个问题和其他问题，但是纯几何方法太复杂了，根本不实用。
相反，您可以使用我编写的用于计算点加法的[交互式工具](https://andrea.corbellini.name/ecc/interactive/modk-add.html)。
## 椭圆曲线群的阶
我们说过，有限域上的椭圆曲线有有限个点。我们需要回答的一个重要问题是：到底有多少个点？
首先，我们设群中点的个数称为该群的阶。
尝试所有可能的值$x$从 0 到$p-1$不是一种可行的计数方式，因为它需要$O(p)$步骤，如果$p$是一个大素数就很“难”。
幸运的是，有一种更快的算法可以计算阶数：[Schoof算法](https://en.wikipedia.org/wiki/Schoof%27s_algorithm)。我不会介绍该算法的细节——重要的是它在多项式时间内运行，这就是我们所需要的。
## 标量乘法和循环子群
与实数一样，乘法可以定义为：
$$
n P = \underbrace{P + P + \cdots + P}_{n\ \text{times}}
$$
并且，我们可以使用翻[倍加和算法](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/#double-and-add)在$O(\log n)$步来执行乘法（或者$O(k)$，$k$为$n$位比特数）。我还编写了一个用于标量乘法的[交互式工具](https://andrea.corbellini.name/ecc/interactive/modk-mul.html)。
椭圆曲线$\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$
对于每个整数$k$请注意，得益于模运算符，这五个方程可以“压缩”为一个方程：
$$
kP = (k \bmod{5})P
$$
不仅如此，我们还可以立即验证这五个点在加法下是封闭的。这意味着：无论我添加什么$0, 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 算法，因为该算法只适用于整个椭圆曲线，而不适用于子群。在解决这个问题之前，我们还需要一些信息：
- 到目前为止，我们已经将阶定义为群中点的数量。这个定义仍然有效，但在循环子群中，我们可以给出一个新的等效定义：$P$的阶是最小的正整数使得$nP = 0$。事实上，如果你看看前面的例子，我们的子群包含五个点，我们有$5P = 0$。
- $P$的阶通过[拉格朗日定理](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory))可以将子群的阶与椭圆曲线的阶联系起来，该定理指出子群的阶是母群阶的除数。换句话说，如果椭圆曲线包含$N$点，并且它的一个子群包含$n$点，那么$n$是$N$的除数。
这两个信息结合起来，为我们提供了一种找出基点$P$子群的阶的方法：
1. 使用 Schoof 算法计算椭圆曲线的阶$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$，这不是子群的阶，而是它的倍数之一。
另一个例子：由以下方程定义的椭圆曲线$y^2 = x^3 - x + 1$在域$\mathbb{F}_{29}$有阶$N = 37$，是素数。其子群只能有阶$n=1$或者$n=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$，是什么$k$使得$Q=kP$？
这个问题被称为椭圆曲线的离散对数问题，人们认为这是一个“难题”，因为没有已知的多项式时间算法可以在传统计算机上运行。然而，没有数学证据支持这一观点。
这个问题也类似于其他密码系统（如数字签名算法 (DSA)、Diffie-Hellman 密钥交换 (DH) 和 ElGamal 算法）使用的离散对数问题——它们有相同的名称并非巧合。不同之处在于，对于这些算法，我们使用模幂而不是标量乘法。它们的离散对数问题可以表述如下：如果我们知道$a$和$b$，什么$k$使得$b = a^k \bmod{p}$？
这两个问题都是“离散的”，因为它们涉及有限集（更准确地说是循环子群）。它们也是“对数”，因为它们类似于普通对数。
ECC 之所以有趣，是因为到目前为止，与密码学中使用的其他类似问题相比，椭圆曲线的离散对数问题似乎“更难”。这意味着我们需要更少的位数来表示整数$k$为了达到与其他密码系统相同的安全级别，我们将在本系列的第四篇也是最后一篇文章中详细介绍。
Sign in with Wallet
Connect another wallet