非对称加密与椭圆曲线

易衡知行 2017-09-29

展开全文

加密一直是通信领域的重要话题，我们经常听说各类算法，什么对称加密，非对称加密等等这类名词，云山雾绕，不得所以，经过这段时间的了解，接下来让我用九浅一深的语言，解释这个听上去深不可测，其实更是一头雾水的概念。
要解释加密技术，首先就要了解一下什么是对称加密。

对称加密

维基百科的解释如下：

对称密钥加密（英语：Symmetric-keyalgorithm）又称为对称加密、私钥加密、共享密钥加密，是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥，或是使用两个可以简单地相互推算的密钥。实务上，这组密钥成为在两个或多个成员间的共同秘密，以便维持专属的通讯联系。与公开密钥加密相比，要求双方取得相同的密钥是对称密钥加密的主要缺点之一。

上面这段话看上去太抽象，不好理解，举个例子，假如把A-Z的26个字母，用某种方式替换成另一套符号，比如，就把A替换成01，B替换成02，C替换成03，以依此类推Z替换成26，那么当我要写一个单词happy的时候，就成了0801161625，以上这串数字虽然看上去不明所以，但因为明文和密电文之间是一一对应关系的，A永远对应1，Z永远对应26，这种加密与解密一一对应的加密方式，就叫做对称加密。

对称加密的缺点是，看似复杂，实则破解难度不高，虽然以上数字0801161625，看着不明觉厉，但因为语言书写总有一定的规律性，比如对于英文，字母e的出现频率远高于其他字母，而z的出现频率又远低于其他字母，所以，只要有足够的样本，通过比对和暴力破解，就不难找出明文和密电码的对应关系，即使不用数字，而使用某些特殊字符代替，甚至是图片，也一样容易破解。

比如，《福尔摩斯探案集》里，有一章《跳舞小人符号案件》就是一种对称加密技术：

福尔摩斯看到画有小人的纸条后，是真么分析的：

交给我的第一张纸条很短，我只有把我断定，其中一个符号代表E，大家都知道，英文中字母E最常用，即使在短句中，它的出现频率也最高。第一张纸条上有15个符号，其中四个完全一样，因此有理由认为这个符号代表E。这些图形中，有的带一面小旗，有的没有，从小旗的分布来看，带旗的图形可能代表了单词之间的空格。

有网友总结过跳舞小人代表的26个字母，典型的对称加密。

摘自《福尔摩斯探案全集》之《跳舞小人符号案件》

所以，对称加密可以写成以下形式

明文 <-> 密钥 <-> 密文

常见的对称加密算法有DES、3DES、AES、Blowfish、IDEA、RC5、RC6。

好了，既然对称加密安全性不高，于是人们开始寻找一种更安全，更不容易被破解的加密技术—非对称加密。

非对称加密

非对称加密，简单来说就是“在已知x的情况下，通过算法很容易求得y，但是知道了y，反过来求x却非常非常的困难”。

举个最最简单的例子，公式：y=3x^3 2x^2-1，假设x=1，然后你马上算出y=4。

那现在y=1的时候，x等于多少呢，开始掰手指头了吧，对普通人来说，这个求解有点难度，但是对计算机来说，还是小菜一碟。

椭圆曲线加密-ECC

真正的非对称算法比这复杂多了，常见的非对称加密算法有RSA，还有椭圆曲线加密-ECC-Elliptic Curve Crytograph。

接下去就重点讲下，这个什么椭圆，什么曲线，是个什么鬼？

椭圆曲线

简单说它就是一套数学公式，比如：y^2 = x^3 ax b

（当a和b满足4a3 27b2 ≠ 0的，才是一根有效的椭圆曲线）

当然，椭圆曲线有多种变化，通过系数a和b的变换，可以有以下形状：

(b = 1, a 取值由 2 变化至 -3)

实际上真正拿来加密用的曲线，a和b的取值都是天文数字

为了简单理解，我们假设有根曲线，其公式是y^2=x^3-x 1，

该曲线有个特点，任意一根穿过该椭圆曲线的直线，最多和曲线有三个交点。

假设1

