一个关于椭圆曲线密码学的初级读本

今天药忘吃喽~ 2022-09-25 10:18 167阅读 0赞

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][213610us3zh9ltye3mfje8.png]

> 作者Nick Sulivan在最近加入CloudFlare之前作为一个系统工程师为苹果公司效力了6年，他的许多最重要的密码学成就是在那时造就的。他有一个滑铁卢大学的数学本科学位和一个卡尔加里大学的专攻密码学的计算机科学硕士学位。这篇文章最初登在 CloudFlare blog 网站，然后被简易编辑后出现在Ars网。  
>   
> 读者被提醒椭圆曲线密码学（ECC）是一套加密和解密数据的算法和交换的秘钥。Dual\_EC\_DRBG是被怀疑包含一个被国家安全局设计的后门程序的密码学标准，这是一个用椭圆曲线密码学生成一串随机数字的函数。这个初级读本已经存在了两个月在国际公认的密码学家呼吁全世界的同事采用ECC来避免一个可能“密码学大灾难”之后。

ECC是一个最强大的但最难懂的密码学类型在广泛应用的今天。越来越多的网站广泛使用ECC来保证一切从客户的HTTPS连接到他们数据中心之间的数据传递的安全。从根本上，为了信任安全系统，终端用户了解它背后的技术是很重要的。为了那个目的，为了和我们的用户分享，我们四处查找一个很好的，相当易懂的ECC初级读本。但没有找到，所以我们决定自己写一份。即下列所述。  
  
警告：这是一个复杂的主题，把它写成一个精简的博客博文是不可能的。换句话说，我决心写一篇有点宏大的文章，因为它覆盖很广。如果你只想得到要旨，这是摘要版本：ECC是基于当前已明白的数学的下一代的公钥密码学。这提供一个比前一代公钥密码学系统(如RSA)更安全的基础。如果你担心在维护性能时保证最高水平的安全，那ECC有理由被采用。如果你对细节感兴趣，继续读下去。  
  
公钥密码学的黎明  
  
密码学的历史可以分成两个时代：传统时代和现代。两个时代的转折点发生在1977年，当RSA algorithm和Diffie-Hellman秘钥交换被引进时。这些新的算法是革命性的因为他们代表第一代安全基于数论的切实可行的密码学方案；这也是第一次使没有共享秘钥的双方能够安全通讯的方案。密码学从全世界传输密码电报到已证明能够在不用担心某人窃听密钥交换的双方安全通讯。

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214205wzsll5wr6zlolzg4.jpg]

现代密码学被建立在一个理念之上，这个理念是你用来把你的数据译成密码的钥匙可以公之于众在解译你的数据的钥匙能被保持私有的时候。同样的，这些系统被称为公钥密码学系统。首先，这些系统里最广泛被应用的被认为是RSA——用第一个公开描述这个算法的三个人名字的首字母命名，这三个人是：Ron Rivest，Adi Shamir，和Leonard Adleman。  
  
你需要一个公钥密码学系统来运行的是一套容易单方向处理但很难破解的算法。至于RSA,这个容易的算法乘以两个质数。如果乘法是简单的算法，它的困难度一对算法是把乘法的结果因式分解成两个质数。有一个方向容易，另一方向难的特性的算法被称作trapdoor函数。找到一个好的trapdoor函数对造一个安全的公钥密码学系统是很要紧的。简单来说，在一个trapdoor函数中运转一个方向和另一个方向间的难度之间传播难度越大，基于此的系统就将会越安全。  
  
一个玩物似的RSA算法  
  
RSA算法是最流行的和最被了解的公钥密码学系统。它的安全性依赖于因式分解是缓慢的和乘法的快速的这个事实。下列所述是一个关于小RSA系统看起来像什么和它如何工作的快速演练。  
  
总之，一个公钥加密系统有两部分，一个是公钥，一个是私钥。加密通过信息传递运行和应用一个数学运算来得到一串随机号码。解码采用这组随机号码并且应用一个困难的运算来退回原来的号码。有公钥的加密只能被有私钥的解码解开。  
  
计算机用杂乱无章的大量号码无法很好工作。我们通过选择最大数能确保我们处理的数不会变得太大并且仅处理那些小于最大数的数字。我们能处理那些像模拟时钟上的数字。任何产生一个比最大数大的数的计算要超限折返一个有效范围内的数。  
  
在RSA里，这个最大值（叫max）可通过乘以两个随机数得到。这个公钥和私钥是两个专门挑出来的大于零小于最大值的数字（叫pub和priv）。把一个数字译成密码，你用它乘以它自己pub次，确保超限折返当你撞上最大值。解码一个信息，你用它乘以它自己priv次，你得到原来的数字。这听起来令人惊讶，但这确实起作用。在被发现时这个性质是一个大突破。  
  
