1椭圆曲线密码学：简介

原文链接：https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

你们中知道公钥密码学的人可能已经听说过ECC, ECDH或ECDSA。第一个是椭圆曲线密码学（Elliptic Curve Cryptography）的首字母缩写，其他两个是基于它的算法的名称。

今天，我们可以在TLS、PGP和SSH中找到椭圆曲线密码系统，这只是现代网络和IT世界所基于的三种主要技术之一，更不用说比特币和其他加密货币了。

在ECC流行之前，几乎所有的公钥算法都是基于RSA、DSA和DH等（基于模块化算法的可选加密系统）。RSA及其友类算法在今天仍然非常重要，并且经常和ECC一起使用。然而，虽然RSA及其友类算法背后的魔力（原理）可以很容易解释，被广泛理解，粗略的代码实现也可以很容易地编写，但是ECC的实现基础对大多数人来说仍然是一个谜。

本文将通过一系列的博客文章介绍椭圆曲线密码学的世界。本文的目标不是提供一个完整详细的ECC指南(网上有很多关于这个方面的信息)，而是提供一个简单的“ECC是什么”和“为什么它被认为是安全”的概述，而不是浪费时间在冗长的数学证明或枯燥的实现细节。我还将提供一些有用的示例，以及可视化交互工具和脚本。

具体来说，以下是我将涉及的主题:

实数域上的椭圆曲线和群公理(包括在这篇博客中)
有限域上的椭圆曲线与离散对数问题
密钥对的生成和两种ECC算法:ECDH和ECDSA
破坏ECC安全性的算法，并与RSA进行比较

为了理解这里所写的内容，您需要了解集合论、几何和模运算的一些基本知识，并熟悉对称和非对称密码学。最后，您需要清楚地知道什么是“易解”问题，什么是“难解”问题，以及它们在密码学中的作用。

准备好了吗？开始！

椭圆曲线

首先，什么是椭圆曲线？Wolfram数学世界给出了一个优秀而完整的定义。但针对我们的学习目标，椭圆曲线将简化为由下面这个等式描述的点集：

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

其中 $4a^{3}+27b^{2}\neq 0$ （这是为了排除奇异曲线）。上面的等式就是所谓的椭圆曲线的维尔斯特拉斯范式（Weierstrass normal form）。

图 1 不同形状的椭圆曲线（b=1,a的取值从2到-3）

图 2 两种不是有效的椭圆曲线。奇点的类型:左图，一条带尖角的曲线（y²=x³）右图，具有自交叉的曲线（y²=x³-3x+2）

根据a和b的值，椭圆曲线在平面上可能呈现不同的形状。这是很容易看出和证实的，椭圆曲线是关于x轴对称的。

对于我们的目标，我们还需要一个无穷远处的点(也称为理想点)作为椭圆曲线的一部分。从现在起，我们将用符号0表示无穷远处的点。

如果我们想显式地考虑无穷远处的点，我们可以按如下的方式细化椭圆曲线的定义:

$\left \{ (x,y)\in \mathbb{R}^{2}|y^{2}=x^{3}+ax+b,4a^{3}+27b^{2}\neq 0 \right \}\cup \left \{ 0 \right \}$

群

在数学中，群是我们定义的二元运算（我们称之为“加法”，并用符号+表示）的集合。为了使集合 $\mathbb{G}$ 成为一个群，加法的定义必须符合以下四个性质:

　　　1.封闭性：如果a和b都是集合 $\mathbb{G}$ 中的元素，则（a+b）也是集合 $\mathbb{G}$ 中的元素

　　　2.结合性： $\left ( a+b \right )+c=a+\left ( b+c \right )$

　　　3.单位元：存在单位元0使得 $a+0=0+a=a$

　　　4.逆元：每个元素都有逆元，即，针对任意一个a，都存在b使得a+b=0

如果我们增加第五个要求:

　　　5.交换性：a+b=b+a

那么这个群就叫做阿贝尔群（abelian group）。

根据通常的加法概念，整数的集合 $\mathbb{Z}$ 就是一个群(而且，它是一个阿贝尔群)。然而，自然数的集合 $\mathbb{N}$ 不是一个群，因为它不能满足第四个性质（自然数集是全体非负整数组成的集合，常用 N 来表示。自然数有无穷无尽的个数。）。

群很nice，因为如果我们能证明这四个性质是成立的，我们就可以免费获得其他一些性质。例如:单位元是唯一的；逆元也是唯一的，即对于每个a，有且只有一个b使得a+b=0(我们可以把b写成-a)无论是直接的还是间接的，这些和其他关于群的性质将对我们以后的学习非常重要。

椭圆曲线的群公理

我们可以在椭圆曲线上定义一个群。具体地说:

群的元素是一条椭圆曲线上的点;
单位元0是无穷处的点;
点P的逆元是关于x轴的对称点;
加法，由以下规则给出:给定三个处在同一直线上的非零点P，Q和R，它们的和P+Q+R=0。

Three aligned points

图 3 同一直线上的三点之和等于0

