后量子密码技术发展分析

xman

作者：助理研究员/武获山 知远战略与防务研究所网络空间战略分析与评估中心

密码技术是网络安全的根基。在网络行为已经渗透到社会生活每个领域的今天，无论是网上银行、电子商务还是电子邮件、即时消息服务，密码技术无时无刻不在保护着用户的信息安全。如果当前普遍运用的密码系统遭到根本性威胁，所有网络活动的安全性无疑都将面临严峻挑战。事实上，具有强大密码破解能力的量子计算机近年来已经不断取得实质性进展，研究者们普遍认为应该尽早部署能够抵御这种威胁的后量子密码技术，从而将全球信息网络系统面临的总体风险降至最低。

一、潜在的量子计算能力将对当前普遍使用的密码系统构成颠覆性威胁

加密算法都是建立在特定数学难题的基础之上，但是这些数学问题的困难性可能会因新型计算能力或者算法的出现而削弱。由于量子计算机技术取得了出人意料的快速发展，大量仅能抵御经典计算机暴力破解的密码算法面临被提前淘汰的困境。

（一）计算安全性是密码系统正常运行的基本前提

任何密码系统的应用都需要在安全性和运行效率之间做出平衡，密码算法只要达到计算安全要求就具备了实用条件，并不需要实现理论上的绝对安全。在其1945年发布的《密码学的数学原理》中，美国数学家克劳德·E·香农严谨地证明了一次性密码本或者称为“弗纳姆密码”（Vernam）具有无条件安全性（unconditionallysecure）。【1】但这种绝对安全的加密方式在实际操作中需要消耗大量资源，不具备大规模使用的可行性。事实上，当前得到广泛应用的密码系统都只具有计算安全性，即通过计算暴力破解密文所花费的时间远大于该信息的有效时间，并且破解密文的成本远高于加密信息的价值。

随着计算能力的发展，密码系统也需要做出调整和改进，从而确保其计算安全性继续成立。例如，IBM公司和美国国家安全局在20世纪70年代开发出了使用56位密钥的DES密码系统（DataEncryption Standard），即计算机需要在256的搜索空间内寻找可能的密钥，这对于当时以及此后相当长一段时间内的计算机来说都是不可能完成的任务。但到了90年代，先进的超级计算机已经开始能够在合理的时间内遍历DES密码系统的密钥空间。因此，在计算安全性遭到破坏的情况下，DES密码系统也很快被至少使用128位密钥的AES密码系统（AdvancedEncryption Standard）所取代。

一般情况下，密码系统在开发过程中都会考虑破解计算技术发展的速度和水平，因此，现代密码系统的应用都存在特定生命周期。然而，任何基于计算安全性密码系统面临的致命威胁是：计算能力出现远超正常预期的大幅跃升，而当前量子计算机技术的发展正在加速使这种隐现的威胁成为现实。

（二）量子计算能力对于现行密码系统的潜在冲击

在当前的网络通信协议中，使用范围最广的密码技术是RSA密码系统、诸如ECDSA/ECDH等ECC密码系统以及DH密钥交换技术，这些通用密码系统共同构成了确保网络信息安全的底层机制。诸如大数分解（integer factorization）和离散对数（discrete logarithm）等经过长期深入研究的数学问题构建出上述先进加密技术的底层机制，而且此类困难问题在过去数十年间的运行过程中表现出了充分的可靠性。【2】但随着量子计算机技术不断取得突破，特别是以肖氏算法为典型代表的量子算法的提出，相关运算操作在理论上可以实现从指数级别向多项式级别的转变，这些对于经典计算机来说足够“困难”的问题必将在可预期的将来被实用型量子计算机轻易破解。

造成这种现象的根本原因是，当现在普遍使用的密码系统被提出之时，所谓量子计算只是存在于世界上少数几位物理学家头脑中的设想，当前大多数密码系统在开发过程中都没有考虑量子算法威胁的因素。例如，罗恩·李维斯特（Ron Rivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）在1977年就了提出RSA公钥密码解决方案，而此时距离理查德·P·费曼（RichardP. Feynman）和保罗·贝尼奥夫（PaulBenioff）分别从理论上提出驾驭量子物理属性进行计算操作的方案尚有5年时间，贝尔实验室科学家彼得·肖直到1994年才提出了解决大数分解问题的肖氏算法。【3】

