@ 2015.08.25 , 16:00

NSA升级算法抵抗量子攻击

[-]

量子计算是建造计算机的新方式——利用粒子的量子属性以与传统计算机非常不同的方式在数据上执行操作。在某些情况下,算法加速量非同寻常。

具体来说,使用Shor算法的量子计算机能有效地对数字分解因子,突破RSA加密。一个变种能突破Diffie-Hellman和其它基于对数的离散加密系统,包括使用椭圆曲线的那些。这有可能使所有现代公钥算法都不安全。在你惊慌之前,请注意到目前为止用量子计算机分解了因子的最大数字是143。所以尽管实用量子计算机还是科幻小说,它并不是那种愚蠢的科幻小说。

(注意这和量子加密完全不同,量子加密是在两方之间依赖量子物理特性传递比特,以确保安全。量子计算和量子密码学唯一的关联就是名字里前两个字。它也和NSA的量子计划完全不同,这是他家直接工作在互联网骨干上的包注入系统的代号。)

[-]

实用的量子计算并不意味着密码学的末日,还有更不知名的公钥算法如McEliece算法和基于网格算法,虽没有我们使用的那些高效,但目前对量子计算是安全的。而且量子计算仅仅把暴力密钥搜索以平方根倍数加速,所以任何对称算法都能通过加倍密钥长度来对量子计算机确保安全。

从斯诺登文档中我们知道,NSA正对量子计算和量子密码学两者实施研究,但并没有投很多资金,而且没多少人相信NSA已经在此领域的理论或应用物理中取得了进展。我的猜测是,我们会在三、四十年内看到一台实用的量子计算机,但不会更早很多。

这些全都意味着现在是时候思考生活在一个后量子世界会是什么体验。NIST发挥了其作用,在今年早些时候召开这个课题的会议。而NSA宣布它正在转向抗量子攻击的算法。

[-]

这个星期早些时候,NSA的信息保障局更新了其乙类加密算法列表,其中明确表示了量子计算机的威胁:

信保局将在不太遥远的将来启动向抗量子算法的过渡。基于部署乙类算法的经验,我们决心尽早开始规划和沟通即将到来的抗量子算法过渡。我们的最终目标是提供抵抗潜在的量子计算机的成本效益安全性。我们正在和USG、供应商、和标准组织的合作伙伴一起工作,以确保有一个清晰计划来以开放和透明的方式研发一套新算法, 形成我们下一套加密算法的基础。

直到新套件研发,并有实现了抗量子算法套件的产品可用,我们将依赖于现有算法。对于那些还未过渡到乙类椭圆曲线算法的合作伙伴和供应商来说,我们建议在这一时间点上不要做出巨大开支再上乙类,而是准备好向即将到来的抗量子算法过渡。

[-]

乙类是经NSA批准的一套加密算法,它是NSA密码现代化计划的一部分。传统上,NSA的算法是机密的,并且只能在专门构建的硬件模块上运行。乙类算法则是公开的,可以用在任何东西上。这并不是说乙类算法就是二等公民,或者说能被NSA破解,它们正被用来保护美国的秘密:“甲类会在乙类可能不合适的应用中使用。甲类和乙类都能用来保护可向外国发布信息、美国特供信息,和敏感隔离信息(SCI)。”

NSA对技术进步的担心程度已足以动手过渡对量子计算机脆弱的算法,而这是否意味着该机构的机密实验室已经接近能工作的原型机?不大可能。这是否意味着他们设想实用量子计算机会比我的30~40年估计更早?当然。

[-]

与大多数个人和企业应用不同,NSA常规性地处理想要保密几十年的信息。即便如此,我们都应该跟随NSA的带头,在未来十年左右——甚至更早,把我们自己的系统也过渡到抗量子算法。

# 原文注解:

更新:分解143的计算还意外地“分解了大得多的数字,如3599、11663,和56153,而该研究的作者却并未察觉。”这表明量子真的很怪异。

更新2:我不坚持30~40年的预测。NSA的行动就好像实用量子计算机会早得多就存在一样,我会听从他们的专家意见。

[-]
夏洛克向花生解释谋杀动机为什么是加密算法

本文译自 schneier,由译者 王丢兜 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力 !
支付宝打赏 [x]
您的大名: 打赏金额:

3.5
赞一个 (7)

24H最赞