ECC -- 椭圆曲线问题

椭圆曲线密码学 (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\).

\[\lambda \equiv \frac{3(2)^{2} + 1}{2(7)} \pmod{11}\]

\[\lambda \equiv \frac{3(4) + 1}{14} \pmod{11}\]

\[\lambda \equiv \frac{13}{14} \pmod{11}\]

现在我们进行模 \(11\) 的简化：

\(13 \equiv 2 \pmod{11}\)
\(14 \equiv 3 \pmod{11}\)

\[\lambda \equiv \frac{2}{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\)

\[x_3 \equiv \mathbf{5} \pmod{11}\]

步骤 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}\)

\[y_3 \equiv \mathbf{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}\)

\[\lambda \equiv \mathbf{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}\)

\[x_3 \equiv \mathbf{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}\)

\[y_3 \equiv \mathbf{3} \pmod{11}\]

所以，\(3g = \mathbf{(8, 3)}\).

结果核对

您文件中的表格也显示了以下结果:

\(g\)	\(2g\)	\(3g\)
\((2, 7)\)	\((5, 2)\)	\((8, 3)\)