本文是关于椭圆曲线加密的非常基础的介绍。内容虽然基础,但对于椭圆曲线加密的门外汉来说,简单易懂,适合于初学者。
原文标题:《一文读懂椭圆曲线加密学》
作者:Lane Wager
翻译:王泽龙
这是一篇椭圆曲线密码学的基本介绍。我假设本文的绝大多数读者来这里的目的是:了解为什么椭圆曲线加密是一种有效的加密工具,以及它为什么有效。我试图用通俗的方式来解释它,我将跳过论证与实现的细节,转而聚焦在其运行原则上。
椭圆曲线示例
它是做什么的?
椭圆曲线加密是一种加密数据方法,只有特定人,才能对其进行解密。它在现实生活中有许多应用场景,但其主要应用在于加密互联网上的数据与流量。例如,椭圆加密曲线可以用于确保一封邮件何时发送,且除了收件人外无人可以读取该邮件。
椭圆曲线加密是公钥加密技术
公钥加密风情万千,椭圆曲线加密只是其中一种风味。其他加密算法还有 RSA,DiffieHelman,等等。我将简单交代公钥加密的大体背景作为开头,进而展开我们后续的阐述,以此更深入理解椭圆曲线加密。有空时,你可以花些时间深入研究公钥密码学知识。
如下图所示,公钥加密允许以下过程发生 :
上图展示了两个钥匙,一个公钥和一个私钥。这些密钥用于加密和解密数据,这使得世界上的任何人都可以在传输时看到加密数据,但无法读取信息。
让我们假设 Fcebook 将收到来自特朗普的私密贴。Facebook 需要能够确保特朗普通过网络发文时,没人(包括 NSA 或互联网服务供应商)可在其中阅读该消息。使用公钥加密后,整个数据传输过程呈现如下状态 :
l 特朗普告知 Facebook 他将向后者发送一篇私密帖
l Facebook 将其公钥发送给特朗普
l 特朗普使用公钥加密其帖子:
“我喜爱福克斯(Fox)与朋友们”+公钥 =“s80s1s9sadjds9s”
l 特朗普只把加密后的信息发送给 Facebook
l Facebook 使用他们的私钥解密消息:
“s80s1s9sadjds9s” +私钥 =“我喜爱福克斯(Fox)与朋友们”
如你所见,这是一项非常有用的技术。以下是其中的一些要点:
l 公钥可发送给任何人,它是公开的
l 私钥必须被妥善保管,因为如果某人获取了私钥,他们便可以解密信息
l 计算机可以迅速地用公钥来加密消息,并用私钥来解密消息
l 如果没有私钥,计算机可能需要花费极长的时间(数百万年)来破解加密后的消息
它是怎样运作的:陷门函数
所有公钥加密算法的关键在于它们各自都有其独特的陷门函数。陷门函数只能被单向计算,或者至少只能容易地单向计算(使用现代计算机在不到几百万年的时间内)
不是陷门函数:A+B=C
如果被给到 A 与 B,我就可以算出 C。问题是如果我被给到 B 与 C,我也可以算出 A。并非是陷门函数。
陷门函数:
“我喜爱福克斯(Fox)与朋友们”+公钥 =“s80s1s9sadjds9s”
如果我被给到“我喜爱福克斯(Fox)与朋友们”+公钥 , 我可以得出“s80s1s9sadjds9s”,但是如果我被给到“s80s1s9sadjds9s”与公钥,那我无法得出信息:“我爱福克斯(Fox)与朋友们”。
在 RSA (可能是最流行的公钥系统)中,陷门函数主要取决于将大数字纳入其主要因子的难度。
公钥:944,871,836,856,449,473
私钥:961,748,941 and 982,451,653
在以上的例子中,公钥是一个非常大的数字,私钥是公钥的两个主要因子。这是陷门函数的一个好的例子,因为在私钥中很容易将多个数字相乘以获取公钥,但如果你拥有的只是公钥,那将花费一台电脑很长的时间才能重建私钥。
注意 : 在真实的加密中,私钥需要 200+位数以上的长度以确保安全。
是什么让椭圆曲线加密与众不同
人们使用椭圆曲线加密的理由跟 RSA 完全相同。它生成公私钥对并允许两方安全沟通。然而,椭圆曲线加密有一胜过 RSA 的优势。椭圆曲线加密中 256 位数的密钥所提供的安全性与 RSA 算法中 3072 位数密钥所提供的安全性相同。这意味着在资源有限的系统中,如智能手机、嵌入式电脑、加密网络,椭圆曲线加密相较于 RSA 加密算法,它使用的硬盘空间和带宽不到 RSA 算法的 10%。
(译注:也就是说,椭圆曲线加密比 RSA 算法在资源有限的情况下,更省资源,可行性更高。)
椭圆曲线加密的陷门函数
这可能是绝大多数读者阅读本文的原因。这是椭圆曲线加密有别于 RSA 加密算法的部分,也是它的特殊之处。陷门函数类似于池中的数学游戏。我们从曲线上的某一点开始。我们使用一个“点函数”(dot function)来发现一个新的点。不断重复“点函数”并围绕曲线跳跃(hop),直到我们最终抵达最后一个点上。让我们看看以下整个算法。
l 从 A 点开始;
l A 点 B=-C (从 A 到 B 点画一条线并最终落在-C 点)
l 从-C 到 C 跨 X 轴反射;
l A 点 C=-D (从 A 点向 C 点画一条线并最终落在-D)
l 从-D 到 D 跨 X 轴反射;
l A 点 D=-E (从 A 向 D 画一条线并最终落在-E)
l 从-E 到 E 跨 X 轴反射
这是一个伟大的陷门函数,因为如果你知道哪里是起点(A)以及需要多少跳才能达到终点 E,那么找到终点会很容易。从另一方面来说,如果你知道的只是起点与终点的位置,那么,要发现需要多少跳才能抵达终点几乎是不可能的。
公钥:起点 A,终点 E;
私钥:从 A 到 E 的跳数
有问题吗 ?
以下是我初次了解椭圆曲线加密时所产生的相关问题。希望我能妥善地解决它们。
如何发现第二点?如果点函数(dot function)只是在两点之间画一条线,难道不需要第二点来帮助开始吗 ?
回答:不需要。第二点(我们将其称为下图中的-R 点)实际上是 P 点函数 P (让我们假设第一个点被称为 P)
P 点函数 P=-R
那么,什么是 P 点函数 P?它实际上只是 P 的切线。请看以下图片:
如果点函数产生一条线路会走到某个极端,会发生什么?
如果线没有抵达靠近原点的曲线,我们实际上可以定义一个最大 X 值,其中线将回绕并从头开始。有关示例,请参见下图。
我理解了暗门函数,但实践中公私钥是如何创建的?它们是如何与要加密的数据一起使用的?
这是一个好问题,但它要求更深入的答案。在这篇文章中我给出了关于 RSA 与椭圆曲线加密较为通俗的解释。然而,还有更多技术资源,我期望你去研究它们。