非对称加密与椭圆曲线

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

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

对称加密

维基百科的解释如下:

对称密钥加密(英语: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 条评论
登录 后参与评论

相关文章

来自专栏媒矿工厂

HDR关键技术:HEVC/H.265编码方案

前文我们对HEVC的HDR编码优化技术做了介绍,侧重编码性能的提升。本章主要阐述HEVC中HDR/WCG相关的整体编码方案,包括不同应用场景下的HEVC扩展编码...

1250
来自专栏MelonTeam专栏

视频编解码学习分享

要解决视频存储难、传输难的问题,综合考虑软硬件成本,最有效的办法应该是压缩视频体积!

1.2K13
来自专栏数据派THU

手把手教你深度学习强大算法进行序列学习(附Python代码)

本文共3200字,建议阅读10分钟。 本文将教你使用做紧致预测树的算法来进行序列学习。

1234
来自专栏AI研习社

一次 PyTorch 的踩坑经历,以及如何避免梯度成为NaN

本文首发于知乎答主小磊在「PyTorch有哪些坑/bug?」下的回答,AI 研习社获原作者授权转载。 分享一下我最近的踩坑经历吧。 这几天在实现一个语义分割的 ...

5856
来自专栏计算机视觉战队

Deep Hash(深度哈希算法)

哈希的简单介绍: 用一个比喻来说明什么是哈希算法:假设有N只小猪,它们的体重各不相同,一开始我们把它们放在一个猪圈里面。如果想寻找其中某只小猪,只能一个一个的...

3876
来自专栏AI科技大本营的专栏

AI 技术讲座精选:条件概率和贝叶斯定理简介

前 言 数据科学专家必须了解概率方面的知识。通常情况下,解决许多数据科学难题的办法与概率的本质息息相关。因此,更好地理解概率能够帮助你更有效率地理解并实现与之相...

3315
来自专栏数据处理

ECC非对称加密算法

2224
来自专栏月色的自留地

Grapher--寂寞无名的神器

1677
来自专栏阮一峰的网络日志

RSA算法原理(二)

上一次,我介绍了一些数论知识。 有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。 ? 六、密钥生成的步骤 我们通过一个例子,来理解RSA...

3326
来自专栏程序员叨叨叨

2.4 图形硬件

这一节中主要阐述图形硬件的相关知识,主要包括 GPU 中数据的存放硬件, 以及各类缓冲区的具体含义和用途,如:z buffer(深度缓冲区)、stencil b...

592

扫码关注云+社区