上期，中国信息协会量子信息分会的康老师带我们剖析了量子安全概念的由来，其提出就是为了应对量子计算的挑战，两者是一矛一盾，一攻一防的关系。

“不知攻、焉知防”

本期，国小盾继续邀请康老师

带各位同学细探“量子计算”

01 量子计算攻击的特点

提起量子计算，经常听到的反应是量子力学“太抽象”，不确定性原理、量子纠缠等量子力学基本规律“反直觉”，量子计算又是属于典型的交叉学科“太综合”、“很难学”，这堂课不是量子计算教学，只是从量子安全这一角度对其进行一番临摹。

量子力学是在最基本的层面上针对物质和能量的研究，它的目标是揭示自然基本构件的属性和行为。而量子计算是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息，解决各类问题的新型计算技术。广义的量子计算还包括应用可控的量子体系对要研究的物理体系进行模拟，它一般也被称为量子模拟，1981年Richard Feynman首次提出量子计算机概念时也阐释为量子计算机能够对量子系统的演化进行有效模拟。

要理解量子计算，确实离不开这一系列抽象概念，而且同学们会发现，量子计算的定义在不同著作及论文、在不同场景和语境下也有多种形式的表达，在此以简洁易懂为原则，以满足我们对量子安全的理解为需求，而尽量不涉及无关的概念。

量子计算之所以具有经典计算无法比拟的信息携带和并行处理能力，是由于它以量子比特为基本单元，通过量子态的受控演化实现数据的存储和计算，以量子相干叠加和干涉来编码和处理信息，量子计算对量子相干叠加态的每一个叠加分量进行变换相当于一次经典计算，所有叠加分量变换对应的经典计算可同时完成，并按一定的概率振幅叠加，给出量子计算输出结果。

量子计算机是实现量子计算的物理装置，它可基于多种不同物理体系实现，如离子阱体系、超导电路体系、半导体量子点体系、腔量子电动力学体系、核磁共振体系、线性光学体系、拓扑体系等，这些物理体系拥有各自的优缺点，作为不同技术路线各自发展阶段和重点、要克服的主要困难也不同，这里就不做展开介绍了。但了解量子计算机的发展阶段对我们了解量子安全发展态势很必要。

第一个阶段是实现量子优越性（quantum advantage或quantum supremacy，也译为“量子霸权”），即针对特定问题的计算能力超越经典超级计算机。达到这一目标需要约50个量子比特的相干操纵。这一阶段目标已在2019年由Google公司在其超导量子计算系统上率先实现。2020年、2021年中国科学技术大学在其光量子计算原型机系统“九章”和超导量子计算原型机系统“祖冲之”上再次实现了量子优越性且性能显著提升，中国已成为世界上唯一一个在两个技术路线上实现量子优越性的国家。

第二个阶段是实现具有实际应用价值的专用量子模拟系统也就是专用量子模拟机，即相干操纵数百个量子比特，应用于组合优化、量子化学、机器学习等特定问题，指导材料设计、药物开发等，达到该阶段需要五至十年。例如，实现高斯玻色采样功能的“九章”量子计算原型机就是专用量子模拟机，还有当前D-Wave公司研发出来的量子退火机，它被大部分研究者认为还达不到这一阶段专用量子模拟机的要求。

第三个阶段是实现可编程通用量子计算机，即相干操纵至少数百万个量子比特，能在经典密码破解、大数据搜索、人工智能等方面发挥巨大作用。由于量子比特容易受到环境噪声的影响而出错，对于规模化的量子比特系统，通过量子容错、量子纠错等技术来保证整个系统的正确运行是必然要求，也是一段时期内面临的主要挑战。由于技术上的难度，何时实现通用量子计算机尚不明确，学术界一般认为还需要十年到二十年的时间。

如上图所示，实现容错量子计算需要一台拥有大量低错误率量子比特的量子计算机，其中虚线对应目前达到的错误率p=1%，实现通用量子计算需要错误率明显低于0.1%的阈值以及百万以上的物理量子比特，目前的技术还是无法实现的。