为了创造一个RSA秘钥对，首先随机挑选两个质数来获得最大值（max）。然后挑选一个数作为公钥pub。只要你知道两个质数，你就能从公钥中计算出一个相应的私钥。这是如何因式分解分开RSA——把最大的数因式分解成它的组成质数允许你从一个公钥中来计算某人的私钥和把解码他们的私人信息解码。  
  
举一个更具体的例子。取质数13和7.它们的结果给我们的最大值为91.我们取5为公钥。然后用我们已知的事实7和13是91的因子并且应用一个叫延伸欧几里得算法的算法，我们得到私钥是29.  
  
这些参数（max:91,pub:5,priv:29）定义一个充分实用型RSA系统。你能取一个数字并且用它乘以它自己5次来加密它，然后取那个数字并且用它乘以它自己29次然后你得回了原来的数字。  
  
用这些标准来加密信息“CLOUD”.  
  
为了用数字表示这个信息，我们要把字母转换成数字。拉丁字母表的通常代表是UTF-8.每个字母相当于一个数字。

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214251x9k4kittebte7x4l.png]

在这次编码下，CLOUD是67,76,79,85,68.每个这些数字小于我们的最大值91，所以我们可以单独地加密它们。让我们开始第一个字母。  
  
我们要用它乘以它自己5次来得到加密的值。  
  
67×67 = 4489 = 30 \*  
  
\*因为4489大于最大值，我们要超限折返。 我们把它除以91然后取余数。  
  
4489 = 91×49 + 30  
  
30×67 = 2010 = 8  
  
8×67 = 536 = 81  
  
81×67 = 5427 = 58  
  
这意味着67（或C）的加密值是58.  
  
对每个字母重复这个过程，我们得到加密信息CLOUD变成：58,20,53,50,87  
  
要解密这个加密形式的信息，我们取每个数字并用它乘以它自己29次：  
  
58×58 = 3364 = 88 (记住，我们超限折返在数字大于max时.)  
88×58 = 5104 = 8  
…  
9×58 = 522 = 67  
  
瞧，我们回到了67。用剩余数字运算，产生原来的信息。  
  
要点是你能取一个数字，用它乘以它自己若干次得到一个随机数，然后用它乘以他自己一个机密次数得回原来的数字。  
  
没有一个完美的trapdoor。  
  
RSA和Diffie-Hellman是如此强大因为他们伴随严格的安全证明。作者证明破坏这个系统相当于解决一个公认很难的数学问题。因式分解是一个很出名的问题并且从古代开始一直被研究。（看这个爱拉托逊斯筛法）。任何突破将会是一个重大新闻并且发现者将赚得大笔意外之财。

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214346i46866fxu5945ulw.jpg]

即便如此，因式分解在位对位基础里不是最难的问题.特殊的算法像两次筛法（Quadratic Sieve）和普通数域筛法 （ General Number Field Sieve ）被创造出来解决素因子分解问题并且是比较成功的。这些算法更快并且比仅仅猜测已知的质数对那种天真的方法更少计算上的加强。  
  
这些因式分解算法随着被因式分解的数字变得越大而变得越有效率。因式分解大批数字和乘以大批数字的难度的差距随着数字（即秘钥的字节长度）变大而缩小。随着有效解码数字的资源增加，秘钥的大小必须更快增长。对限制计算能力的手机和低功率设备来说，这不是一个可持续的情况。从长期来看，因式分解和乘法的差距是不可持续的。  
  
所有这一切意味着RSA不是理想的系统对将来的密码学来说。在一个完美的trapdoor函数里，对于数字大小的问题，简单方法和困难方法都一同样的速率变难。所以我们需要一个基于更好的trapdoor的公钥系统。  
  
椭圆曲线：一个更好的trapdoor的构建区  
  
在引入RSA和Diffie-Hellman后，研究人员探寻另外的基于数学的密码学解决方案寻找其他超越因式分解、充当好trapdoor函数的算法。在1985年，加密算法被提议以一个叫椭圆曲线的数学奥秘分支为基础。  
  
但到底什么是一个椭圆曲线和这个优先的trapdoor函数是如何工作的？不幸的是，不像因式分解——那些我们在中学就学过的东西——大多数人对这个有关椭圆函数的数学不熟悉。这个数学不是那么简单，也没有解释它，但我将要在下一节把它复习一下。（如果你的眼神开始呆滞，你可以跳过标题为“这一切意味着什么。”的章节。）  
  
