猫鼠游戏:加密技术如何对付量子计算机?|深度

雷锋网  •  扫码分享
我是创始人李岩:很抱歉!给自己产品做个广告,点击进来看看。  

编者注:你可能认为量子计算机还属于科幻范畴,但近几十年它就有可能变成现实,而其超强的计算机能力也会对现有的加密技术构成威胁。那有没有加密方法能抵御量子计算机攻击呢? 连线的这篇文章 就对此做了科普,并指出这不仅是技术问题,更需要安全与效率的平衡。雷锋网对全文编译如下:

今年8月的时候,美国国家安全局(NSA) 在其网页上更新了一段不起眼的内容 ,他们计划对现在政府和军方加密数据的方式更新,以期能够阻挡来自量子计算机的攻击。NSA的发言人表示,量子计算机能够带来更新更强的计算能力,显然现有的安全措施和加密方式无法承受来自这种设备的攻击。如果要严密保护国家系统的安全的话,那么他们需要在这一方向取得显著发展。

量子计算机对于过去的人而言听起来就像是遥远的神话,但现在人们普遍认为在5到30年内它就将成为现实。通过不断探索量子物理的法则,不管是NSA的绝密档案、银行记录还是邮箱密码,这种机器能够解密现在世界上绝大多数“机密”的数据。在意识到这可能的威胁后,密码学家们正在量子计算机大范围使用以前,抓紧开发能够防止量子破译的方案。

现在看来,最可行的方案是 基于格的数学方案(mathematics of lattices) 。这种方案有效性在于,要在一个拥有几百空间维度的格中找出隐藏的信息非常难,除非你知道那条秘径。

但是去年十月,英国政府通讯总部(GCHQ)的密码专家发表论文指出,即便是最有效的格方案也面临着安全问题。这些发现意味着,在以效率为目标发展了几十年后,这种高效暴露出了安全风险。专家们通过简化他们方案中的格,导致这些方案更容易受到攻击。

基于上面所述的问题,一些密码专家从去年开始都在做实验,看哪些基于格的方案会被量子计算机打破,而哪些至少对于现在而言又是安全的。对于编写密码和破解密码的专家而言,这就是一场猫鼠游戏。当解码员沉默的时候,编码员为了效率会放松方案的安全性,有时候,其结果就是导致安全越过了那条红线。

公开的秘密

在谈论这一话题前,我们需要先对现在的加密方式有一个了解。事实上,当你每次访问以“HTTPS”开头的链接时,你都会发送和接收加密的信息,而这一安全的网络交易方式使用了基于加密技术的公共密钥。这一创造性的发明始于上个世纪70年代,而在此前,密码技术基本就是政府和间谍之间的比赛。通常而言,参与信息传递的人,例如一个人和他的对接人之间如果想要偷偷交流的话,要事先约定一个暗号或者“钥匙”。而公共密钥的技术则可以让任何人给其他人发送一组加密信息,不管是否有人在偷听,只有指定的接受人可以解密,即使参与的人一开始并没有串通好。

在公钥加密技术中,人们通过一些数学技巧来保证数据的安全性,一些数学问题解答起来容易,但是要用逆向工程解码则很难。例如,要计算机计算两个质数的乘积很容易,但是如果给计算机一个数,要它解出组成这个数的质因子,则可能要花费很多时间。在基于质数分解的方案中,这个质数就是某人并不与他人共享的“私钥”。而质数的乘积则是“公钥”,公开分发。当某人用公钥来加密信息时,只有这个拥有私钥的人才能够解密信息。

有两个公钥加密方案自上世纪70年代以来广为应用:一个是基于质因子的RSA方案,另一个是基于离散算法的Diffie-Hellman方案。虽然这两种方案并不是说一定就无法破解,但是没人能够找到高效计算出结果的方法。如果要用计算机将特定长度的公钥进行计算出来,可能要花费数年的时间。因此,这两种方案成了保护互联网信息的力盾。不过它们带来的这份安全,似乎已快来到了终结之时。

Shor的算法

计算机难以短时计算出结果这一神话在1994年被打破,当时AT&T的研究人员Peter Shor提出了一种理论,他认为未来的量子计算机会具有破解算法的能力。

在普通计算机中,信息以比特的形式存储。比特存在两种状态中的一种,即0或者1,而计算机的计算能力与比特数量相称。但是在量子计算机中,数据是用量子位方式存储的,数据存储格式既可以是0也可以是1。由于大量的量子位,使得其中可以存在大量可能的组合形式和可能的个体状态。因此随着量子位数量的上升,量子计算机的计算能力会以指数级的方式增长。

基于此,量子计算机比普通计算机会具有更强的运算能力。然而要开发出其潜力,还必须同时找到一个合适的算法,能够充分利用这种同时存在的状态,即得到正确的解答。80年代量子计算机被提出来以后,超过10多年间都没有什么有用的算法出现,这个领域似乎前途暗淡。

