1. 链一财经首页
  2. 资讯

加密算法之椭圆曲线密码学(ECC)启蒙

本文是关于椭圆曲线密码学(ECC)的基本介绍,目的是让大多数读者了解为什么ECC是一种有效的加密工具以及ECC运作的基础知识。我希望在一般意义上对其进行解释,我将省略相关的证明和实现细节,并把精力集中在使ECC发挥作用的高级原则上。

加密算法之椭圆曲线密码学(ECC)启蒙

ECC可以做什么?
ECC是一种用来加密数据的方法,加密过后只有特定的人才能对其进行解密。在现实生活中,使用ECC的例子非常多,但主要用途还是互联网数据和流量加密。例如,ECC可用于确保用户在发送电子邮件时,除了收件人之外,没有人可以阅读这封邮件。

ECC是一种公钥加密技术
公钥加密技术的类型非常多,椭圆曲线加密不过是其中一个类别。其它加密算法包括RSA,Diffie-Helman等。为了更好地讨论ECC以及构建于相关概念的想法,首先我将简要介绍公钥密码学的背景。如果你有时间的话,可以更加深入地研究。

公钥加密的发生过程如下图所示:

加密算法之椭圆曲线密码学(ECC)启蒙

图中共有两把密钥,其中一把是公钥(public key),一把是私钥(private key)。这些密钥用于加密和解密数据,世界上的任何人都可以在传输时查看加密数据,但无法读取消息。

我们不妨假设Facebook将要接收特朗普的私人邮件。Facebook需要确保当总统通过互联网发送邮件时,中途没有人(如NSA或互联网服务提供商)能够读取该邮件。使用公钥加密的交换过程如下:

特朗普通知Facebook他要向他们发送私人邮件;

1.Facebook向特朗普发送他们的公钥;
2.特朗普使用公钥来加密他的信息:“I love Fox and Friends”+ 公钥 = “s80s1s9sadjds9s”
3.特朗普只将加密的消息发送给Facebook
4.Facebook使用他们的私钥来解密消息:“s80s1s9sadjds9s”+私钥 = “I love Fox and Friends”

如你所见,这是一项非常有用的技术。以下是几处要点:

· 公钥可以发送给任何人。这是公开的。
· 私钥必须要被安全保管,因为一旦中途某人获得了私钥,他就可以解密数据。
· 计算机可以非常快速地使用公钥来加密消息,并用私钥来解密消息。
· 如果没有私钥,那么计算机将需要花费很长时间(数百万年)才能从加密消息中获取原始数据。

工作原理:陷门函数
所有公钥加密算法的关键在于每种算法都有各自独特的陷门函数(trapdoor function)。陷门函数是一种只能进行单向计算,或者单向计算更容易的函数(使用现代计算机耗费的时间少于数百万年)。

非陷门函数:A + B = C

如果给我A和B,我可以得到C。问题是如果给我B和C,我同样可以计算出A。因此这不是陷门函数。

陷门函数:“I love Fox and Friends”+公钥=“s80s1s9sadjds9s”

如果给我原始数据“I love Fox and Friends”和公钥,我可以生成加密数据“s80s1s9sadjds9s”。但是如果给我加密数据“s80s1s9sadjds9s”和公钥,我不能生成原始数据“I love Fox and Friends”。

在加密算法RSA(可能是最流行的公钥系统)中,陷门函数的作用取决于将大数分解成素数因子(prime factors)的难度。

在加密算法RSA(可能是最流行的公钥系统)中,陷门函数的作用取决于将大数分解成素数因子(prime factors)的难度。

公钥:944,871,836,856,449,473
私钥:961,748,941和982,451,653

在上面例子中,公钥是一个非常大的数字,而私钥是公钥的两个素数因子。这是一个很好的陷门函数示例,因为我们只要将私钥中的数字相乘就能很容易地得到公钥,但如果你只有公钥,那么即使使用计算机也需要很长时间才能重新得到私钥。

