原文链接，非常好的椭圆曲线加密技术入门文章。如发现错误，请留言或者发送邮件到zwzm85@gmail.com。未经授权，请勿转载。

椭圆曲线加密技术（Elliptic Curve Cryptography，简称ECC）是当今广泛使用的最强大但最不被理解的加密技术之一。在CloudFlare，我们重度使用ECC加密从客户的HTTPS连接到数据中心传输数据的所有一切内容。

本质上，我们相信在信任任何安全系统之前弄明白其背后的技术十分重要。为了这个目的，我们到处寻找质量优良并且相对容易理解的ECC入门教程给我们的用户。最后一无所获，我们决定自己来写这个教程。接下来的内容就是。

请注意：这是个十分复杂的话题，不可能在一个简练的博客中写完。换句话说，因为涉及的内容太多，所以这篇文章是其精华版。如果你只需要重点，那就是：ECC是基于当前数学知识的下一代公钥加密技术，可以提供明显比类似RSA的第一代公钥加密技术更加安全的基础。如果你正在为既可以获得最高安全级别又保持性能的问题而发愁，ECC就是合适的选择。如果你对其细节感兴趣，请看下文。

公钥加密技术的起源

加密技术的历史可以划分成两个时代：古典时代和现代。两者的转捩点位于1977年，当时出现了RSA算法和Diffie-Hellman密钥交换算法。这两个新算法具有革命性，因为它们是第一种切实可行的基于数论的加密方案，其安全性基于数论。它首次实现了通讯双方不需要共享密码就可以进行安全交流。密码学中如何实现双方安全通讯的技术从需要在全世界范围内安全传递密码本，演变成无需担心中间人窃听的密钥交换。

Whitfield Diffie and Martin Hellman

现代密码学基础是：加密数据的密钥可以公开，但解密的密钥要保密（译者语：公约加密，私钥解密；私钥签名，公约验证）。因此，这些系统被称为公钥加密系统。第一个这样的系统是RSA，至今任然被广泛使用。命名为RSA是为了纪念该算法最初的三个发明人：Ron Rivest, Adi Shamir and Leonard Adleman（译者语：为了方面对照RSA三个字母，名字不做翻译）。

为了使公钥加密系统工作，你需要一系列在一个方向上容易计算但是反向计算困难的算法。以RSA为例，容易的算法会做两个素数乘法。如果乘法是容易的算法，那么与之配对的困难的算法是把乘法的积因式分解为两个素数。有如下特性的算法被称为陷门函数：在一个方向上容易计算，其他方向上难以计算。找寻优秀的陷门函数对创建安全的公钥加密系统至关重要。简单点说：一个陷门函数越难从一个方向到其他方向，基于它的加密系统就越安全。

一个玩具RSA算法

RSA算法是最流行和最被大众熟识的公钥加密系统。它的安全性依赖于因式分解很慢但乘法很快的事实。下面我们快速浏览一下小型RSA系统的样子及其工作原理。

正常情况，公钥加密系统有两个组件：一个公钥和一个私钥。加密会接收一个消息，然后对其应用数学操作获取一个随机的数字。解密会对那个随机的数字应用一个不同的操作重新获得原来的数字。使用公钥加密只能被对应的私钥解密。

计算机不能很好地处理任意长度的大数字。我们要确保处理的数字不能大于选择的最大数，只处理比最大数小的数字。我们处理数字的方式类似时钟上的数字。任何导致结果大于最大值的计算都需要把其处理到有效范围内。

在RSA中，这个最大值（称为max）由两个随机的素数相乘得到。公钥和私钥是两个专门被选择的数字并且大于零小于最大值，分别称为pub和priv。要加密一个数字，你需要把它乘以自己pub次，注意当结果超过最大值的时候需要处理它。要解密一个消息，你需要把它乘以自己priv次，然后你就可以重新得到原来的数字了。这听起来让人惊讶，但是确实有效。这个特性被发现的时候，确实是一个重大突破。

要创建一个RSA密钥对，首先随机选取两个素数以生成最大值（max）。然后选取一个数作为公钥pub。只要你知道这两个素数，你就可以根据这个公钥计算出对应的私钥priv。这就是破解RSA所需用到的因式分解：把最大值因式分解成两个素数以便你可以从公钥计算出某人私钥，然后解密他们的私有消息。

