量子计算对密码算法的颠覆性影响及抗量子攻击密码算法发展现状分析
量子计算目前是世界各地的尖端研究热点，并且可能会以每年量子量增加一倍的“量子摩尔定律”前进。但是，由于量子计算机的强大计算能力，一旦“量子霸权”成为现实，现有的加密系统可能会颠覆。本文分析了量子计算对现有的加密算法的影响，并总结了抵抗量子计算攻击的公共密钥加密算法的当前开发状态。
1。量子计算简介1。量子计算原理的概述
量子计算将Qubits作为基本单元，并通过量子状态的受控演变实现数据存储和计算。它具有携带能力和并行处理功能的信息，这些功能与经典计算无与伦比。量子计算机的原理和体系结构的示意图如图1所示。
图1：量子计算机的示意图
1）携带能力的量子信息
由于存在量子叠加态，量子位比经典位可以携带更多信息。
量子叠加：当没有外部观察干扰时，量子系统可以处于不同量子状态的叠加状态，即著名的“Schrödinger'sCat”。
Qubit：量子位可以代表0、1或0和1的叠加，因此它所传递的信息量远远超过只能代表0或1的经典位。
n经典的位存储器只能存储2 n可能的n位数字之一，而n个量子内存可以同时存储2^n数字，并且其存储信息的能力随着n的增加而呈指数增长。
2）量子并行处理能力
由于量子叠加效应，量子计算中的单一转换可以同时在叠加态中的所有组件上运行。因此，量子计算机可以同时执行多个并行计算，这也是量子计算机超强信息处理能力的来源。
在经典的计算中，所谓的并行性只是某个状态上的时间间隔过程。
在量子计算中，由于量子位的叠加状态特征，所有可能的状态都可以同时处理。
2。量子计算的开发过程
自概念诞生以来，量子计算已经通过理论探索，算法研究和技术验证。具体细节如图2所示。
图2：量子计算开发历史记录
2019年，Google宣布实现所谓的“量子至上”，即，量子计算机具有超出古典计算机的计算能力。他们使用更稳定的53 QUITABLE可编程超导处理器来完成随机量子线采样任务，而超级计算机通常需要数万年的时间才能完成。但是，由于诸如计算功能的局限性之类的因素，包括IBM在内的行业对Google是否真正实现了“量子霸权”。
应该注意的是，上述量子数是指物理位。由于存在噪声和物理位的不稳定性，需要大约800个物理位的冗余误差校正才能获得1位逻辑位，而目前没有组织无法实现1位逻辑位编码。
2。量子计算对加密系统的影响1。对称加密算法的影响
1）Grover算法
量子计算中的Grover随机数据库搜索算法可以提高空间搜索效率，而“指数减半”。如果通过详尽的搜索键的攻击复杂性来衡量对称加密的安全性，则将导致对称密码学的安全性减半，即在经典计算环境中安全的对称加密算法在量子计算环境中仅2^64安全。
影响：量子计算可以将诸如DES，AES，SM4和流媒体算法等数据包密码算法的安全性降低到原始的1/2。但是，由于Grover算法需要指数内存，因此对对称的加密算法几乎没有影响。
2）应对策略
增加关键长度：为了达到2^128的量子计算安全性，必须将对称密码的有效密码大小设计为至少为256位。应该注意的是，密钥长度的增加对加密和解密操作的速度有影响，但是影响是可控的，将其从密钥长度的约450mb/s减少到密钥长度256位的约320mb/s。
AES算法：支持256位密钥长度，可以暂时满足量子计算安全性。
SM4国家秘书处算法：关键长度固定在128位，可能会受到影响。
2。对哈希消化算法的影响
1）量子随机步行算法
量子随机行走算法可以提高经典搜索算法的时间效率，从而增加在一定时间内随机找到两个碰撞原始图像的可能性，从而实现了反碰撞蛮力破裂，并降低了悬浮算法的安全性。
影响：量子计算可以降低原始的Hash Digest算法的安全性，例如MD5，SHA和SM3至2/3。
2）应对策略
增加摘要长度：量子计算对哈希消化算法的影响很小，只需使用具有较大消化长的算法即可。
SHA算法：支持SHA-512支持支持，可以暂时满足量子计算安全性。当前，SHA-256在古典计算环境中被认为是安全的，因此至少应在量子计算环境中使用SHA-384。
SM3国家秘密算法：摘要长度固定在256位，可能受到影响。
3。对公共密钥密码学算法的影响
1）Shor算法
Shor量子算法可以解决多项式时间中的大型整数分解问题和离散对数问题。用2048位强度破解RSA钥匙可能需要超过10亿年的经典计算机，而Google表示，一台2000万个Qubit量子计算机可以在短短8个小时内破解2048位RSA算法。
影响力：量子计算可以基于大整数分解（例如RSA和公共密钥加密算法）基于离散对数（例如ECDSA和SM2）的公共密钥加密算法。
2）应对策略
替换新算法：在量子并行计算环境中很容易破解大整数分解和离散对数难度的问题，因此您可以考虑选择无法有效地平行计算来构建量子量子公共密钥密钥密码算法的数学难度问题。
4。概述对密码算法安全级别的影响
表1显示了经典计算环境和量子计算环境中各种加密算法的安全级比较。
表1：密码算法的安全级别的比较
3。量子加密算法的进度1。国内外的量子加密抗晶体计划
1）美国
2015年8月，国家安全局（NSA）宣布，将升级美国政府在2015年过渡期使用的加密套件的安全性，从2015年的正式发布量子加密标准的正式发布，如表2所示。
表2：美国过渡标准
算法说明功能标准参数国家秘密基准测试
AES
高级加密标准
块密码算法
FIPS Pub 197
使用AES-256
SM4仅支持128
ECDH
椭圆曲线差异 - 赫尔曼
关键谈判
NIST SP 800-56A
使用P-384椭圆曲线
SM2仅支持P-256椭圆曲线
ECDSA
椭圆曲线数字签名
数字签名
FIPS Pub 186-4
使用P-384椭圆曲线
SM2仅支持P-256椭圆曲线
莎
哈希算法
计算消息摘要
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个是数字签名算法。
公共密钥加密和钥匙谈判算法：自行车，Classicmceliece，Crystals-kyber，Frodokem，Frodokem，HQC，Lac，LeDacrypt，Newhopp，Newhope，Ntru，Ntruprime，NTS-KEM，NTS-KEM，Rollo，Rollo，Round5，Round5
数字签名算法：晶体 - 硅锂，猎鹰，宝石，路易夫，MQDSS，野餐，QTESLA，QTESLA，RAINBOW，SPHINCS+
与传统的不对称加密算法（例如支持加密和签名功能的RSA）不同，量子加密系统分别构建了公共密钥加密/密钥谈判算法和数字签名算法。
2）欧洲
2015年3月，欧洲电信标准协会ETSI建立了“量子密码安全行业标准工作组”，该工作组主要负责量子加密算法的收集，评估和标准表达。同年，欧盟连续推出了抗Quantum加密算法Projects Pqcrypto和Safecrypto。
欧洲量子加密算法的战略是与美国NIST的算法集合完全合作，并根据NIST的算法促进量子加密迁移。
3）亚洲
2016年，中国，日本，韩国和其他国家开始组织“亚洲反量子加密论坛”，该论坛分别在中国，日本和韩国举行。
在中国，中国密码学会于2019年发起了全国密码算法设计竞赛，并且收集的算法中有许多抗量子的加密算法。据报道，中国可能在2022年左右对量子加密算法进行标准化，并在2025年左右实施。
2。量子公共密钥密码学算法
由于有一些可以抵抗量子计算攻击的现有非公共密钥密码算法的版本，因此量子密码学主要讨论量子计算下公共密钥加密系统的替代方案。
1）反量子代码的定义
量子密码系统（也称为量词后加密系统）是指可以抵抗现有的经典计算攻击和未来量子计算攻击的密码系统。它至少应满足以下要求：
能够抵抗已知的经典攻击方法；
能够抵抗已知的量子计算攻击方法（例如Shor算法）；
在多项式中，没有已知的加密算法成功攻击。
无法通过量子离散的傅立叶变换来解决一些困难问题，例如网格（SVP）/最新矢量问题（CVP），方程式的非线性系统解决问题，背包问题等。您可以考虑构建基于此类问题的Quantam-Nargypographic Algorithm。
2）反量词代码分类
如表3所示，抗量词加密算法包括基于网格的密码，多元密码，基于哈希密码，基于哈希的密码，基于编码的密码和其他类型。
表3：抗量子加密分类
使用分类数学困难的示例
基于类别的密码
基于网格中的困难问题，主要包括LWE（学习错误），ring-lwe，sis等。
加密/签名/钥匙交换，等等。
NTRU，Newhope，Bliss，GLP
多元密码
在有限域上的多个二次多项式方程的求解难度
加密/签名
彩虹
基于哈希的密码
基于哈希算法的碰撞阻力
符号
括约肌，默克尔签名
基于编码的密码
基于编码理论中的困难问题（长线性代码的解码是NP问题）
加密/签名
mceliece
在第二轮NIST抗量词加密算法集合中的26个算法中，有12个基于网格的密码，7个基于编码的密码，4个多变量密码，2个基于哈希的密码和1个超级奇异的同源密码。其中，基于网格的LAC算法是由中国科学院信息技术研究所的研究团队提交的。
3）基于类别的密码
基于晶格的密码学是量子公共密钥加密算法的最具代表性类别。网格是与基团，环和域平行的代数结构，而LWE（学习错误）是网格中的困难问题。 2005年，Regev提出了LWE问题，并通过量子算法将LWE降低到网格上最短的矢量困难问题（SVP），并根据LWE提供了公共密钥密码术方案。与以前的网格上的困难问题相比，LWE在构建加密系统时更方便。
Ring-Lwe（在戒指上学习错误）是LWE的变体。在基于环的密码中，键由多个多项式表示，而不是LWE中的矩阵，从而降低了密钥大小，同时提高了加密和解密速度。
4）各种反量词代码的特征
表4显示了各种抗量子的加密算法的特征，例如基于网格的密码，多元密码，基于哈希的密码和基于编码的密码的特征。
表4：各种反量词代码的特征
基于类别的密码多元密码基于哈希的密码基于编码的密码
NTRU是早期代表，已成为欧洲的标准。目前，新算法主要基于LWE或RING-LWE
以彩虹为代表
默克签名
以GOPPA编码为基础的McEliece代表
群集密码可以实现加密，签名，密钥交换，同构和其他功能
主要是加密和签名的解决方案
只能实现数字签名，可扩展性差
主要是加密和签名的解决方案
NTRU不符合已验证的安全性，但在20年中没有受到损害；基于LWE或RING-LWE的算法满足了可靠的安全性
不满意可以证明安全，但可以抵抗已知的攻击
无数数学问题的基础可以证明安全而无需讨论
满足可靠的安全性
关键不是很大（几个KB）
钥匙稍大（超过100kb）
关键不是很大（几个KB）
密钥尺寸很大，131个Qubit安全性需要1024kb的公共密钥
量子加密算法最知名的类别
更快的速度，适用于不经常更换公共钥匙的场景，例如物联网
国家管理相对复杂，可以更换哈希算法
实用时，公共钥匙存储空间的高要求
4。摘要
目前，有些算法可以在传统的计算场中分解768位RSA整数，而量子计算机仅成功地分解了整数56153（约16位）。但是，RSA算法目前建议安全长度为2048位，并且需要一台具有2000万吨的量子计算机来通过Shor量子算法进行破解。目前，量子计算机尚未超过100位，因此量子计算机不会对现有的加密系统构成短期威胁。
尽管“量子霸权”尚未真正实现，但为了将来快速迁移到后量子加密系统，该行业需要考虑在计划长期申请时，量词后加密算法的兼容性。