请注意:在实际加密应用中,私钥长度超过200位数字才能被认为是安全的。

为什么椭圆曲线加密与众不同?

使用ECC的原因与RSA完全相同。我们只需生成公钥和私钥,然后双方就能进行安全通信。然而,ECC拥有RSA没有的优点:使用ECC加密的256位密钥所提供的安全性,与使用RSA加密的3072位密钥相当。

这意味着在诸如智能手机、嵌入式计算机或者加密货币网络等资源有限的系统中,使用ECC所需的硬盘空间和带宽不到RSA的10%。

ECC的陷门函数
也许这是大家阅读本文的原因,也是ECC区别于RSA的地方。陷门函数类似于数学游戏池子。我们从曲线上的某一点开始,并使用点函数(dot function)来寻找另一个新点。我们不断重复点函数,不断地在曲线上跳跃,直到得到最后一点。我们不妨看看具体算法:

加密算法之椭圆曲线密码学(ECC)启蒙

· 从A开始:
· A与B进行点函数运算得到 -C(从A到B绘制一条直线,直线与椭圆曲线相交于点 -C);
· 作 -C关于X轴的对称点,在椭圆曲线上得到点C;
· A与C进行点函数运算得到 -D(从A到C绘制一条直线,直线与椭圆曲线相交于点 -D);
· 作 -D关于X轴的对称点,在椭圆曲线上得到点D;
· A与D进行点函数运算得到-E(从A到D绘制一条直线,直线与椭圆曲线相交于点-E);
· 作-E关于X轴的对称点,在椭圆曲线上得到点E。

这是一个很棒的陷门函数,因为如果你知道起点(A)的位置以及到达终点(E)所需的跳数,那么你很容易就能找到终点。另一方面,如果你只知道起点和终点的位置,那么你几乎不可能得到到达目的地所需的跳数。

公钥:起点A,结束点E
私钥:从A到E的跳数

答疑时间
以下是我第一次了解ECC时遇到的几个问题,希望我能正确解答。

第二点是怎么找出来的?如果点函数运算是在两点之间画一条直线,你不需要先找到第二点吗?

答案:不。第二点(不妨称其为-R)实际上是P(假设第一点为P)与P进行点函数运算得到的结果:P

与P进行点函数运算得到第二点-R。

那到底什么是P与P的点函数运算?它实际上只是P的切线。如下图所示:

加密算法之椭圆曲线密码学(ECC)启蒙

如果点函数运算画出的线走到某个极端,会发生什么?

如果直线与曲线的交点离原点很远,我们实际上可以定义一个最大值X,这时直线将回绕并从头开始。有关示例请参见下图:

加密算法之椭圆曲线密码学(ECC)启蒙

现在我了解了陷门函数,但在实践中,我该如何创建公钥和私钥呢?它们如何与将要加密的数据一起使用?

这是一个很好的问题,不过它的答案要比本文论述的范围更加深入。在本文中,我仅对RSA和ECC进行了非常简洁的解释。不过相关的技术资源有很多,我建议你去了解这些资源。

跟我有什么关系?
我一开始研究ECC是因为我对比特币和加密货币感兴趣。ECC之所以被用作加密货币的加密密钥算法,是因为它所需的密钥大小(和扩展数据)不到RSA的10%。

我希望你能对ECC和公钥加密有所了解,本文并不是技术说明。我希望能吸引更多人关注ECC的用途,并对其工作原理有所了解。

参考来源:

https://devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832

翻译:喏呗尔
原文作者:Lane Wagner
原文链接:https://blog.goodaudience.com/very-basic-elliptic-curve-cryptography-16c4f6c349ed

根据国家《关于防范代币发行融资风险的公告》,大家应警惕代币发行融资与交易的风险隐患。

本文来自LIANYI转载,不代表链一财经立场,转载请联系原作者。

发表评论

登录后才能评论

联系我们

微信:kkyves

邮件:kefu@lianyi.com

时间:7x24,节假日bu休息

QR code