让我们用个例子来具体说明。以素数13和7为例子，它们的乘积作为最大值是91。假设我们的公钥是数字5。那么我们已知7和13是91的因子，然后应用名为“扩展欧几里得算法”的算法，我们得到私钥是数字29（译者语：有兴趣的同学可以自己计算一下，（29， -2）是其中一组解，（101，-7）是另一组解）。

译者语：作者可能因为主要是要介绍ECC，所以这里对RSA的介绍比较简单。整个RSA系统涉及的数字有：p，q，n，k，e，d。具体含义如下：p和q是两个随机的素数，n等于p乘以q，也就是文中的max。k也是基于p和q计算而来，k=(p-1)(q-1)。数学上称为欧拉函数，主要用于计算私钥。e是公钥，可以随意选取，但目前行业上中普遍选取65537。然后使用稳重提到的扩展欧几里得算法求解出一组私钥d。

但是RSA的密钥一般用（e，n）和（d，n）分别表示公钥和私钥。所以如果使用RSA的证书，浏览器就会知道e和n的值。

可能有些细心的读者会问为什么因式分解是RSA陷门函数的另一个方向。我们知道公钥中包含n，这个n是由p乘以q的出来的。后面计算私钥时又要用到k，其等于(p-1)(q-1)。所以要破解RSA必须计算出p和q，答案就在于此。

这些参数（max:91, pub:5, priv:29）定义了一个功能完备的RSA系统。你可以用一个数乘以自己5次来加密它，然后用那个数字（译者语：加密后的数字）乘以自己29次，那么你就会得到原来的数字。

让我们使用这些值（译者语：那三个参数）来加密“CLOUD”这条消息。

为了以数学方式表示这个消息，我们需要把字母转换成数字。常用的拉丁字母表示方式是UTF-8。每个字母都对应一个数字。

image

依据这个编码规则，CLOUD就是67，76，79，85，68。每个数字都小于最大值91，所以我们可以各自加密它们。让我们从第一个字母开始。

我们要把它乘以自身5次以得到加密后的值。

因为4489比最大值要大，我们必须处理一下它。我们把它除以91，保留余数。

4489=91x41+30

这意味着数字67加密后是58。

对每个字母重复上述步骤我们得到加密后的消息CLOUD是：

58，20，53，50，87

要解密这一团乱的消息，我们需要让每个数字都乘以其自身29次：

（记住，我们需要在结果大于最大值时处理它）

...

瞧，我们有重新得到了67。这对其他的数字都有效，可以复原初始消息了。

需要注意的是你用一个数乘以它自身多次得到了一个随机的数字，然后再把那个随机数字乘以它自身多次（具体次数是保密的），就可以恢复原始数字。

并不是一个完美的陷门

RSA和Diffie-Hellman之所以如此的有影响力是因为它们有严格的安全性证明。作者证明想要破解系统等同于解决一个公认难以解决的数学难题。因式分解是一个众所周知的问题，并且在古代就已经进行研究（见埃拉托斯特尼筛法）。任何这方面的突破都将会是重大新闻，并且还可以给发现者带来巨大的意外之财。

找到因子，得到金钱

也就是说，因式分解并不是最难的问题。特定的算法例如二次筛选法和普通数域筛选法被创造出来解决素数分解并且取得了一定的成功。这些算法相比原生的猜已知素数对方法要更快且计算量更少。

这些算法在需因式分解的数越大就越高效。当数字（即密钥的比特长度）变大时，因式分解大数字和大数字相乘之间的难度差距正在缩小。当可以用来解密的资源越来越多时，密钥的长度增长的却更快。这对于计算能力有限的手机和低功耗设备来说是不可持续性的。因式分解和乘法之间的差距不会维持很久。

以上所有的这些都意味着RSA并不是未来密码学的理想系统。在一个理想的陷门函数中，随着数字越大，简单的方法和困难的方法是以相同的速率变的更加困难。

我们需要一个基于更好的陷门的公钥系统。

椭圆曲线：构建更好的陷门

在RSA和Diffie-Hellman出现之后，研究人员探索其他基于数学的加密方案，希望找到超越因式分解的算法作为优良的陷门函数。在1985年，出现了基于被称为椭圆曲线的深奥数学分支的加密算法。

但是椭圆曲线到底是什么和基于它的陷门函数如何工作呢？很不幸，不像因式分解——我们都会在中学第一次接触它——大多数人不熟悉椭圆曲线相关的数学知识。数学不简单，也很难解释清楚，但我将在下面几节中尝试一下（如果你开始糊涂了，你可以直接跳到这个章节：这到底意味着什么（译者语：没有相关数学背景的同学看这几小节可能出现的场景如下：我是谁？我在哪？我在干什么？:smirk:））。

