量子计算是目前全世界范围内的前沿研究热点，并可能正以量子体积每年翻倍的“量子摩尔定律”向前发展。然而，由于量子计算机的强大运算能力，一旦“量子霸权”成为现实，现有密码体制可能发生颠覆性的崩塌。本文就量子计算对现有密码算法的影响进行了分析，并总结了抗量子计算攻击的公钥密码算法的发展现状。
一、量子计算简介
1、量子计算原理概述
量子计算（Quantum Computing）以量子比特为基本单元，通过量子态的受控演化实现数据的存储计算，具有经典计算无法比拟的信息携带能力和并行处理能力。量子计算机的原理架构示意图如图1所示。
图1：量子计算机示意图
1）量子信息携带能力
由于量子叠加态的存在，与经典比特相比，量子比特可携带更多的信息。
量子叠加：在无外界观测干扰时，一个量子系统可以处在不同量子态的叠加态上，即著名的“薛定谔的猫”。 量子比特（Qubit）：一个量子比特可以表示0、1或0和1的叠加，因此其搭载的信息量远超只能表示0或1的经典比特。
一个n经典比特存储器只能存储2^n种可能的n比特数中的一个，而一个n量子比特存储器可以同时存储2^n个数，且其存储信息的能力随n的增加而指数上升。
2）量子并行处理能力
由于量子叠加效应，量子计算过程中的幺正变换可以对处于叠加态的所有分量同时进行操作。因此，量子计算机可以同时进行多路并行运算，这也是量子计算机超强信息处理能力的源泉。
在经典计算中，所谓并行性只是对一个确定的状态进行分时处理。 在量子计算中，由于量子比特的叠加态特性，可对所有可能状态进行同时处理。
2、量子计算发展进程
量子计算自概念诞生起发展至今经历了理论探索、算法研究、技术验证等阶段，具体如图2所示。
图2：量子计算发展历程
2019年，谷歌宣布实现所谓的“量子霸权（Quantum Supremacy）”，即量子计算机拥有一项超越经典计算机的计算能力，其使用更稳定的53量子比特可编程超导处理器仅用200秒就完成了随机量子线路采样任务，而超级计算机通常需要上万年的时间才能完成。但是，由于计算功能局限性等因素，谷歌是否真正实现了“量子霸权”受到了包括IBM在内的业界质疑。
需要注意的是，以上所述量子比特数量指的都是物理比特。由于噪声的存在以及物理比特的不稳定性，需要约800个物理比特的冗余纠错才能实现1位逻辑比特，而目前没有任何一家机构能实现1位逻辑比特的编码。
二、量子计算对密码体制的影响
1、对对称密码算法的影响
1）Grover算法
量子计算中的Grover随机数据库搜索算法能够以“指数减半”的效果提升空间搜索效率。对称密码的安全性如果以穷举搜索密钥的攻击复杂度进行衡量，将导致对称密码的安全性减半，即在经典计算环境下2^128安全的对称密码算法，在量子计算环境下只有2^64安全。
影响：量子计算可使DES、AES、SM4等分组密码算法和流密码算法的安全性降低为原来的1/2。但由于Grover算法需要指数级内存，其对于对称密码算法的实际影响不大。
2）应对策略
增加密钥长度：为了达到2^128的量子计算安全，需将对称密码的有效密码尺寸设计为至少256比特。需要注意的是，密钥长度增加对加解密运算速度有影响，但影响可控，从密钥长度128bit的约450MB/s降低至密钥长度256bit的约320MB/s。
AES算法：支持256比特密钥长度，可暂时满足量子计算安全。 SM4国密算法：密钥长度固定为128比特，可能受到影响。
2、对哈希摘要算法的影响
1）量子随机行走算法
量子随机行走算法可提高经典搜索算法的时间效率，进而增加一定时间内随机找到两个碰撞原像的概率，实现对抗碰撞性的暴力破解，降低哈希摘要算法的安全性。
影响：量子计算可使MD5、SHA、SM3等哈希摘要算法的安全性降低为原来的2/3。
2）应对策略
增加摘要长度：量子计算对哈希摘要算法的影响不大，只需采用摘要长度较大的算法即可。
SHA算法：最高支持SHA-512，可暂时满足量子计算安全。目前认为SHA-256在经典计算环境下是安全的，所以量子计算环境下至少应使用SHA-384。 SM3国密算法：摘要长度固定为256比特，可能受到影响。
3、对公钥密码算法的影响
1）Shor算法
Shor量子算法可以在多项式时间内破解大整数分解问题和离散对数问题。破解2048比特强度的RSA密钥可能需要经典计算机耗费10亿年以上的时间，而谷歌称2000万量子比特的量子计算机只需8小时就可破解2048比特RSA算法。
影响：量子计算可破解RSA等基于大整数分解的公钥密码算法和ECDSA、SM2等基于离散对数的ECC椭圆曲线公钥密码算法。
2）应对策略
更换新的算法：大整数分解和离散对数困难问题在量子并行计算环境下可被轻易破解，因此可考虑选取无法高效并行计算的数学困难问题构造抗量子公钥密码算法。
4、对密码算法安全级别的影响总览
各类密码算法在经典计算环境和量子计算环境的安全级别对比如表1所示。
表1：密码算法安全级别对比
三、抗量子密码算法进展
1、国内外抗量子密码计划
1）美国
2015年8月，美国国家安全局（NSA）宣布将美国政府使用的密码套件进行安全性升级，用于2015年至抗量子密码算法标准正式发布前的过渡期，如表2所示。
表2：美国过渡期标准
算法 | 算法描述 | 功能 | 标准 | 参数 | 国密对标 |
|---|---|---|---|---|---|
AES | 高级加密标准 | 分组密码算法 | FIPS Pub 197 | 使用AES-256 | SM4仅支持128 |
ECDH | 椭圆曲线Diffie-Hellman | 密钥协商 | NIST SP 800-56A | 使用P-384椭圆曲线 | SM2仅支持P-256椭圆曲线 |
ECDSA | 椭圆曲线数字签名 | 数字签名 | FIPS Pub 186-4 | 使用P-384椭圆曲线 | SM2仅支持P-256椭圆曲线 |
SHA | 哈希算法 | 计算消息摘要 | FIPS Pub 180-4 | 使用SHA-384 | SM3仅支持256 |
DH | Diffie-Hellman 密钥交换 | 密钥协商 | IETF RFC 3526 | 使用3072比特模值 | 3072位RSA相当于283位椭圆曲线，SM2无法满足 |
RSA | / | 密钥协商 | NIST SP 800-56B rev 1 | 使用3072比特模值 | 3072位RSA相当于283位椭圆曲线，SM2无法满足 |
RSA | / | 数字签名 | FIPS Pub 186-4 | 使用3072比特模值 | 3072位RSA相当于283位椭圆曲线，SM2无法满足 |
2016年4月，美国国家标准与技术研究院（NIST）公布了抗量子密码标准化计划：
2016年秋-2017年11月，面向全球征集抗量子密码算法； 2017年-2022年，进行3-5年的密码分析工作； 2022年-2023年，完成抗量子密码标准的起草与发布。
截至目前，NIST抗量子密码算法征集的实际进展如图3所示。
图3：NIST抗量子密码算法征集实际进展
NIST共收到82个算法，首轮公布前即淘汰了13个算法。在剩下的69个候选算法中，2019年初第二轮仅剩26个有效候选算法，其中17个为公钥加密与密钥协商算法，9个为数字签名算法。
公钥加密与密钥协商算法：BIKE、ClassicMcEliece、CRYSTALS-KYBER、FrodoKEM、HQC、LAC、LEDAcrypt、NewHope、NTRU、NTRUPrime、NTS-KEM、ROLLO、Round5、RQC、SABER、SIKE、ThreeBears 数字签名算法：CRYSTALS-DILITHIUM、FALCON、GeMSS、LUOV、MQDSS、Picnic、qTESLA、Rainbow、SPHINCS
与RSA等传统非对称密码算法同时支持加密与签名等功能不同，抗量子密码体制对公钥加密/密钥协商算法和数字签名算法进行分别构造。
2）欧洲
2015年3月，欧洲电信标准协会ETSI成立“量子密码安全工业标准工作组”，主要负责抗量子密码算法的征集、评估和标准制定。同年，欧盟相继启动抗量子密码算法项目PQCRYPTO和SAFECRYPTO。
欧洲在抗量子密码算法方面的策略是全力配合美国NIST的算法征集，并基于NIST的算法推动抗量子密码迁移工作。
3）亚洲
中国、日本、韩国等国家于2016年开始组织“亚洲抗量子密码论坛”，分别在中日韩三国举办。
在国内，中国密码学会于2019年开展了全国密码算法设计竞赛，在征集到的算法中不乏抗量子密码算法。据报道，中国或将于2022年左右开展抗量子密码算法标准化工作，于2025年左右实现应用落地。
2、抗量子公钥密码算法
由于现有非公钥密码算法存在可抵抗量子计算攻击的版本，因此抗量子密码主要讨论的是公钥密码体制在量子计算下的替代方案。
1）抗量子密码定义
抗量子密码体制也称为后量子密码体制（Post-Quantum Cryptography），是指既能抵抗现有经典计算攻击又能抵抗未来量子计算攻击的密码体制，至少应满足以下要求：
能够抵抗已知经典攻击方法； 能够抵抗已知量子计算攻击方法（如Shor算法）； 尚不存在已知的量子攻击方法在多项式内成功攻击的密码算法。
一些困难问题无法利用量子离散傅里叶变换解决，如格上的最短向量问题（SVP）/最近向量问题（CVP）、非线性方程组求解问题、背包问题等，可考虑基于此类问题构造抗量子密码算法。
2）抗量子密码分类
抗量子密码算法包含基于格的密码、多变量密码、基于Hash的密码、基于编码的密码等类型，具体如表3所示。
表3：抗量子密码分类
分类 | 数学困难问题 | 用途 | 举例 |
|---|---|---|---|
基于格的密码 | 基于格上的困难问题，主要有LWE（Learning with Errors）、Ring-LWE、SIS等 | 加密/签名/密钥交换等 | NTRU、NewHope、BLISS、GLP |
多变量密码 | 基于有限域上的多元二次多项式方程组的难解性 | 加密/签名 | Rainbow |
基于Hash的密码 | 基于Hash算法的抗碰撞性 | 签名 | SPHINCS、Merkle签名 |
基于编码的密码 | 基于编码理论中的困难问题（对长的线性码的译码是NP问题） | 加密/签名 | McEliece |
在NIST抗量子密码算法征集的第二轮26个算法中，有12个基于格的密码、7个基于编码的密码、4个多变量密码、2个基于Hash的密码、1个超奇异同源密码。其中，基于格的LAC算法由国内的中科院信工所研究团队提交。
3）基于格的密码
基于格的密码（Lattice-Based Cryptography）是目前抗量子公钥密码算法中最具代表性的一类。格是一种与群、环、域并列的代数结构，LWE（带错误的学习）是格上的困难问题。2005年，Regev提出LWE问题并通过量子算法将LWE归约到格上的最短向量困难问题（SVP），并给出了基于LWE的公钥密码方案。与之前出现的格上困难问题比较，LWE在构建密码系统时更方便。
Ring-LWE（环上带错误的学习）是LWE的变体。在基于Ring-LWE的密码中，密钥由若干个多项式表示，而不是LWE中的矩阵，因而减小了密钥大小，同时提高了加解密速度。
4）各类抗量子密码特点
基于格的密码、多变量密码、基于Hash的密码、基于编码的密码等各类抗量子密码算法的特点如表4所示。
表4：各类抗量子密码特点
基于格的密码 | 多变量密码 | 基于Hash的密码 | 基于编码的密码 |
|---|---|---|---|
以NTRU为早期代表，已在欧洲成为标准；目前新算法多基于LWE或Ring-LWE | 以Rainbow等为代表 | 以Merkle签名为代表 | 以基于Goppa编码的McEliece为代表 |
格密码可实现加密、签名、密钥交换、同态等功能 | 以加密和签名方案为主 | 仅能实现数字签名，可扩展性较差 | 以加密和签名方案为主 |
NTRU不满足可证明安全，但20年未被攻破；基于LWE或Ring-LWE的算法满足可证明安全 | 不满足可证明安全，但能抵抗已知攻击 | 无数学难题做基础，不讨论可证明安全性 | 满足可证明安全 |
密钥不大（几KB） | 密钥稍大（超过100KB） | 密钥不大（几KB） | 密钥尺寸较大，131量子比特安全需要1024KB公钥 |
抗量子密码算法中最受认可的一类 | 速度较快，适用于无需频繁更换公钥的场景，如物联网 | 状态管理较为复杂，可更换哈希算法 | 实用时对公钥存储空间要求较高 |
四、总结
目前，传统计算领域已有可分解768位RSA整数的算法，而量子计算机仅成功分解了整数56153（约16比特）。然而，RSA算法目前建议的安全长度为2048比特，需要2000万量子比特的量子计算机才能通过Shor量子算法实现破解，而目前量子计算机还未突破100位，因此量子计算机对现有密码体制不具有短期威胁。
虽然“量子霸权”还未真正意义上实现，但为了未来能够快速向后量子密码体制迁移，业界在布局长期应用时需要考虑后量子密码算法的兼容性。
*本文作者：狴犴安全团队，转载请注明来自FreeBuf.COM
