近期一项研究表明,随着量子计算技术的发展,RSA加密的安全性面临新的挑战。来自上海大学的王超和同事们利用D-Wave系统的量子退火处理器成功因式分解了一个22位的RSA整数,这一成就标志着量子计算在破解密码学问题上的潜力。
尽管22位的键相对于当前标准的2048位RSA密钥显得微不足道,但研究者们认为这一尝试具有重要的意义。在过去,使用类似硬件的尝试仅止步于19位的因式分解,且在此过程中所需的量子比特数量相对较高。
王超团队将因式分解问题重新转化为二次无约束二进制优化问题,以便使用D-Wave Advantage系统解决。该系统通过让量子比特穿越能量障碍,寻找最低能量状态,从而实现了对22位RSA整数的因式分解。
此次研究还将相同的方法应用于替换-置换网络(SPN)密码,例如Present和Rectangle。他们表示,这是首次使用真实的量子计算机对多个当前正在使用的SPN结构算法构成实质性威胁。
尽管22位密钥显得脆弱,但研究中的新方法打破了以往在量子计算方面的限制,让人对更大密钥有了新的希望。研究表明,通过减少Ising模型中的局部场和耦合系数,可以显著降低噪声,使量子退火器更容易找到正确的因子。
Analyst Prabhjyot Kaur警告称,量子计算的发展可能会严重威胁各种企业的数据安全和隐私。
与之相比,通用的基于门的量子计算机能够运行Shor算法,理论上可以在多项式时间内破解RSA,寻找模幂运算的周期。然而,这些设备在错误纠正方面仍面临诸多挑战;而D-Wave的量子退火器具备超过5000个量子比特,能够在低温环境下进行模拟演化,避免了深电路的问题。
量子退火器在组合优化方面表现优异,因此上海团队将因式分解问题重新定义为此类搜索问题,绕过了基于门的量子计算机目前面临的量子比特数量限制。然而,这一方法也带来了指数级的复杂性,因此此次成功只限于22位模数。
标准组织并未坐等技术发展。2024年8月,NIST发布了FIPS 203、204和205,这是首个基于晶格问题的后量子密码学联邦标准。预示着2025年将选择HQC作为下一轮的标准。
白宫活动呼吁美国各机构开始替换易受攻击的密钥,因为敌手可能已经在“现在加密,之后解密”的攻击模式中积累了加密数据。
《华尔街日报》的首席信息官简报提到,企业在更新加密算法时应视其为一项需要多年的基础设施工程。
绝大多数企业尚未更新其加密算法Inventory,甚至不知道其系统依赖于哪些算法。安全专家建议,企业应首先进行内部审计,以识别所有使用RSA、ECC等易受攻击的算法,然后制定替代方案。
虽然全面迁移可能需要数年时间,但组织可以开始测试如Open Quantum Safe等量子安全库,并部署混合密钥交换方法。
增强加密灵活性,即在不重构整个系统的情况下,能够迅速更换加密算法,也是一种良好的选择。这样在新标准推出时,可以减轻未来的升级负担。
尽管目前大键RSA的安全性尚在,但这一研究表明,硬件的改进和更智能的嵌入方式持续缩小了安全与风险之间的差距。
D-Wave计划在今年推出一款具有超过7000个量子比特的Zephyr拓扑处理器,并且每次拓扑升级都会改善连接性,从而减少所需的物理量子比特数量。
与此同时,密码学家建议企业采用混合方案,将基于晶格的算法(如CRYSTALS-Kyber)与古典RSA签名结合,以在过渡期中提供前馈安全性。
对于那些存储敏感数据数十年的组织,例如健康记录、基因组文件和外交电缆等,如果等到全面量子计算机到来后再做准备,将面临最大的风险。
一些观察人士指出,上海的研究结果依赖于重度的经典预处理和后处理,并且 quantum annealer仍然需要多次运行才能找到正确的因子。尽管如此,历史证明,加密破解的概念验证往往不会停留在小范围内:DES在1998年仅用25万美元的机器就被攻破,仅在第一个部分破解的四年后。
这项研究发表在《中国计算机学报》上。
图片源于:earth