本文需要一点抽象代数基础, 需要了解群环域, 同态与同构相关概念和相关定理

抽象代数的应用举例

椭圆加密

前置

考虑椭圆曲线方程:

$$ y^2 \equiv x^3+ax+b \pmod p (a,b \in F_p, 4a^3+27b^2 \not\equiv 0 \pmod p )$$

将加法如下定义:

如果点$ P(x_1,y_1), Q(x_2,y_2) $在曲线上, 经过两点的直线能唯一交于曲线上的第三个点$ R(x_3,y_3) $, 再对这个点做关于x轴的对称点即可得到$-R(x_3,-y_3)$(即定义取逆为做关于x轴的对称点), 即:

$$ P+Q=-R $$

我们稍微需要一点射影几何的知识, 考虑椭圆曲线在射影坐标$ [X:Y:Z] $, 在射影坐标中$ [X:Y:Z] $与$ [\lambda X:\lambda Y:\lambda Z] $等价, 或者说它们属于同一个等价类

当$Z \neq 0 $时, 此时射影坐标下的$ [X:Y:Z] $可以对应到坐标$ (\frac{X}{Z},\frac{Y}{Z}) $(此时对应的射影坐标为$ [\frac{X}{Z}:\frac{Y}{Z}:1] $)

下面我们将给出这种加法构成一个群的证明

其中封闭性, 交换律如下:

两点确定的直线与椭圆曲线的交点依旧在椭圆曲线上, 而曲线明显关于x轴对称, 所以对称操作也不会影响封闭性

交换两个点等价于一个求$P$和$Q$确定的直线, 另外一个求$Q$和$P$确定的直线, 这显然不会改变所确定的直线, 因而不会改变第三个点

单位元与逆元

对于单位元, 我们定义射影平面的无穷远点$\mathcal{O} $为单位元

当$ Z=0 $时, 此时在形式上对应一条直线, 我们将其对应为一条包括所有无穷远点的无穷远直线, 在在仿射平面上所有相互平行的直线, 都会在射影平面上相交于这条直线上的某一个点, 我们定义每个斜率均对应一个无穷远点, $X$为0时可以对应斜率无穷大(或者说垂直于x轴的情况), 由于在这种定义下的射影坐标 $ [X:Y:Z] $ 表示的是一个直线方向, $ (0,0,0) $无意义, 所以我们规定射影坐标不能全为0

借由射影坐标, 我们将方程

$$ y^2=x^3+ax+b $$

转化成射影方程(即代入$ x=\frac{X}{Z},y=\frac{Y}{Z} $), 此时有

$$ Y^2Z=X^3+aXZ^2+bZ^3 $$

当$Z=0$, 可以解得$X^3=0$, 此时可得$ [0:Y:0] $, 与$[0:1:0] $等价, 而射影坐标不能同为0, 所以这类椭圆曲线均交于相同的无穷远点$ \mathcal{O} $, 同时所有垂直于x轴的直线均经过这点

根据前面确定的加法法则, 当我们代入计算 $ P+ \mathcal{O} $ 时, 易得下列等式:

$$ P+ \mathcal{O} = P $$

而$P$的选取的任意的, 所以可以得到$\mathcal{O}$确实是其中的单位元

由前面的讨论也能知道关于x轴对称的两点也恰好经过 $ \mathcal{O} $ , 因而对称操作确实是满足逆元定义的

结合律

严谨证明需要使用到代数几何中的Chasles 定理的三次曲线特例, 我们会使用其主要思路给出一个简短的证明(可以自己简单手动画一下图), 并在最后附上基于线性代数的直观但不那么严谨的证明

  • 考虑如下直线:
    • $L1$:经过$P,Q,-(P+Q)$的直线
    • $L2$:经过$P+Q,R,-((P+Q)+R)$的直线
    • $L3$:经过$Q+R,-(Q+R),\mathcal{O}$的垂直直线
    • $M1$:经过$Q,R,-(Q+R)$的直线
    • $M2$:经过$Q+R,P,-(P+(Q+R))$的直线
    • $M3$:经过$P+Q,-(P+Q),\mathcal{O}$的垂直直线

并令$C_1$为$ L_1,L_2,L_3 $对应的直线方程相乘, $C_2$为$ M_1,M_2,M_3 $对应的直线方程相乘

此时检查上述直线与$C_1,C_2$, 发现$ C_1,C_2 $均为三次方程且均经过$ P,Q,R,P+Q,-(P+Q),Q+R,-(Q+R),\mathcal{O} $且这8个点均在椭圆曲线上, 则它们的第9个交点也必然在椭圆曲线上(由Chasles 定理的三次曲线特例), $C_1$与椭圆曲线的第9个交点为$ -((P+Q)+R) $, $C_2$与椭圆曲线的第9个交点为$ -(P+(Q+R)) $, 于是取对称点后结论得证

