非对称加密与椭圆曲线

万金油 发布在 区块链 1 2607

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

 

对称加密

 

维基百科的解释如下:

对称密钥加密(英语: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,也就是只有手握私钥的你才能打开这把锁。(对应数字货币世界,只能向公钥地址发送货币,但没有私钥是不能对账户内的金额进行转账操作的)

 

真正的椭圆曲线

 

最后来看看,真正的椭圆曲线生成点,私钥,公钥都长什么样子吧:

生成点G(x, y)

Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

私钥:

0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb

公钥-点(x, y):

(0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)

参考资料:

Elliptic Curve Cryptography Overview – Youtube

https://youtu.be/dCvB-mhkT0w

Elliptic Curve Cryptography & Diffie-Hellman – Youtube

https://youtu.be/F3zzNa42-tQ

Elliptic Curve Cryptography: a gentle introduction

http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction

ECC加密算法入门介绍

https://www.pediy.com/kssd/pediy06/pediy6014.htm

版权声明: by nc" sa 作者保留权利。文章为作者独立观点,不代表巴比特立场。
发文时比特币价格 ¥22407

评论:1

您需要登录后才可以回复 登录|注册
    Author Image
    cailaiji 25 天前

    神籁之笔,化神奇为简易

    +1
    +1
    我要点评