量子密码两大阵营：后量子密码与量子密钥分发

原创李少鹏数世咨询

后量子(Post-Quantum)是指，在量子计算机投入使用的时代，传统的密码体系面临极大的威胁和风险，如何“抵抗量子计算(Quantum-resistance)”带来的威胁，是许多国家政府和商业机构正在着手解决的挑战。量子密钥分发(QKD)则是一个由来以久的技术，但其发展也面临着重重困境。本文分别解读了二者的实现原理、关系区别与发展现状。

一、从量子至权谈起

几年前，还有很多人认为量子计算只是理论上存在，应用遥不可及。但随着中、美、英、加、澳、日、印等国庞大资金的投入，量子计算已经开始结出果实。去年底，谷歌率先发布“量子至权”(Quantum Supremacy)引起大量关注和争议。

（数世咨询：之前有很多媒体和机构将Quantum Supremacy译为“量子霸权”，但霸权偏向于政治含义而非技术含义。Supremacy一词的原意是至高无上或最高权力，因此数世咨询将其首译为“量子至权”。）

量子至权隐含了这样一个场景，保护网络空间多年的公开密钥体系面临淘汰，一夜之间，拥有量子计算机的国家可以破解多年来从敌对国家收集回来的秘密。无以数计的口令密码、私密谈话将会曝光，全世界的各国家的关键基础设施向攻击者敞开大门。考虑到军事、交通、能源、医疗等关键基础设施将遭受无法抵御的攻击，令我们无法忽视量子计算可能带来的巨大风险。

抵抗具备大规模并行处理能力的量子计算机，一个有效的方法就是，基于数学理论和计算机科学设计出难以破解的算法。但前提是，这种算法要易于部署和使用，否则无法普及。

二、非对称算法的问题

并非所有的传统密码技术在量子计算面前都不堪一击，比如基于对称算法的AES，以及基于哈希算法的SHA。但基于非对称算法的RSA和ECC（椭圆曲线密码），毫无疑问面临巨大的威胁。

（数世咨询：AES通常用来保护静态数据，SHA用于证明文件的完整性。两者共同的问题在于，由于其增加破解难度的手段是提升密钥的长度，所以需要大规模经典计算能力的支撑。）

非对称算法和PKI（公开密钥基础设施）解决了密钥交换过程中被拦截窃听的问题，当今互联网使用的加密通信协议SSL/TLS主要就是基于RSA算法，有时在计算能力较弱的移动设备和IoT设备则会用ECC来替代RSA。

