非对称加密与椭圆曲线

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

要解释加密技术,首先就要了解一下什么是对称加密。

对称加密

维基百科的解释如下:

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

上面这段话看上去太抽象,不好理解,举个例子,假如把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满足4a^3 + 27b^2 ≠ 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.15x10^77,按照现阶段的计算机算力,大概要算上几百万年吧。

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

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

有限域

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

像不像23x23的围棋棋盘?有没有完全看不懂?

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

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

得到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

--- END ---

原文发布于微信公众号 - 申龙斌的程序人生(slbGTD)

原文发表时间:2017-09-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列四:图像转置的SSE优化(支持8位、24位、32位),提速4-6倍

一、前言       转置操作在很多算法上都有着广泛的应用,在数学上矩阵转置更有着特殊的意义。而在图像处理上,如果说图像数据本身的转置,除了显示外,本身并无特殊...

2589
来自专栏新智元

【AI系统首次实现真正自主编程】利用遗传算法,完爆初级程序员

【新智元导读】让AI自动编程是人工智能领域长久以来的梦想之一。现在,来自彭博和英特尔实验室的两位研究人员,号称实现了首个能够自动生成完整软件程序的AI系统“AI...

34910
来自专栏华章科技

AI系统首次实现自主编程,完爆初级程序员!

让AI自动编程是人工智能领域长久以来的梦想之一。现在,来自彭博和英特尔实验室的两位研究人员,号称实现了首个能够自动生成完整软件程序的AI系统“AI Progra...

684
来自专栏iOSDevLog

google 机器学习速成课程字幕和视频

5747
来自专栏顶级程序员

AI系统首次实现真正自主编程:利用遗传算法,完爆初级程序员

让AI自动编程是人工智能领域长久以来的梦想之一。现在,来自彭博和英特尔实验室的两位研究人员,号称实现了首个能够自动生成完整软件程序的AI系统“AI Progr...

3955
来自专栏章鱼的慢慢技术路

利用MATLAB进行曲线拟合

1293
来自专栏云计算教程系列

如何使用Scikit-learn在Python中构建机器学习分类器

机器学习是计算机科学、人工智能和统计学的研究领域。机器学习的重点是训练算法以学习模式并根据数据进行预测。机器学习特别有价值,因为它让我们可以使用计算机来自动化决...

1325
来自专栏用户2442861的专栏

基于级联分类器的多目标检测

原文地址:http://blog.csdn.NET/ariesjzj/article/details/8639208

421
来自专栏企鹅号快讯

如何在短时间迅速提升Python功力?Python应该怎样去学习呢?

最近有一段时间没有看后台的留言,。昨天我打开后台一看有很多同学给我留言,其中有5条是问我关于如何快一点提高Python功力的相关问题~~ 确实当你学了Pytho...

1959
来自专栏有趣的Python

TensorFlow应用实战-18-Policy Gradient算法

2314

扫描关注云+社区