喜好计算的读者也可以使用方程联立然后直接一通爆算出它们的第9个点是一样的坐标, 或者参考下面的线性代数视角下的证明:

经过射影变换后, 任何一个三次曲线的方程都能写成一个齐次三次多项式:

$$ \begin{aligned} F(X,Y,Z) = & aX^3 + bY^3 + cZ^3 + dX^2Y + eX^2Z \\ & + fY^2X + gY^2Z + hZ^2X + iZ^2Y + jXYZ \end{aligned} $$

这一共有十个系数, 从而构成了一个十维的向量空间, 而只需要确定它们之间的比例就能确定一条曲线

每交于一个点便对应了一个线性约束, 交于八个点便对应八条约束, 于是所有经过这八个点的三次曲线构成了一个二维的线性子空间, 而$C_1, C_2$线性独立($C_1,C_2$对应的三次曲线分别记为$F_1,F_2$), 于是它们的线性组合

$$ \alpha F_1(X,Y,Z)+\beta F_2(X,Y,Z) $$

便能表示所有的经过这八个点的三次曲线$F_3$:

$$ F_3(X,Y,Z)=\alpha F_1(X,Y,Z)+\beta F_2(X,Y,Z) $$

考虑第九个点$P_9$, 这个点是$C_1, C_2$的交点, 此时有:

$$ F_1(P_9)=F_2(P_9)=0 $$

故:

$$ F_3(P_9)=\alpha F_1(P_9)+\beta F_2(P_9)=\alpha \cdot 0+\beta \cdot 0=0 $$

即:在射影平面上交于9个点的两个三次曲线, 如果第三条三次曲线经过了其中八个点, 那么它必然也经过第9个点, 从而完成整个的证明

加密与解密流程

Alice有密钥对$(d_A, Q_A)$, Bob有密钥对$(d_B, Q_B)$, 其中$ Q_A= d_AG, Q_B= d_BG $其中$d_A,d_B$是私钥

在发送时, 只需要传输$ Q_A, Q_B, G $即可

考虑加密过程, 通信双方需约定一组椭圆曲线域参数（Domain Parameters），通常记为 $T = (p, a, b, G, n, h)$：

  • $p$：定义有限域的素数。
  • $a, b$：椭圆曲线方程的系数。
  • $G$：基点（Generator Point），即曲线上的一个已知点。
  • $n$：基点 $G$ 的阶（Order），即满足 $nG = \mathcal{O}$ 的最小正整数。根据 Hasse 定理，$n$ 的大小与 $p$ 处于同一数量级。
  • $h$：余因子（Cofactor），$h = \frac{N}{n}$，其中 $N$ 是曲线上点的总数。通常选择 $h=1$ 的曲线（如 secp256k1）以避免小群攻击。

密钥生成：

  • 私钥（Private Key）：随机选择一个整数 $d \in[1, n-1]$。

  • 公钥（Public Key）：计算点 $Q = dG$。公钥是曲线上的一个坐标点 $(x, y)$。

  • Alice 的密钥对为 $(d_A, Q_A)$，Bob 的密钥对为 $(d_B, Q_B)$。

  • Alice 计算 $S_A = d_A \cdot Q_B = d_A \cdot (d_B \cdot G)$。

  • Bob 计算 $S_B = d_B \cdot Q_A = d_B \cdot (d_A \cdot G)$。

  • 根据标量乘法的交换律，$S_A = S_B = (d_A d_B)G$。双方提取该点的 $x$ 坐标作为共享密钥。窃听者仅知 $Q_A, Q_B, G$，受限于 ECDLP 无法求出 $d_A$ 或 $d_B$。

用于验证消息的完整性与发送方身份。假设要对消息哈希值 $z$ 进行签名。

  • 签名过程（由 Alice 使用私钥 $d_A$ 执行）：
    1. 随机选择临时密钥 $k \in [1, n-1]$。
    2. 计算点 $(x_1, y_1) = kG$。
    3. 计算 $r \equiv x_1 \pmod n$。若 $r=0$ 则重试。
    4. 计算 $s \equiv k^{-1}(z + r \cdot d_A) \pmod n$。若 $s=0$ 则重试。
    5. 签名结果为 $(r, s)$。
  • 验证过程（由接收方使用公钥 $Q_A$ 执行）：
    1. 计算 $w \equiv s^{-1} \pmod n$。
    2. 计算 $u_1 \equiv z \cdot w \pmod n$ 以及 $u_2 \equiv r \cdot w \pmod n$。
    3. 计算点 $(x_2, y_2) = u_1 G + u_2 Q_A$。
    4. 验证 $x_2 \equiv r \pmod n$ 是否成立。 (数学证明：$u_1 G + u_2 Q_A = (zw)G + (rw)d_A G = w(z + r d_A)G = s^{-1}(ks)G = kG = (x_1, y_1)$)