一个椭圆曲线是满足一个特殊方程的点集。一个椭圆曲线方程看起来有点像这个：y2 = x3 + ax + b  
  
这个图形看起来有点像露露柠檬贴在包装侧面的商标：

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214436s2x0blmtm11q2xh1.png]

也有其他椭圆曲线的代表，但学术上一个椭圆曲线是一个满足一个变量为二阶，另一个变量为3阶的二元方程。一个椭圆曲线不仅仅是一个漂亮的图片，它也有一些使它成为密码学的一个好环境的性能。  
  
奇特的对称性  
  
靠近看上文标绘的椭圆曲线。它有几个有趣的特性。  
  
其中一个是水平对称。曲线上的任何点以X轴反射并且仍然是同样的曲线。一个更加有趣的特性是任何不垂直的线穿过曲线最多有三个交点。  
  
让我们来把曲线想象成一个奇异的桌球游戏。取曲线上的任意两点并且把他们连起来；这条线与曲线有一个（译者：怎么感觉是两个以上）以上的交点。在这个桌球游戏里，你拿球从A射向B.当它撞上曲线，这个球向上反弹（它位于X轴以下）或者向下反弹到曲线的另一边。

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214514i5fjlwyngjfmfh5d.gif]

我们把球移向两点叫“打点（dot）”。曲线上的任意两点能被同时打点得到一个新点。  
  
A dot B = C  
  
我们也能同时做一串移动来用它自己反复“打点"。  
  
A dot A = B  
  
A dot B = C  
  
A dot C = D  
  
...  
  
事实证明如果你有两个点，一个最初的点用它自己打点n次到达一个最终点，在你只知道最重点时找到n和最初点是很难的。继续我们的奇异桌球比喻，想象一个人在一段任意时间里在一个房间里单独玩我们游戏。对他来说，他跟着上述规则来反复击球是容易的。如果一个人后来走进房间并且看到球最终的位置，即使他们知道这个游戏的所有规则和球的起点，在没有全程观察游戏直到球到达同一点的情况下，他们也不能算出球击打到那的次数。容易做，但很难解开。这就是一个非常棒的trapdoor函数的基础。  
  
Let’s get weird  
  
上文的简化曲线对观看和解释椭圆曲线的大体概念是非常好的，但这不代表用于密码学里的曲线看起来的样子。  
  
为此，我们不得不把我们自己限制在一个固定范围的数字像在RSA里的一样。而不是允许曲线上点的任何值，我们把自己限制在一个固定范围内的所有数字。当我们计算椭圆曲线的公式时（y2 = x3 + ax + b），在我们击打到最大值时，我们用同样的诀窍rolling over 数字。如果我们挑一个质数做最大值，这样的椭圆曲线叫做”基本曲线“并且有杰出的加密学性能。  
  
这是一个以所有数字标绘的曲线的例子：

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214708rpn9z3hjo6z6v39k.png]

这是只用代表最大值97的整数标绘的同一曲线：

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214729t0hhla1y88quftl1.png]

以传统观念来看，这看起来几乎不像一个曲线，但它就是。这就像被折回在边缘的原始曲线和只有击打到的整数坐标被填色的曲线的部分。你甚至还能看到它的对称性。  
  
实际上，你还能在这个曲线上玩这个桌球游戏并且同时打点。曲线上一条线的方程任然有同样的特性。此外，打点操作能被有效的计算。你能设想在两点间有一条折回在边缘的线知道撞上一点。这就像，在我们的奇异桌球游戏里，当一个球打到桌子的边缘（max）并且然后用魔法把它运送到桌子的对面，继续它的路径直到到达一个点有点像贪吃蛇游戏。

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][214838iuneggurovjwowjv.gif]

用这个新的曲线表示，你可以获得信息和表示信息作为曲线上的一点。你能够想象获得一个信息并且把它设置为一个X坐标，并在曲线上得到y。这比在实践中略微难懂，但那是大体的概念。  
  
你得到这些点  
  
(70,6), (76,48), -, (82,6), (69,22)  
  
没有与65配合的x值；在现实世界里，这能够被避免。  
  
通过选取一个质数作最大值、一个椭圆方程、一个曲线上的公共点，一个椭圆曲线密码系统能被定义。一个私钥是数字priv，一个公钥是用它自己打点priv次的公共点。在这种密码学系统里，通过公钥计算私钥叫做椭圆曲线离散对数函数。这证明是那个我们寻找的trapdoor函数。  
  
这一切意味着什么？  
  