尽管主流的密码系统目前依然能够有效运行，但是在量子计算技术的潜在冲击下，几乎所有的加密算法都需要进行改进甚至必须进行迁移。在2016年4月的内部报告中，美国国家标准与技术局对当前主要的密码技术将受量子计算能力影响的情况进行了预测（见表1）。其他研究者也普遍认为，尽管对于某些对称密钥加密技术来说，增加密钥长度可能是对抗量子威胁的有效手段；但对于RSA和ECC密码系统来说，上述做法显然不足以继续确保其安全性，密码开发人员需要在公钥密码系统中运用生成密钥的全新方法。【4】


表1：量子计算能力对于当前通用加密系统的影响【5】

（三）量子计算的前溯性威胁使部署后量子密码技术需求更加紧迫

真正全功能型量子计算机何时才能出现尚没有准确的预期，但研究者普遍认为如果当前不采取实质性预防措施，网络安全体系的崩溃很可能就是不远将来的确定性事件，而且量子计算威胁的前溯性还将使网络安全防御者面临更加复杂的局面。

在2016年的“密码标准工作组”（AWorkshop About Cryptographic Standards, AWACS）会议上，量子计算和密码学专家米凯利·莫斯卡（Michele Mosca）用一组时间不等式反映了部署后量子密码技术的紧迫需求。【6】假设当前密码系统的生命周期为X，从当前密码系统迁移至后量子密码系统的时间为Y，实用型量子计算机研制的时间为Z；其得到的结论是：（1）只有X+Y＜Z成立才能确保密码系统安全的底线，即现行密码生命周期与系统迁移时间之和必须小于量子计算机投入实际应用的时间；（2）如果Y＞Z，即迁移时间大于量子计算机研制时间，那么网络安全系统必将面临崩溃。


图1：量子计算能力威胁时间不等式图解

在此基础上，网络安全领域研究者还应该考虑“现在拦截，将来破解”（interceptnow, decrypt later）的威胁模式。【7】如果现在的通信网络流量遭到窃听并被存储下来，未来潜在的对手利用量子计算能力，就能对这些通常处于加密状态的信息进行破解，从而在多年以后将威胁范围追溯到当前。因此，在上述时间不等式模型的基础上，应该引入量子计算技术的前溯性威胁时间范围变量R。由于秘密收集信息工作的开始时间并不确定，当前很难判断量子计算技术的前溯性威胁时间范围，但假设潜在对手已经或者准备着手进行相关工作并非无稽之谈。


图2：引入前溯变量R的量子计算能力威胁时间不等式图解

在2015年的报道中，《自然》杂志引用荷兰情报与安全总局（DutchGeneral Intelligence and Security Service）负责人的观点认为，不法攻击者现在开始拦截和存储金融交易数据、个人电子邮件及其他互联网加密流量行为，“并不会让人感到意外”。【8】除此之外，大规模数据收集毫无疑问已经成为某些国家政府组织的例行性工作。根据斯诺登揭露的资料，美国和英国情报机构正在通过“上游”计划，利用海底光缆登陆站毫无遗漏地收集约占全球联网流量99%的光缆通信信息。《连线》杂志早在2012年就披露美国国家安全局已经开始在犹他州新建一座数据中心，【9】其有能力将互联网自诞生以来产生的所有流量全部保存下来，从而使其成为一种战略资源，供美情报机构在掌握量子计算能力后进行开发。因此，虽然量子计算机的出现可能还需要数十年，但这种能力本身已经具有了现实性威胁。


二、后量子密码是量子安全选项的重要组成部分

作为功能对立的两个领域，量子计算能力与量子安全选项的发展呈现出双螺旋上升的趋势，一方的显著进步必然带动另一方的迫切需求。在量子计算机发展受到业内广泛关注的当前，量子安全选项的研究与开发也被多国相关机构提上议事日程。

（一）后量子密码与量子加密技术构成了抵御量子威胁的组合方案

