2025-12-27

椭圆曲线群

定义

\Omega = \{ (x, y) \in F \times F: y^2 + a_1 x y + a_2 y = x^3 + a_3 x^2 + a_4 x + a_5 \}

和另一个点（无穷远点） $O$ 构成的集合，即

E = \{ O \} \cup \Omega

其中，Weierstrass 方程也可以用其他椭圆曲线方程取代，例如蒙哥马利方程。

设 $F$ 是一个域， $a_1, a_2, a_3, a_4, a_5 \in F$ ，则域 $F$ 上的椭圆曲线 $y^2 = x^3 + a x + b$ 是由满足 $F$ 上的方程 $y^2 = x^3 + a x + b$ 的所有点

G = \{ (x, y ) \in F \times F: y^2 = x^3 + a x + b \}

和另一个点 $O$ 构成的集合

E = \{ O \} \cup \{ (x, y ) \in F \times F: y^2 = x^3 + a x + b \}

该椭圆曲线的判别式为 $\Delta = 4 a^3 + 27 b^2$ （一般要求 $\neq 0$ ）。

\frac{\partial E}{\partial X} (x, y) = \frac{\partial E}{\partial Y} (x, y) = 0

则称点 $P$ 在曲线 $E$ 上是奇异的。如果曲线上至少有一个奇异点，就是奇异曲线。

由定义 1 定义的椭圆曲线奇异 $\Leftrightarrow \Delta = 0$ 。

则称 $n$ 为点 $P$ 的阶，记为 $n = ord(P)$ 。

由阶为 $n$ 的点 $P$ 在加法定义下生成的循环群 $<p>$ 是椭圆曲线群 $(E(F), +)$ 的一个 $n$ 阶子群。

设 $E$ 是有限域 $F$ 上的椭圆曲线， $G$ 是 $E$ 的一个循环子群，点 $a$ 是 $G$ 的一个生成元，即 $G = \{ k a: k \ge 0 \}, b \in G$ ，在已知 $a, b$ 的条件下，求解整数 $k$ 使 $k a = b$ 。

已知曲线上的点 $P, Q \in E(F)$ ，且都不是无穷远点，令 $P = (x_1, y_1), Q = (x_2, y_2), P + Q = R$ ，则 $R = ?$

定义：

P + Q = \left\{ \begin{array}{l} O, \qquad \qquad \ 若 x_1 = x_2 且 y_1 = -y_2 \\ (x_3, y_3), \qquad 其它 \end{array} \right.

其中

\left\{ \begin{array}{l} x_3 = \lambda^2 - x_1 - x_2 \\ y_3 = \lambda (x_1 - x_3) - y_1 \end{array} \right. 且 \lambda = \left\{ \begin{array}{l} \frac{y_2 - y_1}{x_2 - x_1}, 若 P \ne Q \\ \frac{3 x_1^2 + a}{2 y_1}, 若 P = Q \end{array} \right.

计算点乘运算可以拆分成点加和倍乘运算。

定理：椭圆曲线按定义的加法运算构成交换群 $(E, +)$ ， $O$ 就是该群的零元。

当有限域特征为 $2$ 时，可将椭圆曲线化为标准型：

y^2 + x y = x^3 + a x + b, \qquad a, b \in F

当有限域特征 $\ge 3$ 时，可将椭圆曲线化为标准型：

y^2 = x^3 + a x + b, \qquad a, b \in F

密码学中一般使用以上标准型。

除法当作乘除数逆元即可。

利用椭圆曲线群一个阶很大的循环子群代替有限域的乘法群进行构造，并将阶作为本原元。

公开 $F, E, P, Q$

选择随机 $k$

已知明文 $m = (m_1, m_2) \in F^* \times F^*$

计算密文 $c = (c_0, c_1, c_2) \in E \times F^* \times F^*$

将 Elgamal 有限域中的数化为群中的点。