椭圆曲线密码学简介

引言

本文简单介绍椭圆曲线密码学的基本内容，目标是直观、简化，忽略严谨性。切记，简单是为了导向严肃而不是庸俗。

阅读以下内容，在有群论与密码学的基础上，大概需要1个小时。如果没有密码学基础，可忽略密码学，而重点关注椭圆曲线的定义与相关计算。建议安装SageMath，在阅读过程中尝试运行相关代码，以助理解。

什么是椭圆曲线？

忽略严谨性，简单而言，

所谓椭圆曲线就是满足以下方程的点(即序对$(x,y)$)形成的集合。 \[y^2 = x^3 + ax + b\]

其中，要求 $\Delta = 4a^3 + 27b^2 \ne 0$，暂时不解释，大家先接受并记得这个常量。如果$a$和$b$是实数，则$x$和$y$自然是实数。让我们看看这样的点形成什么样的曲线。

1
2
3

sage: a = -5; b = 4
sage: E1 = EllipticCurve(RR, [a, b])
sage: show(plot(E1, hue=.9))

如果改变$a$和$b$的值，可以得到其他的曲线，比如：

1
2
3

sage: a = 2; b = 3
sage: E2 = EllipticCurve(RR, [a, b])
sage: show(plot(E2, hue=.9))

还可以选取随机的$a$和$b$，去看看曲线长什么样。比如我们完全无法预测以下曲线的模样：

1 2	sage: E3 = EllipticCurve(RR,[RR.random_element(), RR.random_element()]) sage: show(plot(E3, hue=.9))

通过以上的图，我们得到了对椭圆曲线的第一印象：长得很不椭圆。有一点可能大家已经注意到：曲线沿$X$轴对称。

但是，这些曲线还不是我们最关心的，我们更关心的是，如果$a$和$b$落在有限域$F$上的情形。本文主要考虑的有限域是素域$F_p$，$p$是素数。因为我大部分的学生对有限域的概念比较陌生，而恰巧他们都精通 略微了解有限群。于是，我这样说，设$a, b \in Z_p^*$，$p$是一个素数。有限域$F_p$比$Z_p^*$多了一个加法($Z_p$是加法群啊！)和$0$元，仅此而已，不要慌！其实是我很慌......

比如，我们运行以下代码。

sage: p = 137 #p是一个素数
sage: F = GF(p) #一种有限域，也可以用 F = FiniteField(p)命令
sage: E137 = EllipticCurve(F, [F.random_element(), F.random_element()])
sage: show(plot(E137, hue=.9))

这幅图告诉我们，原来椭圆曲线所谓的“曲线”既不“曲”，也不成线，而是离散点的集合。到底有多少个点呢？这是椭圆曲线研究关心的大问题。对我们而言，只需要知道以上曲线大概的点数即可。可以使用以下命令。

1	sage: E137.points()

椭圆曲线群及其基本运算

看到这里，你至少知道椭圆曲线就是一堆”乱七八糟“点的集合，这有什么用呢？暂时还没什么用，直到我们说，椭圆曲线上的点在加法上成群。首先，我们再一次给出椭圆曲线的定义。

$\mathbb{F}$为有限域，设 $a, b \in \mathbb{F}$为常数，它们使得 $\Delta = 4a^3 + 27b^2 \ne 0$。非奇异椭圆曲线 $E$ 是满足方程 $y^2 = x^3 + ax + b$上的解集合 $\{(x, y) \in \mathbb{F} \times \mathbb{F}\}$ 加上一个称为”无穷远点“的特殊点 $\mathcal{O}$ ，并且$E$在加法上形成交换群。

所谓无穷远点$\mathcal{O}$就是加法的单位元。这里的内涵比较丰富，暂时可以不管。我们迫切要做的是把点的加法定义出来。在定义前，先规定一些表示法。$P,Q \in E$表示曲线$E$上的两个点，注意，点是一个序对$(x,y)$。所谓加法（群上点的加法）就是给定$P$和$Q$求$R$，使得$R = P + Q$。加法有两种情形。

加法1：P != Q

如图所示，给定不同的点$P$和$Q$，作$P$和$Q$的连线，该线与$E$相交于某个点，把这个点沿$X$轴翻转就得到了点$R$。这个$R = P + Q$。

具体到数值计算，设 $P = (x_1, y_1)$和 $Q = (x_2, y_2)$， $R = (x_3, y_3)$，则

