量子计算机要来了,从量子计算到量子安全

美国国家标准与技术研究院选出了90名候选人来帮助开发量子抵抗算法(QRA),这表明到2022年-2023年,将会推出第一个量子抵抗算法。

首先,NIST将自己定位为全球抗量子标准化工作的“带头大哥”,希望整合世界各国关于抗量子密码研究的力量,并按照美方给出的时间表、路线图进行标准制订工作。在二月份日本PQCrypto
2016会议上,各国密码学家,包括欧洲、日本、韩国等国也纷纷表示了对参与美方标准制订极大的兴趣。事实上,美国方面在密码标准制订方面,在事先进行预判的基础上来整合国际上的科研力量,并在幕后推动和引领密码算法的走向这一策略早已有成功的案例,包括2003年“高级加密算法标准”和2015年“安全散列函数标准”的制订均是这种情况。

“通过设计新的量子态或者效应,已经展现出了很多的量子所具备的能力,并且在未来的几十年内,使我们生活的很多方面都发生阶跃变化。”Sharma解释道。

2016年2月,在日本召开的PQCrypto
2016年会上,NIST正式向世人公布了他们关于抗量子密码标准化的路线图。4月NIST又公布了关于对以上四类抗量子密码算法框架的总体评估报告。8月,该机构又公布了一份指导性文件,详细阐述对新一轮抗量子密码进行标准化的若干细节,包括递交候选算法的各种要求,对候选算法进行安全和性能评估的各种考虑。9月,在ETSI召开的第四次量子安全密码年会上,NIST的官方代表再次解释了“集全球之力”推动抗量子密码标准化的决心。美方抗量子密码标准化工作的要点可以归纳如下:

量子计算机会带来很多的好处,但是其中一个副作用是它会打破目前用于保护信息的机制。但业界正在努力,澳大利亚的QuintessenceLabs正在发挥关键作用。

然而,1994年,美国贝尔实验室的数学家Peter
Shor发明了一种破解算法,从理论上证明了这种算法能够在很短的时间内完成对上面的数学困难问题的求解,从而宣布了现代公钥密码已经不再安全。只不过他的这个破解算法有一个前提,那就是必须使用“大规模的量子计算机”,而这在当时纯属天方夜谭。因为在二十多年前,造出一台能够达到破解现代公钥密码水平的量子计算机所面临的困难就如同让一名幼儿园小朋友马上完成博士论文一样不可思议。

美国国家安全局也参与其中,要求机构使用大型对称性秘钥,而不是PKI使用的非对称性秘钥。

3抗量子密码大家族

“这就是威胁,但是我们当前面临的挑战是,虽然量子计算机能够为我们带来的所有的好处,但是有一个副作用是它会打破我们如今用于商业交换中保护电子商务和金钱的机制。”

2015年7月29日,美国正式对外公布“国家战略计算倡议”。正当人们纷纷猜测该战略倡议中提到的未来新型计算是什么样的时候,二十天后的8月19日,美国国家安全局网站上发布了一则消息,开宗明义指出“由于面临量子计算机的潜在威胁”,国家安全局这个负责统管美国政府和军方密码系统的最高机构决定将联邦政府所使用的“B包密码体制”替换成“抗量子密码体制”。一石激起千层浪。首先,在现实社会当中美国国家安全局一直非常低调和神秘(这也是为什么好莱坞总是喜欢拿它来吸引眼球的原因),而这次美国国家安全局居然一反常态在互联网上公开阐明其最核心的秘密—联邦政府部门所使用的密码系统可能面临的巨大威胁,这件事情本身就非常诡异。美国国家安全局用意何在?“8.19”声明背后是否有什么“阴谋”?其次,什么是“抗量子密码”?它和“量子密码”又是什么关系?此外,量子计算机都还没有研发出来,怎样说明一个密码能够抗击量子计算机的攻击?……

如今,信息的商业交换主要是由PKI(公钥构架)来保护的,PKI的安全性则是依赖于特定数学运算的计算复杂性。

作为迫切想“弯道超车”的我们,更应该特别冷静地注意到目前国际上主要的IT企业对抗量子密码的高度重视,就如同它们对量子计算机研发的重视一样。在2016年2月的PQCrypto
2106会议上,在9月ETSI的“量子安全密码年会”上,除了欧美各国政府代表纷纷“以本色示人”积极参会和发表主旨演讲之外,Cisco、Google、Microsoft、Intel、Amazon等全球着名企业均高调参加,甚至在会上发表专题演讲,力图在抗量子密码的制标过程中反映出各自的利益。首先是全球瞩目的网络设备厂商Cisco,该企业目前正在积极考虑在其网络设备当中嵌入抗量子密码算法,从而为未来激烈的市场竞争埋下伏笔。微软则特别强调抗量子密码的加密功能(这也是为什么他们会高度专注上述的“密钥协商算法专利”的原因),Intel则扬言到2020年之际准备在其芯片上嵌入抗量子密码算法……

QLabs特别关注的是网络安全和通讯领域的应用,并从澳大利亚政府获得资金,以帮助它在国防级别上实现这一目标。