椭圆曲线离散对数算法是基于ECC最难的问题。即使将近30年的研究，数学家任然没有找到一个解决这个改进天真方法问题的函数。换句话说，和因式分解不同，基于当前已弄懂的数学，没有出现一个缩短在一个基于这个问题的trapdoor函数的差距的捷径。这意味着对于许多同样大小的数字，解决椭圆曲线离散对数算法是比因式分解难很多的。因为一个困难问题在计算上越强化意味着一个加密系统越强大，于是出现了椭圆曲线密码学系统比RSA和Diffie-Hellman更难攻破的结果。  
  
为了设想这有多难被攻破，Lenstra最近引进了“全球安全（Global Security）”的概念。你可以算出攻破一个密码学算法需要多少能量并把它与水沸腾需要多少能量对比。这是一种密码学的碳量排放。通过这次测量，破解一个228字节的RSA秘钥需要的能量少于煮沸一茶勺水的能量。相比地，破解一个228字节的椭圆曲线秘钥需要足够煮沸地球上所以水的能量。为此，RSA要达到一个安全的水平，你需要一个2,380字节的秘钥。  
  
用ECC,你可以使用更小的秘钥获得同水平的安全。小秘钥是重要的，特别是在一个越来越多的密码学方法应用在小功率设备（比如手机）的世界里。虽然同时乘以两个质数比把结果因式分解成它的因子要简单，但当质数开始变得非常长，甚至只是乘法步骤都要花费一段时间在一个低功率设备。虽然你或许能通过增加秘钥长度来延长保持RSA的安全性，但随之而来的是在客户端上更缓慢的密码学性能。ECC似乎提供了一个较好的权衡：使用短并且快的秘钥达到高安全性。  
  
椭圆曲线的运用  
  
在一个慢启动后，椭圆曲线基础算法获得普及，采用它的步伐正在加快。ECC现在被用于各种各样的应用：美国政府使用它保护内部通讯，Tor项目用它来帮助确保匿名，这是用于证明比特币的所有权的机制，这提供苹果iMessage服务的签名，这被用于与DNSCurve一起加密DNS信息，并且这是通过SSL/TLS协议验证安全网页浏览的首先方法。使用ECC来提供对网络隐私必不可少的完全转发保密（perfect forward secrecy）的网站越来越多。第一代密码学算法比如RSA和Diffie-Hellman在很多地方仍然是规范，但ECC正在快速成为网络隐私和安全的首选解决方案。  
  
如果你从最近的很多版本的Chrome或Firefox浏览器里访问HTTPS版本的Cloudflare博客，你的浏览器用的就是ECC.你可以自己来检查这个。在Chrome里，你可以点击地址栏的锁并且到连接标签可以看到建立这个安全连接用的是哪一个密码学算法。点击Chrome30版的锁出现下面的图像。

![一个关于椭圆曲线密码学的初级读本（相当容易懂)][215043b7g677u6hu66u7u9.png]

文章里讨论ECDHE\_RSA. ECDHE的相关部分代表Elliptic Curve Diffie Hellman Ephemeral，这是一个基于椭圆曲线的秘钥交换机制。这个算法在SSL里被网站用来提供完全转发保密。RSA元件（The RSA component ）意味着RSA被用来检验服务器的身份。用USA的网站使用它是因为他们的SSL证书一定要RSA秘钥对。现代的浏览器也支持基于椭圆曲线的证书。如果一个网站的SSL证书是一个椭圆曲线证书，这个页面会陈述ECDHE\_ECDSA. 服务器的身份验证将会用ECDSA（椭圆曲线数字签名算法）来做。  
  
这有一个ECDHE的简单ECC曲线。（这和谷歌用的是同样个曲线）：  
max: 115792089210356248762697446949407573530086143415290314195533631308867097853951  
curve: y2 = x3 + ax + b  
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948  
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291  
  
ECDSA的性能改善超过RSA是引人注目的，与一个没有最佳装配椭圆曲线代码的OpenSSL一样，一个有256字节秘钥的ECDSA签名比一个有2048字节秘钥的RSA签名快大于20倍。  
  
在一个用OpenSSL0.9.8的苹果笔记本里（MacBook Pro），“速度”基准收益：  
  
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倍。  
  
用ECC节省服务器和浏览器的时间，能量和计算资源，帮助我们更快、更安全地浏览网页。  
  
消极面  
  
椭圆曲线也不尽完美。这有一些问题和不确定性阻止它们被行业里的每个人信奉。  
  