计算连线$L$的斜率$\lambda = (y_2 – y_1) / (x_2 – x_1)$ 。$L$可记为： \[y = \lambda(x - x_1) + y_1;\]
求$L$ 与 $E$ 相交的另一个点：将$L$的方程(用斜率$\lambda$与$x$表达的$y$)代入椭圆曲线方程： \[(\lambda(x - x_1) + y_1)^2 = x^3 + ax + b,\] 整理可得： \[0 = x^3 - \lambda^2 x^2 + \cdots ;\]
因为以上方程是一个三次方程，它有三个不同的根，所以， \[ x^3 + \lambda^2 x^2 + \cdots = (x - x_1)(x - x_2)(x - x_3 ) = x^3 - (x_1 + x_2 + x_3) x^2 + \cdots = 0 \]
因此，可得：$x_3 = \lambda^2 - x_1 - x_2$，进而可得$y_3 = \lambda(x_1 - x_3) - y_1$。注意，这里已经做了值的翻转！

注意，三次方程就一定有三个不同的根，难道不能是重根吗？很希望大家能问这个问题，只是因为我的学生基本都知道原因，所以上课从来没人问，所以我上课也从来都不解释，以至于我也差不多要忘记了：三次方程的判别式 $\Delta=4a^3 + 27b^2 \ne 0$ 已经确保了重根不会出现。

加法2：P == Q

如图所示，此时，只给定了一个点$P$，我们要计算$R = P + P$。

首先，沿点$P$作曲线的切线，与$E$相交于某点，然后沿$X$轴翻转该点就得到$R$。具体计算如下：

$\lambda = (3x_1^2 + a) / 2y_1$
$ x_3 = ^2 - 2x_1$, $y_3 = \lambda(x_1 – x_3) - y_1$

具体推导与解释就不再展开，鼓励大家自己先推导，也可参考相关教科书。

无穷远点到底是什么？

我们知道$\mathcal{O}$是群的单位元，也就是说$P + Q = \mathcal{O}$，如果$P$与$Q$互为逆元。而$P$与$Q$互为逆元意味着，它们曲线上是沿$X$轴对称的两个点，那么它们的连线永远是垂直于$X$轴的线。与$X$轴垂直的线与曲线在哪里还能相交出一个点呢？理论上就只能在无穷远的地方。直观上，$\mathcal{O}$就代表所有垂直于$X$轴的线在曲线上的交点。

椭圆曲线群满足的属性

最简单来说，因为$E$是交换群，它必然满足所有的群公理：

单位元：$P + \mathcal{O} = \mathcal{O} + P = P$;
逆元：$P + (-P) = \mathcal{O}$, 其中 $P = (x, y)$, $-P = (x, -y)$;
结合律：$P + (Q + R) = (P + Q) + R$;
交换律：$P + Q = Q + P$;

在有限域$\mathbb{F}$上的椭圆曲线

不知道讲到这里大家是否会提出这样的异议：没错，如果椭圆曲线是在实数域上$\mathbb{R}$，以上推导基本没什么问题，但是我们知道，如果椭圆曲线落在$\mathbb{F}$上，曲线是离散点的集合，那么做连线、切线、求斜率等等，这一系列我们都做不到啊！？

答案是，说得没错，这一系列几何意义确实很难体现。但是，不要忘记，所有的域都可以做加减乘除运算。只需要把所有相关操作“平移”到域上即可！

试举一个曲线$E_{137}$的例子。设$a = 3$，$b=4$，曲线方程是：$y^2 = x^3 + 3x + 4b$，给定两个点$P = (x_1=18,y_1=100)$，$Q=(x_2=20,y_2=114)$，求$R = P + Q$。

解法如下：

求$\lambda = (y_2 – y_1) / (x_2 – x_1) = (114 - 100)/(20 - 18) = 7$。
$x_3 = \lambda^2 - x_1 - x_2 = 7^2 - 18 - 20 = 11$
$y_3 = \lambda(x_1 - x_3) - y_1 = 7(18-11) - 100 = 86$ ；注意，所有加减乘除都是域上运算！

所以，$R =(x_3,y_3)=(11, 86)$。大家可以通过SageMath进行验证：

sage: p = 137
sage: F = GF(p)
sage: E137 = EllipticCurve(F, [3,4])
sage: P = E137(18,100)
sage: Q = E137(20,114)
sage: R = P + Q; R