这篇博客文章展示了一个我们开源的新密码原语：p751sidh。量子威胁今天的大多数密码学都被设计成能够抵御具有巨大计算能力的对手。这意味着估计某些计算（如分解一个数或求一个离散对数）所需的工作量，并根据我们对破坏系统所需工作量的最佳估计来选择密码参数。如果有可能建造一个大规模的量子计算机，那么许多我们所依赖的安全问题将不再难以解决。尽管大规模量子计算机是否可能实现（请参阅本文以获得良好的概述），但开发量子抵抗（或后量子）密码术的广泛兴趣是一个足够大的风险：在我们今天拥有的普通计算机上工作的密码术，但它对于可能的量子计算机是安全的。在Cloudflare，我们对加密技术的最大用途是TLS，它既用于为客户的网站服务（所有Cloudflare站点都可以获得免费的HTTPS），也可以用于后端的内部数据中心间通信。在TLS上下文中，我们希望在客户机和服务器之间创建一个安全的连接。这里基本上有三个密码问题：真实性：服务器需要向客户端证明它是真实的服务器（也可以选择向服务器证明它是真实的客户端）；密钥协议：服务器和客户机需要通过不安全的连接，就只有他们知道的临时共享机密达成一致；对称加密：服务器和客户机需要使用它们的共享密钥来加密它们希望通过安全连接发送的数据。真实性可以防止主动攻击者，但由于量子计算机还不存在，主要风险是追溯攻击：例如，一个国家的对手（简称"NSA"）可以记录加密流量，等待构建量子计算机，并尝试解密过去的流量。此外，量子算法对对称加密似乎只有很小的加速，所以要解决的"密钥"问题是#2，量子抵抗密钥协议。这是一个活跃的研究领域，无论是在新密码系统的设计及其实现和部署。例如，去年，Google在Chrome中完成了一项使用基于晶格的密钥交换的实验。基于格的密码体制是一个非常有前途的量子抗算法家族。它们的安全性依赖于研究得很好的计算问题，而且计算效率很高。但是，它们有大的密钥大小，并且需要额外的通信（这可能需要在TLS之类的协议中进行额外的往返）。另一类密码系统是超奇异同系系系统，特别是超奇异同系异源Diffie-Hellman（SIDH）。与基于晶格的系统相比，它们依赖于更奇异的计算问题，并且计算成本更高。但是，它们的密钥大小要小得多，并且不需要额外的通信：SIDH完全符合tls1.3的密钥协商机制。tls1.3是TLS协议的最新版本。今年夏天，我在Cloudflare工作，为tls1.3的量子抗性版本做了一个实验，使用了一个混合密钥协议，该协议结合了X25519和超奇异同系异源Diffie-Hellman（SIDH）。为了实现这一点，我在Go中实现了一个tls1.3客户端（作为Cloudflare TLS tris的一部分），在amd64架构中实现了SIDH，并将SIDH实现与tls1.3密钥协商机制相结合来执行一个抗量子的tls1.3握手。这扩展了Microsoft Research先前关于TLS1.2的基于SIDH的密钥交换的工作，讨论如下。TLS 1.3中的Diffie-Hellman密钥协议在TLS的最新版本TLS1.3中，密钥协商机制（第2部分）与身份验证机制（第1部分）完全分离。TLS1.3使用Diffie-Hellman进行密钥协商，通常使用椭圆曲线组。在深入研究量子抗性版本之前，让我们回顾一下Diffie-Hellman（DH）是如何工作的，以及它在tls1.3的上下文中是如何工作的。在Diffie Hellman，我们有两个政党，爱丽丝和鲍勃，希望建立一个共同的秘密。它们固定了素阶p的交换群G，并加成了G的生成元p（基点）。Alice然后选择[0，p]范围内的一致随机整数a。这决定了一个映射的乘法运算，通常表示为[a]：G->G。Alice计算[a]P，她映射下的基点的图像，并将其发送给Bob。类似地，Bob在[0，p]范围内选择一个随机整数b，确定映射[b]，计算[b]p，并将其发送给Alice。Alice和Bob同意共享秘密[ab]P，Alice计算为[a]（[b]P），Bob计算为[b]（[a]P）：（这里我用地图来描述这个过程，以便稍后显示与SIDH的相似之处）。在TLS1.3上下文中，其工作原理如下。客户端通过发送TLS ClientHello消息来启动连接，该消息包含（除其他数据外）客户端支持的DH组的列表，以及这些组中某些（或全部）的"密钥共享"（即[A]P值）。服务器选择服务器和客户端都支持的DH组之一。在正常情况下，服务器选择客户机为其提供密钥共享的组，并发回一个包含服务器密钥共享的ServerHello消息。从这一点开始，客户机和服务器之间的所有握手消息（如证书、扩展等）都使用从密钥共享派生的"握手机密"进行加密。（在不愉快的情况下，如果客户机没有提供可接受的密钥共享，服务器会要求客户机重试，强制执行额外的往返）。应用程序数据随后使用从握手机密中派生的密钥以及其他数据进行加密，因此应用程序数据的安全性取决于密钥协议的安全性。然而，TLS中现有的DH群都容易受到量子算法的攻击。超奇异同系异源Diffie-HellmanSIDH是由lucadefeo和davidjao于2011年提出的，是一个相对较新的使用椭圆曲线来构建量子抗性Diffie-Hellman方案的建议。粗略地说，SIDH并不是在单个椭圆曲线组中工作，而是在一系列相关的"类同源"椭圆曲线中工作。同系是椭圆曲线的一个映射phi:E_1->E_2，它将源曲线E_1的单位元素发送到目标曲线E_2的单位。结果是，对于每一个同系系phi:E_1->E_2，都有一个双重同系psi:E_2->E_1，所以我们可以说这两条曲线是同构的，如果它们是由一个同系系系连在一起的。现在我们可以考虑一个同系图，它的边是同系图，顶点是椭圆曲线。Alice和Bob没有选择秘密的乘-n映射在一条椭圆曲线内移动，而是选择秘密的同素在一系列同构曲线内移动（即，他们选择一条穿过等代图的随机路径），而系统的安全性与计算任意曲线间等值线的难度有关。结果图稍微复杂一些，但在结构上与上面的图相似：这到底是怎么回事？起始曲线E_0以及点P_A、Q_A、P_B、Q_B是系统参数。同系系唯一地由它的核决定（源曲线上的点的子群，它映射到目标曲线的同一点）。爱丽丝选择秘密标量m_A、n_A、n_A，决定一个秘密点[m_A]P_A+[n_A]Q_A，产生核心子群的核心子群，并由此确定她的秘密同系异系系系phi_A A，爱丽丝在点P_B、Q_B处对phi_A进行评估，并将E_A、phi_A（P_B）、phi_A（Q_B）、phiu A（Q_B）发送给鲍勃，鲍勃，鲍勃，发送E_A、phi_A（P_B）、phiu A（Q_B）给鲍勃，Bob，Bob，在，谁做了相同的步骤与A和B交换。接下来，Alice使用E_B、phi_B（P_A）、phi_B（Q_A）等E_B、phi_B（Q_A）来构建一个同系同系phi_A，其中内核，而Bob则使用E_A、phi_A（P_B）、phi_A（Q_B）来构造同系系系phi\ub）的同系系系phi\Ub B与内核。现在phi'''u A映射到曲线Eüu AB，而phi''u B映射到曲线EüBA。曲线E峎AB和E_BA是同构的。因为椭圆曲线是用一个叫做j不变量的数来分类的，j（E_AB）=j（E_BA），这是Alice和Bob之间的共同秘密。关于这一过程的详细技术解释可以在Luca De Feo、David Jao和Jérôme Pl廑t对SIDH论文的扩展中找到（上图是该论文的图1），Luca De Feo在这篇文章中可以找到关于火箭飞船穿越超奇异时空的解释。另外，这里有一段Deirdre Connolly在2017年2月Cloudflare加密会议上的讲话录音。2016年，Microsoft Research的Craig Costello、Patrick Longa和Michael Naehrig发表了一篇关于SIDH高效算法的论文，将高速ECC的优化技术应用到最初的SIDH提案中。他们还发布了一个用C和assembly编写的固定时间的优化实现，以及一个OpenSSL的补丁来为tls1.2创建SIDH密码套件。我的Go实现基于他们的工作（算法和代码），如下所述。Go TLS中的SIDH密钥协议p751sidh包中的SIDH实现有两个部分：包含SIDH功能的外部p751sidh包和提供低级功能的内部p751toolbox包。由于SIDH是在一个大的有限域中实现的，因此域算法的性能对协议的性能至关重要。不幸的是，这需要编写程序集，因为在Go中编写高性能的算法是不可能的——这根本不是语言的设计目标。最明显的是，有很少的原因可以直接计算64位的积该代码部分源于上面提到的Microsoft Research实现。特别地，将域算法移植到fr