椭圆曲线是一系列满足特定数学方程式的点的集合。一个椭圆曲线方程式看起来类似这样：

这个图形看起来有点像往侧面倾斜的Lululemon（译者语：加拿大的一家运动服装零售商）的标志：

一个椭圆曲线

还有其他展示类型的椭圆曲线，但是在技术层面上，椭圆曲线就是满足特定二元方程式的点的集合，该方程式的一个变量的次数是2，另一个变量的次数是3。椭圆曲线不只是一副漂亮的图片，它还有一些成为优秀加密技术的特性。

奇特的对称性

再来进一步看一下上面绘制出的椭圆曲线。它有一些有趣的特性。

其中之一就是水平对称性。曲线上的任何点的x轴对称点一定也在曲线上。一个更有趣的特性是任何非垂直的直线和曲线的交点最多不会超过三个。

让我们想象一个以这条曲线为背景的古怪的台球游戏。在曲线上取任意两点然后在它们之间画一条直线，那么它将会和曲线相交于另一点。在这个台球游戏中，你在A点拿着一个球，把它射向B点。当它撞击到曲线时，球会朝着曲线的另一侧向上反弹（如果它位于x轴下方）或者向下反弹（如果它位于x轴上方）。

image

我们将这个台球在两点的运动称为“dot”（译者语：这里不做翻译，保持原文。因为下面的公式使用的也是dot）。曲线上的任意两点都可以被连接在一起，从而得到一个新的点。

A dot B = C

我们可以把上述运动串联起来，一遍又一遍的对一个点进行“dot”。

A dot A = B

A dot B = C

A dot C = D

...

事实证明，如果你有两个点，一个初始点“dot”自身n次会到达一个终点，当你只知道初始点和终点想求解出n很难。继续我们古怪的台球这个比喻，想象有个人在房间中独自一人玩了随机时长的我们的游戏。他很容易按照上述规则反复的击球。如果后来有人走进房间，看到了球最后停留的位置。即使他知道游戏的规则和球的起点，除非重新走一遍整个游戏直到球来到同一位置，否则他不可能确定球要撞击几次。做起来容易，但是反向解开很难：这正是一个非常好的陷门函数的基础。

译者语：这里使用台球游戏来说明椭圆曲线是很好的陷门函数译者觉得不太合适。我自己在看的时候就特别疑惑。为什么重新走一遍游戏会很困难？两者的难度应该是等价的。第二个人在玩游戏的过程除了每次对比一下球的落点是不是最终的位置之外并没有其他的难度。后来我去网上查阅了资料才明白反向解开为什么难。这里简单说一下。寻找最终点的过程等同于A dot A dot A dot A dot ...A N次，如果已知N，可以使用类似快速幂这样的方法大大减少执行dot操作的次数，复杂度是O(logN)。但如果N未知，只能执行N次dot，复杂度是O(N)。由于dot本身计算复杂度就比乘法这些高，所以当N值很大时（比如256位）执行N次dot操作会比logN时间长的多得多。

让我们开始

上面的简化版曲线看起来很棒也很容易讲解椭圆曲线的基本概念，但是这并不表示密码学所使用的曲线也是如此。

我们必须把数字限定在一个固定的范围，就像在RSA中那样。我们限定所有的数字必须在一个固定范围内，而不是允许曲线上的点的任意值。当计算椭圆曲线方程（）时，我们要对超过最大值的数字使用相同技巧来回滚它们。如果我们选择的最大值是素数，那该椭圆曲线被称为素数曲线，拥有极好的加密特性。

这是一个适用所有数字的曲线（）图：

image

这个是同样的曲线图，但是限制所有点代表的值不能超过最大值97：

image

从传统意义上很难看出这像曲线，但是它确实是。这好像原来的曲线被在边缘出缠绕一样，并且只有符合是整数的坐标才会被着色。你甚至仍然可以看出其水平对称性。

事实上，你还可以在这个曲线上玩台球游戏并且将点点在一起。曲线上的方程式仍然具有一样的属性。此外，dot操作也可以高效地运算。你可以将两个点视为有条线在边界环绕直到它到达一个点。就好像在我们古怪的台球游戏中，当球撞击到球桌边缘（就是max）时，它会被神奇地运送到桌子的另一侧然后继续其行进路线直到到达一个点，类似《爆破彗星》（译者语：是由Atari公司在1979年发行的一个街机游戏，它是街机黄金年代里最受欢迎的游戏之一）游戏。

