量子计算遭遇安全和纠错挑战

点击：  作者：云卷云舒    来源：战略前沿技术微信号   发布时间:2024-04-11 10:40:27

 

 

密码学家们争相寻找更好的安全方案，而物理学家们则试图修复量子比特的错误。

 

随着政府、银行和其他实体为应对大量泄露的数据和不可信的数字签名做好准备，有关后量子加密(PQC)世界的警告数和量正在上升。

 

这究竟何时会成为真正的威胁还有些模糊，因为这取决于开发强大量子比特的进展。麦肯锡公司(McKinsey & Co.)的一份报告估计，到2030年，将有大约5000台量子计算机投入运行，但解决复杂问题所需的硬件和软件可能要到2035年左右才会出现。还有人说，量子比特和模块化架构之间的一致性可以加快速度。

 

在此期间，面对迫在眉睫的威胁和不确定的最后期限，关注安全的群体正在竞相建立防御。如果说早期的密码学是关于符号和替换的，那么至少现代密码学的一部分将是关于用算法来对抗算法的。

 

“密码学家和数学家从2017年开始就一直在谈论这个问题，当时他们第一次坐下来说，‘这很糟糕。我们需要更新这些算法，’”Rambus的硅安全产品高级总监Scott Best指出。“可怕的是，他们已经取得了很大进展。”

 

量子计算的力量来自于量子领域的丰富的物理学，当0和1处于相同状态时，存在叠加。

 

“想想抛硬币，”Keysight量子解决方案和规划主管Mohamed Hassan说，该公司已经在研究量子EDA工具。“这枚硬币不是正面或反面，而是两端同时旋转。如果你停止它并测量它，它会变成两者之一，它会坍缩量子态。同时，还有量子纠缠，无论它们相距多远，如果你测量其中一个，你就能猜出另一个的状态。”

 

RSA、ECC

 

说到最广泛使用的加密算法，首先也是最重要的是RSA (Rivest-Shamir-Adleman)，这是一种非对称加密形式，其中发送方使用可以广泛分发的公钥对消息进行编码，并且知道只有拥有相应私钥的接收方才能解码它。这意味着即使消息被劫持，它仍然是安全的，不会被解密。它的强度源于密钥长度，或者密钥中的位数。目前nist推荐的RSA密钥长度为2048位。

 

RSA使用复杂的公式来确定安全密钥。其核心是两个素数相乘的简单过程，其乘积成为进一步改进以创建密钥的基础。RSA之所以显得坚如磐石的安全，是因为“分解”的困难，也就是说，发现原始质因数是什么。如果一个乘积足够小，大多数人只要知道基本的乘法就能分解它，但如果使用的质数足够大，试图发现原始因子可能需要数千年的时间。

 

至少人们是这么认为的。1994年，麻省理工学院的数学家彼得·肖尔创造了一种算法，解决了离散对数问题，为破解RSA加密开辟了道路。从本质上讲，离散对数是易于执行但难以反转的函数，例如分解。在量子计算机上使用肖尔的算法，找到RSA因子可能从几乎不可能变成仅仅是计算时间和计算能力的问题。

 

“量子计算机擅长的事情相当有限，”位于瑞士苏黎世的IBM研究院安全研究小组经理迈克尔·奥斯本(Michael Osborne)说。“它们不太擅长我们所说的精确问题，因为它们的表现非常具有概率性。不幸的是，肖尔的算法受益于量子加速，因为从本质上讲，它适合一种不同的看待问题的方式。”

 

另一种流行的非对称加密是椭圆曲线加密(ECC)，它基于对椭圆曲线的操作。(缩写不应与纠错码混淆，纠错码是信息论的一部分。)ECC比RSA更快、更复杂，是区块链安全的基础。然而，其计算的保护性复杂性也可能被量子计算机的速度所抵消，因为它们在迪菲-赫尔曼密钥交换中共享数学根源。

 

此外，还有对称加密，它最常用于身份验证。对称加密仅使用单个密钥进行加密和解密。其最著名的例子是美国国家安全局批准的AES。因为它们基于哈希，所以它们不太容易受到Shor算法的攻击，但可能容易受到其他方法的攻击。

 

“肖尔的算法几乎破解了我们今天使用的所有公钥密码系统，包括RSA和Diffie-Hellman，以及椭圆曲线版本，”数学家、NIST后量子密码项目负责人达斯汀·穆迪(Dustin Moody)说。“对于像AES这样的对称算法，以及像SHA2和SHA3这样的散列函数，我们不需要更换算法，因为它们没有被破坏。在最坏的情况下，我们只是使用稍微长一点的键链接。”

 

由于纽约大学Courant数学科学研究所的Oded Regev教授的研究，肖尔的算法可能执行得更快，该研究扩展了肖尔在周期发现方面的工作。(更多的技术性讨论可以在这里找到。)

 

现在收获，以后解密

 

这些漏洞导致攻击者采取了一种被称为“现在收获，以后解密”(HNDL)的策略，即黑客入侵，尽可能多地窃取加密数据，然后等待容错量子计算机上线，这样他们就可以收集值得采取行动或持有赎金的信息。

 