根据是否基于量子物理原理，量子安全选项可划分为两种基本类型，即后量子密码与量子加密技术。后量子密码（post-quantumcryptography），又被称为抗量子密码（quantum-resistantcryptography），是被认为能够抵抗量子计算机攻击的密码体制。此类加密技术的开发采取传统方式，即基于特定数学领域的困难问题，通过研究开发算法使其在网络通信中得到应用，从而实现保护数据安全的目的。后量子密码的应用不依赖于任何量子理论现象，但其计算安全性据信可以抵御当前已知任何形式的量子攻击。尽管大数分解、离散对数等问题能够被量子计算机在合理的时间区间内解决，但是基于其他困难问题的密码体制依然能够对这种未来威胁形成足够防御能力。更为重要的是，它们还可以与当前网络系统实现较高程度的兼容，从而会减小当前密码系统向后量子密码迁移可能面临的阻力。

量子加密技术是量子通信科学发展的成果之一，又被称为量子密钥分发（QuantumKey Distribution）。依靠包括叠加态、量子纠缠和不确定性等在内的量子物理独特性质，量子密钥分发技术能够实现传统密钥交换的功能，并且可以检测和规避窃听企图。【10】但这种方案也面临着包括成本和传播距离等因素在内的限制，而且攻击者还能够通过拒绝服务式攻击严重削弱量子密钥分发的效率。尽管上述两种加密手段目前都处于发展阶段，依然存在诸多问题需要解决，但是未来量子安全措施必然包含这些解决方案的恰当组合。

（二）后量子密码技术发展的重点是非对称密码系统

根据密钥类型的不同，密码技术通常可以划分为对称密码和非对称密码系统。在对称密码系统中，通信的双方使用完全相同的密钥，诸如DES、AES和3DES密码等都是典型的对称密码系统。这类密码通常具有良好的加密和解密运算效率，但对称密码系统的应用首先需要在通信双方之间建立并交换密钥。关于对称密码系统面临的量子计算威胁，目前仅有洛夫·格罗弗（LovGrover）在1996年提出的量子算法将对AES等对称密码系统产生影响，而且与经典计算机的破解速度相比，其能够产生效率优势仅仅是一般方法的平方。【11】通过密钥长度加倍的措施，这种威胁可以得到有效化解。

在目前大量应用的密码算法中，已知的量子计算威胁对非对称密码影响更加显著。与对称密码系统不同，非对称密码——又被称为公钥密码系统——使用两种独立的密钥，分别用于加密和解密信息。作为一种发展历史较短的加密方式，非对称密码系统有效解决了对称密码面临的安全密钥交换问题，因而广泛应用于公钥基础设施、数字签名、联合授权、公共信道密钥交换、安全电子邮件、虚拟专用网以及安全套接层等大量网络通信活动之中。【12】不幸的是，随着肖氏算法的提出，包括RSA密码、ECC密码系统以及DH密钥交换技术等非对称密码算法已经从理论上被证明彻底丧失了安全性。相对于对称密码系统还可以采取升级措施应对量子威胁，非对称密码系统必须采取全新方法进行重建，因而其也就成为后量子密码技术发展的重点领域。

（三）后量子密码的主要研究领域

当前，国际后量子密码研究主要集中于基于格密码（Lattice-basedcryptography）、基于编码（Code-basedcryptosystems）的密码系统、多元密码（Multivariatecryptography）以及基于哈希算法签名（Hash-basedsignatures）等领域。【13】

在所有被认为具有抵御量子威胁潜力的计算问题中，基于格密码系统在过去十年中得到了最为广泛的关注。与大数分解和离散对数问题不同，目前没有量子算法可以借助量子计算机对其进行破解。而且，格密码系统在最坏情况假设条件下依然具备安全性。在诸如RSA等公钥密码系统中，生成密钥需要选择2个既是质数又能形成分解困难问题实例的随机大数，但是这个过程中存在选择错误数字而导致安全性下降的可能性。而在格密码系统中，所有可能的密钥选择方式都能够形成足够的困难性。基于格加密的核心问题是最短向量问题（ShortestVector Problem, SVP），即在格系统内找到最短的非零向量。目前，NTRU密码以及带错误学习问题（LearningWith Error, LWE）是基于格密码系统发展实用前景最好的两种方式。

纠错码长期以来就在通信技术中发挥着重要作用，而从罗伯特·麦克利斯（RobertMcEliece）在1978年首次提出基于纠错码的加密技术概念以来，这项理论已经得到大量深入研究。此类密码系统加密过程速度非常快，而且解密速度也相对合理，阻碍其取得实际应用的最大问题是密钥长度。2001年，库尔图瓦（Courtois）、菲尼亚斯（Finiasz）和桑垂尔（Sendrier）又提出基于纠错码的数字签名体制CFS，其突出优势是签名长度短并且验证速度非常快，但其与麦克利斯密码系统一样，其面临的突出问题是密钥长度的限制。

