一文读懂椭圆曲线加密学

编者按：本文来自蓝狐笔记（ID：lanhubiji），作者：Lane Wager，来源于medium，由“蓝狐笔记”公众号社群的“王泽龙”翻译，Odaily星球日报经授权转载。

前言：本文是关于椭圆曲线加密的非常基础的介绍。内容虽然基础，但对于椭圆曲线加密的门外汉来说，简单易懂，适合于初学者。

这是一篇椭圆曲线密码学的基本介绍。我假设本文的绝大多数读者来这里的目的是：了解为什么椭圆曲线加密是一种有效的加密工具，以及它为什么有效。我试图用通俗的方式来解释它，我将跳过论证与实现的细节，转而聚焦在其运行原则上。

椭圆曲线示例

它是做什么的？

椭圆曲线加密是一种加密数据方法，只有特定人，才能对其进行解密。它在现实生活中有许多应用场景，但其主要应用在于加密互联网上的数据与流量。例如，椭圆加密曲线可以用于确保一封邮件何时发送，且除了收件人外无人可以读取该邮件。 

椭圆曲线加密是公钥加密技术

公钥加密风情万千，椭圆曲线加密只是其中一种风味。其他加密算法还有RSA,DiffieHelman，等等。我将简单交代公钥加密的大体背景作为开头，进而展开我们后续的阐述，以此更深入理解椭圆曲线加密。有空时，你可以花些时间深入研究公钥密码学知识。 

如下图所示，公钥加密允许以下过程发生:

http://itlaw.wikia.com/wiki/Key_pair

上图展示了两个钥匙，一个公钥和一个私钥。这些密钥用于加密和解密数据，这使得世界上的任何人都可以在传输时看到加密数据，但无法读取信息。

让我们假设Fcebook将收到来自特朗普的私密贴。Facebook需要能够确保特朗普通过网络发文时，没人（包括N S A或互联网服务供应商）可在其中阅读该消息。使用公钥加密后，整个数据传输过程呈现如下状态: 

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），直到我们最终抵达最后一个点上。让我们看看以下整个算法。

 https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/2/

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的切线。请看以下图片：

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

如果点函数产生一条线路会走到某个极端，会发生什么？ 

如果线没有抵达靠近原点的曲线，我们实际上可以定义一个最大X值，其中线将回绕并从头开始。有关示例，请参见下图。

https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/2/

我理解了暗门函数，但实践中公私钥是如何创建的？它们是如何与要加密的数据一起使用的？

这是一个好问题，但它要求更深入的答案。在这篇文章中我给出了关于RSA与椭圆曲线加密较为通俗的解释。然而，还有更多技术资源，我期望你去研究它们。