image

有了这个新的曲线表示形式，你可以把消息表示成曲线上的点。你可以想象你有一个消息，把它设置成x坐标，然后在曲线上算出对应点（译者语：x坐标相同的那个点，可能会有两个）的y坐标。实际操作上会更加复杂一些，但是原理相同。

你得到了下面这些点：

(70, 6), (76,48), -, (82,6), (69,22)

不存在x值是65的坐标，在现实中可以避免这种情况

可以通过选取一个素数作为最大值、一个曲线方程和曲线上的一个公开点来定义椭圆曲线加密系统。私钥是一个数字priv，公钥是公开点对自己执行dot操作priv次以后得到的那个点。以这种方式从公钥计算私钥在加密系统中被称为椭圆曲线离散对数函数。它被就是我们要找的陷门函数。

这到底意味着什么

椭圆曲线离散对数难题是支撑椭圆曲线密码学的基础。尽管经过了差不多三十多年的研究，数学家仍然没有发现比原始方法更快的算法来解决这个问题。换句话说，与因式分解不同的是，以当今数学发展水平，还没有一种捷径可以缩短基于该问题的陷门函数的两个方向上难易差距。这意味着对于相同大小的数字，解决椭圆曲线离散对数远远难于因式分解。由于更高计算强度的难题等同于更安全的加密系统，这意味着椭圆曲线加密系统比RSA和Diffie-Hellman加密系统更难以破解。

为了直观感受破解难度的增加，Lenstra最近提出了一个“Global Security”的概念。你可以计算破解一个加密算法需要多少能量，然后对比这些能量可以将多少水烧开。这是一种密码学的碳足迹（译者语：原文是carbon footprint，用来标示一个人或者团体的碳耗用量）。依据这个测算，破解一个228位的RSA密钥需要的能量比烧开一茶匙的水还要少。相比之下，破解一个228位的椭圆曲线密钥所需的能量足够把地球上所有的水都烧开。想要RSA达到相同的安全等级，你需要2380位的密钥。

使用ECC，你可以用更短的密钥获得一样的安全等级（译者语：对比RSA的密钥长度）。短密钥很重要，因为越来越多的加密是由类似手机的低功耗设备来完成。尽管乘以两个素数比把乘积因式分解要简单，但是低功耗设备上当素数变的非常大时仅仅乘法也要耗费一些时间。尽管可以通过增加密钥长度来继续保证RSA安全性，但是其代价是拖慢客户端加密性能。ECC的出现提供了更好的权衡：用短、快的密钥提供高安全性。

椭圆曲线实战

在缓慢的开端之后，椭圆曲线算法开始广受欢迎且使用量一直加速增长。椭圆曲线加密技术被广泛使用在不同类型的应用中：美国政府用它来保护内部通讯，Tor项目使用它来帮助确保匿名，比特币用它做所有权证明，苹果的iMessage服务用它来签名，DNSCurve使用它来加密DNS信息，它是通过SSL/TLS进行安全网络浏览的首选方法。CloudFlare使用椭圆曲线加密技术提供完美的向前安全性，这是在线隐私的基础。类似RSA和Diffie-Hellman这样的第一代加密算法在大多数领域里仍然是规范，但是椭圆加密技术正在迅速称为在线隐私和安全的首选解决方案。

如果你是用足够新版本的Chrome或者Firefox访问HTTPS版本的本博客，你的浏览器正在使用椭圆曲线加密技术。你可以自己检查一下。在Chrome中，你可以点击地址栏中的锁图标（译者语：地址栏最左面），然后去连接标签看用来建立安全连接使用的是哪种加密算法。在Chrome 30里点击锁图标应该出现以下图片中的内容：

image

这段文字和本文讨论相关点就是ECDHE_RSA。ECDHE代表Elliptic Curve Diffie Hellman Ephemeral，是一种基于椭圆曲线的密钥交换机制。这个算法被CloudFlare用来在SSL中提供完美向前安全性。RSA组件的含义是RSA被用来证明服务器的身份。

我们使用RSA是因为CloudFlare的SSL证书绑定的是RSA密钥对。现代浏览器也支持基于椭圆曲线的证书。如果CloudFlare的SSL证书是椭圆曲线证书，那上面图片中会是ECDHE_ECDSA。服务器的身份证明将使用ECDSA，即椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm）。

