量子计算对密码学的威胁及应对方式

PrimiHub一款由密码学专家团队打造的开源隐私计算平台，专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。

当量子计算机问世时，许多加密方式将慢慢失去效果。本文将阐述原因以及正在研究的后量子密码学，以帮助人们适应后量子时代的密码学。量子计算机的出现不仅会对现代密码学构成挑战，还可能永远改变我们的数据加密方法。

关于量子计算机的大多数讨论都集中在为供应链优化和化学研究等领域带来的机遇。但同样有人担心量子计算机对密码学的影响，以及如今的加密方法是否足以保护数据安全。虽然这个威胁还要数年后才会出现，但数据中心管理员和安全团队应该重视它，并且早做规划以适应未来。

随着量子计算机研究和开发的不断深入，理论上量子计算机可以破解如今许多机构使用的加密方法。量子攻击可能会对非对称和对称密码学加密方法构成风险。因为量子计算机有足够的算力去破解他们。好在许多研究人员正在探索可以保护数据中心基础设施免受量子攻击的加密方法。

1.量子计算可能会削弱当前加密方法的安全性

现代密码学中的许多算法都是依赖于数学困难问题的难度。有了量子计算机，原本需要数年时间破解的密码，理论上在几天内就可以完成，而非对称加密和对称加密都面临这种风险。除了安全电子邮件和 Web 浏览等领域之外，许多机构经常在各种数据中心资产（包括存储和网络设备）中使用对称加密和非对称加密。

Shor算法对非对称加密构成威胁

Rivest-Shamir-Adleman(RSA)加密和大多数公钥加密(也称为非对称加密)是建立数学困难问题的基础上。例如，RSA基于大整数的质因数分解。根据IBM的说法,在公钥算法中会生成一个公钥和私钥,这两个密钥在数学上是相关的。即使用暴力破解，传统计算机也可能需要数年时间才能破解RSA等加密方法。

RSA和其他非对称算法的安全性取决于大整数分解的难度，因为大整数分解正是Shor算法的强项。许多公钥加密方法使用质因数分解来生成密钥，但理论上，Shor算法可以利用量子计算机的强大算力来破解非对称加密。根据欧洲数据保护委员会的技术和隐私部的说法,量子计算机可以在不知道私钥的情况下进行解密。

通过使用量子计算机，Shor算法也可能破解其他加密方案,包括Diffie-Hellman密钥交换协议和椭圆曲线加密(ECC)。

Grover算法针对对称加密

机构还可以使用对称加密来对存储数据进行加密，对称加密算法的示例包括高级加密标准 (AES)、RC4 和3DES。对称加密是使用单个密钥对数据进行加密和解密。例如，AES-256需要一个256位的密钥来加密和解密数据。根据IT管理和服务供应商N-able的计算，暴力攻击者需要从约1.1579209 x 10^77（2256）个可能的密钥中选出正确的密钥。这保证了AES-256和其他类似的对称加密算法的安全。

然而，假如攻击者可以使用量子计算机运算Grover算法，可以用更快地找到加密密钥。Grover算法比传统计算机比可以更快地搜索大型数据库。根据IBM的说法,如果一个算法有N个项目，Grover算法可以在√N步内搜索项目列表并找到特定项目。这减少了找到密钥所需的时间。

而且，攻击者还可以使用Grover算法和量子计算机破解哈希函数,，如SHA-2和SHA-3。

2.后量子密码学和抗量子加密的候选技术

人们正在研究各种加密方法，用以对抗基于量子计算的对数据中心基础设施和数据的攻击威胁。许多选择基于一些研究人员和专家认为可以抵抗量子计算的密码技术。
格密码学
格密码学是基于格和向量的数学概念。目前，大多数密码学遵循代数问题，而格密码学基于几何学。格密码学的困难问题是基于最短向量问题，攻击者必须找到一个离原点最近的点。但是，当引入多个维度而不是二维空间时，解决这个问题变得极其困难。一些人认为早期的量子计算机可能无法破解基于格的加密，这是最有希望的选择。

量子密钥分发

量子密钥分发(QKD)利用量子力学分发密钥。它依赖量子的特性：即如果你去测量一个量子系统，它就会被干扰。因此，如果恶意行为者试图拦截密钥，双方就会知道被窃听了。

光子通过光纤电缆在各方之间传输，其中每个光子具有随机量子态。当光子被传输并到达目的地时，它会通过分束器并选择一条路径或另一条路径随机进入光子收集器。由于接收方不知道正确的偏振，因此它会测量光子的偏振，并通过另一个通道与发送方共享该信息。用错误的分路器读取的光子被忽略，剩余的序列被用作密钥。

量子密钥分发仍在发展中。然而,美国国家安全局表示，它只是量子安全的一个部分解决方案。

编码密码学

编码密码学基于错误校正编码,它依赖于解码包含随机错误的消息的难度，攻击者必须恢复编码结构。其中最著名的是经典的McEliece算法。
NIST要求密码学家开始研究和开发量子安全的加密算法以供审阅，并考虑了McEliece。然而，NIST并没有将其标准化，因为它的公钥很大，正在对其进行进一步审查。

多变量密码学

多变量密码学基于解决方程组的难题。它使用一个随机的多项式方程组，其中接收者必须使用私钥对生成的密文执行逆运算。即使获取了加密数据，攻击者也必须解决方程式才能读取它，而这是一项艰巨的计算任务。

同源密码学

同源密码学与ECC类似，也使用椭圆曲线加密数据。它不是依赖ECC方法中的对数问题，而是依赖同源,也就是椭圆曲线之间的映射。与格密码学一样，这些计算可能足够困难，可以抵抗量子计算机的攻击。

各种组织正在研究的其他抗量子计算的加密方法，包括零知识证明和基于散列的密码系统。

3.我们如何为后量子密码学做准备

2016年，NIST要求密码学家开始研究和开发量子抗计算加密方法，并提交给NIST进行审查。2022年，NIST选择了四种潜在的抗量子计算加密算法，计划将它们纳入后量子密码标准，更多算法还在审查中。
NIST表示，这四种算法中有三种基于格结构，一种使用哈希函数。在第四轮审查中，NIST将检查另外四种算法。三种基于代数，一种基于同源曲线。有些将用于常规加密，有些将用于数字签名。
尽管专家普遍认为量子计算机对安全性的严重威胁还要多年后才会出现，但数据中心管理员和安全团队不应坐以待毙。量子计算机安全威胁可能不会成为问题——直到它们成为问题的时候。
安全专家Tim Hollebeek 在接受TechTarget采访时表示，人们应该看看他们的系统中使用密码学的地方，“它保护什么以及数据的被保护寿命有多久”。人们需要开始与安全团队和利益相关者合作，为后量子世界准备系统，并在需要时规划硬件和软件升级。及时了解NIST对后量子算法的审查情况，并评估抗量子计算的潜在加密方案。

原文地址：Explore the impact of quantum computing on cryptography
原文作者：Ryan Arel
翻译 & 整理：开放隐私计算 & PrimiHub