非对称加密算法，区别于对称加密算法，加解密需要两个密钥，分别是公钥和私钥。公钥是公开的，私钥是保持私有的。

非对称加密算法的原理，私钥生成公钥很容易，由公钥反推私钥则很难。

RSA算法，作为非对称加密算法之一，它把公钥反推私钥的过程等价于一个数学难题——极大整数的因式分解，一定程度上保证了RSA算法的安全性。

RSA算法的复杂性取决于因式分解的难度，数字越大因式分解越难，随着计算机的算法、运算的进步，大数字因式分解的难度正在随着数字变大而缩小。

所以这意味着RSA算法对未来的密码学来说并不是理想的加密系统，我们需要一个更好的加密系统。

今天我们将学习椭圆曲线加密算法。

椭圆曲线加密算法 （Elliptic curve cryptography，缩写为 ECC），1985年由Neal Koblitz和Victor Miller分别独立提出。

那到底什么是椭圆曲线算法呢？

让人失望的是，椭圆曲线不像因式分解是那种我们初中就学过的知识，可以说大多数人对椭圆曲线函数的知识并不熟悉。

这部分的内容并不简单，也没那么容易理解，接下来，我尽量避免罗列公式，用通俗易懂的语言介绍下椭圆曲线。

（学霸轻喷，学酥请绕行，如果你阅读过程中身体稍有不适，请直接跳到文章末尾结论处。）

上节在讲RSA算法的时候，我们提到一个数学概念——单向函数，就是正向计算很容易，反向计算很难的函数。

而RSA算法的单向函数体现在计算乘法很容易，因式分解则是一道数学难题。

那么椭圆曲线的算法的单向函数是什么呢？

首先我们来看看椭圆曲线方程组，y^2=x^3+a^x+b，有点抽象，我们来看看它长什么样子:

这两种曲线都是椭圆曲线，可以说是孪生兄弟，根据参数a、b的不同，所以样子上有点区别。

你会发现，右边的曲线跟欧米伽特别像。

我们仔细看椭圆曲线，它有着一个非常有趣的特性，就是任何不垂直的直线穿过曲线最多有三个交点。

还有一个特性，曲线上任一点做X轴对称后得到的点仍然在椭圆曲线上。为了避免出现大部分公式，笔者尽量用图片来解释椭圆曲线算法。

曲线上任意两点的连线延长做一条直线，这条直线与曲线有一个交点，根据椭圆曲线的对称性，我们做这个交点的x轴对称，得一个新的点，该点仍在曲线上。

这个过程，我们叫打点，即dot。我们来看上图，A dot B得到的是C点。（很多文献把这个过程定义成椭圆曲线的加法）

我们持续这一过程反复

A dot B=C

A dot C=D

A dot D=E

……

重复这一过程，我们来看看结果，我们发现了一些特性，如果图像无限大的话，打点这一过程可以一直持续。

也就是说，我们可一直打点，我们假设进行了无数次的打点，并得到其中一点G，如果我们只知道G和A，那么G点是A打点几次得出的？我想这是一个很难的数学问题。

结论

在给定起始点A和终点G的情况下，我们想找出打点次数n的值是很困难的。正推容易，反推很难，这就是ECC算法的单向函数，也是ECC算法的数学基础。

我们再来看看ECC算法的加密过程：

1. 小倩选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

2. 小倩选择一个私有密钥k，并生成公开密钥K=kG。（这一步既是上文提到的打点过程）

3. 小倩将Ep(a,b)和点K，G传给小高。

4. 小高接到信息后，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n）。

5. 小高计算点C1=M+rK；C2=rG。

6. 小高将C1、C2传给小倩。

7. 小倩接到信息后，计算C1-kC2，结果就是点M。因为

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

然后再对点M进行解码就可以得到明文。

在这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、K、G、C1、C2， 而通过K、G 求k 或通过C2、G求r 都是相对困难的，原因上文已经提到。

因此，H无法得到A、B间传送的明文信息。

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线密码（ECC）对数字签名算法（DSA）的模拟。

ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。

与普通的离散对数问题（discrete logarithm problem  DLP）和大数分解问题（integer factorization problem  IFP）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem ECDLP）没有亚指数时间的解决方法。

秘钥强度

因此椭圆曲线密码的单位比特强度要高于其他公钥体制。

椭圆曲线离散对数算法是基于ECC最难的问题。

即便最近30年的研究，数学家任然没有找到一个能够解决这个问题的改进方法。

也就是说，和因式分解不同，基于当前已知的数学方法，找不到可以缩小该单向函数的正反计算难度差值的办法。

这意味着对于许多同样位数长度的数字，解决椭圆曲线离散对数问题要比因式分解困难的多。

因为一个算法的计算空间越密集意味着一个密码系统越强大，所以椭圆曲线密码学系统比RSA和Diffie-Hellman更加难以攻破。

为了理解这到底有多难被攻破，Lenstra最近提出了“全球安全（Global Security）”的概念。

你可以计算攻破一个（椭圆曲线）密码学算法需要多少能量和计算该能量能煮沸多少水进行对比。

这是一种密码学的碳排放量的衡量。

通过这样的测量方法，破解一个228字节的RSA秘钥所需能量少于煮沸一勺水的能量。

相对地，破解一个228字节的椭圆曲线秘钥所需能量足够煮沸地球上所以水。

而RSA要达到这样的安全强度，需要2,380个字节的秘钥长度。 

使用ECC，你可以用更简短的秘钥获得相同的安全强度。

简短秘钥是非常重要的，尤其是在现实中密码学算法越来越多的运行在小功率设备里，例如手机。

尽管两质数相乘比把结果因式分解要简单，但当质数变得非常大，在低功率设备上仅仅只是乘法步骤都将花费很长一段时间来计算。

虽然可以通过增加秘钥长度来保持RSA的安全性，但却是以牺牲客户端的性能为代价。

相对于RSA，ECC提供了一个较好的选择：使用简短并且快速的秘钥来达到高安全性。而破解ECC秘钥你至少需要250万年。

文章原标题：侯震：ECC算法——安全快捷，再也不担心私房钱被发现了  原作者：侯震