我们在曲线上有A点和B点，两点成直线后的延伸线又和曲线相交，于是就有了C点，见下图。

A，B，C三点C点满足以下关系：

A B C = 0

另外，椭圆曲线是相对于x轴对称，所以，由C点可以得到镜像点C’，两者满足关系

C = -C’

请注意，这里的加法是几何意义上的加法，不同于普通的加减乘除

到这里，你会问，知道了这些又如何，这根曲线有个卵用阿？别急，接下来，我们把C’和A点相连，新的直线相交曲线得到D，

把D镜像为D’，再与A相连，新的直线与曲线相交，又得到点E，

这个过程持续重复，就会得到点G，如下图：

然后根据椭圆曲线上点的加减规则，把过程中所有点的关系列出来
A B C = 0
A D C’ = 0
A D’ E = 0
A F E’ = 0
A F’ G = 0
C = -C’
D = -D’
E = -E’
F = -F’

经过一系列的加法运算

得到：

-G=5A B

看明白了么，就是说终点G的值，只和曲线上初始点A和B的位置有关系。

有人把这个过程比作弹子球不断碰撞反弹，再碰撞再反弹的过程。

假设2

现在考虑一种特殊的情况，当初始点A=B的时候，此时，从A点出发的直线与椭圆曲线相切，重复上述过程：

以上过程表达为：
A A C = 0
C’ C’ D = 0
D’ D’ E = 0
E’ E’ F = 0
C = -C’
D = -D’
E = -E’
F = -F’

最终得到：

F’=16A，

其中A被称作起始点，16其实是2的k次方，k为迭代次数

在ECC加密算法里，其几何学的意义，正是通过对“生成点”做反复切线，最终得到一个点，这个点正是公钥-K，而迭代的次数就是私钥

K=k*G

生成点：G，Generator，

迭代次数：k，“私钥”—一个256比特的二进制数字

在已知k和G的情况下，进行的其实是相加的计算，并通过一种叫做square and multiply-的方式，可以快速算出K。

但如果反过来，知道了K和G，反算k就非常困难，办法倒不是没有，就一招—老老实实一步一步计算，英文叫做-Baby-step giant-step，有个更直白的称呼，你一定知道，叫—暴力破解，不过迭代的范围是2的256次方，即1.15×10^77，按照现阶段的计算机算力，大概要算上几百万年吧。

请注意上面公式变换成k = K/G是不成立的，k ≠ K/G。

这套密码的好处，是私钥和公钥对，随时可以变化，随机生成一个，就有完全不同的密钥来加密信息了，相比对称加密一尘不变的密码对，要安全很多。

以上就是ECC椭圆曲线加密的基本原理。

有限域

在真正的ECC算法里，会对椭圆曲线进行有限域转换，变成下面这个鬼样子：

像不像23×23的围棋棋盘？有没有完全看不懂？

是的，我也完全看不懂，反复纠结和琢磨后，大致可以理解成，把一个复杂的曲线，进行归一化，离散化，整数化的方法。

比如我们的表盘就是个模-mod为12的有限域，无论时间走了8小时，14小时，20小时，还是49小时，表盘上显示的只是8，2，8，1，相当于把无限的线性时间，折叠在有限的表盘内，这样的好处是，当你看着表盘上的8点(公钥)，你根本不知道，究竟是上午8点，下午8点，还是n天后的8点，因为你完全不知道指针走了几圈啊(私钥)，从而增加了密码的强壮性。（具体我还没完全懂，吹不下去了）

把y^2=x^3-x 1写成有限域内的公式就有y^2 mod p=(x^3-x 1) mod p，p表示网格的范围，是个素数，比如上图的p=23，又是个玄乎的东西

实际的ECC加密算法secp256k1里，有限域的模p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1，你自己掰手指头数吧，反正你可以把它想象成一张无比巨大的网格。
经过上面的一系列计算，得到K-公钥后，给到对方，就能进行信息的加密了，但是对方只能用公钥对信息进行加密，并不能对信息进行解密，解密需要私钥k，也就是只有手握私钥的你才能打开这把锁。(对应数字货币世界，只能向公钥地址发送货币，但没有私钥是不能对账户内的金额进行转账操作的)