从上述发展阶段描述容易看出，一是实现实用的通用量子计算机技术难度很大，是一个需要全球学界、工业界长期艰苦努力的任务。目前研发出的量子计算机（如谷歌的Sycamore等）属于中型含噪量子（NISQ）计算阶段的初期，仍处于技术验证和原理样机研制阶段，仍面临量子比特数量少、相干时间短、出错率高等诸多挑战。二是比起通用量子计算，专用量子计算（或称非标准量子计算）会更早实现，对于破译密码这一具有战略价值的需求，是否会提前催生出专擅此道的量子专用机来？我们不得而知。

在此引述量子密码专家高飞、孙思维在2021年《密码学报》量子计算与密码分析专栏序言中开篇一段话作为总结——“量子计算是一种全新的计算模式，是一项可能对传统技术体系产生冲击、进行重构的重大颠覆性技术创新。量子计算在大整数分解、离散对数计算、密钥穷搜索等多个计算问题上展现出了显著优势，一旦成规模的通用量子计算机问世，将对一些密码体制构成严重的威胁。”

02 典型量子攻击——Shor算法

1994年，Peter Shor发现能够快速分解大数质因子的量子算法，由此展开了研究量子算法的第一次热潮，可见其重要性。Shor量子算法可以在多项式时间内解决大整数分解和离散对数求解等复杂数学问题，因此可以对广泛使用的RSA、ECC、DSA、ElGamal等公钥密码算法进行快速破解。例如：分解一个400位的大整数，经典计算机约需要5×10²²次操作，而量子计算机约需要6×10⁷次操作，量子计算机所需操作数仅为经典计算机的80万亿分之一。

Shor算法另一个重要特点是，RSA和ECC等公钥密码算法无法通过增加密钥长度抵御未来量子计算机使用Shor算法的攻击。研究表明，攻击RSA算法所需的量子比特数与RSA密钥的长度大致成线性比例关系，所需的量子门操作次数与RSA密钥的长度成多项式关系，也就是说，RSA算法无法通过增加密钥长度来抵御量子计算的指数加速攻击。

近期研究论文已表明，破解主流的2048位RSA加密，在可预见的未来就可能实现。2019年谷歌研究团队发文认为量子计算机将在8小时内破解2048位RSA加密，但需要2000万个量子比特。2021年法国研究者发布的研究成果表明，通过将量子存储器集成到量子计算机中，13436个量子比特耗费177天就能破解RSA-2048，比此前所需的量子比特数减少了3个数量级。根据IBM和谷歌的技术路线图，到2029年将实现百万量子比特，未来随着量子比特数的增加，破解时间将指数级缩减，Shor算法的实际破解威力也将愈加显现，密钥长度再增加也抵御不了这种指数级增长的攻击难易程度变化。况且，RSA-2048相较RSA-1024密钥长度进行了加倍，意味着运算时间、存储要求这些方面的增加不是简单的二倍关系而是更多。简单的认为现有公钥可以随意的将密钥长度增长下去以抵御量子攻击是错误的。

所以，结论就是，Shor量子算法对基于大整数分解和离散对数问题的公钥密码产生的严重威胁，无法通过增加密钥长度解决，需要采用新的、量子安全的密码算法和技术加以应对。

03 典型量子攻击——Grover算法

1996年Lov K. Grover提出了Grover量子算法。简单地说，它能够将无序数据库的搜索时间降为平方根时间。例如，当需要从N个未分类的客体中搜索出某个特定客体时，经典计算机需要一个个查询，直到找到所要的客体，平均要查（N+1）/2次，而采用Grover算法的量子计算机只需 N^(1/2) 次。

那么，搜索问题是如何扩展应用到密码破解问题上的呢？这是因为，依据计算复杂性理论，好的对称密码算法设计能在理论上等价于不可区分的伪随机数生成问题，而对于伪随机数的可区分性问题，一般认为又可以等价为无结构数据库的随机搜索问题求解这一问题。例如，Grover算法可以有效地攻破DES或轻量级算法等密钥长度较短的对称密码。对于DES破译而言，其本质就是从2⁵⁶个可能的密钥中寻找正确密钥。若以每秒10⁶次的运算速率，经典计算机要花1000年，而采用Grover算法的量子计算机所需时间低于4分钟。

对比于Shor算法，Grover算法破解密码的方式看似比较“暴力”，适用性也强——它同时适用于对称密码和公钥密码破译，但破解效率的比对却没有Shor算法那么悬殊，也就是Grover量子算法破解密码比传统计算机效率更高，但这个加速不是指数级加速，而是平方级加速，再通俗的说，Grover算法破解密码的能力基本上等价于将等效密钥长度减半。这也就直接导致了对Grover算法攻击的应对措施比较“温和”，密码界研究者一般公认需将对称密码算法使用的密钥长度加倍；对于无密钥参与的哈希函数,应将哈希函数输出长度加倍。