首先,就是任务繁重。如上所述,抗量子密码包括了C、S、M和L等若干种类,每一类都衍生了若干具体的算法。要在这些算法当中遴选出替代第一代公钥密码算法的候选者,仅凭NIST的抗量子密码组的十余位管理者和专家要在短短的三五年时间之内完成此项工作,这是一项不可能的任务。而尽管人们相信NSA强大的密码专家团队在整个标准制订过程中将扮演极为重要的角色,但世界各国各界对NSA这个机构的顾忌也是不言而喻的。因此,在NIST的制标过程中,必将很大程度上采取“公开透明”的方式来说服世界各地的研究人员参与其中。

“在量子计算方面取得的成就会给我们以前用于保护信息安全的机制带来风险。但是有趣的是,量子技术也能够提供一些解决方案来缓解这一风险或者迎接这一挑战。”他说道。

那么人类对现代公钥密码的安全性如此信任,原因何在呢?

这也是QLabs当前正在着手解决的问题。

其次,是算法成熟度。由于各类抗量子密码算法发明的时间各有先后,有的早在上个世纪七十年代就已经出现了,有的则在近几年才引起人们的关注,因此,一个算法是否已经经过了各国密码学家充分的研究,这对于制标工作而言非常重要。人们肯定不希望看到一款入选的算法公布出来不久之后,就面临严重的安全隐患吧?需要指出的是,并非出现得越久的算法,受到的关注就越广泛。事实上,整个抗量子密码家族也是近几年才引起全球密码学界的广泛关注和研究的。此外,此次抗量子密码制标工作,NIST要求是“纯抗量子密码标准”。换言之,不采用第一代公钥密码与新一代抗量子密码“混编”的方式,即不制订第一代公钥密码向抗量子密码“平滑过渡”的标准。这对抗量子密码的成熟度提出了更高的要求。

这三个方法受到了广泛的认可,因为它们能够保证量子安全。Sharma也指出,将这三种方式整合到一起,则会构成未来网络安全系统的基础,从而对敏感信息进行存储和传输。

顺便说一句,人们有时候也将量子密码称为“硬密码”,主要是说它依赖于量子物理的铁律,以及在实现它的时候需要大量专用硬件设备。与之相对的是“软密码”,即我们人类历史上延续了数千年并且将继续传承下去的“数学密码”。四十年前诞生的第一代公钥密码就是“软密码”家庭中的“新生成员”。遗憾的是,它们即将退出历史舞台,新一代公钥密码—抗量子密码呼之欲出了。

“这也是威胁所在…我们需要在下一个十年内认识到这些威胁,大多数人或许会争辩道,我们已经有了可用且有用的量子计算机。”

4抗量子密码标准化

“这应该就是他们所说的高熵,因为这一编码都是完全随机的。”Sharma在谈论量子安全的第二种方式时说道。

2 量子密码与抗量子密码的区别

第二次量子革命也一触即发,Sharma指出,1947年发明出了晶体管,在20世纪50年代早期,出现了很多使用晶体管的器械、设备和仪器。

密码算法自古以来就是直接与应用相关的。随着计算机网络的快速发展,密码应用也从传统的仅仅用于那些“神秘的部门”走向了千家万户,甚至进一步成为了当今网络空间安全的基石。我们希望在人类即将进入新的“量子时代、智能社会”之际,我国的密码科学工作者也能充分认知量子密码与抗量子密码的本质,摒弃狭隘的个人及小团体利益,以国家与民族大业为重,尽可能避免低水平的重复,立足高远,从容布局,力争新高地。

美国国家标准与技术研究院(NIST)一直在实行一个项目,来决定下一组算法,以保护量子安全的数据。

1 美国国家安全局的“8.19”声明

量子计算会使世界发生彻底的变革,澳大利亚也将第一个冲向量子终点线。但是量子计算机对药物等领域带来好处的同时,也会破坏当前的安全方法。

第三,既然是打“抗量子密码”牌,NST要求所有算法候选者均要“双肩挑”,即既能抵抗各种经典的密码破译分析,又能抵御“量子计算机的攻击”。而且在美方公布的指导性文件当中还特别注明:算法设计者们应当把“大型通用量子计算机获得广泛应用”作为设计算法的前提假设。这一点对于全球密码专家而言都提出了全新的挑战。

澳大利亚量子网络安全公司QuintessenceLabs(以下简称为QLabs)的创始人兼首席执行官Vikram
Sharma在上周的ACS堪培拉大会发表演讲后接受了ZDNet的访谈,他详细描述了全球安全行业的计划,为在接下来的十年内实现量子计算机而做准备。

