初识椭圆曲线密码学

##非对称加密

接触过密码学的人一定听说过大名鼎鼎的非对称加密算法RSA（不了解RSA的同学可以看看这篇文章非对称加密算法RSA）。RSA于1977年被三位数学家提出，它的诞生正式标志着现代密码学的开始，成功的解决了不安全信道中密钥交换的问题。直到今天RSA依然是非对称加密算法的主力。RSA算法原理简单，容易理解，实现起来也比较容易，因此被开发者广泛了解，很多人直接将非对称加密和RSA等同起来了。但是随着现代超级计算机算力的不断提升，RSA必须不断的使用更长的密钥才能保证安全性，这意味着RSA在普通计算机中加解密的性能将越来越低。长期来看，新的更加高效的算法取代RSA已经成为一个必然的趋势。

而新一代非对称加密算法椭圆曲线密码学也由此应运而生，它加密强度高，运算速度快，密钥更短等特点弥补了RSA的几个短板。作为RSA的替代品椭圆曲线密码学正在快速的崛起。

今天我们就介绍一下号称加密算法中最难懂，也是最强大的加密算法椭圆曲线密码学。

椭圆曲线密码学英文缩写ECC（Elliptic Cuver Cryptography）。作为后来者，在非对称加密算法中表现出了优异的性能，相比RSA它有更短的密钥，更高的安全强度，更快的计算速度。并且同样适用于密钥交换和验签。越来越多的大公司已经投入了ECC的怀抱。作为一个优秀的开发者，我们也应到跟上技术的革新，了解一下这个神秘而强大的加密算法。

椭圆曲线密码学涉及到群公论、离散对数问题、几何加法、数论、有限域等众多数学问题，异常晦涩难懂。但是作为一个正在被广泛使用的非对称加密算法，它值得我们花费时间和精力去了解。这里我将尽力以最小的篇幅让读者对ECC有一个基本的认识，要想探究ECC的详细原理可以看看前面几篇翻译的文章，有非常详细的原理讲解。

初识椭圆曲线

在椭圆曲线密码学中我们将下面等式上的所有点的集合称为椭圆曲线：
$y^{2}=x^{3}+ax+b$
注意：这个椭圆曲线和我们平常认为的椭圆没有任何关系，之所以叫椭圆曲线是数学上一个遗留的名称问题。
当 $a$ 和 $b$ 取确定的值时，这个等式所表示的图形大概如下：

记住这个图形，我们接下来要介绍的算法就是工作在这样一个图形上。
要想加解密，就得进行计算。我们定义椭圆曲线上新的加法规则：

当曲线上的点 $P,Q,R$ 在同一条直线上时， $P+Q+R=0$ 。
曲线上的任意点 $P$ 关于 $x$ 轴对称的点为 $-P$ ,则 $P+(-P)=0$ 。

由此我们可以得出 $P,Q,R$ 在同一条直线上时,其中两点的合等于第三个点关于 $x$ 轴对称的点。
这种基于图形定义的加法被称为几何加法（我们平常使用的加减乘除都是代数计算），ECC算法就是建立在几何运算上。
我们可以借助图形工具来计算 $P+Q$ 的值。

根据上图我们可以轻松得到: $P+Q=-R$ 。
这样我们就定义了一种全新的运算。但是这个运算现在还不完善！
过平面与椭圆曲线相交的直线并不一定都与曲线有三个交点，有可能只有两个交点，因此我们要改进一下我们新定义的几何运算：

规定无穷远的点为单位元 $0$ 。
规定任何点 $P+0=P$ 。
当 $P=-Q$ 时（此时直线与 $x$ 轴垂直，这两点关于 $x$ 轴对称），此时我们认为第三个交点在无穷远点 $0$ ， $0$ 点关于 $x$ 轴对称的点依然是 $0$ ,所以有 $P+Q=P+(-P)=0$ .
当 $P=Q$ 时（此时直线与曲线相切），此时有 $P+Q+R=P+P+R=0$ , $P+P=-R$ 。

我们还规定椭圆曲线上的乘法运算为： $2P=P+p,3P=2P+P$ …。

至此，我们已经有了椭圆曲线上的基本运算规则，下面我们是不是可以进行加密了？如果这样的话，椭圆曲线就不能称为最晦涩难懂的加密算法了，实际上椭圆曲线的加密运算并不是真正工作在我们看到的这个图形上，而是这个图形的变体：椭圆曲线有限域上的离散对数问题。

如果我继续深入到基于椭圆曲线的有限域上的离散对数问题，我相信很多人无法继续读下去了，这也违背了这篇文章的初衷：让大家对椭圆曲线有一个初步认识。因此，我打算先介绍一个简单版本的椭圆曲线密码学（和椭圆曲线有限域上的离散对数问题的基本原理一样，只不过一个是连续的，一个是离散的），然后再推到出实际使用的椭圆曲线域上的离散对数问题。

