专注区块链信息及金融服务
入驻火星号
APP
下载火星财经客户端

扫描下载APP

加密技术核心算法之安全快捷的ECC算法

Astar ·

05月09日

热度: 170496

相对于RSA,ECC提供了一个较好的选择:使用简短并且快速的秘钥来达到高安全性。而破解ECC秘钥你至少需要250万年。

非对称加密算法,区别于对称加密算法,加解密需要两个密钥,分别是公钥和私钥。公钥是公开的,私钥是保持私有的。

非对称加密算法的原理,私钥生成公钥很容易,由公钥反推私钥则很难。

RSA算法,作为非对称加密算法之一,它把公钥反推私钥的过程等价于一个数学难题——极大整数的因式分解,一定程度上保证了RSA算法的安全性。

RSA算法的复杂性取决于因式分解的难度,数字越大因式分解越难,随着计算机的算法、运算的进步,大数字因式分解的难度正在随着数字变大而缩小。

所以这意味着RSA算法对未来的密码学来说并不是理想的加密系统,我们需要一个更好的加密系统。

今天我们将学习椭圆曲线加密算法。

椭圆曲线加密算法 (Elliptic curve cryptography,缩写为 ECC),1985年由Neal Koblitz和Victor Miller分别独立提出。

那到底什么是椭圆曲线算法呢?

让人失望的是,椭圆曲线不像因式分解是那种我们初中就学过的知识,可以说大多数人对椭圆曲线函数的知识并不熟悉。

这部分的内容并不简单,也没那么容易理解,接下来,我尽量避免罗列公式,用通俗易懂的语言介绍下椭圆曲线。

微信图片_20180509165125.jpg

(学霸轻喷,学酥请绕行,如果你阅读过程中身体稍有不适,请直接跳到文章末尾结论处。)

上节在讲RSA算法的时候,我们提到一个数学概念——单向函数,就是正向计算很容易,反向计算很难的函数。

而RSA算法的单向函数体现在计算乘法很容易,因式分解则是一道数学难题。

那么椭圆曲线的算法的单向函数是什么呢?

首先我们来看看椭圆曲线方程组,y^2=x^3+a^x+b,有点抽象,我们来看看它长什么样子:

微信图片_20180509165222.jpg

这两种曲线都是椭圆曲线,可以说是孪生兄弟,根据参数a、b的不同,所以样子上有点区别。

你会发现,右边的曲线跟欧米伽特别像。

微信图片_20180509165305.jpg

我们仔细看椭圆曲线,它有着一个非常有趣的特性,就是任何不垂直的直线穿过曲线最多有三个交点。

还有一个特性,曲线上任一点做X轴对称后得到的点仍然在椭圆曲线上。为了避免出现大部分公式,笔者尽量用图片来解释椭圆曲线算法。

曲线上任意两点的连线延长做一条直线,这条直线与曲线有一个交点,根据椭圆曲线的对称性,我们做这个交点的x轴对称,得一个新的点,该点仍在曲线上。

微信图片_20180509165343.jpg

这个过程,我们叫打点,即dot。我们来看上图,A dot B得到的是C点。(很多文献把这个过程定义成椭圆曲线的加法)

我们持续这一过程反复

A dot B=C

A dot C=D

A dot D=E

……

微信图片_20180509165421.jpg

重复这一过程,我们来看看结果,我们发现了一些特性,如果图像无限大的话,打点这一过程可以一直持续。

也就是说,我们可一直打点,我们假设进行了无数次的打点,并得到其中一点G,如果我们只知道G和A,那么G点是A打点几次得出的?我想这是一个很难的数学问题。

结论

在给定起始点A和终点G的情况下,我们想找出打点次数n的值是很困难的。正推容易,反推很难,这就是ECC算法的单向函数,也是ECC算法的数学基础。

我们再来看看ECC算法的加密过程:

1. 小倩选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。

2. 小倩选择一个私有密钥k,并生成公开密钥K=kG。(这一步既是上文提到的打点过程)

3. 小倩将Ep(a,b)和点K,G传给小高。

4. 小高接到信息后,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r(r<n)。

5. 小高计算点C1=M+rK;C2=rG。

6. 小高将C1、C2传给小倩。

7. 小倩接到信息后,计算C1-kC2,结果就是点M。因为

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

然后再对点M进行解码就可以得到明文。

在这个加密通信中,如果有一个偷窥者H ,他只能看到Ep(a,b)、K、G、C1、C2, 而通过K、G 求k 或通过C2、G求r 都是相对困难的,原因上文已经提到。

因此,H无法得到A、B间传送的明文信息。

椭圆曲线数字签名算法(ECDSA)是使用椭圆曲线密码(ECC)对数字签名算法(DSA)的模拟。

ECDSA于1999年成为ANSI标准,并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受,并且包含它的其他一些标准亦在ISO的考虑之中。

与普通的离散对数问题(discrete logarithm problem  DLP)和大数分解问题(integer factorization problem  IFP)不同,椭圆曲线离散对数问题(elliptic curve discrete logarithm problem ECDLP)没有亚指数时间的解决方法。

秘钥强度

因此椭圆曲线密码的单位比特强度要高于其他公钥体制。

椭圆曲线离散对数算法是基于ECC最难的问题。

即便最近30年的研究,数学家任然没有找到一个能够解决这个问题的改进方法。

也就是说,和因式分解不同,基于当前已知的数学方法,找不到可以缩小该单向函数的正反计算难度差值的办法。

这意味着对于许多同样位数长度的数字,解决椭圆曲线离散对数问题要比因式分解困难的多。

因为一个算法的计算空间越密集意味着一个密码系统越强大,所以椭圆曲线密码学系统比RSA和Diffie-Hellman更加难以攻破。

为了理解这到底有多难被攻破,Lenstra最近提出了“全球安全(Global Security)”的概念。

你可以计算攻破一个(椭圆曲线)密码学算法需要多少能量和计算该能量能煮沸多少水进行对比。

这是一种密码学的碳排放量的衡量。

通过这样的测量方法,破解一个228字节的RSA秘钥所需能量少于煮沸一勺水的能量。

相对地,破解一个228字节的椭圆曲线秘钥所需能量足够煮沸地球上所以水。

而RSA要达到这样的安全强度,需要2,380个字节的秘钥长度。 

使用ECC,你可以用更简短的秘钥获得相同的安全强度。

简短秘钥是非常重要的,尤其是在现实中密码学算法越来越多的运行在小功率设备里,例如手机。

尽管两质数相乘比把结果因式分解要简单,但当质数变得非常大,在低功率设备上仅仅只是乘法步骤都将花费很长一段时间来计算。

虽然可以通过增加秘钥长度来保持RSA的安全性,但却是以牺牲客户端的性能为代价。

相对于RSA,ECC提供了一个较好的选择:使用简短并且快速的秘钥来达到高安全性。而破解ECC秘钥你至少需要250万年。


文章原标题:侯震:ECC算法——安全快捷,再也不担心私房钱被发现了  原作者:侯震

推广
相关新闻
本文来源:

AstarLab

原文标题: 加密技术核心算法之安全快捷的ECC算法

涨幅榜

你可能感兴趣的内容
下一篇

数字证书的作用机构和分发机制是什么?