数论与群论密码学-16-椭圆曲线密码系统

\(E/F\) 为一椭圆曲线,其中为了简化讨论,仅考虑 \(F := \mathbb{F}_p\), \(p \ge 5\) 为素数的情况。

如前文所述,\(E(F)\) 为交换群,其阶 \(N_{E/F} = \big| E(F) \big|\) 根据哈赛定理有 \(N_{E/F} \approx p\).

根据定义,我们注意到 \(E(F)\) 中的群运算是十分高效的:

\[ \mathsf{Time}(P + Q) = \Theta(\log^2 p) \]

\(\mathbb{F}_p\) 中的加法,乘法及逆运算皆需进行 \(\Theta(\log^2 p)\) 次为运算。而求 \(P\)\(Q\) 的和的公式需要进行至多 20 次上述运算,因此总共需要 \(\Theta(\log^2 p)\) 次位运算。

由于 \(E(F)\) 上的群运算是以加法表示的,因此关于它的离散对数问题叙述为:

给定 \(P \in E(F)\)\(Q \in <P> = \{kP : k \in \mathbb{Z}\}\),求满足 \(Q = xP\)\(x\),记这样的 \(x\)\(x := DL_P(Q)\).

椭圆曲线 \(E(F)\) 上的 Diffie-Hellman 秘钥交换

公开确定椭圆曲线 \(E/F\) 及其上一点 \(P \in E(F)\),通信双方 A, B 进行如下操作:

A: 随机选取数 \(k_A \in \mathbb{N}\),计算 \(P_A = k_AP\) 并将 \(P_A\) 发送给 B.
B: 随机选取数 \(k_B \in \mathbb{N}\),计算 \(P_B = k_BP\) 并将 \(P_B\) 发送给 A.

如此一来有秘钥 \(S_{AB} = k_BP_A = k_AP_B = k_Ak_BP\) 仅为 A, B 所知。

\(E(\mathbb{F}_p)\) 中表示文本的方法

如先前的做法,将明文分段并将每段通过如 ASCII 之类的方法编码为 \(m \in \mathbb{N}\)。通过选择分段的大小和素数 \(p\) 使得 \(m < p\),于是有 \(m \in \mathbb{F}_p\)。因此在 \(E(\mathbb{F}_p)\) 中表示 \(m \in \mathbb{N}\) 等价于选取一个代表该消息段的点 \(P_m \in E(\mathbb{F}_p)\).

我们来逐一考察以下方法。

方法 1

固定点 \(P \in E(\mathbb{F}_p)\) 并取 \(P_m := mP\) 来表示 \(m\).

该方法并不实际。因为从点 \(P_m\) 恢复出 \(m\) 等价于求解一个离散对数问题。

方法 2