CloudFlare用于ECDHE的ECC曲线是（Google.com也使用这个曲线）：

ECDSA相比RSA有非常大的性能提升。即使在没有对椭圆曲线代码进行汇编优化的老版本OpenSSL中，256位密钥长度的ECDSA签名也比2048位密钥长度的RSA快20倍以上。

在一台MacBook Pro上使用OpenSSL 0.9.8，执行速度的基准测试结果如下：

Doing 256 bit sign ecdsa's for 10s: 42874 256 bit ECDSA signs in 9.99s

Doing 2048 bit private rsa's for 10s: 1864 2048 bit private RSA's in 9.99s

使用ECDSA签名比RSA签名快23倍。

CloudFlare一直致力于提升SSL性能。就在这个星期，CloudFlare开始使用汇编优化后的版本的ECC，其运行速度超过ECDHE的两倍。使用椭圆曲线加密技术节省服务器和浏览器的时间、能源和计算资源，帮助我们实现更快更安全的网络。

缺点

椭圆曲线并不是完美无瑕的，存在一些问题和不确定性阻碍工业界每个人都接受它。

最近在新闻上被爆出的是双重椭圆曲线确定性随机比特生成器（Dual_EC_DRBG）。这是由美国国家标准与技术研究院（NIST）标准化的随机数生成器，由NSA推广使用。Dual_EC_DRBG使用椭圆曲线运算生成随机数。这个算法需要在曲线上获取两个点，然后多次执行椭圆曲线的“dot”操作。发布以后就被报道说它可能被设计留有后门，意味着返回的随机数序列可以被拥有正确密码数字的人完全预测出来。最近，RSA公司召回了一些它们的产品，就是因为其安全系列产品使用这个随机数生成器作为其默认伪随机数生成器。无论这个随机数生成器是否有后门，都不会改变椭圆曲线技术本身的优点，但是它确实引出了椭圆曲线标准化流程的问题。正如之前所写的那样，也应该确保你系统使用足够随机的数字的原因之一。在未来的博客中，我们会讨论后门是如何混入该算法的规范。世界上有一些持怀疑态度的密码学家普遍不信任NIST本身和其发布并被NSA支持的这些标准。几乎所有已实现的椭圆曲线都属于这个范畴。目前并没有针对这些特定被选为计算高效的曲线的攻击事件，但是不好的曲线确实存在，安全比道歉更好。有一些非NIST的计算高效的曲线正在开发中，包括Daniel Bernstein（djb）发明的曲线25519，和最近由Paulo Baretto和合作者计算出的曲线，但是广泛使用这些曲线还需要几年的时间。除非浏览器实现这些非传统曲线，否则它们不能在网络上被用于安全的加密传输。

另一个关于椭圆加密技术的不确定性是专利。黑莓公司（通过2009年收购Certicom获得）拥有超过130个特定用途的椭圆曲线专利。很多这些专利被授权给私人企业甚至是NSA使用。这让一些开发者暂停了他们ECC实现，因为不确定是否侵犯了这些专利。在2007年，Certicom诉讼索尼公司侵权使用一些椭圆曲线，但是在2009年被撤回了。现在有很多不会侵犯这些专利的椭圆曲线加密技术被广泛使用。

ECDSA数字签名相比于RSA有一个缺点，它需要一个好的熵的来源。没有良好的随机性，私钥可能被泄露。Android上的随机数生成器缺陷让黑客与2013年发现了几个人用来保护比特币钱包的ECDSA私钥。索尼的Playstation的ECDSA实现也有类似的漏洞。电子签名需要一个良好的随机数产生源。不推荐使用Dual_EC_DRBG。

展望未来

尽管有上述这些问题，但是椭圆曲线加密技术优于传统的RSA事实还是被广泛接受。很多专家担心RSA和Diffie-Hellman背后的数学算法可能在5年之内被破解，那么ECC就是唯一可用的选择了。

所有现代浏览器都支持椭圆曲线，并且大多数证书颁发机构都提供椭圆曲线证书。每一个通过现代浏览器的发起的对受CloudFlare保护的网站的SSL连接默认都是使用ECC。很快，CloudFlare将会允许客户上传自己的椭圆曲线证书。这将会使得ECC即被用于身份验证又被用于加密传递的消息，全面加速HTTPS会话。当功能可用时还会有更多好处。