美国国家安全局启动抗量子密码体制
2015年7月29日，美国正式对外公布“国家战略计算倡议”（NSCI）。正当人们纷纷猜测该战略倡议中提到的未来新型计算是什么样的时候，二十天后的8月19日，美国国家安全局（NSA）网站上发布了一则消息，开宗明义指出“由于面临量子计算机的潜在威胁”，国家安全局这个负责统管美国政府和军方密码系统的最高机构决定将联邦政府所使用的“B包密码体制”（B suite）替换成“抗量子密码体制”。
一石激起千层浪。首先，在现实社会当中美国国家安全局一直非常低调和神秘（这也是为什么好莱坞总是喜欢拿它来吸引眼球的原因），而这次美国国家安全局居然一反常态在互联网上公开阐明其最核心的秘密—联邦政府部门所使用的密码系统可能面临的巨大威胁，这件事情本身就非常诡异。美国国家安全局用意何在？“8.19”声明背后是否有什么“阴谋”？其次，什么是“抗量子密码”？它和“量子密码”又是什么关系？此外，量子计算机都还没有研发出来，怎样说明一个密码能够抗击量子计算机的攻击？
我们先来看一看美国国家安全局这个“8.19”声明的要点。国家安全局在密码领域承担了“密码破译”和“密码设计”两大任务。密码破译的工作由国家安全局下属的“信号情报部”（Signals Intelligence Directorate，SID）负责，其前身甚至可以追溯到第二次世界大战期间破译日本的“紫密”等工作，中途岛海战大败日本帝国海军，以及日本“战神”三本五十六的座机被击落均是它立下的战功。而密码设计的工作则由美国国家安全局下属的“信息保障局”（Information Assurance Division，IAD）负责。信息保障局负责“攻”，信息保障局负责“防”，一矛一盾。此次美国国家安全局的“8.19”声明是指其下属的信息保障局研发的B包密码体制将面临量子计算机的威胁，并要求使用“抗量子密码”来替换它。一句话，这次的“8.19”声明是针对美国联邦政府部门自身的密码升级方案。那么B包密码体制为何不再安全了呢？
B包密码体制包括了多种以现代公钥密码为基础的加密算法、数字签名算法、密钥协商算法和随机数生成算法（主要用于产生原始密钥）等。而现代公钥密码诞生于上个世纪七十年代中叶，其安全性依赖于数学上的皇冠—数论中的一类困难问题。美国国家安全局组织专家对公钥密码的安全性分析了整整三十年，在确认没有什么安全漏洞之后，才于2005年允许B包密码体制在联邦政府内部的信息系统当中投入使用。根据NSA的相关规定，B包密码体制可以用于联邦政府的机密信息传递，而且和更为神秘的A包密码体制一道，可以用于处理最高密级为绝密级（Top Secret）的信息，例如美联储等机构就可以使用B包密码体制来传递敏感信息。
其实，现代公钥密码不仅仅用于美国或其他国家的政府部门。在人们日常生活或工作当中，在当今互联网的正常运行与维护当中，均离不开现代公钥密码。例如，各种软件版本的自动更新，各种网络设备补丁的下载与升级，政府部门的电子政务，企业的电子商务，个人的网上消费（如“双十一”）…...均依靠现代公钥密码体制来提供虚拟社会各成员之间（无论是人还是各种软硬件设备）的相互认证，只不过这些认证工作都是在后台默默的完成，无须人们动手。因此，现代公钥密码构成了网络空间的信任链之锚。可以毫不夸张的讲，人类社会从来没有像今天这样，将如此巨大的资产（实体的和虚拟的）托付于现代公钥密码体制。所以，一旦网络空间的这个信任锚“基础不牢”，必将“地动山摇”。
那么人类对现代公钥密码的安全性如此信任，原因何在呢？
四十年前诞生的现代公钥密码体制，无论是RSA算法，ECC椭圆曲线算法，还是DH密钥协商算法，它们的安全根基都系在“一根绳上”—数论中的“大数素因子分解/离散对数”困难问题之上。由于人们相信仅凭现在的计算机（即使是比现有最强大的超级计算机还快千百万倍）都难以在数十年甚至上百年之内破译这些公钥密码算法，因此世人一直高枕无忧。
然而，1994年，美国贝尔实验室的数学家Peter Shor发明了一种破解算法，从理论上证明了这种算法能够在很短的时间内完成对上面的数学困难问题的求解，从而宣布了现代公钥密码（在理论上）已经不再安全。只不过他的这个破解算法有一个前提，那就是必须使用“大规模的量子计算机”，而这在当时纯属天方夜谭。因为在二十多年前，造出一台能够达到破解现代公钥密码水平的量子计算机所面临的困难就如同让一名幼儿园小朋友马上完成博士论文一样不可思议。
但是人类追求技术进步的步伐有时候也超出了自身的预料。进入本世纪之后，特别是2012年之后，设计制造量子计算机的关键技术接二连三取得突破。尽管现在人们研发量子计算机的原动力已经远远超越了破解公钥密码算法，而是更加急迫的希望能够把它用于先进材料、新药设计、基因工程等领域来提升人类社会的生活品质，甚至探索宇宙的终极秘密，如量子场论等。然而，量子计算机一旦真的制造出来，毫无疑问将对现有公钥密码体制带来毁灭性的打击，如果人们不能尽快找到替代方案，那么当今的网络空间也必将荡然无存。一句话，设计“新型抗量子公钥密码”的队伍现在必须和那些研发量子计算机的队伍赛跑。
量子通信与抗量子密码
2015年8月19日，美国国家安全局在其官方网站上宣布正式启动“抗量子密码体制”，即“8.19”声明。事隔整整一年之后，2016年8月16号，中国的量子科学实验卫星“墨子号”在酒泉卫星发射中心成功发射，而“量子通信”这一概念落入普通大众的视野，而“量子通信”其实就是密码领域常说的“量子密码”。对此，我们很有必要厘清一下量子密码与抗量子密码的区别。
一、量子通信（也即量子密码）
量子密码本身并不是一种密码算法，而是利用量子物理，特别是量子纠缠的神奇特点来实现传统的加密算法的密钥协商（分发），简称量子密钥分发（Quantum Key Distribution，QKD）。由于这种特点，QKD主要的应用是不断给用户更新密钥，而不能像公钥密码体制那样进行数字签名和用户身份认证。现阶段世界各国（包括我国）建设的各类量子通信网络，均是指上述的QKD。通信双方在进行保密通信之前，可以依靠QKD系统来“分发”这次加密算法所使用的密钥。由于量子纠缠状态的“不可测性”这一基本物理定律的保障，使得人们从理论上得到了安全性保障，即如果有人企图“偷听”密钥的传递，那么处于纠缠态的量子对就会发生坍塌，从而让通信双方得知此次密钥的传递发生了问题，于是可以再次协商、再次传递…（当然，如果窃听方就是存心捣乱，持续通过这种“偷听方式”来干扰你进行密钥分发，这又带来新的安全隐患）。
在现阶段，量子密码QKD面临的主要技术障碍有两个：一个是纠缠态的量子对的传输距离有限，需要进行“中继传输”，就像奥运火炬一样一棒一棒的接力下去。这就要求每一个“火炬手/二传手”都必须是可靠、可信的。如果某个火炬手“狸猫换太子”，那么整个通信安全就受到破坏。因此如何解决“二传手”本身的可信问题？目前一种解决办法是用公钥密码来对量子通信的各个节点进行“身份认证”。一个典型的例子是世界上著名的量子通信产品生产厂商，瑞士的IQD公司所生产的量子通信设备（即QKD），就是使用现代公钥密码来对传输节点进行身份认证的。但如果现代公钥密码在量子计算机面前不堪一击，那么节点的身份依然可能被冒充。事实上，人们正在考虑使用抗量子公钥密码来替换上一代公钥密码，为量子通信网络中的各个节点提供身份认证。
第二个问题是兼容性。现阶段用于传递密钥的量子通信网络是一个独立运行的、中继节点必须是可信的通信网络。而人类社会在过去三十多年来投入了巨大的软硬件资源建设了另一张网络：基于TCP/IP协议的计算机网络，而且还在不断快速扩张当中，如移动互联网、物联网等等。这张网最大的特点就是“天生不可信”。因此人们一直以来就以“网络环境不安全为前提假设”来追求计算机网络通信的安全，例如采用上面提到的现代公钥密码来提供网络成员之间的相互信任问题，从而解决“不可信环境下的可信认证问题”。因此在量子通信获得更广泛的应用之前，如何解决“可信的量子网络”与“不可信的互联网”这两张网的兼容问题？或者说如何解决量子通信的标准问题？这对于量子通信产业化是必不可少的。还需要指出的是，无论从工程造价以及全球网络互联互通的角度来看，世界上任何一个国家都不可能废弃现有的计算机网络，而花费巨资来重新打造一张“纯量子通信网络”。因此，在可以预见的未来，这两张网必定会共生共存，相互补充。
顺便说一句，人们有时候也将量子密码称为“硬密码”，主要是说它依赖于量子物理的铁律，以及在实现它的时候需要大量专用硬件设备。与之相对的是“软密码”，即我们人类历史上延续了数千年并且将继续传承下去的“数学密码”。四十年前诞生的第一代公钥密码就是“软密码”家庭中的“新生成员”。遗憾的是（或者令人兴奋的是？），它们即将退出历史舞台，新一代公钥密码—抗量子密码呼之欲出了。
二、抗量子密码大家族
抗量子密码（Quantum Resistant Cryptography，QRC）是目前最新的提法，但还有其他很多同义词，比如“后量子密码”（Post Quantum Cryptography，PQC），这是使用时间最长的术语、“抗量子算法”（Quantum Resistant Algorithm，QRA，这是美国国家安全局“8.19”声明中的用法）。这些名称目前在业界当中均在交替使用。这也恰恰说明这是一个“群雄并起”的美好时代。无论它们叫什么，本质上都是指“能够抵御量子计算机攻击的数学密码”。由于现阶段遭受量子计算机攻击的密码系统主要是第一代公钥密码，包括上面提到的RSA/ECC/DH这几类。而这些公钥密码恰恰又构成了当代网络空间的信任链之锚。因此，人们现阶段关注的焦点也是尽快拿出能够替换第一代公钥密码的方案，重新固定网络空间信任之锚。
首先需要指出的是，抗量子密码是泛指，它们大体上可以分为四大类，这四大类之间没有什么“血缘关系”，至少现在人们还没有发现它们之间有何关联。为了叙述简便，我们可以把它们分为基于编码的算法（Code-based Encryption，C类）、基于多变量多项式的加密算法（Multi-variable polynomial，M类）、基于安全散列函数的算法（Secure Hash-based，S类），以及格基加密算法（Lattice-based Encryption，L类）。这些加密算法发明出来的时间前后不一，例如C类算法甚至可以追溯到上个世纪七十年代，即发明第一代公钥密码算法的时代。只是因为当时C类算法加密的性能要比第一代公钥密码算法慢很多，因此并未引起人们太多的关注。M类算法诞生于上个世纪八十年代中叶，之后经过了诸多变形。S类算法中最典型的一例是SHA-3，它诞生的时间相对较晚，直至2015年才成为美国国家标准；L类算法是目前最受关注的一类算法，最早产生于1994年（居然与破解第一代公钥密码体制的Shor算法同时诞生！），后来又开枝散叶衍生了诸多分枝，包括现在炙手可热的全同态加密算法，其基本原理也属于L类。
大约在2006年左右，国际密码学界开始把上述4大类数学密码统称为“后量子密码”（即现在的“抗量子密码”）。之所以给它们整体冠以“抗量子”这顶桂冠，主要原因有二：一、它们所依赖的数学上的困难问题均与第一代公钥密码算法所依赖的，被Shor算法破解了的那类困难问题无关。换言之，Shor算法对它们都不起作用；二、它们各自依赖的数学困难问题之间没有什么关联关系，“鸡蛋没有放在一个篮子里面”。即不存在这种风险，将来如果发现它们当中某一个困难问题能够被求解出来，于是就“株连九族”，就像第一代公钥密码那样，RSA算法、ECC算法，以及DH算法，都被Shor破解算法连锅端了。
人们可能会感到奇怪，既然已经有这么多形态各异的抗量子算法存在，为什么我们不立即用它们来替换现有的公钥密码系统，形成网络空间新的信任锚。这样一来，即使将来量子计算机研发出来了，人们不是也可以继续高枕无忧吗？
三、抗量子密码标准化
凡事有利必有弊。上述这些抗量子密码算法，虽然各自依赖不同的数学上的困难问题，因而从理论上具备抗量子计算机攻击的特性，但与第一代公钥密码算法相比，它们又有一些缺陷。例如，它们目前普遍效率较低：或者密钥规模较大，或者加解密速度太慢…。一旦贸然将它们投入到当今的互联网当中，有可能会带来运行效率大幅下降。毫无疑问，人们肯定不愿意使用这样一种加密算法，它会花上好几个小时来认证微软的官方网站是否可信，然后才决定是否下载最新的补丁吧？另外一个缺陷是目前这些算法当中，没有一个能够集“加密、签名、认证于一身”。而这恰恰是上一代公钥密码算法的一大优点。更为重要的是，任何密码算法的最终目标是应用，而要应用到现代互联网乃至将来更多更新的网络当中，就必须对它们制订标准，从而使得全世界的软硬件开发厂商遵循同样的标准体系来设计密码应用产品。而这一点正是目前国际密码学界，特别是各大国际标准化机构关注的核心。
美国国家安全局（NSA）在2015年“8.19”声明当中，除了提出要替换现有的B包密码体制之外，还要求美国国家标准局（NIST）尽快启动抗量子密码标准的制订工作。对于美方如此急迫的行为，人们尽管有各种各样的分析或猜测，但有一点是无需置疑的，那就是美国方面将毫不掩饰的继续引领新一代抗量子密码的发展趋势，掌控其标准制订框架，并进而影响其他国际标准化组织。
美国有关机构，特别是NSA和NIST的密码管理部门早在十年前就开始关注国际上各类抗量子密码算法的研发进展。随着这些算法逐步成型，以及2012年之后量子计算机关键技术不断取得突破，美国方面开始利用一些著名的专业国际会议来进行“标准化布局”。2013年9月，在欧洲电信标准化委员会（ETSI）召开的第一届“量子安全密码”（Quantum Safe Cryptography，QSC）国际会议上，美国NIST抗量子密码组首次向世人展示了他们将上述四类抗量子密码家族纳入标准化的想法。随后几年当中，美国方面加大了对抗量子密码标准化的宣传工作。2015年11月，NIST颁布了《加密算法与密钥长度在过渡期的使用建议》（NIST SP 800-131 Ar1）。在该建议当中，立即禁用了一款随机数生成算法（DUAL_EC_DRBG），对于其他未经授权的密钥协商/交换算法，最多给出两年的暂缓期，至2017年年底全面禁用。该建议进一步收紧了第一代公钥密码算法的使用期限，为下一步转向抗量子密码做了铺垫。
2016年2月，在日本召开的PQCrypto 2016年会上，NIST正式向世人公布了他们关于抗量子密码标准化的路线图。4月NIST又公布了关于对以上四类抗量子密码算法框架的总体评估报告（NISTIR 8105）。8月，该机构又公布了一份指导性文件，详细阐述对新一轮抗量子密码进行标准化的若干细节，包括递交候选算法的各种要求，对候选算法进行安全和性能评估的各种考虑。9月，在ETSI召开的第四次量子安全密码年会上，NIST的官方代表再次解释了“集全球之力”推动抗量子密码标准化的决心。美方抗量子密码标准化工作的要点可以归纳如下：
首先，NIST将自己定位为全球抗量子标准化工作的“带头大哥”，希望整合世界各国关于抗量子密码研究的力量，并按照美方给出的时间表、路线图进行标准制订工作。在二月份日本PQCrypto 2016会议上，各国密码学家，包括欧洲、日本、韩国等国也纷纷表示了对参与美方标准制订极大的兴趣。事实上，美国方面在密码标准制订方面，在事先进行预判的基础上来整合国际上的科研力量，并在幕后推动和引领密码算法的走向这一策略早已有成功的案例，包括2003年“高级加密算法标准”（AES）和2015年“安全散列函数标准”（SHA-3）的制订均是这种情况。
其次，NIST给出了明确的抗量子密码标准化时间表，一共分为三个阶段：算法征集阶段。从2016年2月至2017年11月为面向全球进行抗量子算法的征集阶段。尽管NIST/NSA对上述四类算法进行了多年的内部研究，但他们仍然希望通过“算法公开征集”这种措施来达到两大目的：一是看看是否尚有“漏网之鱼”，二是增加那些将来获得最后批准的算法的公信力。这一点在“斯诺登事件”之后对“重塑美方的威信”而言尤为重要。算法评估阶段。从2018年开始，预计安排3-5年时间进行候选算法的安全和性能评估。考虑到目前抗量子算法远比当年评选单一的AES或SHA-3算法要复杂，但评选时间却更短，这将在未来几年当中充满挑战。算法制标阶段。最后计划安排两年左右的时间对最终入选的各类抗量子密码算法制订相应的美国国家标准。从上述时间安排可以看出，大致上到2020年或稍后一点的时间，美国方面将完成对各类抗量子密码算法族的评估，从而为“抗量子密码”赢得对“量子计算机研发”的竞赛奠定基础。
第三，既然是打“抗量子密码”牌，NST要求所有算法候选者均要“双肩挑”，即既能抵抗各种经典的密码破译分析，又能抵御“量子计算机的攻击”。而且在美方公布的指导性文件当中还特别注明：算法设计者们应当把“大型通用量子计算机获得广泛应用”作为设计算法的前提假设。这一点对于全球密码专家而言都提出了全新的挑战。
毫无疑问，美方抗量子标准化路线图的企图是雄心勃勃的。然而，它也面临若干挑战。对此，美国国家标准技术研究所（NIST）抗量子密码组的专家们也毫不讳言。
首先，就是任务繁重。如上所述，抗量子密码包括了C、S、M和L等若干种类，每一类都衍生了若干具体的算法。要在这些算法当中遴选出替代第一代公钥密码算法的候选者，仅凭NIST的抗量子密码组的十余位管理者和专家要在短短的三五年时间之内完成此项工作，这是一项不可能的任务。而尽管人们相信NSA强大的密码专家团队在整个标准制订过程中将扮演极为重要的角色，但世界各国各界对NSA这个机构的顾忌也是不言而喻的。因此，在NIST的制标过程中，必将很大程度上采取“公开透明”的方式来说服世界各地的研究人员参与其中。
其次，是算法成熟度。由于各类抗量子密码算法发明的时间各有先后，有的早在上个世纪七十年代就已经出现了，有的则在近几年才引起人们的关注，因此，一个算法是否已经经过了各国密码学家充分的研究，这对于制标工作而言非常重要。人们肯定不希望看到一款入选的算法公布出来不久之后，就面临严重的安全隐患吧？需要指出的是，并非出现得越久的算法，受到的关注就越广泛。事实上，整个抗量子密码家族也是近几年（特别是美国NSA“8.19”声明之后）才引起全球密码学界的广泛关注和研究的。此外，此次抗量子密码制标工作，NIST要求是“纯抗量子密码标准”。换言之，不采用第一代公钥密码与新一代抗量子密码“混编”的方式，即不制订第一代公钥密码向抗量子密码“平滑过渡”的标准。这对抗量子密码的成熟度提出了更高的要求。
第三，是算法覆盖面。由于目前没有一种抗量子密码算法能够很好的兼顾“加密”、“签名”、“认证”等功能点，而这恰恰是第一代公钥密码的优势，因此NIST必将会针对每一个功能点来筛选相应的算法，而且每一个功能点可能还会遴选两种以上的算法。这毫无疑问又加大了工作量。
第四，是算法适应性。与第一代公钥密码出现后，主要面向互联网应用不同。抗量子密码算法必将面临更多、更新、更复杂的网络应用，包括移动互联网、卫星通信、物联网、大数据、云计算等等。例如各种用于物联网终端的“轻量级抗量子密码”是否足够抵抗“普遍使用的量子计算机攻击”同时又有很快的加解密速度？又例如这些抗量子密码如何平滑过渡到现有的网络安全协议栈（包括TLS、IKE等）而不会影响网络的运行效率？
第五，是安全新概念。现阶段人们对密码算法安全性的认识主要是基于所谓的“比特安全”（bit security），因为可以用它来“量化”一个加密算法抵御现有计算机攻击的能力。例如AES-128就是指该算法的密钥长度为128比特。它意味着如果使用电子计算机（无论它有多强大）来进行“暴力破解”，也就是穷举所有密钥的可能性的话，计算机需要计算2的128次方种可能性。按照现有的计算能力，即使到数百亿年之后宇宙终结之时也计算不完。但是，“量子计算机依然遵循比特安全”这种规律吗？NIST提出了这样的疑问。
最后，但也非常实际和重要的一点就是算法的专利问题。这个问题尤其突出体现在抗量子密码的“密钥协商”算法上（与之对应的第一代公钥密码体制当中，就是在当今网络空间当中得以广泛应用的著名的DH算法，遗憾的是该算法在量子计算机出现后已经不堪一击）。与其他可以用于“加密”、“签名”的抗量子算法候选种类相对较多不同，目前唯一能够用于“密钥协商”的抗量子算法从本质上来讲只有一款算法。这是一类基于L类密码（格基密码以及一种所谓“基于错误学习”的方法）算法发明的“密钥协商算法”。这种算法是由一位在美国的华人密码学家JINTAI DING于2012年发明的，并且已经获得了美国专利。而基于其他类型（C类、M类和S类）的抗量子密码来设计“密钥协商算法”的种种努力到目前为止都以失败而告终。这对于NIST希望推进的标准化工作而言是一个极大的障碍，因为它要求所有算法入选者必须声明放弃算法专利才能入选其“候选算法池”。如果该专利的持有者拒绝放弃专利，那么在将来抗量子密码标准的功能点上就缺少了“密钥协商算法”这一环，这将成为抗量子算法族的一大缺陷。由于目前Google推出的一款基于该密钥协商算法的试用软件—“新希望”（New Hope）正面临可能的法律诉讼，以及其他厂商，如微软等对该算法知识产权表现出来的关注和尊重，这都提醒人们未来抗量子密码及其应用所面临的挑战不仅是技术层面的，也包括知识产权保护方面的。
作为迫切想“弯道超车”的我们，更应该特别冷静地注意到目前国际上主要的IT企业对抗量子密码的高度重视，就如同它们对量子计算机研发的重视一样。在2016年2月的PQCrypto 2106会议上，在9月ETSI的“量子安全密码年会”上，除了欧美各国政府代表纷纷“以本色示人”积极参会和发表主旨演讲之外，Cisco、Google、Microsoft、Intel、Amazon等全球著名企业均高调参加，甚至在会上发表专题演讲，力图在抗量子密码的制标过程中反映出各自的利益。首先是全球瞩目的网络设备厂商Cisco，该企业目前正在积极考虑在其网络设备当中嵌入抗量子密码算法，从而为未来激烈的市场竞争埋下伏笔。微软则特别强调抗量子密码的加密功能（这也是为什么他们会高度专注上述的“密钥协商算法专利”的原因），Intel则扬言到2020年之际准备在其芯片上嵌入抗量子密码算法......
“山雨未来风满楼”。目前世界各国，特别是欧美各国标准化机构纷纷加大了对新一代抗量子密码的研究工作，力图在标准层面抢占战略制高点。值得一提的是，日、韩等亚洲国家对此也高度关注，例如他们派出专家参加了今年6月在我国召开的“首届亚洲抗量子密码论坛”之后，韩国原定为明年的东道国，但他们已经决定提前在今年十一月底在召开第二届亚洲抗量子密码论坛......
密码算法自古以来就是直接与应用相关的。随着计算机网络的快速发展，密码应用也从传统的仅仅用于那些“神秘的部门”走向了千家万户，甚至进一步成为了当今网络空间安全的基石。我们希望在人类即将进入新的“量子时代、智能社会”之际，我国的密码科学工作者也能充分认知量子密码（量子通信）与抗量子密码的本质，摒弃狭隘的个人及小团体利益，以国家与民族大业为重，尽可能避免低水平的重复，立足高远，从容布局，力争新高地。
原文发布时间为：2017-12-11
本文作者：陶卿
本文来源：九州量子，如需转载请联系原作者。