尽管存在这些担忧，奥斯本质疑我们是否应该在其他攻击之前担心HNDL攻击，基于传统的安全方法，这种方法非常实用。“你永远不可能防范所有的攻击，所以你需要优先考虑攻击者的能力和攻击成本，以了解相关的风险，”他说。

 

虽然HDNL似乎是一个模糊而遥远的威胁，但还有其他威胁。以Grover算法为例，它可以用来发现数据中的模式。格罗弗的算法可以通过量子计算实现其全部功能，从而成为一个增压的搜索工具，可以理解所有解密的收获数据。和肖尔的一样，它也有可能破解加密密钥。

 

量子错误可以为安全措施争取时间

 

在当前嘈杂的中等规模量子时代，量子计算机的量子比特数量远远低于RSA推荐的2048个密钥。在2019年，估计是2000万个物理量子位，这个数字经常受到挑战。去年冬天，中国研究人员声称已经用10个量子比特将整数分解为48位。然而，许多研究人员对这项工作持怀疑态度。肖尔本人在推特上写道:“这篇论文显然可能存在问题。”

 

不过，时间紧迫。它的速度有多快还不得而知。与传统计算机一样，量子计算机容易受到内部和环境噪声的影响，这可能导致可靠性问题。量子计算机的情况可能更糟，因为噪声会导致量子比特退相干(失去叠加状态)，模糊维持计算所必需的量子状态，因此不仅会像经典计算机那样降低性能，而且会彻底摧毁它。

 

许多关于破解加密所需量子比特数量的讨论都是基于逻辑量子比特，这个数字远远小于使计算机实际工作所需的物理量子比特。任何关于设备中量子比特数量的说法都必须与能够在退相干中存活的物理量子比特数量相平衡。目前的估计是，1个逻辑量子位需要1000个物理量子位，这一开销严重影响了量子计算机何时完全上线的预测。

 

为了推动这一领域的发展，IBM、AWS、Google和一些初创公司(如QuEra、inflqtion和quantum)正在努力通过改进纠错来实现高相干时间。大多数改进都是基于量子低密度奇偶校验(qLDPC)代码，本质上是经典香农奇偶校验的量子级更新。上个月，IBM在这方面处于领先地位，在《自然》杂志上发表了一篇封面文章，称使用qLDPC变体将纠错开销降低了90%。

 

《自然》杂志的文章加重了解决这个问题的危机感，因为实现同样的攻击需要更少的逻辑量子比特。这加大了做好准备的紧迫性。”

 

由于量子和微软本周宣布的研究，这个时间可能更紧迫，这给安全研究人员带来了更大的压力。他们共同展示了“有史以来最可靠的逻辑量子位，错误率比物理量子位高800倍”，已经运行了超过14,000个量子位而没有错误。该成果使用主动综合征提取，允许在不破坏逻辑量子位的情况下进行错误诊断和纠正，从而大大降低了1/1000的比率。尽管令人兴奋，但值得注意的是，他们的论文还没有经过同行评审。

 

量子笼养时代

 

除了他们的同名算法外，Rivest、Shamir和Adleman还创造了密码学名人夫妇“Alice和Bob”，这是方程式中使用的“A”和“B”的具体体现。这是一个密码学内部的笑话，以至于一家法国量子创业公司把它作为自己的名字。爱丽丝和鲍勃的方法通过创造一个更健壮的量子比特来减少错误，他们以量子物理学中最著名的猫命名。结合qLDPC纠错，“猫量子比特”可以抵抗比特翻转，该公司已经证明，它们可以将运行肖尔算法所需的量子比特数量减少多达200倍。

 

AWS也采用了cat量子比特的想法，并制定了自己的方法。然而，像所有量子位一样，cat量子位仍然容易受到相变错误的影响。

 

猫量子比特实际上是量子比特设计的一部分。《科学》杂志的一篇评论文章详细描述了前五名最受关注的科研热点，第一个是超导电路，量子比特是其中的一个子集。超导电路以不同的方式也受到谷歌、IBM和AWS的青睐。接下来的四种方法是量子点、色心、捕获离子(由量子与微软合作使用)和拓扑量子比特，也受到微软的青睐。

 

是德科技的哈桑说:“制造量子计算机有很多硬件技术。它们都有一个共同的特点，那就是有一个量子对象作为代码元素来进行计算——作为量子比特。对于超导量子比特来说，它基本上是一个约瑟夫森结。有趣的是，引擎盖下的超导量子比特是微波电路。”

 

量子比特思想的多样性和工作的定制性也可能为安全研究人员赢得时间。"工具之间有许多空隙。"哈桑说。“人们使用点工具和本地工作流来完成他们的设计，这导致了昂贵的开发周期和非标准的工程程序。这些东西需要从研发领域转移到生产领域，这时就需要EDA工具来实现这些系统的系统化工程。”

 

如果微软、IBM、Alice & Bob或其他玩家在纠错方面取得成功，Schrödinger的猫可能会像老虎一样跳出盒子，撕裂非对称密码。然而，仍然必须注意物理量子比特数量的进展。去年12月，IBM发布了一款突破性的1000量子比特芯片，但仍远低于大多数合法的密码破解预期。

 