变化发生于1994年,Shor提出了一个量子计算机算法,能够高效破解了质因子和离散算法,也就是说打破了RSA加密方法和Diffie-Hellman密钥交换理论。于是一瞬间,人们对量子计算机的兴趣一下子燃烧了起来。随着Shor的算法揭示出了量子计算机高级的运算能力后,世界范围内的研究人员争相进行研究,试图找出破译的方式。而与之相对应的是,密码编译专家们也在竞相赛跑,提出量子计算机无法攻破的方案。最后他们发现,格似乎是一个不错的选择。

迷失在格里

其实同RSA加密方案类似,理论上来说,计算质数的乘积很容易,但是求解质因子很难,基于格的安全加密方案也取决于,让计算机迷失在一个500维的格中有多难。不同的是,在格方案中,私钥与格点相关,而公钥则与空间中的特定位置有联系。

除了一开始的惊艳,这种加密方案却发展迟缓。80年代的时候,这种方案的公钥都太长,交换数据需要海量的字节空间。为了提高效率,密码学家不得不简化潜在的格。在一个普通的格中,格点是由计算一组向量的线性组合得出。给这些向量分配一个模式,使得算出来的结果简单化,则相关的密钥也更短。但这带来的问题是,简化方案使得人们可以从公钥中推论出私钥,从而破坏这个方案。因而,格对于密码学来说,又成了灾难的代名词。

随着时间的前进,一些密码学专家仍然在不断完善格。1995年的时候,一些专家提出了一种基于“环状”的格,可以产生在任意方向旋转的向量。这个名为NTRU的方案极其高效,甚至比老的RSA和Diffie-Hellman方案更高效。尽管没有证据表明这种方案就是一定安全的,但20年过去了还没有人能破解它,证明某种程度上还是具有安全性的。

格的前景自1997年以后变得明朗起来,IBM的研究人员提出第一种较好的加密方案,这种加密方案名为Learning With Errors(LWE),意即伴随误差学习,由于要找到最近的通用格要很长时间,因而可以抵抗来自量子计算机的攻击。基于理想格下,他们开发出了一个更行之有效的方案。

什么是LWE方案

在2005年,Oded Regev基于LWE问题提出了一种加密方案,他证实这个方案解决起来很难,因而比较安全。这个方案的基本思路是这样的:

首先选择任何一个奇数,并且不要告诉任何一个其他人,这就是你的私钥。然后把它乘上任何一个数,再加上一个小的偶数。重复多次,得到一系列的数,这些数就是你的私钥,然后再把它们告诉别人。


现在,如果有谁想给你发信息,如0或1,首先这个人随机地在你的公钥里选择一半的数,把它们加起来。然后如果要发送0,他们就把数据加起来然后发给你。如果要发送1的话,就把数据加1并发给你。之后你想要解码这段数据的话,只要用你的私钥求出这个和数的商。如果余数是偶数的话,这个信息就是0。如果是奇数,则为1。

再一次,人们似乎又要在安全和效率间进行权衡。鱼和熊掌不可兼得,LWE方案虽然更加通用并且安全性更高,但它的效率较低。研究人员在这个方向上,还在不断探索,之后提出了一些其他方案。

猫鼠游戏

不仅科研人员在开发基于格的加密方案,GCHQ的人员也在做同样的事。他们使用数论开发除了名为Soliloquy的方案,把公钥的大小从一个包含大量数据的矩阵降为仅仅是一个质数。把它量化到格里而言,则是产生一个非常短的矩阵。然而,这种方案的便利也正是其致命之处。

在他们发布的论文中可以看出,他们虽然发明出了这种方案,但是在2013年后又弃用了,原因是他们发现量子攻击可以把这个加密方案攻破。虽然这篇论文只是对攻击草草描绘了一下,但是给人们留下了无限的疑问:其他的格方案是不是也会受到影响?似乎在追求效率的同时,安全的红线随时也被越过。问题是,这条安全的警戒线到底该放在哪里?

GCHQ的团队并没有找出多少细节,而仅仅是觉得有很强的证据证明,这种攻击会被开发出来,因而就推论Soliloquy不适用于现实。于是密码学家们花了差不多一年来了解Soliloquy攻击的范围,此后研究人员发现,这种攻击竟然只需要一台普通的电脑就可以实现。

除了Soliloquy以外,他们的发现还表明,其他基于理想格的方案,构造单独短向量的方法也可以被攻破,而基于一般格的方案,如Ring-LWE和NTRU则不受影响。用研究人员的话来说,似乎想要把这些技术转化成有效的方案还有一些技术上的难题,需要更深的研究。

就安全和效率的对称性而言,密码学家过于倾向效率这一边。在他们给政府和银行等机构寻找最好的抵御量子攻击的时候,Soliloquy这样的攻击迫使他们重新审视过去,回到那些可能没有那么有效率,但是更加稳固的方案。对于一个方案而言,在效率和安全性这两条相反的道路上,还是需要研究人员仔细权衡。

via wired

随意打赏

提交建议
微信扫一扫,分享给好友吧。