后量子时代的密码学

背景

目前的社会工程、钓鱼邮件、勒索软件攻击等都是由黑客和传统计算机完成的，如果黑客拥有一台量子计算机，那么将在瞬间完成攻击，破解银行账号密码窃取资金和信息等。此外，量子计算机还可以快速解密所有的流量信息。然而，量子计算机已经离我们越来越近了。

2019年，谷歌用53-Qubit的量子计算机证明了量子计算系统具备某些特殊能力可击败传统计算机(以2分30解决了超级计算机1000年才能解决的问题)，虽然IBM持有不同的意见，认为不需要1000年，仅需2天。但是本质上已经说明，量子计算机确实在特殊问题上超越了传统的超级计算机，这无疑会将人类带去一个从来就没有探索触及过的新天地。

2020年12月3日，《科学》杂志在线发表了中国科学技术大学潘建伟、陆朝阳等组成的研究团队与中科院上海微系统所、国家并行计算机工程技术研究中心合作的研究成果——“九章”量子计算机。“九章”是76 个光子 100 个模式的量子计算原型机，实现了具有实用前景的 “高斯玻色取样”任务的快速求解。根据现有理论，该量子计算系统处理高斯玻色取样的速度比目前最快的超级计算机快一百万亿倍(“九章”一分钟完成的任务，超级计算机需要一亿年)。其速度比去年谷歌发布的 53 个超导比特量子计算原型机快一百亿倍。

目前全球已经在开展保护数据和通信以应对量子计算机威胁的研究。后量子密码学就是可以抵抗量子计算机攻击的密码学算法。

量子计算是什么?

传统的计算机用比特来编码信息，每个比特用1或0来表示。量子计算机处理的是量子比特。量子计算机，就是由量子比特单元组建的量子中央处理器，在运行上，量子芯片遵循量子算法，对量子信息进行高效处理。量子计算机就是这样一种运算机器。现在的计算机使用的是电子的两种状态，也就是0和1，但是量子计算机则是使用电子的32个量子态，这让量子计算机拥有难以想象的、强大的并行计算能力。一个由250量子比特(包含250个原子)的存储器，可能存储数据高达2的250次方，比目前宇宙中所有的原子量还多。

量子计算对密码学的影响

Peter Shor 和 Lov Grover分别在1994年和1996年成功提出了两个使用量子并行性(quantum parallelism) 的算法。Shor 提出的方法可以攻破所有的公钥加密算法，因为公钥加密算法的安全性依赖于大整数分解或离散对数难题。包括RSA、EC-DSA、ECDHE等在内的公钥加密和签名方案受到影响。Grover提出的算法可以减少暴力破解攻击所需的时间。对AES和TDES 这样的公钥加密算法，只要拥有一台量子计算机，256比特的密钥的安全性相当于目前传统计算机对应的128比特的安全性。Grover提出的算法减少了碰撞攻击的时间，降低了哈希函数的安全强。有了量子计算机后，SHA256的安全强度也从128位降到了80位，SHA384的安全强度从192位降到了128位。

量子计算机对传统安全的威胁

量子计算机不仅仅可以打破加密通信，还可以破解目前经过加密的数据。如果有了量子计算机，用于认证和机密性的加密方案和密钥交换都需要改变;对对称密码学来说，不仅仅需要一种交换私钥的方式，还需要增加对称密钥的大小和哈希的大小。

美国国家标准和技术研究所NIST目前领导推进着一个名为后量子标准化(Post Quantum Standardization，PQS)的项目，旨在定义新的可应对量子计算机威胁的新算法。PQS 项目目前已经进入最后阶段，预计2年内将能够完成。

量子安全计算的过渡

为了实现到量子安全计算的过渡，SSH、IPSec、SSL\TLS等安全协议也需要进行升级，这些协议既需要与现有的协议相结合，也需要引入额外的一层来建立安全通信以应对对量子攻击的保护。

这一改变会对非对称加密和密钥生成算法产生影响，需要增加对称密码学算法的密钥大小。因此也会对性能和带宽带来影响。硬件厂商也需要对硬件进行升级以实现与这些新算法的一致和过渡。

本文翻