其他
密码体制如何应对“量子霸权”？
前沿君微信：tech99999 手机：18501361766
来源：全球技术地图
作者：狴犴安全团队
量子计算是目前全世界范围内的前沿研究热点，并可能正以量子体积每年翻倍的“量子摩尔定律”向前发展。然而，由于量子计算机的强大运算能力，一旦“量子霸权”成为现实，现有密码体制可能发生颠覆性的崩塌。本文就量子计算对现有密码算法的影响进行了分析，并总结了抗量子计算攻击的公钥密码算法的发展现状。
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。
2.对哈希摘要算法的影响
1）量子随机行走算法
量子随机行走算法可提高经典搜索算法的时间效率，进而增加一定时间内随机找到两个碰撞原像的概率，实现对抗碰撞性的暴力破解，降低哈希摘要算法的安全性。
影响：量子计算可使MD5、SHA、SM3等哈希摘要算法的安全性降低为原来的2/3。
2）应对策略
增加摘要长度：量子计算对哈希摘要算法的影响不大，只需采用摘要长度较大的算法即可。
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 美国过渡期标准
2016年4月，美国国家标准与技术研究院（NIST）公布了抗量子密码标准化计划:
截至目前，NIST抗量子密码算法征集的实际进展如图3所示。
图3 NIST抗量子密码算法征集实际进展
NIST共收到82个算法，首轮公布前即淘汰了13个算法。在剩下的69个候选算法中，2019年初第二轮仅剩26个有效候选算法，其中17个为公钥加密与密钥协商算法，9个为数字签名算法。
与RSA等传统非对称密码算法同时支持加密与签名等功能不同，抗量子密码体制对公钥加密/密钥协商算法和数字签名算法进行分别构造。
2）欧洲
2015年3月，欧洲电信标准协会ETSI成立“量子密码安全工业标准工作组”，主要负责抗量子密码算法的征集、评估和标准制定。同年，欧盟相继启动抗量子密码算法项目PQCRYPTO和SAFECRYPTO。
欧洲在抗量子密码算法方面的策略是全力配合美国NIST的算法征集，并基于NIST的算法推动抗量子密码迁移工作。
3）亚洲
中国、日本、韩国等国家于2016年开始组织“亚洲抗量子密码论坛”，分别在中日韩三国举办。
在国内，中国密码学会于2019年开展了全国密码算法设计竞赛，在征集到的算法中不乏抗量子密码算法。据报道，中国或将于2022年左右开展抗量子密码算法标准化工作，于2025年左右实现应用落地。
2、抗量子公钥密码算法
由于现有非公钥密码算法存在可抵抗量子计算攻击的版本，因此抗量子密码主要讨论的是公钥密码体制在量子计算下的替代方案。
1）抗量子密码定义
抗量子密码体制也称为后量子密码体制（Post-Quantum Cryptography），是指既能抵抗现有经典计算攻击又能抵抗未来量子计算攻击的密码体制，至少应满足以下要求：
一些困难问题无法利用量子离散傅里叶变换解决，如格上的最短向量问题（SVP）/最近向量问题（CVP）、非线性方程组求解问题、背包问题等，可考虑基于此类问题构造量子密码算法。
2）抗量子密码分类
抗量子密码算法包含基于格的密码、多变量密码、基于Hash的密码、基于编码的密码等类型，具体如表3所示。
表3：抗量子密码分类
在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：各类抗量子密码特点
四、总结
目前，传统计算领域已有可分解768位RSA整数的算法，而量子计算机仅成功分解了整数56153（约16比特）。然而，RSA算法目前建议的安全长度为2048比特，需要2000万量子比特的量子计算机才能通过Shor量子算法实现破解，而目前量子计算机还未突破100位，因此量子计算机对现有密码体制不具有短期威胁。
虽然“量子霸权”还未真正意义上实现，但为了未来能够快速向后量子密码体制迁移，业界在布局长期应用时需要考虑后量子密码算法的兼容性。
| 一网打尽系列文章，请回复以下关键词查看： |
|---|
| 创新发展：习近平 | 创新中国 | 创新创业 | 科技体制改革 | 科技创新政策 | 协同创新 | 科研管理 | 成果转化 | 新科技革命 | 基础研究 | 产学研 | 供给侧 |
| 热点专题：军民融合 | 民参军 | 工业4.0 | 商业航天 | 智库 | 国家重点研发计划 | 基金 | 装备采办 | 博士 | 摩尔定律 | 诺贝尔奖 | 国家实验室 | 国防工业 | 十三五 | 创新教育 | 军工百强 | 试验鉴定 | 影响因子 | 双一流 | 净评估 |
| 预见未来：预见2016 |预见2020 | 预见2025 | 预见2030 | 预见2035 | 预见2045 | 预见2050 |
| 前沿科技：颠覆性技术 | 生物 | 仿生 | 脑科学 | 精准医学 | 基因 | 基因编辑 | 虚拟现实 | 增强现实 | 纳米 | 人工智能 | 机器人 | 3D打印 | 4D打印 | 太赫兹 | 云计算 | 物联网 | 互联网+ | 大数据 | 石墨烯 | 能源 | 电池 | 量子 | 超材料 | 超级计算机 | 卫星 | 北斗 | 智能制造 | 不依赖GPS导航 | 通信 | 5G | MIT技术评论 | 航空发动机 | 可穿戴 | 氮化镓 | 隐身 | 半导体 | 脑机接口 | 传感器 |
| 先进武器：中国武器 | 无人机 | 轰炸机 | 预警机 | 运输机 | 直升机 | 战斗机 | 六代机 | 网络武器 | 激光武器 | 电磁炮 | 高超声速武器 | 反无人机 | 防空反导 | 潜航器 |
| 未来战争：未来战争 | 抵消战略 | 水下战 | 网络空间战 | 分布式杀伤 | 无人机蜂群 | 太空战 | 反卫星 |
| 领先国家：美国 | 俄罗斯 | 英国 | 德国 | 法国 | 日本 | 以色列 | 印度 |
| 前沿机构：战略能力办公室 | DARPA | 快响小组 | Gartner | 硅谷 | 谷歌 | 华为 | 阿里 | 俄先期研究基金会 | 军工百强 |
| 前沿人物：钱学森 | 马斯克 | 凯文凯利 | 任正非 | 马云 | 奥巴马 | 特朗普 |
| 专家专栏：黄志澄 | 许得君 | 施一公 | 王喜文 | 贺飞 | 李萍 | 刘锋 | 王煜全 | 易本胜 | 李德毅 | 游光荣 | 刘亚威 | 赵文银 | 廖孟豪 | 谭铁牛 | 于川信 | 邬贺铨 |
| 全文收录：2017文章全收录 | 2016文章全收录 | 2015文章全收录 | 2014文章全收录 |
| 其他主题系列陆续整理中，敬请期待…… |