首先需要指出的是,抗量子密码是泛指,它们大体上可以分为四大类,这四大类之间没有什么“血缘关系”,至少现在人们还没有发现它们之间有何关联。为了叙述简便,我们可以把它们分为基于编码的算法(Code-based
Encryption,C类)、基于多变量多项式的加密算法(Multi-variable
polynomial,M类)、基于安全散列函数的算法,以及格基加密算法(Lattice-based
Encryption,L类)。这些加密算法发明出来的时间前后不一,例如C类算法甚至可以追溯到上个世纪七十年代,即发明第一代公钥密码算法的时代。只是因为当时C类算法加密的性能要比第一代公钥密码算法慢很多,因此并未引起人们太多的关注。M类算法诞生于上个世纪八十年代中叶,之后经过了诸多变形。S类算法中最典型的一例是SHA-3,它诞生的时间相对较晚,直至2015年才成为美国国家标准;L类算法是目前最受关注的一类算法,最早产生于1994年(居然与破解第一代公钥密码体制的Shor算法同时诞生!),后来又开枝散叶衍生了诸多分枝,包括现在炙手可热的全同态加密算法,其基本原理也属于L类。

Sharma表示,重要的是,这一系统依赖的是易于单向解决的数学问题,但是想要反向解密还是有点难度的,当前的网络安全也是如此。这种用于PKI交换的系统是一种RSA(非对称加密)算法。

我们先来看一看美国国家安全局这个“8.19”声明的要点。国家安全局在密码领域承担了“密码破译”和“密码设计”两大任务。密码破译的工作由国家安全局下属的“信号情报部”(Signals
Intelligence
Directorate,SID)负责,其前身甚至可以追溯到第二次世界大战期间破译日本的“紫密”等工作,中途岛海战大败日本帝国海军,以及日本“战神”三本五十六的座机被击落均是它立下的战功。而密码设计的工作则由美国国家安全局下属的“信息保障局”(Information
Assurance Division,
IAD)负责。信号情报部负责“攻”,信息保障局负责“防”,一矛一盾。此次美国国家安全局的“8.19”声明是指其下属的信息保障局研发的B包密码体制将面临量子计算机的威胁,并要求使用“抗量子密码”来替换它。一句话,这次的“8.19”声明是针对美国联邦政府部门自身的密码升级方案。那么B包密码体制为何不再安全了呢?

原文作者:Asha McLean

美国国家安全局在2015年“8.19”声明当中,除了提出要替换现有的B包密码体制之外,还要求美国国家标准局尽快启动抗量子密码标准的制订工作。对于美方如此急迫的行为,人们尽管有各种各样的分析或猜测,但有一点是无需置疑的,那就是美国方面将毫不掩饰的继续引领新一代抗量子密码的发展趋势,掌控其标准制订框架,并进而影响其他国际标准化组织。

“多层防御也会协同工作。”他补充道。

第二个问题是兼容性。现阶段用于传递密钥的量子通信网络是一个独立运行的、中继节点必须是可信的通信网络。而人类社会在过去三十多年来投入了巨大的软硬件资源建设了另一张网络:基于TCP/IP协议的计算机网络,而且还在不断快速扩张当中,如移动互联网、物联网等等。这张网最大的特点就是“天生不可信”。因此人们一直以来就以“网络环境不安全为前提假设”来追求计算机网络通信的安全,例如采用上面提到的现代公钥密码来提供网络成员之间的相互信任问题,从而解决“不可信环境下的可信认证问题”。因此在量子通信获得更广泛的应用之前,如何解决“可信的量子网络”与“不可信的互联网”这两张网的兼容问题?或者说如何解决量子通信的标准问题?这对于量子通信产业化是必不可少的。还需要指出的是,无论从工程造价以及全球网络互联互通的角度来看,世界上任何一个国家都不可能废弃现有的计算机网络,而花费巨资来重新打造一张“纯量子通信网络”。因此,在可以预见的未来,这两张网必定会共生共存,相互补充。

和第二次革命不同的是,第一次革命看到了自然界中发生的量子效应的被动杠杆化;第二次革命的特点是可以积极地设计自然界中不存在的量子态。

毫无疑问,美方抗量子标准化路线图的企图是雄心勃勃的。然而,它也面临若干挑战。对此,美国国家标准技术研究所抗量子密码组的专家们也毫不讳言。

他说:“我们希望量子计算机不会破坏这些机制。”

凡事有利必有弊。上述这些抗量子密码算法,虽然各自依赖不同的数学上的困难问题,因而从理论上具备抗量子计算机攻击的特性,但与第一代公钥密码算法相比,它们又有一些缺陷。例如,它们目前普遍效率较低:或者密钥规模较大,或者加解密速度太慢…。一旦贸然将它们投入到当今的互联网当中,有可能会带来运行效率大幅下降。毫无疑问,人们肯定不愿意使用这样一种加密算法,它会花上好几个小时来认证微软的官方网站是否可信,然后才决定是否下载最新的补丁吧?另外一个缺陷是目前这些算法当中,没有一个能够集“加密、签名、认证于一身”。而这恰恰是上一代公钥密码算法的一大优点。更为重要的是,任何密码算法的最终目标是应用,而要应用到现代互联网乃至将来更多更新的网络当中,就必须对它们制订标准,从而使得全世界的软硬件开发厂商遵循同样的标准体系来设计密码应用产品。而这一点正是目前国际密码学界,特别是各大国际标准化机构关注的核心。

Leave a Comment.