区块链中的密码学（3）：椭圆曲线加密分析 - BlockAA/blockchain-courses GitHub Wiki
在目前密码学的非对称加密算法中，RSA算法依然是一种主流，但是随着比特币中对于一种之前不太流行的算法：椭圆加密算法（ECC）的成功应用后，这种算法得到了很大的关注和普及。有一种说法是中本聪不信任RSA算法，认为美国人在其中留有后门，而据斯诺登的爆料也确实如此。相较RSA，ECC不仅在某种程度上杜绝所谓留有后门的情况，而且加密性能/安全性都有提高。本文就带大家一窥ECC算法的天地。
鉴于ECC算法对数学知识要求比较高，不像RSA依赖于中学数学的水平，ECC用到了许多《近世代数基础》，《初等数论》的知识，本文将从一个密码学爱好者并区块链的角度，讲述一下ECC在区块链中的应用。
什么是椭圆曲线加密(ECC)？
椭圆曲线可以简单的理解为公式：
这是一个数学公式，它的理论基础要从平行线谈起。数学上人们认为的平行线永不相交，这在某种程度上是无法验证的，因为没有一个无限远处的概念，假设平行线在无限远处相交，这样的好处是所有的直接都有且只有一个焦点，那么基于这个事实，我们中学学过的笛卡尔平面直角坐标系可以映射出另外一个平面坐标系：
假设平面直角坐标系中有点A(x,y),我们定义 X= x/z,Y = y/z,Z=z;那么联立方程：aX+bY+c1Z =0； aX+bY+c2Z =0 可以计算出z=0；所以我们新的坐标系中的点可以表示为：（X：Y：0）；这是椭圆曲线建立的坐标系基础。
下面在看椭圆曲线的定义：数学把满足Weierstrass方程的曲线称为椭圆曲线
这个方程的曲线生成的图像有很多，基于文章的目的，这里指介绍形如：y2=x3+ax+b的公式，因为这种情况下的椭圆曲线才适合加密，例如y^2=x^3-10x+12的曲线如下：
感兴趣的读者可以去https://www.desmos.com/calculator/0mnue7w8lk 模拟一下，通过修改a，b的值观看曲线变化。需要注意的是并不是所有椭圆曲线都是关于X轴对称的。读者可以改变多改变a1的值来发现。
数学家在这个曲线上定义了一种椭圆曲线的加法，在上面定义的公式曲线图中：
显然这并不是传统的数学上的加法，运算法则：任意取椭圆曲线上两点P、Q （若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R，过R做y轴的平行线交于R’。我们规定P+Q=R’。所以很容易理解nP的值，就是P经过n次加法（对P做切线，取得另一个交点的关于X轴的对称点）。
椭圆曲线算法在比特币中的应用
比特币公钥加密中使用的椭圆曲线参数是依照secp256k1标准。在比特币流行之前很少有人使用过secp256k1，但现在由于它的几个不错的属性越来越受到欢迎。比特币官网这么讲到：
Most commonly-used curves have a random structure, but secp256k1 was constructed in a special non-random way which allows for especially efficient computation. As a result, it is often more than 30% faster than other curves if the implementation is sufficiently optimized。
secp256k1标准通过特别的算法，使得生成的曲线比别的曲线快30%。这在移动端等小型设备上是非常重要的。椭圆曲线中还有一个有限域Fp的概念，以素数p为模数的数的集合。它定义椭圆曲线中x，y的范围，同时它也有自己的加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。列如F23（p的值是23，要求p是素数），它是数据 0到22的集合，关于它的算法：
加法：(18 + 9)mod 23 = 4
减法：(7 - 14) mod 23 = 16
乘法：4 * 7 mod 23 = 5
加法逆元： x + 5 = 0 mod 23 => x= 18
乘法逆元： x *9 = 1 mod 23 => x= 18
所以对于比特币中的椭圆曲线算法，需要明确知道的是( p,a,b,G,n,h )。p是Fp的模的范围，比特币中定义的是：
- p=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
- = 2256-232-29-28-27-26-24-1
a，b是椭圆曲线的参数，分别是a=0，b=7。G是基点，可以理解为椭圆曲线中第一个点，列如前面的P。比特币中定义的点G 为
（02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798，483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8）
n 是基点G的可倍积阶数，定义为能够使得点倍积 nG不存在的最小的整数 n ，比特币中它的值为：
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h是一个整数常量，它跟椭圆曲线运算中得到点的集合以及 n 有关， h 一般取值为1。比特币中也是1。比特币中的椭圆曲线如下：
加密流程：以一个随机生成的私钥k为起点，我们将其与曲线上预定的生成点G相乘以获得曲线上的另一点，也就是相应的公钥 K。生成点是secp256k1标准的一部分，比特币密钥的生成点都是相同的：{K = k * G}。
这就是比特币中秘钥的生成过程，也就是比特币中安全性依赖的根本。
椭圆曲线算法安全性，现状，运用
目前椭圆曲线应用的范围越来越广，在BTC，ETH，EOS，莱特币，DASH等都有使用。密码学中把正向计算是很容易的，但若要有效的执行反向则很困难的算法叫做陷门函数。
在RSA的章节中已经介绍过，RSA会随着因式分解的数字变大而变得越有效率，对于私钥增长的需求决定了RSA并不能算作一个完美的陷门函数。事实证明在椭圆曲线中如果你有两个点，一个最初的点乘以K次到达最终点，在你只知道最终点时找到n和最初点是很难的，这就是一个非常棒的trapdoor函数的基础，最近三十年的研究，数学家还没有找到一个方法证实。
密码学家Lenstra引进了“全球安全（Global Security）”的概念：假设破解一个228字节的RSA秘钥需要的能量少于煮沸一勺水的能量。那么破解一个228字节的椭圆曲线秘钥需要煮沸地球上所有水的能量。如果RSA要达到一个同样的安全水平，你需要一个2,380字节的秘钥。就像前面文章中讲到的，ECC能够使用较小的资源而产生安全性较高的效果。
本文首发于blockgeek.org
BG论坛思考题
按照惯例，为大家随机挑选一条Blockgeek.org上的技术问题，有兴趣的同学可以挑战一下, 来吧, 别犹豫！
作者简介
Figo：Blockgeek.org 签约技术作者，区块链重度爱好者。热衷于区块链技术推广，参与hyperledger fabric中文社区翻译，对以太坊，EOS，HPB,星云等各大公链有深入研究。