早在 2016 年,有关量子计算机的文章就已在数据安全领域引发不确定性——前提是能够构建出足够强大的量子计算机。本文试图厘清这一局面。
什么是量子计算?
量子计算是量子力学原理在计算中的应用。具体而言,量子计算利用亚原子粒子(如叠加态和纠缠态)的量子态来创建量子计算机。当应用于具有足够算力的量子计算机时,特定算法能够比经典计算机快得多地完成计算,甚至解决当前计算技术无法触及的问题。因此,全球政府和行业对开发量子计算机的兴趣日益浓厚。量子计算近期的进展,如 IBM 的 Quantum Heron 处理器,已显著改善了错误抑制,展示了该领域的快速进步。配备这些先进处理器的 IBM Quantum System Two 的推出,标志着向以量子为中心的实用超级计算迈出了一大步。
经典计算 vs 量子计算
经典计算依赖比特(bit),通过电路中的电流表示 1 和 0,来解决复杂问题。量子计算利用量子比特(如 IBM Quantum Heron 中的那些),通过增强的纠错和量子比特稳定性,在计算能力上超越经典计算。
与比特不同,量子比特可以处于叠加态,同时代表 1 和 0。这一能力允许单个量子比特同时表示两种状态,并且每多一个量子比特,可表示的状态就呈指数级翻倍(n 个量子比特为 2^n)。例如,一台拥有 10 个量子比特的量子计算机可以表示 1024 种状态,而经典计算中的 10 个比特则只能表示 10 种。
量子纠缠是一种复杂且尚未被完全理解的现象,它使量子比特相互关联,从而提高计算效率。通过同时利用叠加和纠缠,量子计算机在多维空间中运行,执行并行计算,这与经典计算的顺序方法不同。
这种先进的计算能力使量子计算机能够处理经典计算机无法触及的问题,例如精确模拟化学反应中的分子相互作用。这对科学和技术具有深远影响,包括可能比经典计算机快得多地解决问题,影响到密码学等领域。
量子计算如何影响密码学?
如上所述,密码学基于难以处理的数学问题而存在——这并不意味着它们无法求解,而是逆转它们所需的时间和资源使其在实践中是安全的。
量子计算通过应用特定算法来最小化求解此类问题所需的时间,从而改变了这一生态。
例如,Shor, P.W. (1994) 发现的算法《Algorithms for Quantum Computation》,以及该算法在 IBM 的 Quantum Heron 等先进量子处理器背景下的意义,凸显了对抗量子密码系统的迫切需求。
"1994 年,贝尔实验室的 Peter Shor 指出,量子计算机——一种利用物质和能量的物理特性进行计算的新技术——可以高效求解这些(基于数论的)问题中的每一个,从而使所有基于此类假设的公钥密码系统失效。因此,一台足够强大的量子计算机将使许多现代通信形式——从密钥交换到加密再到数字认证——陷入危险。"
简而言之,一台具有足够算力的量子计算机可能直接摧毁公钥基础设施,从而需要重新设计整个网络安全生态。
后量子密码学(PQC)最近的消费者应用已出现在 Chrome 对某一 PQC 算法的支持中,这表明量子计算对当前密码系统的实际影响。
但这还不是全部。另一个由 Grover, Lov K. (1996) 提出的算法《A fast quantum mechanical algorithm for database search》可能对对称密码学构成威胁,尽管其严重性不及 Shor 的算法。当应用于足够强大的量子计算机时,Grover 算法能以四倍于经典计算的速度破解对称密钥。这是一个显著的提升,但可以通过使用更大的密钥并保持当前安全水平来应对。
量子计算很快会到来吗?
物理学已经证明量子计算是可行的。现在,这是一个工程问题,尽管是一个极其困难的问题。量子计算机的构建涉及最先进技术的实施,其中包括 superfluids 和超导体。创建稳定且可扩展的量子力学系统这一挑战是巨大的,它促使全球各地的团队追求不同的路径。量子计算机有若干种类型,包括量子电路模型、量子图灵机、绝热量子计算机、单向量子计算机以及各种量子元胞自动机。其中最广泛使用的是量子电路模型。
任何模型的一个重大问题是,就其本质而言,量子比特一旦被测量就会失去其叠加态,因此对外部干扰极为敏感。因此,量子比特很难维持其量子态。一些解决方案包括使用离子阱,但完全消除外部干扰可能难以实现。因此,创建量子计算机最关键的问题之一是稳健的纠错机制。
随着 IBM 在量子计算方面的近期突破,该领域已超越理论模型,迈向更实用、更强大的量子系统,使量子时代比此前预期的更近。
总体来看,突破可能正在此刻发生,也可能需要数年时间才能创造出具有足够算力的可用原型。已经有一些原型,其中 IBM Q System One 最为著名,但它们的算力仍然太小,不足以对密码系统构成威胁。当然,网络安全界绝不可松懈。即使我们拥有了高效的后量子安全方案,将整个生态迁移到这一新标准也是一项巨大的任务。因此,多项工作正在进行中,以迎接后量子时代。
后量子时代极具前景的技术
随着我们接近量子技术的广泛应用,对抗量子的 PKI 的需求变得愈发迫切。下面,我们将尝试总结最有前景的算法家族,并对旨在建立后量子密码学的集体项目及其面临的挑战作简要回顾。
后量子算法家族
过去 15-20 年的研究已经证明了抗量子攻击算法的存在。下面我们简要描述最有可能为后量子世界提供安全方案的算法家族。
基于编码的密码学(Code-based Cryptography)
该领域近期的进展使用纠错码来构建公钥密码学。它最早由 Robert McEliece 于 1978 年提出,是最古老、研究最深入的非对称加密算法之一。基于 Niederreiter 方案(McEliece 方案的二元变体)可以构建签名方案。McEliece 密码系统迄今抵御了密码分析。原始系统的主要问题在于公私钥尺寸过大。
基于哈希的密码学(Hash-based Cryptography)
随着在实际应用中的日益部署,基于哈希的密码学代表了一种极具前景的后量子数字签名方法。哈希函数是将任意长度字符串映射到固定长度字符串的函数。它们是最古老的公钥密码学方案之一,其针对经典和基于量子的攻击的安全性评估已被充分理解。哈希函数已经是最广泛使用的密码学工具之一。长期以来人们已知它们可以单独作为构建公钥密码学的工具。此外,基于哈希的密码学灵活,能满足不同的性能预期。不利的一面是,基于哈希的签名方案主要是有状态的(stateful),意味着私钥需要在每次使用后更新,否则安全性无法保证。也存在无状态的方案,但代价是更长的签名、更长的处理时间,以及签名者需要追踪某些信息(例如密钥被用于创建签名的次数)。
基于格的密码学(Lattice-based Cryptography)
正被考虑用于更先进的密码学解决方案,基于格的密码学是基于子集和问题(subset sum problem)的密码学的特例,最早由 Ajtai 于 1996 年提出。它是利用格构建的密码学原语的统称。其中一些构造似乎能同时抵抗量子和经典计算机的攻击。此外,它们还具有其他吸引人的特性,如最坏情况困难度(worst-case hardness)。它们还表现出简洁性和并行性,并且足够通用,可构建稳健的密码学方案。最后,它们是唯一一个包含构建后量子公钥基础设施所需全部三类原语——公钥加密、密钥交换和数字签名——的算法家族。
多变量密码学(Multivariate Cryptography)
多变量密码学指的是公钥为多元非线性(通常为二次)多项式映射的公钥密码学。求解这些系统已被证明是 NP 完全的,因此使该算法家族成为后量子密码学的良好候选。当前,多变量加密方案被证明不如其他方案高效,因为它们需要相当大的公钥和较长的解密时间。另一方面,它们更适合构建签名方案,因为在后量子算法中它们提供最短的签名尺寸,尽管它们会带来相当大的公钥。
基于同源的密码学(Isogeny-based Cryptography)
基于同源的密码学利用椭圆曲线之间的映射来构建公钥密码学。作为后量子密码学候选的算法是 2011 年提出的超奇异同源 Diffie-Hellman 密钥交换(SIDH),使该方案成为候选中最新的一个。SIDH 在提出的密钥交换方案中需要最小的密钥之一,并支持完美前向保密。然而,其相对年轻意味着基于该概念的方案并不多,也缺乏对其潜在漏洞的充分检视。
后量子密码学项目
存在多个后量子密码学方案的工作组,如 Open Quantum Safe(OQS)项目和 ENISA。但最连贯的倡议是 NIST 后量子密码学标准化项目,自 2021 年以来已取得重大进展,新算法正成为后量子时代行业标准化的领跑者。该过程始于 69 个候选算法,其中 26 个进入第二轮评估。2020 年 7 月,第三轮候选公布。总体而言有 7 个决赛入围者和 8 个备选候选。表中注明了它们是用于加密还是签名方案、所属的算法家族,以及所基于的困难问题。
算法评估基于以下三个标准:
- 安全性:这是最关键的标准。NIST 已确立若干因素来评估每个候选算法所提供的安全性。除了算法的量子抗性外,NIST 还定义了当前网络安全生态之外的其他安全参数,包括完美前向保密、对旁路攻击(side-channel attacks)的抗性,以及对多密钥攻击的抗性。
- 成本与性能:算法根据性能度量进行评估,如密钥尺寸、公钥与私钥操作和生成的算力效率,以及解密失败率。
- 算法与实现特性:假设算法提供了良好的整体安全性和性能,则根据灵活性、简洁性和采用的难易程度(例如是否存在涵盖该算法的知识产权)进行评估。
密码学敏捷性(Cryptographic Agility)
在设计信息安全协议时的一个重要范式是密码学敏捷性。它规定协议应支持多种密码学原语,使实现特定标准的系统能够选择哪些原语组合是合适的。密码学敏捷性的主要目标是允许用稳健的原语和算法快速替换易受攻击的密码学原语和算法,而无需对系统基础设施做出破坏性更改。这一范式在后量子密码学设计中至关重要,并且至少需要部分自动化。例如,一家普通企业持有多达数十万份证书和密钥——而且这个数字还在持续增长。面对如此多的证书,组织必须部署自动化方法,以便在所依赖的密码学变得不安全时能够快速替换这些证书。
组织的绝佳首要措施是开始实施混合密码学(hybrid cryptography),即量子安全的公钥算法与传统公钥算法(如 RSA 或椭圆曲线)一同使用,从而使方案至少不弱于现有的传统密码学。
展望未来
量子计算正从理论上的可能性转变为实际的现实,近期量子处理器和系统的发展便是例证。因此,网络安全领域需要迅速适应这些变化。
作为网络安全的领先参与者和身份与密码学标准机构的积极成员,行业持续研究并紧跟量子计算进步所带来的挑战与机遇,并将成为基于专业知识和不断发展的公钥基础设施解决方案的新抗量子密码学标准的早期采用者。