研究人员发现模拟量子密码攻击复杂性的新方法

量子计算机可能仍处于起步阶段,但已经有人担心它们可能会破坏几种现有的加密算法。为了解决这些问题,研究人员一直在探索量子密码算法在实践中如何工作的机制,他们的研究可能会由于量子计算领域的改进而导致更安全的算法。

阿拉伯联合酋长国技术创新研究所 (TII) 的研究人员展示了一种在经典计算机上运行的量子模拟器上模拟加密黑客算法的新方法。其中一个关键发现是一种对此类计算的复杂性进行建模的方法,这种方法可以扩展到全尺寸的量子计算机。该研究使他们能够创建更安全的加密设计。

考虑到它可能对安全、隐私、金融和电子商务产生重要影响,研究人员一直在探索这一领域。一种方法是通过关注问题的一个小元素,然后最后将这些部分组合起来,对全尺寸的密码学问题进行量子攻击。攻击密码算法涉及许多数学过程的相互作用,这种方法可能难以估计不同部分之间的相互作用将如何扩大。

因此,TII 的研究人员找到了一种方法来缩小密码问题,以保持所有不同部分之间的适当关系。TII 首席密码学家 Emanuele Bellini 说:“这在以前是不可能的,因为量子模拟器会消耗大量能量。我们正在使用的那个允许我们管理足够的模拟量子位来运行有意义的样本。”

抗量子密码学的目标

抗量子密码学的目标是创建无法被量子计算机有效攻击的算法。量子密码学在量子计算机上运行算法,后量子密码学探索了改进在经典计算机上运行的算法的方法,这些算法仍然可以抵抗量子攻击和经典攻击。这项具体研究侧重于后量子密码学。

目前正在进行各种类型的密码研究,探索攻击非对称和对称密码方案的方法。其他研究已经研究了使用 Shor 算法的技术如何破解非对称加密方案,例如 RSA 和离散对数。

在这种情况下,该团队正在研究如何使用 Grover 算法对对称加密方案进行建模和攻击。这项研究展示了 Grover 算法的所有组件作为一个完整的组件集合的首次实现。其他研究人员已经在数学上探索了一个完整的实现,但无法运行它或仅使用完整算法的一小部分运行它。TII 研究人员将问题调整到较小的规模,这使他们能够运行 Grover 算法的完整实现来解决问题。

模拟量子算法的重要性

量子模拟器以允许研究人员在经典计算机上运行算法的方式模拟量子计算机的操作。这使研究人员能够探索算法的组件如何协同工作,为未来更强大的量子计算机做好准备。当前的模拟器可以支持 35-40 个量子位,这比几年前有了相当大的进步。

在密码学研究中,蛮力攻击会穷尽所有可能的密码,直到找到正确的密码为止。它不是很有效,因此密码学家正在寻找可以更轻松地找到解决方案的捷径。然而,分析蛮力攻击的计算需求可以提供一个基准来比较与其他算法的改进。

定义可扩展到真实结构的玩具加密算法

科学家们取得的一项关键发现是如何创建几类“玩具算法”,这些算法保留了全尺寸密码算法的密码特性,但又小到可以使用蛮力方法破解。与在经典计算机上运行的传统蛮力算法相比,这允许研究人员对量子算法的加速进行基准测试。他们特别发现,与 Grover 算法的 2 n/2相比,扩展蛮力算法所需的处理能力以 2 n的速度增长,这被认为是二次改进。

研究人员制作了两种类型的玩具算法,称为 Toy Sponge Hash 模型和 Toy BLAKE Hash 模型。Toy Sponge Hash 模型没有现实世界的对应物,但它确实捕获了更大的加密算法的元素。需要一台大约有 500 个量子位的量子计算机才能从全尺寸的实现中检索密码。该团队能够以一种可以外推到更大问题的方式计算复杂性。

Toy Blake 哈希模型是在某些加密标准中使用的真实函数。然而,它需要超过 35 个量子位来检索密码,因此该团队无法模拟它。该算法的全面实现将需要大约 2,000 个量子位。

量化量子门复杂性

这些新模型的一个关键进步是,研究人员能够计算复杂性并以一种能够将其外推到实际实现的方式对其进行扩展。测量门和量子位等量子资源为密码学研究人员提供了基准,以估计破解真正的哈希函数需要多少量子位。

这涉及了解量子电路的构造与经典电路的不同之处。量子计算机具有量子位和将量子位连接在一起的量子门。这类似于将位连接在一起的经典计算机中的门。这些门连接到不同种类的逻辑功能,例如 NOR、XOR 和 OR。在量子计算机中,门本质上是一个矩阵算子。一些经典门在量子计算机中转化为更大的门,这增加了对量子位的要求。

研究人员发现,在密码算法中选择正确类型的逻辑门可以提供比其他几种逻辑门的显着改进。贝里尼说:“我们意识到的一件事是,通过这种量子攻击,某些密码比其他密码更难破解。”

该团队发现难度取决于密码中使用的门类型。在算法中包含更多 OR 和 AND 逻辑门将显着增加量子处理量,以确定如何破解密码算法的哈希函数方面,这有助于找到用于加密数据的密码。

这种难度通常以在合理的时间内破解密码所需的量子位或量子位的数量来衡量。在这种情况下,他们能够在 35 量子位模拟器上运行量子密码攻击。Bellini 估计,一次全面的加密攻击可能需要 2,000 个量子比特。贝利尼指出,现代量子计算机距离实现这种能力还有很长的路要走。此外,现有的量子计算机容易出错,因此大部分量子位用于纠正这些错误。

展望未来,该团队正在探索如何构建玩具算法并模拟针对对称算法的量子密码攻击。这可能包括探索 Shor 算法的替代方案,该算法仅擅长解决涉及因式分解和离散对数的问题。该团队还在探索如何通过 Grover 算法的变化来增强经典攻击。也可能有更好的方法将问题分解为更小的问题,并查看如何模拟每个组件。

为TA充电
共{{data.count}}人
人已赞赏
信息安全

宏碁确认第二次安全漏洞

2021-10-15 22:24:52

信息安全

常见的网络攻击及其背后的策略

2022-3-7 16:32:54

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索