@ 2015.08.25 , 16:00
20

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)

TOTAL COMMENTS: 20+1

  1. 2910916

    以后就是薛定谔的密码了?

  2. 骑着扁担抱牛
    @2 years ago
    2910919

    字我都认识,但是凑到一起就看不明白了。还有最后一张配图是什么鬼?

    [28] XX [1] 回复 [0]
  3. 汤圆
    @2 years ago
    2910924

    人类就靠NSA和伟大长城之间斗智斗勇了!话说GAE关闭了,大家还用什么爬墙啊?

    [12] XX [5] 回复 [0]
  4. helloji
    @2 years ago
    2910925

    小编,首页的无聊和动态更新像你们便秘了一样是什么意思,我一天上来8次,球都没有。

  5. willll
    @2 years ago
    2910941

    “NSA的行动就好像实用量子计算机会早得多就存在一样,我会听从他们的专家意见”——你太天真了,只是那些专家需要经费支持研究故而夸大而已

  6. 王太发财
    @2 years ago
    2910945

    了不起

  7. 胡安
    @2 years ago
    2910956

    信保局…..
    这翻译的好

  8. 2910961

    @骑着扁担抱牛: 一个解出NP完全问题的数学家被谋杀的案情

  9. gogogo
    @2 years ago
    2910963

    @汤圆: 嗯,你家的gae关闭了。真是搞笑,洒家天天用着呢

  10. 2910974

    抵挡智子攻击嗯。。。。

  11. 扬帆大海
    @2 years ago
    2910988

    @汤圆: GAE什么时候关闭了?现在就用着呢。。。

  12. 含苞待放的雏菊
    @2 years ago
    2911002

    如果搞出来了能不能全效玩武装突袭3

  13. 2911021

    如果一个技术发明了很久都没有突破性进展(自己说突破的不算),是不是本身就没有发展的前途?

  14. 2911059

    @gogogo: 墙没那么简单,很有可能是分区的。

  15. 凯恩
    @2 years ago
    2911197

    研究post-quantum cryptography是没错,但量子计算机到底离实用有多远还难说,目前知道的欧洲韩国中国声称有突出进步的基本都是吹出来的然并卵

  16. 东经
    @2 years ago
    2911344

    这种文章我看到一半就有尿意,这么难,太吓人了

  17. 美食家18
    @2 years ago
    2911439

    美版福尔摩斯的编剧特点就是引入大量现代潮流的话题,诸如人工智能、蜜蜂灭绝说、密码学、遗传基因、UBER代驾谋杀等。

  18. 2911517

    实验室80年代就有量子计算机了。但是需要很苛刻的环境,这只是说明了一个问题,如果一个机构有坚定的决心使用一台量子计算机来使坏的话,理论上他只需要有足够的钱烧,技术上不存在什么问题。

  19. 蒸烧饼
    @2 years ago
    2912896

    @骑着扁担抱牛: 那集剧集说的是有个人找到了破解现代加密方法的算法。。。。例如rsa

  20. ZDProj
    @2 years ago
    2912909

    @王丢兜: 知道np完全问题的人也没必要解释了吧

发表评论


24H最赞