多元加密系统的底层数学困难问题是求解有限域内的多元多项式，其可以应用于公钥密码系统及数字签名。多元密码系统中发展潜力最大的是简单矩阵（SimpleMatrix）密码体制。在这种密码系统中，所有计算都在一个有限域中完成，而解密过程只包含线性系统计算，从而使这种密码体制具备较高的运行效率。在多元加密签名系统中，所有计算操作都在单一有限域内完成的单域密码体制最具发展潜力，其中的典型代表包括UOV和Rainbow签名体制。

基于哈希算法密码系统能够在哈希函数的基础上提供一次性签名机制，其原理基于特定加密哈希函数的抗碰撞性。拉尔夫·默克尔（RalphMerkle）在1979年引入了这种密码原理研究方法，但是其在效率方面存在签名过长以及生成速度太慢等诸多短板。经过多年的发展，XMSS和SPHINCS哈希签名体制因其在签名长度和运行速度方面的优势得到较多关注，国际互联网工程任务组（InternetEngineering Task Force）当前还在试图推进并完成XMSS签名的标准化工作。

除了上述四种主要研究方向以外，近年来还出现了其他新型加密算法思路。【14】尽管在量子计算机上运行肖氏算法可以有效解决离散对数问题，但对于超奇异椭圆曲线上的同源问题，能够使其丧失安全性的类似攻击方法目前尚未出现。除此之外，共轭搜索问题（conjugacysearch problem）以及辫群（braidgroups）中的相关问题也受到研究者关注，但对共安全性的研究目前还处于初始阶段。


三、世界后量子密码技术研究发展现状

在向后量子密码系统迁移势在必行的情况下，相关领域的研究已经在国家之间引发“军备竞赛”。近年来，欧洲国家的“后量子密码”（PQCrypto）和“安全密码”（SAFEcrypto）项目和日本的CREST密码数学项目都取得了显著成果，美国也在相关政府机构和企业界的推动下，处于后量子密码研究和应用领域的领先地位。

（一）国际后量子密码学研究始终都在稳步推进

作为密码学的分支领域，国际后量子密码理论和技术研究一直以来都得到了各国的普遍关注，相关学术交流活动不仅在数量和频度上逐年增加，而且影响范围还在向更多国家和领域辐射。作为学术和企业界研究者的联合组织，成立于1982年的国际密码逻辑研究联合会（InternationalAssociation for Cryptologic Research）在2006年就已经开始举办第一届后量子密码技术国际会议。此次会议的成果在集中汇总于2008年出版的《后量子密码》，该书详细介绍了后量子密码研究的几乎全部潜在领域，在此之后，国际后量子密码技术的发展也基本上遵循着该书构建的技术框架。目前这项会议已经在北美、欧洲、东亚等地区连续举办7届，并且通过建立夏季或冬季培训营等形式在各国研究者之间交流和增强密码技术的发展。【15】

欧洲电信标准协会与加拿大滑铁卢大学量子计算中心联合举办的量子安全密码工作组会议（IQC/ETSIQuantum-Safe Crypto Workshop）也在国际后量子密码研究领域产生了重要影响。这项会议开始于2013年，参会代表来自于数学、密码学、物理学、计算机等不同研究领域，目标是实现标准化和部署下一代密码基础设施，特别是抵御量子计算能力威胁的冲击。【16】

亚洲密码研究学者也在积极跟踪相关技术发展的最新形势。2016年6月，首届亚洲抗量子密码论坛（PQCAsia Forum）我国成都顺利召开。【17】鉴于该领域研究工作的飞速发展，下一届东道主韩国首尔大学决定将原定于2017年召开的第二届亚洲抗量子密码论坛也提前到2016年11月。韩国国防部、韩国国家网络发展局、以及主管科技教育的政府部门和产业界，如三星电子等均派高级主管参会。

（二）后量子密码技术标准制定和迁移工作逐步受到政府组织的重视