对策

 

然而，安全专家不愿意冒险，认为这一切都是炒作，一切都会好起来的。RSA一直在举办一场竞赛，寻找最佳的预防措施，结果却发现许多有希望的方法仍然是脆弱的。

 

Flex Logix负责营销和业务发展的副总裁杰森·贝瑟伦(jason Bethurem)说:“竞赛开始时共有69个提案。”“五年后，只剩下了四个。”最终结果预计将在今年夏天的某个时候公布。仍然有一些基于哈希的算法在向前发展。存活时间最长的是那些一直在增加键长度的键。数据路径越来越宽，这当然会让它变得更加困难，因为真正的数据路径的力量，创建所有这些组合只是需要更长的破解时间。”

 

在提供实用可用性的同时，针对已知攻击似乎最健壮的方法是基于格的算法。

 

IBM的奥斯本说:“量子计算机不太擅长处理一些黑箱组合问题。”格是一个组合问题。每个人都能想象一个二维晶格。如果它是一个规则晶格，你在二维晶格中选择一个点，它与其他点中的一个点很接近，但不在它上面，这很直观，你可以在脑海中看到。但是如果你有一个几百维的晶格，这个问题就非常困难了，因为你必须尝试很多种组合来找出这个多维晶格中哪个点靠近你的点。这是你必须尝试的东西的组合爆炸，这就是它对密码学有效的原因。你可以尝试使用蛮力方法，但这只是沧海一粟。”

 

目前最受欢迎的基于格子的算法是旧技术的标准化。Rambus的Best表示:“有一种更新的密钥交换机制，称为CRYSTALS-Kyber算法，以及一种更新的数字签名算法，称为CRYSTALS-Dilithium算法，现在已经足够标准化，人们期望它们能活很长时间，尤其是Dilithium。”

 

 

图1:Rambus的后量子安全方法。来源:Rambus

 

“即便如此，我们也不会把所有的鸡蛋都放在格子篮子里，”NIST的穆迪说。“虽然基于格的加密绝对是最有前途的，但我们选择了四种算法进行标准化。其中三个是基于格的。第二个最有前途的领域是所谓的基于代码的密码学，它使用纠错代码。它在直觉上类似于基于格的密码学。代码用向量表示。当你添加两个码字时，你会得到另一个码字。纠错码的一部分是如果你得到一串比特，那是一个任意的字符串。你通常想要找到最接近的码字，因为这是你想要纠正的。你假设有几个比特被弄乱了，但它应该是这个最接近的码字。这和晶格的情况很相似。加密系统的一个想法是，你有一个矩阵，它生成你的代码，你打乱它来隐藏你设计它的结构，你把它作为你的公钥，这是攻击者必须使用的。而你设计你的纠错码，生成它的矩阵，用一些特殊的结构，使你能够有效地解码。这意味着如果你的向量空间中有一串任意的比特，你可以解码并以一种有效的方式找到最近的码字。”

 

对于寻求内部措施的公司，许多公司强调了加密敏捷性的必要性。Flex Logix的Bethurem表示:“大型ASIC制造商和网络制造商都开始关注加密敏捷性。未来，所有制造商都希望拥有一个核心加密引擎，它可以完成这些复杂算法的许多主要功能和主要处理。“他们可能还必须包括一个更小的加密引擎，这是适应性部分。如果你不具备某种灵活性，那么在某个时候，你今天为保护你的产品所做的假设可能会在未来受到挑战和破坏。”

 

结论

 

虽然每个人都在努力保持对控制PQC的乐观态度，但Synopsys安全IP解决方案产品管理总监Dana Neustadter敦促设计师们现实地思考实施这些解决方案意味着什么。

 

Neustadter说:“引入有缺陷的实现和解决方案的风险非常高，因为这些是新的算法，它们本身就在传输中。”“我们刚刚看到，NIST正准备选择一组算法进行标准化，但在最后一刻，特定的算法遭到了破坏。如何将整个系统和设备转换为与我们今天所处理的完全不同的算法?尽管这些是替代算法，但并不意味着它们不会被打破，因为它们没有得到足够的研究。”

 

Neustadter指出，另一个风险是，仅仅是新颖性和不熟悉性就会增加执行错误的可能性。“如果你回顾过去，情况类似于我们从对称算法(如DES)转向AES时的情况，只是它将更加复杂，需要数年时间。我们正在过渡到全新类型的算法，你可以处理更大的键，这会影响系统内存的可用性。你需要有敏捷性，因为算法在变化。它不会在一夜之间稳定下来。最终，这些问题可以及时解决，但至少在一段时间内，这是一个严重的威胁。”

 

其他人对此表示赞同，并发出了警告。“推动采用量子安全加密技术是我们的职业义务，或许也是我们的爱国义务，”拉姆布斯的贝斯特说。“这项技术即将到来。”

 

编译自《Semiconductor Engineering》

 

远望智库开源情报中心 云卷云舒；来源：战略前沿技术微信号  图片来源网络 侵删