视频

椭圆曲线群

定义

1. 设 $F$ 是一个域，$a_1, a_2, a_3, a_4, a_5 \in F$，则（基）域 $F$ 上的椭圆曲线是由（Weierstrass 方程） $$\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 方程也可以用其他椭圆曲线方程取代，例如蒙哥马利方程。

2. 设 $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$）。

3. 令 $P = (x, y)$ 是曲线 $E$ 上的一点，若： $$\frac{\partial E}{\partial X} (x, y) = \frac{\partial E}{\partial Y} (x, y) = 0$$

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

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

4. 设 $E$ 是有限域 $F$ 上的椭圆曲线， $P \in E(F)$，若 $n = \min\{ k | k > 0, k P = O \}$

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

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

5. 椭圆曲线群上的离散对数问题

设 $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 = ?$

定义：

1. 对 $P \in E$，定义 $P + O = O + P = P$；

2. $P = (x_1, y_1), Q = (x_2, y_2) \in E$，定义

   $$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$ 就是该群的零元。

例

1. 例

当有限域特征为 $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$$

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

2. 例

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

ECC 椭圆曲线公钥密码

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

参数设定

1. 构造有限域 $F$。

2. 生成域 $F$ 上的椭圆曲线 $E$。

3. 取椭圆曲线中的一个点 $P$ （阶足够大，且生成循环群 $G = <P>$ 中的离散对数问题难解）。

4. 选择加密密钥 $Q$ 和 解密密钥 $d$，使 $Q = d P$。（类似与 Elgamal 的 $\beta = a^d$）

公开 $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^*$

• $c_0 = k P; (k_1, k_2) = k Q$

• $c_1 = k_1 m_1$

• $c_2 = k_2 m_2$

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

脱密

• $(k_1, k_2) = d c_0$

• $m_1 = (k_1)^{-1} c_1$

• $m_2 = (k_2)^{-1} c_2$