数论与群论密码学-13-椭圆曲线

如前文所述,定义一个基于离散对数问题(DLP)的密码系统需要一个于计算机中可实现的群代数结构,其中群运算的实现应高效快速。另外,我们需要该结构中的 DLP 不可在合理的时间内被做出解答。

例如,之前我们遇到了 \(G = \mathbb{F}_p^\times\)(其中 \(p\) 为素数)和 \(G = (\mathbb{Z}/m\mathbb{Z})^\times\).

而针对这些系统的攻击有:
1. 对数表
2. SPH
3. 指数运算(次指数时间复杂度)

椭圆曲线

椭圆曲线给出了另一种群结构的实现,其不仅符合上述要求,并且还有如下优势:
1. 选择群(生成元)时有更大的灵活度
2. 不存在任何已知的针对椭圆曲线的指数运算攻击法。

椭圆曲线的基本性质

选择 \(K\) 为一个域结构(例如 \(\mathbb{Q}, \mathbb{R}, \mathbb{C}, \mathbb{F}_p\)),函数

\[y^2 = x^3 + ax + b \quad (a, b \in K)\]

定义了 \(E/K\) 上的一条椭圆曲线。其中要求 \(\Delta = -16 (4a^3 + 27b^2) \ne 0\)。仅当 \(\mathsf{char}(K) \ne 2, 3\) 时存在这样的曲线1

集合

\[E(K) = \{(x, y) \in K \times K : y^2 = x^3 + ax + b\} \cup \{P_\infty\}\]

被称为 \(E/K\) 上的 \(k\)-有理点集。其中 \(\{P_\infty\}\) 将作为 \(E(K)\) 的运算幺元。

定义 \(E(K)\) 上的群运算为

\[(x_1, y_1) \star (x_2, y_2) = (x_3, y_3)\]

\[ \begin{aligned} x_3 &= \lambda^2 - x_1 - x_2\\ y_3 &= \lambda (x_1 - x_3) - y_1 \end{aligned} \]

其中

\[ \lambda = \begin{cases} \frac{y_2 - y_1}{x_2 - x_1}, &\text{若 $x_1 \ne x_2$}\\ \frac{3x_1^2 + a}{2y_1}, &\text{若 $x_1 = x_2$ 且 $y_1 = y_2$} \end{cases} \]

另外,若有 \(x_1 = x_2, y_1 \ne y_2\),那么由于有 \(y_2 = -y_1\),定义

\[(x_1, y_1) \star (x_1, -y_1) = P_\infty\]

而定义 \(P_\infty\) 为运算幺元。

通常将该群运算记作 \(+\) 而非 \(\star\)

\(K = \mathbb{R}\), \(E: y^2 = f(x)\), \(f(x)\) 为使 \(\Delta \ne 0\) 的三次函数。

该曲线在 \(\mathbb{R}^2\) 的图像如下:

我们可以注意到:
- 当 \(f(x)\) 有一个实根时,即 \(\Delta < 0\) 时,曲线是连接的(有一个部分)
- 当 \(f(x)\) 有两个实根(因此也有三个)时,即 \(\Delta > 0\) 时,曲线有两个部分。

此曲线上的群法则有如下的几何意义:

\[ \begin{aligned} &P_1 + P_2 + P_3 = P_\infty \\ &\iff P_1 + P_2 = -P_3 \\ &\iff P1, P2, P3 \text{ 共线} \\ \end{aligned} \]

其中由于根据定义,有 \(-P\)\(P\) 关于 \(x\)-轴的镜像。

\(K = \mathbb{C}\).

复数域上的椭圆曲线与定义如下的双周期椭圆函数有关:

定义 \(\Lambda = \mathbb{Z}\omega_1 + \mathbb{Z}\omega_2 \subset \mathbb{C}\) 为一个格,其通过两个基本频率 \(\omega_1, \omega_2\) 生成复数域。

而双周期椭圆函数定义为满足以下要求的复函数:

\[ f(z + \omega_1) = f(z), f(z + \omega_2) = f(z), \forall z \in \mathbb{C} \tag{1} \]

即函数 \(f(z)\) 的结构在复平面之于格 \(\Lambda\) 的商上重复。

有时也不失一般性地将格定义为 \(\Lambda = \omega_1(\mathbb{Z} + \tau\mathbb{Z}) \subset \mathbb{C}\),其中 \(\tau = \omega_2/\omega_1, \Im(\tau) > 0\)。于是式 (1) 等价于