注意，对于最后一条规则，我们只需要三个点在同一条直线上，并且与点的次序无关。这意味着，如果P,Q和R三点在一条直线上，则 $P+(Q+R)=Q+(P+R)=R+(P+Q)=...=0$ 。这样，我们直观地证明了“+”运算既具有结合性又具有交换性。我们创建了一个阿贝尔群。

到目前为止，一切都很好。但是我们如何计算任意两点的和呢?

几何加法

由于我们使用的是一个阿贝尔群，我们可以把 $P+Q+R=0$ 写作 $P+Q+R=0$ 。等式的这一形式，让我们导出一个几何方法来计算P和Q两点之间的和：如果我们过P和Q两点画一条直线，这条直线将与椭圆曲线上的第三个点R相交（也就是说P,Q和R三点在同一条直线上）。如果对点R求逆得-R，就可以得到P+Q的和。

图 4 过P和Q画线得点R。R的逆则是P+Q的和

这种几何方法是可行的，但需要一些改进。我们尤其需要回答几个问题:

（1）当P=0或Q=0怎么办？显然，我们不能画出这样的直线（0不在xy平面上）。但是已知我们定义了0作为单位元，对任意P和Q都存在P+0=P、0+Q=Q。
（2）当P=-Q怎么办？这种情况下，经过两点的直线是垂直的，不与第三点相交。但是从逆的定义讲，如果P是Q的逆，则P+Q=P+(-P)=0。
（3）当P=Q怎么办？这种情况下，有无数条直线经过这个点P。事情开始变得有点复杂了。但是考虑一个点Q'≠P，使Q'靠近P，越来越靠近P会怎么样？

图 5 当这两点靠得越来越近时，经过它们的直线就与曲线相切

　　　　　当Q‘趋近P时，过P和Q’的直线与曲线相切。根据这一点我们可以这样说P+P=-R，其中R是过P点切线与椭圆曲线的交点。

（4）当P≠Q，但没有第三点R怎么办？我们的情况与前一个非常相似。实际上，在这种情况下，通过P和Q的直线与曲线相切。假设P是切点，在之前的例子中，我们会写P+P=-Q。等式现在写成P+Q=-P。另一方面，如果Q是切点，正确的方程应该是P+Q=-Q。

图 6 如果直线与椭圆曲线只有两个交点，那么该直线为曲线的切线。容易看出两点相加的结果是其中一个点的对称点

几何方法现在是完整的，并且涵盖了所有的情况。用铅笔和尺子，我们就可以对任意椭圆曲线上的每一点进行加法运算。如果你想尝试一下，可以看看我为计算椭圆曲线上的和而构建的HTML5/JavaScript可视化工具!

代数加法

如果我们想把点的加法运算交给计算机来完成，便需要把几何方法转化为代数方法。将上述的规则转换成一组公式，可能看起来很简单，但实际上它可能非常乏味繁琐，因为它需要求解三次方程。因此，这里我将只报告结果。

首先，让我们去掉最烦人的边角情况。已知P+(-P)=0且P+0=0+P=P。因此，在我们公式中，我们将避免这两种情况，我们只考虑非零、非对称的点 $P=(x_{P},x_{P})$ 和 $Q=(x_{Q},x_{Q})$ 。

如果P和Q不相同 $(x_{P}\neq x_{Q})$ ，过这两点的直线斜率为：

$m=\frac{y_{P}-y_{Q}}{x_{P}-y_{Q}}$

这条直线与椭圆曲线的交点是第三点 $R=(x_{R},y_{R})$ ：

$x_{R}=m^{2}-x_{P}-x_{Q}$

$y_{R}=y_{P}+m(x_{R}-x_{P})$

或写成：

$y_{R}=y_{Q}+m(x_{R}-x_{Q})$

因此 $(x_{P},y_{P})+(x_{Q},y_{Q})=(x_{R},-y_{R})$ （注意正负号并记住P+Q=-R）。

如果我们想检查这个结果是否正确，我们必须检查点R是否在曲线上，同时P, Q和R是否在一条直线上。检查点是否共线是很琐碎的，检查R是否属于曲线则容易些，因为我们需要解一个三次方程，这一点都不有趣。

相反，让我们使用一个例子:根据我们的可视化工具，给定椭圆曲线 $y^{2}=x^{3}-7x+10$ 以及P=(1,2)和Q(3,4)，P和Q的和P+Q=-R=(-3,2)。让我们看看我们的方程是否一致：

$m=\frac{y_{P}-y_{Q}}{x_{P}-x_{Q}}=\frac{2-4}{1-3}=1$

$x_{R}=m^{2}-x_{P}-x_{Q}=1^{2}-1-3=-3$

$\begin{equation} \begin{aligned} {\color{Black} y_{R}}&{\color{Black} =y_{P}+m(x_{R}-x_{P})=2+1\cdot (-3-1)=-2}\\&{\color{Black} =y_{Q}+m(x_{R}-x_{Q})=4+1\cdot (-3-3)=-2} \end{aligned} \end{equation}$

是的，这是正确的!

注意，即使P或Q中的一个点是切线点，这些等式也能成立。

让我们试一下P=(-1,4)和Q=（1,2）

