椭圆曲线密码学 (ECC) 总结
这份文件详细介绍了椭圆曲线及其在密码学中的应用，包括其群结构、整数分解的应用以及椭圆曲线离散对数问题 (ECDLP)。
I. 基本概念与启示
椭圆曲线密码学的兴起是受到传统公钥密码系统如 RSA 和 Diffie-Hellman 带来的启示 ：
- RSA 启示：给定一个未知阶数的群，计算该群的阶在计算上不可行（大整数分解问题）。
- Diffie-Hellman 启示：给定一个群，求该群任意元素的阶在计算上不可行（离散对数问题）。
- 总结：寻找其他具有类似性质的代数结构（群结构），椭圆曲线就是其中之一 。
- 椭圆曲线定义：椭圆曲线是阿贝尔群（Abelian group）的点集，其群运算是几何构造的 。它与“椭圆”本身几乎没有关系 。
II. 椭圆曲线的数学定义
1. $\mathbb{R}$ 上的非奇异椭圆曲线 (Non-singular Elliptic Curve over $\mathbb{R}$)
一条非奇异椭圆曲线 $E$ 是满足以下条件的解集 ：
\[y^{2}=x^{3}+ax+b \quad \text{其中 } a, b \in \mathbb{R} \text{ 且 } 4a^{3}+27b^{2}\ne0\]- 点集 $E$：由满足上述方程的所有点 $(x, y) \in \mathbb{R} \times \mathbb{R}$ 和一个特殊的点无穷远点 $\mathcal{O}$ 组成 。
- 群结构：解集 $E$ 带着恒等元 $\mathcal{O}$ 构成一个阿贝尔群 。
2. 有限域 $\mathbb{F}{p}$ 上的椭圆曲线 (Elliptic Curve over Finite Field $\mathbb{F}{p}$)
当 $p > 3$ 是一个素数时，有限域 $\mathbb{F}_{p}$ 上的椭圆曲线是满足以下同余式的解集 ：
\[y^{2} \equiv x^{3} + ax + b \pmod{p} \quad \text{其中 } a, b \in \mathbb{F}_{p} \text{ 且 } 4a^{3} + 27b^{2} \not\equiv 0 \pmod{p}\]- 点集：由满足上述同余式的点 $(x, y) \in \mathbb{F}{p} \times \mathbb{F}{p}$ 和无穷远点 $\mathcal{O}$ 组成 。
3. 有限域 $\text{GF}(2^{n})$ 上的椭圆曲线
由于 $y^{2} = x^{3} + ax + b$ 形式的曲线在 $\text{GF}(2^{n})$ 上计算切线斜率时分母 $2y_1$ 会变为 $0$，因此曲线形式有所不同 ：
\[y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}\]- 点 P 的逆元 $-P$：$- (x, y) = (x, -a_{1}x - a_{3} - y)$ 。
III. 椭圆曲线的群操作与公式推导
椭圆曲线上的群操作定义了一个二元运算 $P + Q = R$ 。
1. 基本群操作性质
[!Note] $\mathcal{O}$ 为一个无穷远点
- 恒等元: $P + \mathcal{O} = \mathcal{O} + P = P$
- 逆元 (在 $\mathbb{F}_{p}$ 上): $P + (-P) = \mathcal{O}$。若 $P=(x, y)$，则 $-P = (x, -y)$。
- 结合律 (Associativity): $P + (Q + R) = (P + Q) + R$
- 交换律 (Commutativity): $P + Q = Q + P$
2. 点加法 $P + Q = R$ 的几何解释与代数公式 (假设 $P=(x_1, y_1)$, $Q=(x_2, y_2)$, $R=(x_3, y_3)$)
| 情况 | 几何解释 | 代数公式 (运算) |
|---|---|---|
| $P \ne Q$ (两点相加) | 连接 $P, Q$ 的直线交曲线于第三点 $R’$， $R$ 是 $R’$ 在 $x$ 轴上的对称点 ($R=-R’$) 。 | 斜率 $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ |
| $x_3 = \lambda^{2} - x_1 - x_2$ | ||
| $y_3 = \lambda(x_1 - x_3) - y_1$ (已经取反) | ||
| $P = Q$ (点加倍) | 过 $P$ 点做曲线的切线，交曲线于另一点 $R’$， $R$ 是 $R’$ 在 $x$ 轴上的对称点 ($R=-R’$) 。 | 斜率 $\lambda = \frac{3x_{1}^{2} + a}{2y_1}$ |
| $x_3 = \lambda^{2} - 2x_1$ | ||
| $y_3 = \lambda(x_1 - x_3) - y_1$ (已经取反) |
- $P \ne Q$ 的 $x_3$ 推导：通过联立直线 $y = \lambda(x - x_1) + y_1$ 和曲线 $y^{2} = x^{3} + ax + b$，可以得到一个关于 $x$ 的三次方程 $0 = x^{3} - \lambda^{2}x^{2} + \cdots$ 。由于 $x_1, x_2, x_3$ 是这个三次方程的三个根，根据韦达定理，有 $x_1 + x_2 + x_3 = \lambda^{2}$，从而得到 $x_3 = \lambda^{2} - x_1 - x_2$ 。
3. 标量乘法 $nP$ 的高效计算
计算 $nP$ 可以使用 $O(n)$ 次加法，但更高效的方法是使用“加倍-相加”算法 (Double-and-Add Method)，将复杂度降至 $O(\log n)$ 步 。
- 原理：将 $n$ 写成二进制形式 $n = n_{0} + n_{1} \cdot 2 + n_{2} \cdot 2^{2} + \cdots + n_{r} \cdot 2^{r}$ 。
- 计算：$nP = n_{0}P + n_{1} \cdot 2P + n_{2} \cdot 2^{2}P + \cdots + n_{r} \cdot 2^{r}P$ 。其中 $2^{k}P$ 只需要 $k$ 次点加倍运算 。
IV. 椭圆曲线在安全中的应用
1. 椭圆曲线离散对数问题 (ECDLP)
- 定义：假设 $E$ 是有限域 $\mathbb{F}$ 上的椭圆曲线， $P \in E(\mathbb{F})$。给定点 $Q$ 是 $P$ 的一个倍数，ECDLP 就是找到整数 $n \in \mathbb{F}$ 使得 $nP = Q$ 。
- 安全性基础：人们相信 ECDLP 是一个困难问题 ，这为椭圆曲线密码学提供了安全保障。
2. 椭圆曲线 Diffie-Hellman (ECDH)
利用 ECDLP 的困难性，可以实现密钥协商。
- Bob 选择秘密整数 $b$，计算 $B = b \cdot P$ (公钥) 。
- Alice 选择秘密整数 $a$，计算 $A = a \cdot P$ (公钥) 。
- 共享秘密：Alice 计算 $a \cdot B$；Bob 计算 $b \cdot A$。两者结果相同，因为 $a \cdot B = a \cdot (b \cdot P) = b \cdot (a \cdot P) = b \cdot A$ 。
3. 椭圆曲线整数分解法 (ECM)
ECM 是一种使用椭圆曲线进行大数分解的算法 。
- 基本思想：选择一个随机参数 $a$ 和一个点 $P \in E(\mathbb{F}_{N})$。计算 $m = \text{lcm}(1, 2, \dots, B)$ 。如果在计算点加法 $mP$ 的过程中，分母与 $N$ 的最大公约数 $g$ 是 $N$ 的非平凡因子，则输出 $g$ 。
4. ECC 的优势与未来
- 优势：相较于传统公钥系统（如 RSA 和有限域 DLP），ECC 在较低的密钥长度下提供了更高的安全性，带来了更高的效率和安全性 。例如，ECDLP 在 $\ell(q) \ge 160$ 时，安全强度可与有限域 DLP 在 $\ell(p) \ell(q) \ge 160$ 或 RSA 在 $\ell(n) \ge 1024$ 时相比 。
- 后量子密码：文件提到了基于同源 (Isogeny-based) 的密码学，这是后量子时代的一个研究热点（如 CSIDH），尽管 SIKE 已被破解 。
好的，我们来详细计算椭圆曲线 $E: y^{2} \equiv x^{3} + x + 6 \pmod{11}$ 在有限域 $\mathbb{F}_{11}$ 上的点加倍 $2g$ 和点加法 $3g$ 的步骤 。
给定信息：
- 椭圆曲线 $E$: $y^{2} \equiv x^{3} + ax + b \pmod{11}$
- 其中 $a = 1$, $b = 6$ 。
- 生成元 (Generator) $g = (2, 7)$.
- 模数 $p = 11$.
1. 计算 $2g$ (点加倍 $P=Q$)
我们需要使用点加倍的公式。由于 $P=Q=g=(2, 7)$, 我们使用以下公式:
\[\lambda = \frac{3x_{1}^{2} + a}{2y_1}\] \[x_3 = \lambda^{2} - 2x_1\] \[y_3 = \lambda(x_1 - x_3) - y_1\]所有运算都在模 $11$ 下进行。
步骤 1: 计算斜率 $\lambda$
- $x_1 = 2$, $y_1 = 7$, $a = 1$.
现在我们进行模 $11$ 的简化：
- $13 \equiv 2 \pmod{11}$
- $14 \equiv 3 \pmod{11}$
我们需要找到 $3$ 在模 $11$ 下的乘法逆元，即 $3^{-1} \pmod{11}$。
我们寻找 $k$ 使得 $3k \equiv 1 \pmod{11}$：
- $3 \times 1 = 3$
- $3 \times 2 = 6$
- $3 \times 3 = 9$
- $3 \times 4 = 12 \equiv \mathbf{1} \pmod{11}$
所以 $3^{-1} \equiv 4 \pmod{11}$.
\[\lambda \equiv 2 \times 4 \equiv \mathbf{8} \pmod{11}\]步骤 2: 计算 $x_3$
\[x_3 \equiv \lambda^{2} - 2x_1 \pmod{11}\] \[x_3 \equiv (8)^{2} - 2(2) \pmod{11}\] \[x_3 \equiv 64 - 4 \pmod{11}\] \[x_3 \equiv 60 \pmod{11}\]- $60 = 5 \times 11 + 5$
步骤 3: 计算 $y_3$
\[y_3 \equiv \lambda(x_1 - x_3) - y_1 \pmod{11}\] \[y_3 \equiv 8(2 - 5) - 7 \pmod{11}\] \[y_3 \equiv 8(-3) - 7 \pmod{11}\] \[y_3 \equiv -24 - 7 \pmod{11}\] \[y_3 \equiv -31 \pmod{11}\]- $-31 = -3 \times 11 + 2$
- 或者 $-31 \equiv -31 + 4 \times 11 = -31 + 44 = 13 \equiv 2 \pmod{11}$
所以，$2g = \mathbf{(5, 2)}$.
2. 计算 $3g$ (点加法 $P \ne Q$)
$3g = g + 2g = (2, 7) + (5, 2)$. 我们使用点加法的公式 。
- $P = (x_1, y_1) = (2, 7)$
- $Q = (x_2, y_2) = (5, 2)$
步骤 1: 计算斜率 $\lambda$
\[\lambda \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod{11}\] \[\lambda \equiv \frac{2 - 7}{5 - 2} \pmod{11}\] \[\lambda \equiv \frac{-5}{3} \pmod{11}\]我们已经知道 $3^{-1} \equiv 4 \pmod{11}$.
\[\lambda \equiv -5 \times 4 \pmod{11}\] \[\lambda \equiv -20 \pmod{11}\]- $-20 \equiv -20 + 2 \times 11 = -20 + 22 = 2 \pmod{11}$
步骤 2: 计算 $x_3$
\[x_3 \equiv \lambda^{2} - x_1 - x_2 \pmod{11}\] \[x_3 \equiv (2)^{2} - 2 - 5 \pmod{11}\] \[x_3 \equiv 4 - 7 \pmod{11}\] \[x_3 \equiv -3 \pmod{11}\]- $-3 \equiv -3 + 11 = 8 \pmod{11}$
步骤 3: 计算 $y_3$
\[y_3 \equiv \lambda(x_1 - x_3) - y_1 \pmod{11}\] \[y_3 \equiv 2(2 - 8) - 7 \pmod{11}\] \[y_3 \equiv 2(-6) - 7 \pmod{11}\] \[y_3 \equiv -12 - 7 \pmod{11}\] \[y_3 \equiv -19 \pmod{11}\]- $-19 \equiv -19 + 2 \times 11 = -19 + 22 = 3 \pmod{11}$
所以，$3g = \mathbf{(8, 3)}$.
结果核对
您文件中的表格也显示了以下结果:
| $g$ | $2g$ | $3g$ |
|---|---|---|
| $(2, 7)$ | $(5, 2)$ | $(8, 3)$ |