diffie-hellman密钥交换

在真正介绍椭圆曲线密码学之前我们先来看一个问题。
Alice和Bob想在一个不安全的信道中协商出一个数用作加密，他们这样做：

他们先协商一个确定的数 $x$ ，并确定用这个数作为后续协商的一个基数（这个数可以公开）。
Alice自己生成一个随机数 $a$ 并计算 $A=x^{a}$ ，然后将 $A$ 传给Bob。
Bob自己生成一个随机数 $b$ 并计算 $B=x^{b}$ ，然后将传给 $B$ Alice。
Alice和Bob拿到对方传给自己的数后分别计算， $B^{a}=(x^{b})^{a}=x^{ab}=m,A^{b}=(x^{a})^{b}=x^{ab}=m$

这样他们就得到了一个相等的书 $m$ ,如果中间人Charlie想要得到同样的 $m$ 就得在 $A$ 和 $x$ 已知的情况下计算出 $b$ ( $b$ 也要计算)。但是解决这个问题是非常“困难”的，这就是数学中难解的离散对数问题。利用离散对数难解的数学原理我们可以实现一个diffie-hellman密钥交换算法。

椭圆曲线密码学原理

而椭圆曲线问题是类似这个离散对数问题的，但其破解难度要大于离散对数问题。
下面我们进入真正的椭圆曲线密码学（当然还不是真正使用的椭圆曲线密码学）：
椭圆曲线密码学有两个应用算法ECDH和ECDSA，ECDH长被用作密钥交换，ECDSA用来验签。这篇文章中我们将以ECDH为例来讲椭圆曲线密码学的工作方式（ECDSA原理一样）。
当Alice和Bob要在一个不安全的信道中用ECDH协商一个数，他们这样做：

首先他们确定椭圆曲线等式中的参数 $a$ 和 $b$ ,然后选取一个椭圆曲线上的点 $G$ 作为密钥交换的基点（确定这些参数的方式很讲究的，一般我们只需要使用加密组建推荐的参数就行）。
Alice选取一个随机数 $m$ ，并计算 $M=mG$ ，然后将 $M$ 传给Bob。
Bob选取一个随机数 $n$ ，并计算 $N=nG$ ，然后将 $N$ 传给Alice。
Alice和Bob分别计算, $Nm=nGm=F,Mn=mGn=F$ .

这样他们就得到了一个相等的数 $F$ ,用这个数生成后续加密用的密钥。这样就用ECDH成功进行了一次密钥交换。

椭圆曲线密钥交换的安全性

从上面ECDH密钥协商过程中我们可以看到。总共有七个参数 $a,b,G,m,M,n,N$ 以及最后协商得到的 $F$ 。
中间人Charlie要想得到同样的 $F$ ,必须解决如下问题：

$F=mnG$ , $G$ 是已知的,必须计算出 $m,n$ 。
$M=mG,N=nG,G,M,N$ 都是已知的，只要解出这两个等式中的未知项就能破解ECDH

但是我们设计的几何运算中形如 $A=aG$ ,在 $A,G$ 已知的情况下（注意：这里 $A,G$ 都是曲线上的点， $a$ 是一个很大的随机数，计算是很简单的）计算 $a$ 是非常困难的，这是ECC安全性保障的核心！你可以想象，其实就是椭圆曲线上点 $G$ 进行 $a$ 次代数变换得到，究竟需要多少次变换得到，只能从第一次开始一次一次去试（不知道 $2G$ 的情况下就无法得到 $3G$ ），没有更快的算法

假如 $a=10^{100}$ ,找出 $a$ 要进行1亿亿亿亿亿亿亿亿亿亿次尝试！在可预见的未来，这个数量级是不可能被穷举的！

实际上破解RSA也是对大数分解的穷举，但是目前大数分解有一些穷举算法还是比较高效的，因此RSA密钥要足够长才能抵抗这种攻击。RSA和ECC的破解难度是：

分解大数<离散对数<椭圆曲线域上的离散对数。

因为ECC抽象程度高，破解困难，所以ECC可以用更短的密钥实现和很长的RSA密钥一样的安全等级（目前认为250位ECC密钥安全强度是大于RSA2048）。更短的密钥意味着更快的计算速度，所以ECC受到了各种大厂的青睐。

当然我们也很早就注意到ECC了，并且在移动端的基础应用中很多地方都用到了，并且在我们开发很多移动端安全组件中都用到了ECDH和ECDSA，实测性能远高于RSA。

至此，你已经基本了解了椭圆曲线加密算法的原理了，但是如果你不满足于此，想真正了解生产使用的椭圆曲线密码学，还得跟我继续深入探究！

椭圆曲线域上的离散对数问题