互联网加密协议的重要性无需多言，可以说没有SSL/TLS就没有现在的电子商务和安全通信。但RSA和ECC在面对量子计算时，却非常脆弱。能够运行舒尔算法(Shor's Algorithm，一种基于量子计算来实现大整数质因数分解的算法）的计算设备，可以在数分钟或几小时内破解用RSA-2048加密的数据，而现在的经典计算机破解2048位的RSA理论上需要几十亿年。正因为如此，美国国家标准与技术研究院(NIST)才如此迫切地寻求能够替代RSA/ECC和抵御量子计算的方法--后量子密码。

三、后量子密码技术

2016年底，NIST发布了对后量子公钥密码标准的招募，旨在2024年完成横跨六种密码类别的量子安全标准。得到审核批准的算法将补充甚至是替代三个在量子攻击面前最为脆弱的标准：FIPS186-4（数字签名）、plusNISTSP800-56A和NISTSP800-56B（公钥密码）。同年初期，互联网巨头谷歌也做出了一个动作，在其Chrome浏览器中加入一个名为NewHope的加密协议，以观察和研究后量子密码技术。NewHope就是NIST后量子密码算法标准的申请者之一。2017年，网络加速公司Cloudflare宣布与谷歌合作，在真实环境下的用户设备上，对NewHope的使用能效进行评估。

基于编码的麦克艾利斯算法

NIST公布了后量子密码算法标准的招募之后，在2016年提交申请的69个算法中有26个通过了投票过程成为正式候选者，其中就有NewHope，属于“基于点阵”密码技术的类别。而“基于编码”的7家候选中，有一个名为“无重复密钥封装机制”(NTS-KEM)的算法，它的实现就以麦克艾利斯(McEliece)密码算法为基础。

麦克艾利斯密码算法首次公布于1978年，发明者麦克艾利斯本人在那个时代从未成名过，因为这个算法产生的密钥很大，小到100K大到几M，以当时的计算机能力来看，这个数字非常大。麦克艾利斯算法的特点，用数学语言来讲是一个“NP难题”，就是说尽管你知道迟早会破解出密钥，但由于超出了人类时间的尺度，所以也是没有意义的，哪怕用的是量子计算机！

麦克艾利斯之所以难以破解，是因为在纠错码机制(Error Correcting Codes)中引入了随机化。每次在加密同一段信息时，引入的错误是随机的。也就是说把同样一段明文变成密文的时候，每次的密文结果是不一样的。信息的接收者在解密时把加入的随机嗓音从密文中移除以得到明文，但对于没有纠错码的拦截窃听者而言，就只能望“文”兴叹了。对于现代的计算机来说，麦克艾利斯算法的密钥已经不算很大，甚至有些情况下加解密速度还要优于RSA，尤其是对于计算力较弱的小型设备而言。

除了“基于编码”(Code-based)和“基于点阵”

(Lattice-based)，后量子密码还包括，“基于哈希”(Hash-based)和“基于多元”(mq-based)等算法。但不管哪种算法，都需要解决落地的问题。为此，NIST要求后量子密码标准的申请者公开其算法，同时还要打包进密码类库(crypto libraries)并向上兼容现有的基础设施，以便于快速部署和应用普及。但想完全替代RSA并非易事，不仅仅是实施的问题，在功能上RSA也有很难取代的地方。如RSA同时支持加密和签名，但类似麦克艾利斯这种后量子密码算法只在加密方面具有优势。

密码敏捷性

在抗量子计算领域有一个重要的概念，密码敏捷性(Crypto-agility)，即在威胁态势发生变化时，在不用对信息基础设施进行很大变动的前提下，快速升级或替换原有密码机制及算法的能力。很明显，目前业界还不具备此能力。就连美国这个信息化程度最高的国家，如果想把银行柜员机从现有的数据加密标准(DES)升级到3DES，可能都至少需要十年。这对于数年内即将到来的量子时代而言，显然是不能接受的。

值得注意的是，现行的密码系统并不只受到量子计算的威胁。长期以来业界都高估了当代密码算法的防破解能力。RSA-768，这个在七十年代开始使用的密钥长度，曾被认为需要“7000年”才能破解，但在十年前，几位研究人员用非常普通的超算，仅用半天的时间就破解了它。

一方面我们需要密码敏捷性，以应对即将到来的量子风险。但另一方面，以现在的状况我们又达不到这种能力。因此，密码体系的通用框架不失为一个现实可行的解决方案。比如，在使用RSA的同时把后量子密码机制也容纳进来。等到量子计算来临时，关掉RSA切换到后量子密码算法。

密码敏捷性决定了后量子密码技术不仅要难于破解，还要能够替代现行密码体系的覆盖度。像麦克艾利斯算法这种基于编码的密码技术无法胜任这样的的要求，而基于点阵的密码技术在这方面则具有优势。

前文提及过谷歌的NewHope就属于“基于点阵”的密码技术，它的加密机制建立在几何学的基础之上。优点是适应性较好，像RSA一样同时支持加密和签名。缺点是需要更大的加密成本，否则容易被破解。当然，容易破解只是与麦克艾利斯这种算法比较而言。

四、真正的随机数生成：量子密钥分发

计算机领域的专业人士都知道，现代计算机由于其与生俱来且不可改变的本质，无法生成真正的随机数。经典计算机生成的都是伪随机数，是有规律可寻的。7年前斯诺登就曾经披露过，美国国家安全局已经破解了RSA的随机数生成器。

去年12月份，密码安全公司Keyfactor的研究人员发现，在使用RSA数字证书的物联网设备中，约有0.58%的设备使用相同的因式生成随机数。0.58%似乎是个很小的数字，但考虑到目前的百亿级数量和未来的千万亿台IoT设备，这个比例就非常恐怖了。但量子随机数生成器(QRNG)则完美的解决了伪随机数的问题，量子密钥分发(QKD)就是目前业内认可度最高的量子密钥生成机制。

早在1984年，两位研究人员Charles Bennett和Gilles Brassard，提出了一个名为BB84的QKD方案，现在几乎所有的QKD都是以BB84为基础的。与基于数学原理的后量子密码技术不同，量子密钥分发(QKD)来源于物理原理，利用亚原子粒子的量子纠缠现象，生成真正的一次一密的随机数，并杜绝了窃听者在不被发现地情况下截获密钥的可能，至少在理论上完全杜绝了中间人攻击。

（数世咨询：量子密钥的两大特征，一是真正的随机，因为代表着0和1的量子具体状态是不可预知的。二是无法窃听，因为一旦进行窃听量子状态就会发生改变，发送方和接收就会知道有人窃听，于是密钥作废。）

五、量子密码的困境

不管是后量子还是QKD，都面临着至少是目前来看难以解决的挑战。

技术与工程方面。由于量子特性非常敏感，任何的干扰都会给传输过程造成不可预知的影响，因此需要良好的天气和良好的传输介质，以及多个中继器和可信节点，才能实现更远距离的传输。而中继器和可信节点，由于必需对传输信号进行复制，因此量子状态消失，节点成为了新的攻击途径，从而打破了量子传输不可窃听的完美理论。另外，发送装置和检测装置也是脆弱点，攻击者对两者实施入侵，从而影响甚至篡改密钥生成过程。

标准与认证方面。作为一个新兴的还处于研究中的高端科技，极度缺乏相关标准和认证。如果双方没有安全的签名认证，如何判定对方的合法身份以交换密钥？

成本与应用方面。QKD的应用场景仅限于点对点通信，而现在包括互联网在内的绝大多数网络都是广播式的。另外，不管是对中继节点、发送检测装置的保护，还是整套设施的投入，都需要很大的建设和维护成本。

（数世咨询：实际上，因为成本和有效性等问题，QKD在我国目前还只处于研究阶段。但反观国外，如瑞士、美国、澳大利亚等民营企业已经推出了量子密码的商用产品。尤其是瑞士的ID-Quantique，早在2007年就在本国的竞选活动中部署了QKD，以保证投票的公正性，该企业已经成为全球主要的QKD厂商和QRNG硬件厂商。）

相对而言，后量子面临的技术挑战倒在其次，它的困难也在于成本和应用。要想替换RSA等已经非常成熟和应用普及的密码体系，成本必需大幅度下降。同时，具备密码敏捷性以增强应用场景的广泛性。考虑到这些问题，很可能未来能够大规模应用的后量子密码技术，要与传统安全密码技术结合起来，形成一种“混搭”模式以适用更多的需求。

从对量子密码技术的投入来看，基于物理原理的QKD与基于数学原理的后量子密码有着一定的竞争关系。虽然前者已经推出了商业化的产品，而后者还没进入实际应用阶段，但相信随着NIST后量子密码标准的遴选进程，后量子密码技术将会得到更多的关注和投入。实际上，QKD与后量子可以有着不同的应用场景，并互为补充。前者偏重于高价值、高安全等级资产（如骨干网）的保护，后者则可以像RSA一样，普及应用在现有的信息基础设施各个方面。

关键词：后量子；抗量子；量子至权；量子霸权；QKD；