综合来看，可以用下表定性描述量子计算机对常用各类密码算法的影响（表格摘自Report on Post-Quantum Cryptography. NIST），可见，量子计算攻击下，很难有密码系统能够“事不关己”或“独善其身”。

在阐述量子计算攻击特点的最后，需要指出，一方面，量子计算、量子算法在快速发展之中，虽然人们认为，并非所有密码算法都容易受到量子计算的攻击，部分算法被认为是量子安全的，但对于评估什么计算问题是量子计算困难的，也要有发展和动态的视角。例如目前被认为是量子安全的算法在未来不再安全的可能性依然存在，这种不安全可能来自新的量子破译算法，也可能来自新的经典密码分析技术。另一方面，量子计算不是万能的，它不能完全取代经典计算，量子计算究竟能多大程度解决多少有重要实际应用价值的计算问题仍在研究和探索中。

04 量子计算攻击点是密码防线的软肋

量子计算作为一种未来可行的攻击方式，其攻击对象本来就是密码这一信息安全的基础，而从上面，我们知道了量子攻击是“有两把刷子”的，那如此厉害的攻击方式，如果选定的具体攻击点又很合适，岂不是可能造成的破坏效果要加倍不成。

在此要说，量子计算的主要攻击点——公钥密码特别是基于公钥密码的密钥管理，确实可以称是现有密码防线的软肋。原因如何，我们接着往下看。

密钥管理是密码系统的必备基础功能，在国标GB/T 17901.1-2020中，定义的密钥管理基本内容包括：生成、注册、认证、注销、分发、安装、存储、归档、撤销、派生以及销毁等。密钥管理内涵丰富、作用重大，它对密码系统起到支撑作用，与密码应用同等重要，可以说没有密钥管理也就没有密码应用。通俗地说，密钥管理与密码应用类似于乐队中的指挥与各乐手的关系，乐队的发声来自乐手，但乐手一定要受指挥的控制，在指挥的无声操控下，众多乐手才能奏响和谐的乐章。

现代密码学者的另一共识就是，密码算法和协议应当不包含秘密，而且最好是经过充分的公开，得到广泛的评估以保证其中无安全漏洞和缺陷。唯一需要保持秘密的是密钥。因此，密钥管理上需要更加严格的安全保护，例如安全防护级别应该更高，密钥管理功能的实现应单独组网、物理隔离，技术体制上也应与密钥应用尽可能有所区别、有独立性。这点也很容易理解，否则，若哪个密码应用系统被破解，会直接导致密钥管理系统的失效和被攻破，而且，借助管理系统与管理服务的“内部通道”，敌人很容易“攻破一点，殃及一片”。

形容管理技术相关的一句话我们都耳熟能详了——“三分技术、七分管理”，应用在密钥管理上也完全适用，因此人们才在高等级密码系统的密钥管理上经常采用人工递送的手段。往深入说，就是由于密钥管理的高度敏感性，新技术的应用人们会更加谨慎，更多的依靠管理上、工程上的重重手段去完成密钥管理任务。

从二战以后，可以说密钥管理上采用的最显著技术革新就是以CA（数字证书认证中心）为代表的公钥密码管理系统，由于公钥体制适用于商用环境下动态的、大规模的密钥分发需求，基于公钥体制的密钥管理系统应用广泛，数量众多。公钥系统的安全性历经了“多年考验”，公钥系统从效率上、商业上、管理上各个角度去衡量也无疑是成功的，在此我们也无意对公钥系统的安全性做具体讨论，但随着量子计算科技的发展，现用广泛的公钥算法受到了量子计算攻击的严重威胁是毋庸置疑的事实。而且就像上面所述一样，这一威胁不是采取拓展密钥长度这类工程性做法就都能解决的，必须靠发展和依靠量子安全的密码科技才能抵御这一威胁。

下期预告

下期小盾课堂将对目前能实现量子安全目标的两类解决方案——基于数学的抗量子计算密码算法和基于物理的量子密码进行介绍和阐述，敬请期待！