量子计算之于密码学，是威胁还是救赎？ | 《腾云》65期精选
现如今，密码在工作生活中发挥着越来越重要的作用，登录账户、快捷支付、网上转账收账，都需要它的参与。试想一下，如果某天我们的密码被不怀好意的人获取，会带来什么样的后果呢？还有一个值得思考的问题是，现在的加密技术真的已经无懈可击了吗？
其实，量子计算的发展就有可能让现有的加密技术失效。而我们对此束手无策了吗？牛津大学量子物理博士，腾讯公司欧洲首席代表葛凌，向我们解释了量子计算对现代密码学的威胁、量子计算到来的时间，以及最后我们还可能要利用量子力学来应对量子计算对现有密码学的威胁。
葛凌
牛津大学量子物理博士
腾讯公司欧洲首席代表
想想我们在自己的手机、笔记本电脑和台式机等不同的连接设备中存储的所有私人数据。这些私人数据包括健康状况这样的个人信息，银行账户的账号，各类地址，发给朋友和家人的私人信息，以及与公司业绩和财务状况有关的公司数据。这些数据被公之于众的话，对个人和公司来说很可能都是灾难性的。
我们怎样保护私人数据的安全？答案就在现代密码学——这是一种通过加密和解密，让保护储存的信息不被可能怀有恶意的第三方获取的方法。
然而，量子计算近期的发展已经使人们对这些现代密码学方法的永久安全性提出了质疑。可扩展的量子计算机可以执行一些算法，使我们能够打破目前在密码学中使用的部分加密方法——这将有可能把我们的私人数据暴露给第三方。因此，许多人预测，伴随着现实中量子计算机的到来，我们将在互联网上失去隐私。
而且，这种危险看起来正步步紧逼。就在去年，量子计算领域有加速之势，因为几家主要的科技公司，比如谷歌、英特尔和IBM，都宣布在量子硬件的研发上取得了显著的进展。一些人乐观预测，“量子霸权”（量子计算机超越经典计算机的临界点）将在2018年到来。
量子计算的发展是否真正威胁到在互联网上我们的数据的一些核心秘密？(更多背景知识，见059期《腾云》文章《我们为什么需要量子计算》)
1
肖尔算法：
量子计算革命的催化剂
1994年，美国麻省理工学院的彼得·肖尔（Peter Shor）发表了一篇论文，题为《量子计算机上的质因数分解和离散对数的多项式时间算法》（Polynomial Time Algorithms for Prime Factorisation and Discrete Logarithms on a Quantum Computer）。这篇论文被认为是一剂催化剂，催生了一场延续至今的建造量子计算机的竞赛。本质上说，通过使用量子平行处理，肖尔算法(Shor’s Algorithm)使量子计算机上的大整数的因式分解比在经典计算中使用已知最快的算法还要快出很多。更精确地说，肖尔算法差不多可以在多项式时间内因式分解N比特整数，与此相比，在经典计算中最有效的算法（称作广义数域筛法，缩写为GNFS）则差不多需要指数时间。这就预示着RSA方法——它的安全性极其依赖于经典计算机因式分解大数N所需的时间——会立即变得不堪一击，同样面临崩溃的还有互联网上公钥密码的主体部分。
在肖尔算法使用量子计算的性质之前，来自经典数论的一些结果已经被用来恰当地处理这个问题。肖尔算法的特别之处在于，它使用模运算中的周期性的概念——对我们要因式分解的数N进行模运算，一个数x必须被自身乘多少次a才能得出答案是1(也就是xa mod N =1)。直到这个周期最终将使我们对N进行分解。
确定这个函数的周期正是量子计算的性质发挥作用的地方，特别是准确地引入量子平行处理这一概念。我们使用两个量子存储寄存器——第一个被放置在所有a（a的范围是从0到q，其中q是2的指数倍，并且满足N2 < q < 2N2）的可能值的叠加态上。注意，这个寄存器必须有足够的量子比特来表示这个大小的整数，比如说，如果N是一个2048比特数（RSA模数的典型大小），那我们就需要大约4000个量子比特。在第一个寄存器中，会用到以N为模的函数xa，而结果会被存储在第二个寄存器中（在这一步中，我们利用了量子平行处理的性质）。
接下来，第二个寄存器会被测量，这意味着第二个寄存器从叠加态塌缩到某个值k。第一个寄存器也随之塌缩，和第二个寄存器保持一致——但是对a的每个值，进行相等的叠加使得xa mod N = k。最终，一个叫作离散傅里叶变换的运算被应用到第一个寄存器上，接着输出m就有很大可能性是这个周期的倍数。一旦得到m，在经典计算机上使用一些相关的简单数论就可以先找到这个周期，然后是N的因式分解。
当肖尔算法成为密码学（公钥）最直接的威胁时，其他一些已经发展起来的算法也对对称式加密产生冲击。特别是格罗弗算法(Grover’s Algorithm)，这种算法使得量子计算机的使用者只使用0.758 N0.5次运算就可以在N项列表中发现特定的一项。这又是一个量子计算允许的与直觉完全相反却又强有力的结果。来看看为什么。想象一下，我们有10000个盒子，并且随机地把一个物品藏在其中一个盒子里。如果我们让某个人去找到这个物品，那么他们将最多不得不打开所有10000个盒子才能确定找到这个物品（这个物品也许正好被藏在他们决定最后一个打开的盒子里）。平均来说，我们可能不得不打开盒子数量的一半才能找到被藏起来的物品，也就是找5000次。然而，使用格罗弗算法，我们实际上可以在0.758√N 次运算中就找到结果。在这个例子中，这意味着我们找75.8次（0.758 * √10000）就可以找到这个物品！
这种算法的力量与穷举搜索攻击有关。正如我们可以回想起来的，穷举搜索攻击就是检查每一个密钥的单值来看看那个密钥是否解码了一条信息。使用格罗弗算法，我们可以极大地加速穷举搜索攻击的过程——例如对于一个长度为128比特的密钥来说，使用格罗弗算法的话，一次穷举搜索攻击可以在 √2128 = 264次内完成。同样，一台可以运行格罗弗算法的量子计算机将意味着某些标准的密钥长度需要增加，特别是AES 128比特不再被认为是安全的，而是需要AES 256比特的密钥。
2
量子计算：
影响是什么？何时到来？
RSA算法并不是今天使用的唯一一种公钥密码学方法——其他两种主要的方法是迪菲—海尔曼（Diffie Hellman）算法和被称为椭圆曲线密码学的一组方法，这组方法利用了数学的单向函数的类似用途。然而，根据肖尔算法，所有这些方法都是易受攻击的。在下面的表格里，美国国家标准与技术研究院（NIST）归纳了量子计算带来的影响。
如果不去应对这些挑战，对我们在互联网上的数据来说，量子计算机的发展将意味着灾难性的安全丧失。数字签名确认我们是谁，密钥交换协议管理网页浏览器和服务器之间的安全，它们都会变得不再安全，而且在互联网上我们也不再能够安全地进行很多我们今天想当然认为是安全的活动。例如，输入账户信息去购买产品或者服务，收发私人邮件，保守商业数据的秘密，信任我们在互联网上浏览的网页的内容——所有这些事情都变得不可能。
一个很自然的问题是，我们距离一台有能力大规模运行肖尔算法或者格罗弗算法的量子计算机有多远呢？目前，在建最强大的通用量子计算机的数量级在50-72个量子比特之间。而正如我们在讨论肖尔算法时看到的那样，一台量子计算机大概需要4000个逻辑量子比特才能因式分解一个2048比特的RSA数。
对以上的一个解释也许是，实际上我们并不处在建造一台有能力打破目前公钥密码学的量子计算机的中期阶段（例如2-5年）内。执行肖尔算法所需的量子比特的数量，远远超过今天我们制造的最强大的量子计算机的能力，而且肖尔算法大规模的可靠的应用还没有被展示出来。今天，我们并不清楚诸如量子比特的退相干，和管理噪声以减少量子系统中的差错等面临的挑战能否被解决。正因为如此，在短期或者中期内建造这样一台可规模化的扩展的量子计算机似乎不太现实。
然而，放眼较长的时间（5-20年），忽视量子计算机对于目前的现代密码学标准的威胁将会是错误的。正如美国国家标准与技术研究院的描述：“一些人预测在接下来的20年左右，足够规模的量子计算机会被制造出来，基本上可以打破目前使用中的所有公钥方案。在历史上，我们花了差不多20年时间去配置现代公钥密码基础架构。因此，不论我们能否准确估计量子计算时代到来的时间，我们都必须现在开始准备我们的信息安全系统，使之能够对抗量子计算。”
3
后量子密码学
和量子保密通信
那么，在量子计算被引入后，密码学看起来是怎样呢？这里有两条路径——后量子密码学和量子保密通信。
后量子密码学
后量子密码学以数学方法为基础定义了一系列新的密码学标准，其中主要是针对公钥密码学。这些方法很强大，足以抵挡来自量子计算机的攻击。美国国家标准与技术研究院已经开始着手实施一项计划来发展这些新的标准。他们将通过一个阶段性的招标流程，收集学术界和工业界对新的密码算法的建议。2018年4月，这个机构组织的一次会议，讨论了第一阶段提交的建议。然而，标准草案可能在2022-2024年才会被提出。下面介绍一些有潜力的新方法。
基于格点的密码 (Lattice Based Cryptography)——格点是N维空间中带有周期性结构的点集，它和N维的有斑点图案的壁纸有些相似。某些数学上的格点问题被认为解决起来非常困难，比如最短向量问题（Shortest Vector Problem），就是给定一个特定的基矢，然后找出一些最短的非零向量。这样的格点问题已经被用来作为构建一些密码学方法的基础。一项正在研究的方法叫做NTRU，它于1996年被提出，使用12881比特的密钥去提供标准的128比特密钥长度具有的安全性。在第一阶段中，众多提交给美国国家标准与技术研究院的方案都是以NTRU的变体（例如NTRU Prime）为基础，这些方法具有在效率和安全性之间提供一种优质平衡的潜力。
基于编码的密码 (Code Based Cryptography)——这类方法是以纠错码为基础的加密系统，最早于1978年被提出，目前已经发展起来，其中最著名的是麦克利斯（McEliece）算法。这些算法以解码线性代码的困难为基础，算法中的私钥与一个纠错码相联系，公钥与加扰版本相联系。这些类型的加密方案的密钥长度往往会长一些，因此令人不免对它们的效率有些担忧（如果密钥长度太长，它的储存和交换会占用相当多的资源）。
多元多项式 (Multivariant Polynomials)——在有限场上包含多变量多项式的数学问题已经被建议用来作为新的加密方法的基础。研究人员已经在这个领域内做出几项尝试，意图建立新的加密方法。然而，由于用到的数学复杂度较低，有些方法已经被证明不安全。还有继续进行的研究关注这些方法是否可以被数字签名所采用。
基于哈希的签名 (Hash-Based Signatures)——这是一种提供数字签名的方法，其中的数字签名来自一种叫作哈希函数的数学函数的复用。在今天的互联网上，哈希函数已经作为鉴别码（MAC’s）的一部分而被广泛地使用和理解。这些方法通常有小的私钥和公钥，签名生成都很快，但是密钥生成相对较慢。
一个基于哈希签名的方案是XMSS，它在2018年6月1日成为在互联网工程任务组（IETF，该组织管理互联网上的开放标准）中发表的第一个后量子签名方案。这份文件的作者强调，“在面对量子计算机时，他们对这个签名方案的密码安全性有信心……同时，互联网上重要部分的安全性也可以依赖于这个方案”。
以上的这些方法依赖于一个相似的方法——它们都使用被认为是非常困难的数学问题作为自身安全性的基础（与RSA类似）。把量子计算的发展先放到一边，如果一个数学家能够发展一种新的数学方法或者技术，可以解决这些“困难的问题”中的一个，比如说大整数N的因式分解，那基于这个问题的加密系统的安全性就只能让步。2017年2月，著名的以色列密码学家阿迪·沙米尔（Adi Shamir）表示：“在我所担心的事情中，量子计算机并不是排在首位的，我认为更有可能发生的是RSA因为一次数学攻击而崩溃”。因式分解是RSA的基础，这个问题至少在几个世纪里被很多伟大的数学家广泛研究过，不过仍然没有被解决。
然而，对于更新的数学挑战而言，比如支撑某些后量子加密系统的数学问题，我们可能需要更长一些的验证周期，才能使这个方法成为一个合适的标准并对它充满信心。或者，量子保密通信这样崭新的概念，可能会使得用高深莫测的数学问题来为密码学服务的观点显得有些多余。
量子保密通信
在量子计算时代里，第二种实现安全的方法被称作量子保密通信。它使用了量子力学本身的性质来确保通信的安全，尤其是通过量子密钥分配（QKD）。其洞见就在于，与其使用数学问题来确保安全，我们更应该使用量子力学的性质来达到目的，其中最值得注意的是量子不确定性和量子纠缠这两个概念。这里有两个主要的被推荐的协议——Prepare & Measurement (P&M)协议和纠缠(Entanglement)协议。
P&M协议使用海森堡不确定性原理——对一个量子态的测量将会以某种方式改变那个状态。这个概念就是BB84协议背后的思想，该协议由查尔斯·本内特（Charles Bennett）和吉列斯·布拉萨德（Gilles Brassard）于1984年提出。在这个系统里，我们用单光子的极化来传输信息比特，其中接受者和发送者使用极化的方向来确定被传输的比特是0还是1。这种方法的安全性来自于这样一个事实，即如果一个窃听者拦截并且试着看被传输的光子的数值，他们就会以某种方式干扰光子的模式，而这种干扰在消息的传输之后是可以被测量到的。我们可以用这种方法建立共享密钥，因而解决了最早给公钥密码学以灵感的这个难题。
理论上这样一个基于量子原理的系统是安全的，然而实际操作上，量子密钥分配的物理实现曾经被破坏过，也就是在发送者或者接受者不知情的情况下密钥被拦截过。同时还要注意，在实践中，光子在最佳光缆上的实际物理传输也会不可避免地持续向系统中引入误差，因此在现实中，一个估计的误码率必须和实际的误码率相比较，以确定是否有传输达不到标准从而提供了较低的安全水平。从技术上讲，发射单光子是很有挑战性的，因此我们使用发射多光子的激光，但这也使这个系统容易遭受光子数分束（PNS）攻击的影响。在光子可以传输的距离上同样也存在限制——使用标准光缆的话，目前距离上限大约是100千米，在这个范围内量子密钥分配的方法是可行的。目前的数据传输速率也很低，在比较短的距离上，每秒几百比特是有代表性的速率。不过，即便存在这些挑战，一些实用的、具有商业可行性的量子密钥分配系统还是已经成功落地，现在一些机构（例如一些瑞士及中国的银行）正在用这样的系统进行密钥交换。
量子密钥分配机制的第二种类型是基于纠缠协议，由阿图尔·埃克特（Artur Ekert）最早在1991年提出。在这种被称为E91的方法中，一个单独的源发射一对发生量子纠缠的物体，例如一对极化的光子，比如给爱丽丝和鲍勃，其中一个给爱丽丝，另一个给鲍勃，而他们两个人在地理位置上是分开的。由于纠缠的性质，如果爱丽丝和鲍勃都以某种方式测量这个极化的话，光子会得到相反的结果（例如，爱丽丝测到的是+1，鲍勃测到的是-1）。通过彼此结果相反的光子对中的一个光子，爱丽丝和鲍勃就可以得到一个共享密钥。
针对窃听的保护通过使用一个叫作贝尔不等式（Bell’s Inequality）的不等式来完成——根据量子物理的性质，如果粒子保持真正的纠缠，也就是没有被一个窃听者拦截，那这个不等式就不成立。
纠缠作为一种量子密钥分配的实验方法一直是研究的热点。值得注意的是，2017年6月，由中国科学技术大学的潘建伟领导的团队成功演示了光子之间的纠缠。这些光子由在轨道上的卫星发射，而被位于地面上的基站测量，卫星与基站之间相距1200千米。虽然每600万个从卫星发射的光子中只有1个能够被基站探测到，目前实现量子密钥分配还不足够，但是这个实验受人瞩目之处在于它证明了“鬼魅般的超距作用”——爱因斯坦如此描述量子纠缠。这个团队未来的研究计划包括通过更长的光子流分发实际的量子密钥到中国的基站。
4
量子力学将可能挽救
现代密码学
人类不同个体之间希望保持信息的私密这一愿望，同语言本身一样古老，而这个愿望所面临的最根本的挑战也存在了相同长的时间。两个人如何商定一个安全的沟通方法，比如说给物品以特别的词语或代号，或者某种共享密钥，使得双方可以彼此理解对方的意思，但是第三方却做不到？伴随着数字技术对我们生活的方方面面的侵入，这些问题之于我们自身安全感的重要性无疑在增加——现在我们想使我们的隐私不被我们的各类连接设备触及几乎不可能，因此正确地保护信息的安全就变得非常重要。
现代密码学已经发展出有效、安全的标准和方法，来促进人与人之间对信息的共享，但是这种共享仍然有其脆弱性。一方面，尽管量子计算机的发展似乎在短期内可能性较低，但是却也使重新考虑和加强这些标准成为必要。快速完成美国国家标准与技术研究院提出的旨在发展安全的后加密算法的计划是非常重要的，从而安全地升级目前网络协议的安全性。另一方面，继续信赖困难的数学问题作为加密系统的基础，限制了我们对这些系统充满十足的信心——因为当明天我们醒来的时候，一位聪明的数学家可能已经很好地解决了这些问题。
于是，量子保密通信提供了一种有力的保证，利用量子力学的固有性质来保障安全性，克服了现代加密方法面对数学攻击时的脆弱性。量子密钥分配，例如来自卫星的纠缠极化光子，通过量子纠缠和海森堡不确定性原理这样的基础量子物理原理来保护通信免于遭到窃听。它的愿景极具吸引力，并且已经开始实验验证。
所以，尽管现代密码学受到来自量子力学的威胁，但最终挽救它的可能也是量子力学。
感谢您关注和支持《腾云》，第65期限量赠阅开放申请中，敬请点击阅读原文填写相关信息，即有机会获赠本期《腾云》。
小编说
密码已与我们的工作生活密不可分，密码的泄露就意味着个人隐私的泄露，你觉得个人应该如何保护自己的隐私呢？欢迎留言告诉我们~
本期主要内容
徐可 腾讯科学家刘霁：开发游戏AI不仅是为了人类玩家体验更爽
张翔/钱坤 张翔：应从宪法高度提出个人信息保护整体方案
王新锐/罗为 Facebook信息泄露事件分析及启示
张玥 隐私悖论：用户到底有多理性？
赵嘉敏 需要“隐私”，是人类的天性吗？
葛凌 量子计算之于密码学，是威胁还是救赎？
埃里克·希尔根多夫 当今欧洲与德国的数据保护
蔡雄山 我们真的搞明白GDPR了吗？
杨舒蕙 艺术与科技的迷思
方可成 新闻的未来：全面适应你的个性化需求？
丨 相关文章