\[ f(z + \lambda) = f(z), \forall z \in \mathbb{C}, \forall \lambda \in \Lambda \]

特别地,若设 \(\omega_1 = 1\),则有 \(\Lambda_\tau = \mathbb{Z} + \mathbb{Z}\tau\),且 \(\forall k \in \mathbb{Z}, f(z + k) = f(z)\).

我们也可以这么理解格:回忆定义在 \(\mathbb{Z}\) 上周期为 \(n\) 的函数相当于将空间 \(\mathbb{Z}\) 作为格 \([0, n)\) 上的商,由于格中各元素分别相当于该空间中截然不同的一个等价类,我们可以将这样的函数理解为仅定义在格 \([0, n)\) 上。类似地,定义在 \(\mathbb{C}\) 上的双周期函数可以被理解为仅定义在格 \(\Lambda\) 上的函数。由于我们随后将要要求该函数在 \(\mathbb{C}\) 中可微(因此连续),我们可以设想在三维空间中将 \(▱ O\omega_1\tau\) 两组对边分别粘连,形成形如甜甜圈一样的环面。而 \(f(z)\) 定义的就是在从该环面到复数域的映射,并且在跨越边界时保持连续。

2

我们断言,给定格 \(\Lambda\),存在函数 \(\wp_\Lambda(z)\) 满足:

  1. 是双周期函数,即对于 \(\Lambda\) 来说是周期的,即式 (1) 对于 \(\wp_\Lambda(z)\) 成立

  2. \(\mathbb{C}/\Lambda\) 上可微,记其微分为 \(\wp'_\Lambda(z)\)

  3. 在每个 \(\lambda \in \Lambda\) 上有一个双极点,即 \(\wp_\Lambda(\lambda) = \infty\)\(((z - \lambda)^2\wp_\Lambda)(\lambda) \ne 0\)

    因此 \(\wp_\Lambda\) 定义了如下的一个函数:

    \[\wp_\Lambda: \mathbb{C}/\Lambda \to \mathbb{C} \cup \{\infty\}\]

  4. \(\wp_\Lambda\) 满足以下微分方程:

    \[\wp'_\Lambda(z)^2 = 4\wp_\Lambda(z)^3 - g_2\wp_\Lambda(z) - g_3\]

    其中 \(g_2, g_3 \in \mathbb{C}\) 是两个常数。

称满足以上条件的函数为 魏尔斯特拉斯 \(\wp\)-函数。

于是有点 \((\wp_\Lambda(z), \frac{1}{2}\wp'_\Lambda(z))\) 在曲线

\[E_\Lambda: y^2 = x^3 + a_\Lambda x + b_\Lambda\]

上。其中 \(a_\Lambda = -\frac{1}{4}g_2, b_\Lambda = -\frac{1}{4}g_3\).

于是我们注意到,映射 \(z \mapsto (\wp_\Lambda(z), \frac{1}{2}\wp'_\Lambda(z))\) 描述了以下双射:

\[\Phi_\Lambda : \mathbb{C}/\Lambda \stackrel{\sim}{\to} E_\Lambda(\mathbb{C})\]

其中 \(E_\Lambda\) 为椭圆曲线,而 \(\Phi_\Lambda\) 描述了两个群间的同构。

注意 \(\Phi_\Lambda(\Lambda) = P_\infty\)\(E_\Lambda\) 上的无穷远点。

另外,若

\[E: y^2 = x^3 + ax + b \quad (a, b \in \mathbb{C})\]

为一条复椭圆曲线,那么存在格 \(\Lambda \subset \mathbb{C}\) 使得 \(a_\Lambda = a, b_\Lambda = b\) 从而有 \(E = E_\Lambda\).

结合上述两点,我们可以发现每一条复椭圆曲线 \(E/\mathbb{C}\) 都有如下解析描述:存在能给出同构 \(\Phi_\Lambda : \mathbb{C}/\Lambda \stackrel{\sim}{\to} E(\mathbb{C})\) 的格 \(\Lambda \subset \mathbb{C}\).


  1. 因此我们不讨论更一般的由 \(E: y^2 + a_1xy + a^3y = x^3 + a_2x^2 + a_4x + a_6\) 定义的椭圆曲线↩︎

  2. 该图片于 Wikimedia Commons 发表在 Public Domain 中↩︎