密码系统的标准化工作是其大规模应用的前提。当前，多种后量子加密算法都已经在技术上具备了进行标准化的基本条件，并且包括美国国家标准与技术局在内的标准机构也开始发布后量子密码发展和迁移指导和实施计划。尽管密码标准体系的建立需要国际社会通过交流合作活动达成共识，但在密码研究领域取得领先的国家无疑将在标准制定过程中占据更多的主动权。

美国电气和电子工程师协会（IEEE）早在2008年就将NTRU加密算法确定为正式标准（Std1363.1-2008）。作为一种基于格加密解决方案，NTRU算法具备抵抗已知量子计算威胁的能力。在随后的2010年，其又被认可标准委员会（AccreditedStandards Committee X9）批准为可用于数据防护的新型加密标准。美国国家标准学会X9.98标准（ANSIX9.98）具体明确了金融交易通过公钥/私钥加密系统如何利用诸如NTRU等格加密算法的方式。虽然在实际应用过程中也面临着特定的漏洞威胁，NTRU算法依然是当前得到全面开发和批准的后量子公钥密码加密解决方案。

2015 年 8 月，美国国家安全局公开宣布由于面临量子计算的威胁，其计划将联邦政府各部门目前使用的ECC/RSA 算法体系向后量子算法进行迁移。而负责标准制定的美国国家标准与技术局也在 2016 年 2 月正式面向全球公开了后量子密码标准化的路线图，并在同年秋正式公布征集密码系统建议的计划，其中包括公钥密码、数字签名以及密钥交换算法，建议征集的截止日期定于2017年12月；此后，国家标准与技术局会利用3-5年时间分析这些建议并发布相关分析报告，最终的标准拟制工作也将耗时1-2年。换言之，国家标准与技术局后量子密码算法标准最终将在2021-2023年出台；而考虑到其具备较好的安全性能以及国际互联网工程任务组已经着手展开了标准化工作，基于哈希算法的签名标准可能会更快地推出。

除此之外，欧洲量子密码学术和工业界研究者联合组织“后量子密码”项目（PQCrypto）也在2015年发布了一份初始报告，在对称加密、对称授权、公钥加密以及公钥签名系统领域都提出了相关标准化建议。针对受到量子计算技术严重威胁的RSA/ECC密码系统，该报告认为麦克利斯密码系统具有发展成为新的公钥加密标准的潜力。

（三）企业界将在后量子密码发展应用过程中发挥重要影响力

从以往的密码系统标准化发展历史来看，任何密码系统都必须在应用过程中增强和完善性能，后量子密码也不例外。因此，通过新型密码产品的商业化推广使用活动，企业界能够不断积累和分析用户数据，从而促进后量子密码系统安全性能和运行效应的提升。

美国安全创新公司（SecurityInnovation）注册并拥有NTRU算法的专利，其提供两种授权选项：开源GNUGPL v2授权以及商业授权。从2011年起，该公司还发布了多种实现NTRU算法的软件库，其中包括安全套接字协议层（SSL）和ARM7/9处理器库等。NTRU工程（NTRUProject）网站中已经存在使用NTRU加密算法的Java和C程序应用。【18】目前，NTRU算法已经在处理能力有限的移动设备以及大容量服务器中得到应用。

进入2016年，美国两家主要信息技术公司在后量子密码应用领域的活动引起了外界关注。微软公司于4月发布了基于格密码库（LatticeCrypto），这种可移植软件的底层机制是基于环上带误差学习问题（RingLearning With Errors）。无论对于使用经典计算机或者量子计算机的攻击者，该软件库至少能够实现128位安全性能。【19】而且，此次发布的软件只是微软公司部署具备抗量子能力密码系统计划的初始措施，在积累足够使用数据后，软件的应用性和安全性也会不断提高。紧随微软公司之后，谷歌公司也于2016年7月在官方安全博客上宣布其将开始进行后量子密码技术的测试活动。【20】在对当前后量子密码技术发展进行调查后，谷歌决定应用这种被称为“新希望”的基于环上带误差学习问题密钥交换协议。虽然谷歌宣称测试工作只是在有限的用户群体中展开，而且其并不意在建立某种安全标准，但在此时实际测试后量子密码技术无疑将促使该公司发展形成全新的核心竞争力，而且在谷歌公司对互联网行业影响力的作用下，后量子密码技术的应用也势必得到有力的推进。（全文完）