$m=\frac{y_{P}-y_{Q}}{x_{P}-x_{Q}}=\frac{4-2}{-1-1}=-1$

$x_{R}=m^{2}-x_{P}-x_{Q}=(-1)^{2}-(-1)-1=1$

$\begin{equation} \begin{aligned} {\color{Black} y_{R}}&{\color{Black} =y_{P}+m(x_{R}-x_{P})=4+(-1)\cdot (1-(-1))=2}\\&{\color{Black} =y_{Q}+m(x_{R}-x_{Q})=2+(-1)\cdot (1-1)=2} \end{aligned} \end{equation}$

我们得到的结果P+Q=(1,-2)，与可视化工具给出的结果相同。

P=Q的情况需要区别对待：等式中x_R和y_R是相同的，但由于x_P=x_Q，我们必须用不同的公式来求斜率:

$m=\frac{3x_{P}^{2}+a}{2y_{P}}$

注意，正如我们所期望的，m的表达式实际上是下面这个函数的一阶导数：

$y_{P}=\pm \sqrt{x_{P}^{3}+ax_{P}+b}$

为了证明这一结果的正确性，只需检验R在曲线上且过P和R的直线与曲线只有两个交点即可。但是，我们并没有证明这个事实，而是举个例子:P=Q=（1,2）

$m=\frac{3x_{P}^{2}+a}{2y_{P}}=\frac{3\cdot 1^{2}-7}{2\cdot 2}=-1$

$x_{R}=m^{2}-x_{P}-x_{Q}=(-1)^{2}-1-1=-1$

$y_{R}=y_{P}+m(x_{R}-x_{P})=2+(-1)\cdot (-1-1)=4$

公式计算出P+P=-R=(-1,-4)。正确！

虽然推导过程非常繁琐，但我们的方程非常简洁。这多亏了维尔斯特拉斯范式：没有它，这些方程可能会非常长和复杂!

标量乘法

除加法外，还可以定义另一种运算：标量乘法，即：

$nP=\underbrace{P+P+...+P}_{n\ times}$

其中n是一个自然数。我也写了一个标量乘法的可视化工具，如果你想玩的话。

这样写的话，计算nP似乎需要n次加法。如果n有k个二进制数字，那么该算法的时间复杂度为 $O(2^{k})$ ，这不是很好。但也有更快的算法。

其中之一是"加倍（double）和相加（add）"算法。通过实例可以更好地说明其运算原理。设n=151。它的二进制表示是100010111₂。这种二进制表示可以转化为2的幂的和：

$\begin{equation} \begin{aligned} {\color{Black}151}& {\color{Black}=1\cdot 2^{7}+0\cdot 2^{6}+0\cdot 2^{5}+1\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}} \\& {\color{Black}=2^{7}+2^{4}+2^{2}+2^{1}+2^{0}} \end{aligned} \end{equation}$

(我们把每个二进制数n都乘以2的幂。)

鉴于此，我们可以这样写：

$151\cdot P=2^{7}P+2^{4}P+2^{2}P+2^{1}P+2^{0}P$

"加倍（double）和相加（add）"算法需要做的是:

取P

加倍，得2P

2P与P相加（为了得到2¹P+2⁰P）

加倍2P，得到2²P

与前一结果相加（得2²P+2¹P+2⁰P）

加倍2²P，得到2³P

对2³P不做任何操作

加倍2³P，得2⁴P

与前一结果相加（得2⁴P+2²P+2¹P+2⁰P）

……

最后，我们可以计算151·P，只需7次“加倍”和4次“相加”运算

如果还不够清楚，这里有一个实现该算法的python代码段：

如果“加倍”和“相加”操作复杂度均为O（1），那么，该算法的时间复杂度为O（log_n）（如果我们考虑的是二进制的长度，时间复杂度或是O（k）），这相当不错。比最初O（n）的算法要好得多

对数

给定n和P，我们现在至少有一个多项式时间算法来计算Q=nP。但反过来呢，逆运算需要计算多少轮呢?如果我们已知P和Q，需要求解n呢?这一问题被称为对数问题。我们称之为“对数”，而不是“除法”，这是为了与其他加密系统保持一致（那些系统中，不称为“乘法”，而称为“幂”）。

我不知道任何关于对数问题的“易解”算法，但通过接触乘法很容易看到一些模式。例如，取曲线y²=x³-3x+1和点P=(0,1)。我们可以立即证明，如果n是奇数，则nP在左半平面的曲线上；如果是n是偶数，则nP在右半平面上的曲线上。如果我们做更多的实验，我们可能会找到更多的模式，最终可以引导我们编写一个算法来有效地计算那条曲线上的对数问题。

但是对数问题还有一种变体：离散对数问题。正如我们将在下一篇文章中看到的，如果我们减少椭圆曲线的域，标量乘法仍然是“易解的”，而离散对数变成了一个“难解”问题。这种双重性是椭圆曲线密码学的关键。

下周见

今天的全部内容就到这里啦，希望你喜欢这篇文章!下周我们将会发现有限域和离散对数问题，以及一些例子和工具。如果你对这篇文章感兴趣，请继续关注!

Read the next post of the series »