量子计算对密码学的颠覆性影响及抗量子攻击公钥密码算法发展现状分析
量子计算目前是世界各地的尖端研究热点，并且可能会以每年量子量增加一倍的“量子摩尔定律”前进。但是，由于量子计算机的强大计算能力，一旦“量子霸权”成为现实，现有的加密系统可能会颠覆。本文分析了量子计算对现有的加密算法的影响，并总结了抵抗量子计算攻击的公共密钥加密算法的当前开发状态。
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。
2。对哈希消化算法的影响
1）量子随机步行算法
量子随机行走算法可以提高经典搜索算法的时间效率，从而增加在一定时间内随机找到两个碰撞原始图像的可能性，从而实现了反碰撞蛮力破裂，并降低了悬浮算法的安全性。
影响：量子计算可以降低原始的Hash Digest算法的安全性，例如MD5，SHA和SM3至2/3。
2）应对策略
增加摘要长度：量子计算对哈希消化算法的影响很小，只需使用具有较大消化长的算法即可。
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美国过渡期标准
2016年4月，美国国家标准技术研究所（NIST）宣布了反量子加密标准化计划：
到目前为止，NIST抗量词加密算法的实际进度如图3所示。
图3 NIST抗量词加密算法的实际进度
NIST总共收到了82种算法，在第一轮公告之前删除了13种算法。在其余的69种候选算法中，在2019年初的第二轮中只剩下26种有效的候选算法，其中17个是公钥加密和密钥谈判算法，而9个是数字签名算法。
与传统的不对称加密算法（例如支持加密和签名功能的RSA）不同，量子加密系统分别构建了公共密钥加密/密钥谈判算法和数字签名算法。
2）欧洲
2015年3月，欧洲电信标准协会ETSI建立了“量子密码安全行业标准工作组”，该工作组主要负责量子加密算法的收集，评估和标准表达。同年，欧盟连续推出了抗Quantum加密算法Projects Pqcrypto和Safecrypto。
欧洲量子加密算法的战略是与美国NIST的算法集合完全合作，并根据NIST的算法促进量子加密迁移。
3）亚洲
2016年，中国，日本，韩国和其他国家开始组织“亚洲反量子加密论坛”，该论坛分别在中国，日本和韩国举行。
在中国，中国密码学会于2019年发起了全国密码算法设计竞赛，并且收集的算法中有许多抗量子的加密算法。据报道，中国可能在2022年左右对量子加密算法进行标准化，并在2025年左右实施。
2。量子公共密钥密码学算法
由于有一些可以抵抗量子计算攻击的现有非公共密钥密码算法的版本，因此量子密码学主要讨论量子计算下公共密钥加密系统的替代方案。
1）反量子代码的定义
量子密码系统（也称为量词后加密系统）是指可以抵抗现有的经典计算攻击和未来量子计算攻击的密码系统。它至少应满足以下要求：
无法通过量子离散的傅立叶变换来解决一些困难问题，例如网格（SVP）/最新矢量问题（CVP），方程式的非线性系统解决问题，背包问题等。您可以考虑构建基于此类问题的Quantam-Nargypographic Algorithm。
2）反量词代码分类
如表3所示，抗量词加密算法包括基于网格的密码，多元密码，基于哈希密码，基于哈希的密码，基于编码的密码和其他类型。
表3：抗量子加密分类
在第二轮NIST抗量词加密算法集合中的26个算法中，有12个基于网格的密码，7个基于编码的密码，4个多变量密码，2个基于哈希的密码和1个超级奇异的同源密码。其中，基于网格的LAC算法是由中国科学院信息技术研究所的研究团队提交的。
3）基于类别的密码
基于晶格的密码学是量子公共密钥加密算法的最具代表性类别。网格是与基团，环和域平行的代数结构，而LWE（学习错误）是网格中的困难问题。 2005年，Regev提出了LWE问题，并通过量子算法将LWE降低到网格上最短的矢量困难问题（SVP），并根据LWE提供了公共密钥密码术方案。与以前的网格上的困难问题相比，LWE在构建加密系统时更方便。
Ring-Lwe（在戒指上学习错误）是LWE的变体。在基于环的密码中，键由多个多项式表示，而不是LWE中的矩阵，从而降低了密钥大小，同时提高了加密和解密速度。
4）各种反量词代码的特征
表4显示了各种抗量子的加密算法的特征，例如基于网格的密码，多元密码，基于哈希的密码和基于编码的密码的特征。
表4：各种反量词代码的特征
4。摘要
目前，有些算法可以在传统的计算场中分解768位RSA整数，而量子计算机仅成功地分解了整数56153（约16位）。但是，RSA算法目前建议安全长度为2048位，并且需要一台具有2000万吨的量子计算机来通过Shor量子算法进行破解。目前，量子计算机尚未超过100位，因此量子计算机不会对现有的加密系统构成短期威胁。
尽管“量子霸权”尚未真正实现，但为了将来快速迁移到后量子加密系统，该行业需要考虑在计划长期申请时，量词后加密算法的兼容性。
作者丨丁比亚安全团队
从丨freebuf.com选择
研究所简介
国际技术与经济学研究所（IETE）成立于1985年11月。它是隶属于国务院发展研究中心的非营利性研究机构。它的主要功能是在我国家的经济，科学和技术社会的发展中研究主要的政策，战略和前瞻性问题，跟踪和分析世界上科学，技术和经济发展趋势，并为中央政府以及相关部委和委员会提供决策咨询服务。 “全球技术地图”是国际技术与经济学研究所的官方微信帐户，致力于向公众传达最先进的技术信息以及科学和技术创新见解。
地址：北京海赖丁区的小南津大楼A大楼
电话：010-82635522