最近新闻上提到了一点是Dual\_EC\_DRBG（双重椭圆曲线决定论随机字节发生器）。这是一个被美国国家标准协会（NIST）制定和并美国国家安全局（NSA）开发的随机数发生器。Dual\_EC\_DRBG利用椭圆曲线的数学生成随机数。这个算法包含在曲线上取点并反复在椭圆曲线上进行“打点”操作。在发表之后，据报道这可能已经设计了一个后门程序，意味着返回的数字顺序能被用正确密码的某人预测。最近，RSA公司召回几个它的产品因为它的安全产品生产线上的这种随机数发生器被设置为默认的伪随机数发生器。无论这种随机数发生器是否被写了后门程序都不会改变椭圆曲线技术本身的力量，但这引起了一些关于对椭圆曲线标准化加工的问题。这也是注意力应该被花在确保你的系统充分使用随机数的部分原因。  
  
世界上一些更多疑的密码学家普遍不信任美国国家标准协会（NIST）本身和国家安全局（NSA）支持发布的标准.几乎所有这些被广泛应用的椭圆曲线都归入这个范畴。没有已知的对这些被选为有效算法的特殊曲线的攻击，但坏的曲线也存在，还有其他的感觉安全点总比比事后后悔更好。美国国家标准协会（NIST）之外使用有效算法的发展中曲线取得了进步，包括被Daniel Bernstein (djb)创造的曲线25519和更多被Paulo Baretto and合作者创造的计算曲线。但离这些曲线的广泛采用还有几年时间。直到这些非官方的曲线被浏览器应用，它们将能够被用于互联网上的安全密码传输。  
  
另一个关于ECC的不确定性与专利有关。有超过130个专利，其中包括被BlackBerry拥有的椭圆曲线特殊用途（通过它2009年收购Certicom）。许多这些专利被批准用于私人组织乃至NSA.这使一些开发商停下来考虑是否他们的ECC工具侵犯了这个专利。在2007年，Certicom申请起诉索尼因为一些椭圆曲线的使用，但诉讼在2009年被撤销。现在有许多ECC工具被认为没有侵犯这些专利并且被广泛应用。  
  
ECDSA数字签名相比于RSA有一个缺点，它需要信息的好来源。没有适当的随机性，私钥能被透漏。安卓系统上的随机数发生器有一个漏洞允许黑客找到了被用来保护几个人的比特币钱包的ECDSA私钥在2013年早期。应用ECDSA的索尼游戏机有一个类似的漏洞。需要一个好的随机数来源在机器上产生签名。Dual\_EC\_DRBG不被推荐。  
  
展望未来  
  
与上述的警告一样，ECC的优势超过被广泛接受的RSA.许多专家担心RSA和Diffie-Hellman背后的算法可能被打破在五年以内。随着时间推移，ECC可能被留下来作为唯一的替代品。  
  
译者注：ECC即椭圆曲线密码学。“Let’s get weird”不会翻译请谅解。  
  
原文标题：A (relatively easy to understand) primer on elliptic curve cryptography，  
原文作者： Nick Sullivan ，  
原文发表时间：2013年10月25日,  
原文网址： [http://arstechnica.com/security/ ... curve-cryptography/][http_arstechnica.com_security_ ... curve-cryptography] ，  
若有错误，欢迎指正。  
如果这篇文章对你有所帮助，可以考虑向我捐赠bitcoin。  
我的地址：183mmDy8v8XGz1FZ2HtSeHSB4d2en8Cq81

[213610us3zh9ltye3mfje8.png]: /images/20220718/e3f914a53a5e4ab2901017821fa8db17.png
[214205wzsll5wr6zlolzg4.jpg]: /images/20220718/7e8a507b3762456da1ae3931c89367e8.png
[214251x9k4kittebte7x4l.png]: /images/20220718/7c40be3af31f44e79e9362818f97952c.png
[214346i46866fxu5945ulw.jpg]: /images/20220718/cdea27501eeb45b7b04489e008102611.png
[214436s2x0blmtm11q2xh1.png]: /images/20220718/d6c6ba9208df4e199d1575ecac4d774b.png
[214514i5fjlwyngjfmfh5d.gif]: /images/20220718/1f697c3eeaf34fdf9e1def5f501ea81e.png
[214708rpn9z3hjo6z6v39k.png]: /images/20220718/9a3b1cdcee634672af30bf519dbd45f4.png
[214729t0hhla1y88quftl1.png]: /images/20220718/f90eb8bebd864fb8a0d95d96ee813c83.png
[214838iuneggurovjwowjv.gif]: /images/20220718/6f52432f579941b7aa0afc0fde2ded7e.png
[215043b7g677u6hu66u7u9.png]: /images/20220718/c9315748547b4ce08f4349e800751594.png
[http_arstechnica.com_security_ ... curve-cryptography]: http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/