同前,视 \(m \in \mathbb{F}_p\) 并找到满足 \(P_m = (m, y) \in E(\mathbb{F}_p\)\(y \in \mathbb{F}_p\).

因为 \(E\)\(y^2 = f(x)\) 定义,该方法要求 \(f(m) \in \mathbb{F}_p^2\),即其为一平方。因此给定一 \(m\) 我们有大约 50% 的概率找不到与之对应的点 \(P_m\).

方法 3 (Koblitz)

根据可接受的失败概率 \(\frac{1}{2^\kappa}\) 固定 \(\kappa \in \mathbb{N}\).
\(M = \lfloor \frac{p}{\kappa} \rfloor\),假设 \(m < M\).
逐项考察 \(x_j = j + mk\), 其中 \(j = 1, \cdots, \kappa\)
使用雅克比符号,可以高效地找出最先满足 \(f(x_j) \in \mathbb{F}_p^2\) 的项。
然后通过模平方根算法计算满足 \(y^2 = f(x_j)\)\(y\) 并且取 \(P_m = (x_j, y)\).

给定 \(P_m = (x, y)\),可通过 \(m = \lfloor \frac{x-1}{\kappa} \rfloor = \mathsf{quot}(x-1, \kappa)\) 还原出 \(m\).

注意,由于

\[ \mathsf{Prob}\left(f(x_j) \in \mathbb{F}_p^2\right) =\mathsf{Prob}\left(\left(\frac{f(x_j)}{p}\right) = 1\right) \approx \frac{N_{E/F}}{2} \cdot \frac{1}{p} \approx \frac{1}{2} \]

其中最后一步的依据为哈赛定理。因此该方法失败的概率为 \(\frac{1}{2^\kappa}\).

椭圆曲线上的 ElGamel 加密算法

考虑 \(E/\mathbb{F}_p\),取点 \(P \in E(\mathbb{F}_p)\) 为一高阶元素,其中要求 \(P\) 的阶对于 SPH 攻击来说是安全的。

此时 ElGamel 密码系统的协议如下:

A 秘密选择数 \(k_A\) 并计算 \(P_a = k_AP\),于是有 A 的公钥 \((p, P, P_A)\)
若 B 要将消息 \(m\) 发送至 A, B 依前文所述方法将 \(m\) 嵌入在 \(E(\mathbb{F}_p)\) 中,得到点 \(P_m \in E(\mathbb{F}_p)\).
B 随机选择数 \(l\),计算 \((P_1, P_2) = (lP, P_m + lP_A)\) 并将之发送给 A.
于是 A 可通过计算 \(P_m = P_2 - k_AP_1\) 得信息 \(m\).

椭圆曲线上的 ECDSA 数字签名

取椭圆曲线 \(E/\mathbb{F}_p\),其中 \(p\) 为素数。取点 \(P \in E/\mathbb{F}_p\),使得 \(ord(P) = q\) 为素数,且 \(q \approx p\)\(q\) 几乎和 \(p\) 一样大)。

\(\newcommand{\rem}{\mathsf{rem}}\)

用户 A 选择数 \(x = x_A\) 作为秘钥,并计算 \(Q_A := x_AP\) 作为公钥。于是有为消息 \(m\) 签名的协议:
1. 随机选取数 \(k\) 使得 \(1 < k < q\)
2. 计算 \((x_1, y_1) := kP\), \(r := \rem(x_1, q)\)
3. 若 \(r = 0\) 则重新选取 \(k\)
4. 计算 \(s := \rem((H(m) + x_Ar)/k, q)\),其中 \(H(m)\)\(m\) 的哈希值。
5. 若 \(s = 0\) 则重新选取 \(k\)
6. 于是 \((r, s)\) 为签名。