因为计算机算力有限，内存中保存的数字大小也是确定的，不能超出最大能表示的数。因此不管使用什么算法进行加解密，我们都必须确定这个算法参与计算的数的最大范围，所有数都不能超过这个最大值。椭圆曲线密码学也是一样的，它也要被限制在一个有限的域上进行运算（实际上这个域也是很大的，里面的点的数量也1亿亿亿亿亿亿亿亿亿亿级别的）。

下面我们将椭圆曲线上的点限制在有限域上，而不是整个实数集合。再次之前我们先介绍几个概念。

群

群是一种特殊的集合。

数学中的群是我们定一个二元运算的集合，这个运算用“+”表示。当这个集合满足如下四个性质时就构成了一个群：

封闭性：如果a和b是集合G中的元素，那么（a + b)也是集合G中的元素。
结合律：(a + b) + c = a + (b + c);
存在单位元0，使得a + 0 = 0 + a =a;
每个元素都有逆元，即：对于任意a，存在b，使得a + b = 0.

如果再满足第五个条件

交换律： a + b = b + a

那么这个群就成为一个阿贝尔群。

我们定义椭圆曲线上的群：
群中的元素是一条椭圆曲线上的点;

单位元为无穷远点0;
点 $P$ 的逆元是其关于 $x$ 轴的对称点;
加法，满足以下规则: 对于3个处在同一直线上的非零点 $P$ , $Q$ 和 $R$ , 它们的和 $P+Q+R=0$ .

这个群是整个实数域，有无限多个元素。

整数模P有限域

有限域就是一个包含有限个元素的集合，我们可以有很多种方式构造一个有限域。常用的方式是模数运算。

椭圆曲线就是用整数模P来构造一个有限域的（这里P是一个素数，因为只有P是素数时构造的有限域才关于乘法运算构成一个阿贝尔群）。

整数模P构造的有限域用𝔽p表示，其中共有P个元素0～P-1，除了关于“+”运算构成阿贝尔群，关于“⋅”运算也是阿贝尔群。即都满足封闭性,结合律,交换律.对这两种操作都存在唯一的单位元,并且域中每个元素都存在一个相反数（逆元）.最后满足乘法分配律: x⋅(y+z)=x⋅y+x⋅z。

例如我们取P=11时：

3 mod 11 = 3。
13 mod 11 =2。
5+6 mod 11 = 0，我们说5和6关于模数11互为加法逆元。
2*6 mod 11 = 1，我们说2和6关于模数11互为乘法逆元。

椭圆曲线域上的离散对数问题

了解了群和有限域我们就可以将椭圆曲线构成的群限制在有限域上。
当我们限制椭圆曲线在𝔽p上时，原来的椭圆曲线等式将变成如下同余式：
$y^{2}(mod P)=x^{3}+ax+b(mod P)$
或者简写成:
$y^{2}≡x^{2}+ax+b(mod P)$
此时椭圆曲线上的点不再是连续的。

上面是曲线 $y^{2}≡x^{3}-7x+10(mod P),P=19,97,127,487$ 时曲线上点的分布，注意对于每一个 $x$ 至多有两个点，并且关于 $y=p/2$ 对称。

椭圆曲线上的点变成离散的点后我们之前定义的加法规则依然不变：当曲线上的点 $P,Q,R$ 在同一条直线上时， $P+Q+R=0$ ，即其中一个点关于 $y=P/2$ 轴对称的点就是另外两个点的和。只不过这时对称轴由 $x$ 变成 $y=P/2$ 。

当我们限制曲线在𝔽127,此时平面的的直线将以如下形式和曲线相交:

由于直线也被限制在𝔽127上，所以直线在平面的轨迹是不断重复的（上图中黄色的线是同一条直线在模127的域上的轨迹）。可以看到红色 $R$ 的就是直线 $PQ$ 与椭圆曲线的第三个交点关于 $y=127/2$ 对称的点，也就是 $P+Q=R$ 。此时我们就可以实现一套和连续椭圆曲线一样的运算，只不过参与计算的点和计算结果都被限制在了𝔽127。

实际生产使用的椭圆曲线就是在运算在这样一个有限域的离散点集合上，这个域中点的数量大概在 $10^{100}$ 左右，在可预见的未来暴力破解对次没有威胁的！

在实际使用时还涉及到如何构造一个可靠的曲线，如果选取合适的域，怎样将几何运算转换为我们常用的代数运算（因为计算机只能进行代数运算），求解三次方程等实际问题。但是这些我们都可以不用了解。以上内容如果你能完全理解，就可以骄傲的说：我已经完全理解了最复杂的密码学算法，椭圆曲线密码学的原理！

初识椭圆曲线

diffie-hellman密钥交换

椭圆曲线密码学原理

椭圆曲线密钥交换的安全性

椭圆曲线域上的离散对数问题

群

整数模P有限域

椭圆曲线域上的离散对数问题

FEATURED TAGS

FRIENDS