网易首页 > 网易数码 > 正文

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

0
分享至

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

今年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这样的攻击迫使他们重新审视过去,回到那些可能没有那么有效率,但是更加稳固的方案。对于一个方案而言,在效率和安全性这两条相反的道路上,还是需要研究人员仔细权衡。

相关推荐
热点推荐
大s律师在微博大骂张兰,网友 这是个律师吗 跟站街骂人的泼妇一样

大s律师在微博大骂张兰,网友 这是个律师吗 跟站街骂人的泼妇一样

娱乐圈酸柠檬
2024-03-28 13:59:42
女人在过夫妻性生活时,为什么总发出声音?医生:大多数人不了解

女人在过夫妻性生活时,为什么总发出声音?医生:大多数人不了解

皮皮讲文
2024-01-02 10:36:17
勇气可嘉,四川一中学家长硬扛老师与家委:我不买,这是道德绑架

勇气可嘉,四川一中学家长硬扛老师与家委:我不买,这是道德绑架

东东趣谈
2024-03-28 15:03:52
大快人心!这些让无数人倾家荡产的机构终于迎来团灭

大快人心!这些让无数人倾家荡产的机构终于迎来团灭

视知产研院
2024-03-27 23:26:43
招商银行近两年向员工追薪1亿多元上热搜!网友:追回的是绩效工资,被追回说明年底没完成任务

招商银行近两年向员工追薪1亿多元上热搜!网友:追回的是绩效工资,被追回说明年底没完成任务

和讯网
2024-03-28 13:41:06
1972年美国将军来华访问姿态傲慢,毛主席怒道:不来就不来

1972年美国将军来华访问姿态傲慢,毛主席怒道:不来就不来

东哥讲故事
2024-03-27 10:15:21
媒体人:很多涉案球员已经出来&最重判三年多 郭田雨可能出国踢球

媒体人:很多涉案球员已经出来&最重判三年多 郭田雨可能出国踢球

直播吧
2024-03-28 14:50:27
曝42岁李晨上海遛娃!推简易婴儿车太低调,女儿五官清秀超像爸

曝42岁李晨上海遛娃!推简易婴儿车太低调,女儿五官清秀超像爸

鑫鑫说说
2024-03-27 16:22:18
每体:亚马尔去年长高10厘米现已达1.8米,肌肉增加约7公斤

每体:亚马尔去年长高10厘米现已达1.8米,肌肉增加约7公斤

直播吧
2024-03-28 14:29:23
总局收视排行:《追风者》《与凤行》断层差距,第一名堪称剧王

总局收视排行:《追风者》《与凤行》断层差距,第一名堪称剧王

娱乐圈十三太保
2024-03-27 14:01:28
6000万送四人进国家队❗李铁:国内右后卫明天一对一防守最强

6000万送四人进国家队❗李铁:国内右后卫明天一对一防守最强

直播吧
2024-03-28 09:09:33
吴君如近照曝光!疑医美过度!苹果肌太饱满,脸上皱纹也不对劲!

吴君如近照曝光!疑医美过度!苹果肌太饱满,脸上皱纹也不对劲!

西瓜爱娱娱
2024-03-28 16:46:20
李溪芮的玉足美腿白皙动人

李溪芮的玉足美腿白皙动人

娱乐圈酸柠檬
2024-03-19 13:39:09
烧烤店老板谈淄博烧烤爆火一年后现状:顾客翻了一倍

烧烤店老板谈淄博烧烤爆火一年后现状:顾客翻了一倍

大众日报
2024-03-28 15:15:00
除了台湾,中国还有“四大领土”没收回,每一个地方都是战略要地

除了台湾,中国还有“四大领土”没收回,每一个地方都是战略要地

科普大堂
2024-03-26 19:25:02
澳门广州两女学生被骗到珠海失联,已找到!有人已转账20万

澳门广州两女学生被骗到珠海失联,已找到!有人已转账20万

南方都市报
2024-03-28 15:05:54
12幅幽默漫画,画出女生夏天的尴尬!

12幅幽默漫画,画出女生夏天的尴尬!

MICU设计
2024-03-28 09:15:27
一个家庭富不起来的根源:垃圾太多

一个家庭富不起来的根源:垃圾太多

洞见
2024-03-26 21:55:38
南宋御街一店铺卖188元奶茶,老板说亏本经营:一杯的茶叶就要200元

南宋御街一店铺卖188元奶茶,老板说亏本经营:一杯的茶叶就要200元

都市快报橙柿互动
2024-03-26 15:53:13
3月28日下午,突然曝出1重大消息,或将产生重大影响?

3月28日下午,突然曝出1重大消息,或将产生重大影响?

股市皆大事
2024-03-28 10:27:03
2024-03-28 19:42:44

头条要闻

原市委书记一家6人被留置 外甥靠他打招呼做了2亿生意

头条要闻

原市委书记一家6人被留置 外甥靠他打招呼做了2亿生意

体育要闻

疯狂的格林,冲刺的火箭

娱乐要闻

莱昂纳多与25岁新女友互相投喂超恩爱

财经要闻

疯狂!三个城市,三个地王!

科技要闻

小米汽车正式发布

汽车要闻

混动增程双模式 长安UNI-Z售11.79万起

态度原创

艺术
旅游
本地
公开课
军事航空

艺术要闻

艺术开卷|从闺阁、庭院到郊野,古画中的女性生活空间

旅游要闻

在广西不洗澡,是不是犯了天条啊?

本地新闻

专访|张伟潮:最年轻的龙头专职制造者

公开课

30岁之前,你要学会的13件事情

军事要闻

乌方声称击落两枚俄"锆石"高超音速导弹 俄方未予回应

无障碍浏览 进入关怀版
×