收到消息的用户通过如下方法验证消息 \(m'\) 确实由 A 所签名:
1. 从受信第三方获取 A 的公钥 \(Q_A\)
2. 验证有 \(1 < r\), \(s < q\)
3. 计算 \(w := \rem(1/s, q)\)
4. 计算 \(u_1 := \rem(H(m')w, q)\), \(u_2 = \rem(rw, q)\)
5. 计算 \((x_0, y_0) := u_1P + u_2Q_A\), \(v = \rem(x_0, q)\)
6. 验证有 \(v = r\).

该协议确保了有:
1. \(Q = xP\)
2. \(r \equiv x_1 \pmod q\)\(0 < r < q\)
3. \(sk \equiv H(m) + xr \pmod q\)
4. \(sw \equiv 1 \pmod q\)
5. \(u_1 \equiv H(m')w \pmod q\)
6. \(u_2 \equiv rw \pmod q\)
7. \(u_1P + u_2Q = (x_0, y_0)\)
8. \(v \equiv x_0 \pmod q\)

若确实有 \(m' = m\),则

\[ u_1P + u_2Q \stackrel{1}{=} u_1P + u_2xP = (u_1 + u_2x)P \stackrel{\text{5, 6 且 $ord(P) = q$}}{=} (H(m')w + rwx)P \stackrel{m' = m}{=} (H(m)w + rwx)P \stackrel{\text{3 且 $ord(P) = q$}}{=} w(sk)P \stackrel{4}{=} kP = (x_1, y_1) \]

于是

\[ \begin{aligned} (x_0, y_0) = (x_1, y_1) &\implies \rem(x_0, q) = rem(x_1, q) \\ &\iff v = r \end{aligned} \]

曲线和点的选择

方法 1:随机选择(固定 \(p\)\(\mathbb{F}_p\)

  1. 随机选择 \(x, y \in \mathbb{F}_p\) 并取点 \(P = (x, y)\)。随机选择 \(a \in \mathbb{F}_p\) 并计算 \(b = y^2 - (x^3 + ax)\),即先选择点再选择穿过该点的曲线。

  2. 验证有 \(\Delta_{E_{a, b}} = 4a^3 + 27b^2 \ne 0\) (在 \(\mathbb{F}_p\) 中)若有,则取 \(E = E_{a, b}\), \(P \in E_{a, b}(\mathbb{F}_p)\)。否则返回第 1 步。

该方法要求计算并验证点 \(P\) 的阶能使得所得密码系统对于攻击来说是安全的。即要求 \(ord(P)\) 有足够大的素因数。因此需要:
1. 计算群的基 \(\big| E(\mathbb{F}_p) \big| = N_{E/\mathbb{F}_p}\)。可使用 Schoof/Elkies/Atkin 方法。
2. 计算 \(N_{E/\mathbb{F}_p}\) 的素因式分解。由于安全的椭圆曲线密码系统所需的秘钥大小(约 160 位)远比 RSA 所需的(约 2048 位)小得多,这是可能做到的。

方法 2:选择 \(P \in E(\mathbb{Q})\) 并 reduce \(\!\!\!\bmod p\)

该方法要求使用有理数上的椭圆曲线 \(E/\mathbb{Q}\):
1. 随机选取整数 \(a, b\)
2. 随机选取点 \(P = (x, y) \in E(\mathbb{Q})\),并通过 Nagell/Luts 或者 Mazur 定理验证有 \(ord(P) = \infty\)。若无则重复第 1 步。
3. 随机选择满足 \(\Delta_E \not\equiv 0 \pmod p\) (即 \(p \not\mid \Delta_E\))的素数 \(p\)。取 \(\overline{E} = E \bmod p\),因此有 \(\overline{E}/\mathbb{F}_p : y^2 \equiv f(x) \pmod p\)。记 \(\overline{P} := (x, y) \pmod p\),因此有 \(\overline{P} \in \overline{E}(\mathbb{F}_p)\)
4. 验证 \((\overline{E}, \overline{P})\) 是密码学上安全的。否则重复第 3 步。

第 4 步所遇到的问题与方法 1 中的相同。不过对于某些被称作 CM-曲线 的椭圆曲线 \(E/\mathbb{Q}\) 来说有个关于 \(p\) 的求 \(\big| \overline{E}(\mathbb{F}_p) \big|\) 的公式。

另外有猜想认为存在无数个素数 \(p\) 使得 \(\overline{P}\)\(\overline{E}(\mathbb{F}_p)\) 的生成元。该猜想于广义黎曼猜想下成立。

方法 3:Koblitz 曲线

  1. 选择 \(p\) 为一个小素数并得到 \(E/\mathbb{F}_p\),并用朴素的方法计算 \(N = \big| E(\mathbb{F}_p) \big|\).
  2. 选取使得 \(q = p^r\) 足够大的数 \(f\)。于是可根据 Artin/Schmidt/Hasse 公式求得 \(\big| E(\mathbb{F}_q) \big|\):

\[ \big| E(\mathbb{F}_p) \big| = \big| \alpha^r - 1 \big|^2 \]

其中 \(\frac{1}{a}\)\(pT^2 - aT + 1\) 的根,\(a = p + 1 - N\).

其依据为哈赛的发现:

\[ pT^2 - aT + 1 = (\alpha T - 1)(\overline{\alpha}T - 1) \]

另外也可以使用如下关于 \(a_n := a_{E/\mathbb{F}_{p^n}} = 1 + p^n - \big| E(\mathbb{F}_{p^n}) \big|\) 的二阶递归关系:

\[ a_{n+2} = aa_{n+1} - qa_n \]

其中 \(a_0 = 2, a_1 = a\).

在使用 Koblitz 的编码消息的方法时,该方法会使得找到合适的点 \(P \in E(\mathbb{F}_q)\) 不那么容易。

另外 2000 年左右 Frey 发现的 Weil descent 攻击使得选取 \(r\) 时有额外的要求。最理想的方法是选取 \(r\) 为素数。