初学者指南
如果我们相信Edward Snowden的话，加密是“对抗监视的唯一真正保护”[1]。然而，量子技术的进步可能会危及这种保护措施。我们的文章讨论了为什么量子计算对数据安全构成威胁以及如何应对。我们不仅仅进行纯理论分析，还使用Python、C和Linux的代码示例进行讨论。
量子基础知识
当谷歌科学家在2019年报告了量子优势的第一个案例时，引起了极大的兴奋。量子计算可能对加密等领域产生重大影响。为了理解这个问题，我们需要讨论一些基础知识。
与经典计算机不同，量子计算机的算法不依赖于比特，而是依赖于量子比特（qubit）。比特只能取0或1的状态。当我们多次测量一个比特时，结果总是相同的。而对于量子比特，情况就不同了。听起来很奇怪，一个量子比特可以同时取值0和1。当我们重复测量它时，只有一定的概率得到结果0或1。在量子比特的初始状态下，测量得到0的概率通常是百分之百。然而，通过叠加，可以生成不同的概率分布。原因在于量子力学，遵循与“正常”生活不同的规律。
量子计算机的主要优势在于其概率性质。经典计算机在需要可靠地得到单一结果的问题上表现出色。而量子计算机则擅长处理概率和组合问题。当我们对处于叠加状态的量子比特执行操作时，该操作同时应用于值0和1。随着量子比特数量的增加，相对于经典计算机的优势也越大。一个具有三个量子比特的量子计算机可以同时处理多达八个值（2³）：即二进制数000、001、010、011、100、101、110和111。
科学文献一致认为，量子计算机将有助于解决以前看似棘手的问题。然而，目前还没有最佳的量子计算机可用。当前一代量子计算机被称为噪声中等规模量子（NISQ）计算机。这些计算机的处理能力有限，并且对错误非常敏感。现代设备提供多达几百个量子比特。例如，IBM在2022年推出了433量子比特的Osprey芯片。现在，该公司计划到2033年开发一台具有10万量子比特的计算机。
我们的文章解释了这种演进对数据安全构成的威胁。我们使用代码示例展示了量子计算机可能破解某些加密算法，并讨论了解决方法。源代码可在GitHub上获得。它是在Kali Linux 2023.2下使用带有Python 3.10的Anaconda开发的。
加密和质因数
在加密消息时，一个相对简单的方法是应用对称算法。这种方法使用相同的密钥对明文进行加密和密文进行解密。这种方法的一个主要挑战是发送方和接收方之间安全交换密钥。一旦私钥被第三方知晓，他们就有机会截获并解密消息。
非对称加密似乎是解决这个问题的方法。像RSA这样的方法使用不同的密钥进行加密和解密。在这里，加密是使用一个或多个公钥进行的，接收方将这些公钥提供给所有人。解密时，接收方使用一个只有他们知道的私钥。这样，发送方可以无风险地获得公钥，因为它本来就不是秘密。只有接收方的私钥必须受到保护。但是，当潜在攻击者知道公钥时，如何加强这样的过程呢？为此，非对称算法依赖于质因数分解等数学问题。
通过示例可以更好地理解质因数分解。在Python中，我们可以使用SymPy库的factorint函数来确定某个整数的质因数。
>>> import sympy>>> sympy.factorint(10){2: 1, 5: 1}>>> 2**1 * 5**110>>> sympy.factorint(1000){2: 3, 5: 3}>>> 2**3 * 5**31000>>> sympy.factorint(55557){3: 2, 6173: 1}>>> 3**2 * 6173**155557>>>上面的控制台输出说明了每个自然数都可以表示为质数的乘积。这些质数称为质因数。回想一下学校的时候，质数只能被1和自身整除。例如，数字10可以通过方程式10=2¹ * 5¹来表示。因此，数字10的质因数是2和5。类似地，数字55557可以通过方程式55557=3² * 6173¹来表示。因此，数字55557的质因数是3和6173。找出给定整数的质因数的过程称为质因数分解。
对于小数字来说，使用传统计算机进行质因数分解是简单的，但对于大整数来说则变得越来越困难。每增加一个数字，可能的组合数量就会大大增加。超过一定点后，传统计算机几乎无法确定质因数。例如，考虑以下来自RSA因子分解挑战（RSA Factoring Challenge）的数字（RSA-260），该挑战在2007年结束。在撰写本文时，该数字尚未被分解。
#!/usr/bin/env pythonimport sympyrsa_260 = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199print("开始分解...")factors = sympy.factorint(rsa_260)# 可能不会执行到这里print(factors)像RSA这样的非对称算法利用了质因数分解和类似问题的计算难度来保证加密的安全性。不幸的是，量子世界遵循自己的规律。
量子算法
在密码学方面，有两个量子算法特别令人关注。Shor算法提供了一种高效的质因数分解方法。当在大型量子设备上执行时，它理论上可以破解RSA等非对称方法。从实际角度来看，这种情况将在未来出现。2023年的一篇《自然》文章提到了至少需要100万个量子比特的数量。除了硬件之外，在大型量子机器上可靠扩展该算法的实现也很困难。IBM的Qiskit框架曾试图实现该函数，但在0.22.0版本中已被弃用。然而，可以在网上找到Shor算法的实验性实现。
Grover算法对对称加密构成威胁。它也被称为量子搜索算法，可以加速对给定函数输入的无结构搜索。量子计算机可以利用它来加速对对称加密信息的穷举攻击。然而，与Shor算法不同，提供的加速不是指数级的。简单来说，这意味着增加用于加密的密钥长度会使搜索变得极其昂贵。例如，对一个128位密钥进行穷举攻击最多需要2¹²⁸次迭代。假设Grover的搜索将这个数字减少到2⁶⁴，将密钥长度加倍到256位后，这个数字再次增加到2¹²⁸次迭代。这为可能的变通方法打开了大门。
对称变通方法
在某些条件下，对称加密是抵御量子算法的一种简单可用的方法。原因是Grover的搜索不会呈指数级增长，而Shor算法只对非对称方法构成威胁。根据当前的最佳知识，具有高度困难度的对称算法可以被认为是抵御量子攻击的。目前，美国NIST和德国BSI都将AES-256列入此类别[2][3]。AES是高级加密标准的缩写，256表示密钥的位长度。在Linux下，GNU隐私保护（GnuPG）实现了AES-256。以下shell脚本展示了如何使用AES-256加密文件，然后再解密。
# 加密gpg --output encrypted.gpg --symmetric --cipher-algo AES256 plain.txt# 解密gpg --output decrypted.txt --decrypt encrypted.gpg上面的脚本将文件“plain.txt”的内容加密，将密文写入到文档“encrypted.gpg”，然后再解密，并将输出保存到文件“decrypted.txt”。在加密之前，GnuPG会要求输入密码短语以生成私钥。出于安全原因，选择一个强密码短语并保持秘密非常重要。当解密时，GnuPG可能会缓存密码短语并不再要求输入。要清除缓存，可以执行以下shell命令。
gpg-connect-agent reloadagent /bye将GnuPG集成到Python中相对简单，可以使用subprocess模块实现。下面的代码片段展示了使用AES-256进行加密的原型实现。
#!/usr/bin/env pythonimport subprocessimport getpass# 读取口令passphrase = getpass.getpass("口令：")passphrase2 = getpass.getpass("口令：")if passphrase != passphrase2: raise ValueError("口令不一致！")# 执行加密print("正在加密...")args = [ "gpg", "--batch", "--passphrase-fd", "0", "--output", "encrypted.gpg", "--symmetric", "--yes", "--cipher-algo", "AES256", "plain.txt",]result = subprocess.run( args, input=passphrase.encode(), capture_output=True)if result.returncode != 0: raise ValueError(result.stderr)上述脚本使用getpass模块获取口令。确认后，口令通过标准输入传递给GnuPG。这通过参数passphrase-fd 0表示。此外，口令也可以通过命令行参数以字符串或文件的形式发送给GnuPG。然而，由于这些参数对其他用户可见，因此原型中都选择了拒绝这两个选项。另一种更安全的方式是使用GPG-Agent。选择哪种方式取决于所需的安全级别。这里提供了一个包括加密和解密的概念验证。除了GnuPG，还有其他AES-256的实现。在这里选择一个可信的源至关重要。
非对称解决方案
在寻找非对称解决方案时，NIST后量子密码学标准化计划是一个很好的起点。从2016年开始，该计划评估了多个用于抵抗量子攻击的算法候选。其中一个获胜者是Kyber。该系统实现了一种称为“安全密钥封装机制”的机制。与其他算法类似，Kyber依赖于一个难以解决的问题来保护两个参与方之间的密钥交换。它不是基于素数因子分解，而是基于一种称为“学习与错误”的问题。Kyber提供的保护级别取决于密钥长度。例如，Kyber-1024的安全级别“大致等同于AES-256” [4]。
在GitHub上可以找到Kyber的C语言参考实现。在Linux下，可以通过执行下面的命令来克隆和构建该框架。安装需要一些先决条件，这些条件在项目的README中有记录。
git clone https://github.com/pq-crystals/kyber.gitcd kyber/ref && make有多种方式可以将参考实现集成到Python中。其中一种方式是编写一个C程序并调用它。下面的C函数使用Kyber在两个虚构的参与方Alice和Bob之间执行密钥交换。完整的源代码请参见这里。
#include <stddef.h>#include <stdio.h>#include <string.h>#include "kem.h"#include "randombytes.h"void round_trip(void) { uint8_t pk[CRYPTO_PUBLICKEYBYTES]; uint8_t sk[CRYPTO_SECRETKEYBYTES]; uint8_t ct[CRYPTO_CIPHERTEXTBYTES]; uint8_t key_a[CRYPTO_BYTES]; uint8_t key_b[CRYPTO_BYTES]; //Alice generates a public key crypto_kem_keypair(pk, sk); print_key("Alice' public key", pk); //Bob derives a secret key and creates a response crypto_kem_enc(ct, key_b, pk); print_key("Bob's shared key", key_b); print_key("Bob's response key", ct); //Alice uses Bobs response to get her shared key crypto_kem_dec(key_a, ct, sk); print_key("Alice' shared key", key_a);}不详细展开，可以看到Kyber使用了多个公钥和私钥。在上面的示例中，Alice生成了一个公钥（pk）和一个私钥（sk）。接下来，Bob使用公钥（pk）派生出一个共享密钥（key_b）和一个响应密钥（ct）。后者返回给Alice。最后，Alice使用响应密钥（ct）和她的私钥（sk）生成一个共享密钥（key_a）的实例。只要双方保持他们的私钥和共享密钥秘密，该算法就提供保护。运行程序时，我们会得到类似下面文本的输出。
Alice' 公钥：F0476B9B5867DD226588..Bob 的共享密钥：ADC41F30B665B1487A51..Bob 的响应密钥：9329C7951AF80028F42E..Alice' 的共享密钥：ADC41F30B665B1487A51..为了在Python中调用C函数，我们可以使用 subprocess 模块。或者，也可以构建一个共享库，并使用 ctypes 模块调用它。下面的Python脚本实现了第二种选项。在加载从Kyber C代码生成的共享库之后，可以像调用其他Python函数一样调用 round_trip 过程。
#!/usr/bin/env pythonimport osimport ctypes# 加载共享库libname = f"{os.getcwd()}/execute_round_trip1024.so"clib = ctypes.CDLL(libname, mode=1)print("共享库加载成功：")print(clib)# 调用 round trip 函数print("执行 round trip：")clib.round_trip()除了Kyber的参考实现，其他供应商也实现了该算法。其中包括开源项目Botan和Open Quantum Safe。
结论
正如我们的分析所揭示的，量子技术仍处于早期阶段。但是我们不应低估它对加密和其他密码方法（如签名）的威胁。颠覆性创新可以随时推动发展。攻击者现在可以存储消息并以后解密。因此，应立即采取安全措施。特别是因为有可用的解决方法。正确使用的对称算法（如AES-256）被认为是抵抗量子攻击的。此外，像Kyber这样的非对称解决方案也在不断进步。选择使用哪种替代方案取决于具体应用。遵循“零信任”模型，采用多种方法的组合可以提供最佳保护。这样，量子威胁可能会像Y2K问题一样，成为一种自我实现的预言。
关于作者
Christian Koch 是 BWI GmbH 的企业架构师，也是纽伦堡技术学院 Georg Simon Ohm 的讲师。
Lucie Kogelheide 是 BWI GmbH 的后量子密码技术主管，负责发起公司的量子安全密码迁移过程。
Raphael Lorenz 是 Lorenz Systems 的创始人和首席信息安全官，专注于整体安全解决方案。
参考文献
- Snowden, Edward: Permanent Record. Macmillan, 2019.
- National Institute of Standards and Technology: NIST Post-Quantum Cryptography: FAQS. 29 June 2023. Accessed: 02 August 2023.
- Federal Office for Information Security (BSI): Quantum-safe cryptography — fundamentals, current developments and recommendations (PDF). October 2021. Accessed: 02 August 2023.
- CRYSTALS — Cryptographic Suite for Algebraic Lattices: Kyber Home. December 2020. Accessed: 02 August 2023.
免责声明
请注意，信息安全是一个关键的主题，作者对所发布内容不提供任何保证。