@ 2015.11.18 , 15:11
30

算法领域取得突破性进展,加密技术或迟早要完

[-]

芝加哥大学数学系著名教授László Babai宣布发明了一种全新的算法,该算法可显著地简化计算机科学领域某些众所周知的困难问题。 这一突破性的进展使得很多算法领域的专家们开始怀疑一直以来他们信以为真的理论也许并不靠谱。同时,该发现也提醒我们,或许可以取得类似突破,使得攻破数据加密算法变得更加容易

László Babai教授将于该校举办三场系列讲座,详细解释他所发明的新算法如何解决著名的图的同构问题(Graph Isomorphism problem)。本周二和周四(11月10日/12日)的两场讲座均人满为患。图的同构问题是指由计算机判断给定的两个图——每个图由一些“点”(vertex)和“边”(edge) 构成——是否具有完全相同的结构。

Babai 教授的讲座非常令人鼓舞。过去三十余年来,图的同构问题都被认为很可能是最难以使用计算机解决的问题之一。若Babi教授的算法正确无误,则这一看似颇具挑战性的问题事实上更可能属于一类易于解决的算法问题,也即存在复杂度至多为多项式时间(complexity class P)算法的问题。

“这一突破使得大家浮想联翩,”佐治亚理工学院(Georgia Institute of Technology)从事计算理论研究的Richard Lipton教授表示,“他把这个问题的难度降低了数个级别”. 麻省理工(MIT)的副教授Scott Aaronson在了解Babai教授的发现后,在他的博客上表示这可能是“计算理论领域近十年来最重要的突破”

在计算机领域,要衡量一个问题的困难程度,科学家们通常考虑随着问题规模的上升,所需要多少的计算能力的增加速度。根据这一标准,图的同构问题被归类为极其困难的问题,因为随着输入图的尺度增加,解决该问题所需要的计算能力几乎呈指数型增长。

该算法由Babai教授和俄勒冈大学(University of Oregon)的Eugene Luks于1983年初次发表。Babai教授称,当输入的图的尺度增加时,他的新算法需要的额外计算能力并不会急速增加。该算法的存在使得图同构的问题的困难程度被显著降低。

Babai教授表示在其研究成果经过同行评审并正式发表之前,不愿接受采访。但他对一名参加他讲座的激动听众说,其论文的预览版将会“很快”发表。

Lipton教授则表示,在完整的论文面世之前,我们应当谨慎对待任何声称的突破性成果。但是凭借Babai教授在业内的崇高声望,大家纷纷表示他所取得的成果很有可能是真实可靠的。“他老人家可是业内的泰山北斗”,Lipton教授说。

若Babai教授的成果最终被确认有效,这一发现目前也只会在计算理论的专家圈子内掀起一些波澜。图的同构问题在某些领域内具有一定的应用价值。例如在数据库内检索特定的分子结构,因为分子结构可以简单地通过图来表示。 不过该问题已经存在类似的替代解决方案。

Babai教授还宣称,在因式分解问题上也取得了类似的突破。因式分解被认为和图的同构问题具有相同的困难程度,但该问题的潜在影响力比图的同构问题更加深远。 因式分解也即将一个数分解为其所有质因子。这一问题是最为常用的加密技术的基石,而该加密技术则被广泛的用于数据和因特网上的通讯加密。

即便使用当前已知的最佳算法,因式分解问题仍然和图的同构问题一样具有很高难度。同时由于因式分解具有某些图的同构问题所不具备的数学性质,Babai教授的算法目前无法用来解决因式分解问题。不过,Lipton教授认为,这一发现的意义在于提醒人们某些长期以来被奉为真理的理论或许会被某些新的算法推下神坛。

“如果能够找到解决因式分解的快速算法,即使只是理论上有效,这也足够让密码学专家们如坐针毡了”, Lipton教授说。当前的加密技术能够被暴力破解,但是如果加密算法使用的秘钥足够长,暴力破解需要使用海量的计算资源。若这方面的算法有所突破,政府机构等或能够切实地利用现有的超级计算机来对当前使用的加密算法进行暴力解密。

即便理论上有效的快速因式分解算法尚不能投入实践,这也足够督促科学家们进行进一步的探索和尝试去破解这一问题,Lipton教授补充道,“密码学专家们恐怕不能再信誓旦旦的公开表示‘我的加密算法是安全的,因为该算法用到了因式分解’。”

本文译自 MIT Technology Review,由译者 Grey Yang 基于创作共用协议(BY-NC)发布。


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

0.0
赞一个 (18)

TOTAL COMMENTS: 30+1

  1. 2987554

    和妹纸图有关系咩

    [2] XX [13] 回复 [0]
  2. 绅士
    @2 years ago
    2987556

    不要怕, 因式分解被强暴以后, 还能用圆锥曲线加密
    圆锥曲线也被搞定的话, 我们还有终极神器:量子加密

    [72] XX [6] 回复 [0]
  3. 逗比
    @2 years ago
    2987559

    呵呵,我的加密是安全的,因为我叫了紫madhqwdgsuihzjkxnvjhuewijoksamxnbjuhijeokwsmaxnzkbjcuhfiojedklsnverdsuhjnfhuiejdskajdbhfrjeiwksbjhvfgrikelsdmxcnjfghutiewokpsalxmcfhioewkpdslxvjfghtiojedksaljdvfhgjieokldsxnjdgeuihjwslokxnguihejsoalkxnchdfgjeriolkdsaxjdvfhgeuijwdsakncfhrioejldskxnjfhgeuiowlskjxcjfhgjkcxhd不要啊!fh98dsciokjfbgtiojekswalzxmcvnbgjfrikleds,xmcdnvbfgtuhjoikpfld;sxvkgnjiropewlds;x,cmvgjvjtirkoledsxcmvnbfjgtrihjewkdsxzmcvngtijroekdslxc对不起我错了vfndh9cujgbtormnebhgedfsjiokxmbhgujeiwdkasmlzn xbcjgfklewsmx jbhuifjoedskalxmnvbjghijfoedkwlsamxncjvghfjdisok

    [55] XX [14] 回复 [0]
  4. asdfas
    @2 years ago
    2987563

    @绅士: 然后黑客就用量子计算机暴力破解破解

    [4] XX [15] 回复 [0]
  5. 二哒猫
    @2 years ago
    2987564

    说突破性进展有点夸张了,依然没有证明图同构是p的还是npc的,但是对复杂图的处理确实比以前的算法优化了许多

  6. 神响
    @2 years ago
    2987582

    什么时候能解密了我们这个世界就碉堡了,超人有一集是大反派获得了超人的能力,然后大反派呆了,超人说,哦他第一次看到了如此瑰丽的世界,很正常,是超人么那部片子?

    [17] XX [0] 回复 [0]
  7. 成都肛肠医院
    @2 years ago
    2987585

    www.cdgcyy.com

    [0] XX [39] 回复 [0]
  8. 2987592

    只是针对同构图问题提出了一个复杂度较低的算法而已,没证明这个算法是P的,也没证明同构图是NPC的。如果算法达不到P,那么也基本上相当于把386换成最新的i7罢了,没有特别本质的区别,只是安全密钥长度可能从128位要加长到256位,但是算法本身依然安全。

    [24] XX [2] 回复 [0]
  9. 大力
    @2 years ago
    2987596

    @神响: 是第一次被噪音折磨死了吧,钢铁之躯里就是

  10. 烧了个饼
    @2 years ago
    2987599

    是我看漏了啥还是什么问题?
    图的同构问题本来就没有被证明是np问题。。。。

    然后虽然都属于疑似np问题,但是现行的非对称加密方式,和图的同构也没有说有什么特别联系,是不是说少了什么东西?

  11. 神响
    @2 years ago
    2987618

    @大力: 这个也是,我记得超级英雄们都喜欢蹲在楼顶。

  12. 2987619

    以前要一千年,改进后提升十倍,一百年。

  13. 2987632

    @asdfas: 量子通信的特征是通信内容一旦被第三方截获,整个状态就被破坏了,这是物理原理层面的性质而不是数学算法上有多复杂。通俗地说,A给B发送一条量子加密的信息,C哪怕看了信息一眼,B在拿到信息以后就会知道它被看过。

  14. 2987635

    @abc: 文中已经说了,简化成p问题了

  15. 2987644

    以后利用这种算法,可以轻易开发出找碴游戏外挂

  16. 2987647

    @cc: 文中的说法是“更可能属于”,但没有说出明确的定论。并且后面说的是之前的复杂度是指数级别的,但是指数级别和多项式级别之间还有很大一块位置呢。

    抛开这个结果本身,吐槽下这文的逻辑:
    在数学中有很多很复杂的问题,其中某些看起来似乎有点像。
    解决了其中一个。
    “有理由相信”,其他的都能解决(并得到我们想要的那个结果)!

    我还真看不懂这种鸡血思维……

  17. 2987651

    @cc: 好吧,没认真看到标题中有个必杀字:“或”
    嗯这个三大名将之一出现了……我败退

  18. 猫粮供应机
    @2 years ago
    2987781

    我C 你们到底在说什么阿?

  19. 2987806

    昨天才做完一份人手RSA加密解密的練習作業,今天告訴我這加密方法要被破解了?
    不開心

  20. 2987825

    这篇文章翻译出来就毫无膈应感,那谁应该来学学 @王丢兜

  21. threezhiwang
    @2 years ago
    2987883

    @绅士:
    1.2都是基于大数的分解

  22. 韩国货
    @2 years ago
    2988039

    ls几位的要求也太高了,不搞出个npc的多项式算法就不算成果吗

  23. 2988117

    吹,可劲吹,加密高阶方程随便拉几次就好,和你这啥啥啥的有毛关系

  24. 2988176

    @绅士: 等你量子加密差不多了,量子计算机也估计快了。

  25. 2988177

    还没经过同行审议,让我们拭目以待吧。

  26. 2988298

    意思就是P约等于NP

  27. 2988309

    爱自拍的小心红了喔~

  28. 2988361

    量子通信呢?

  29. 2988423

    @韩国货: P、NP、NPC是对问题的分类称呼,而不是对算法的分类。
    另外说一下外行特别容易脑补出来的一个错误认知:P和NP不是互斥关系,NP并不是“非P”或者“不是P”的意思。同样NPC也不是和P或者NP并列的一个分类。

    P和NP是包含关系,P属于NP。所有的P问题都是NP问题。
    NPC和NP也是包含关系,NPC属于NP。
    但是以上两条是不同判断方式,P和NPC没有直接关联。

    如果真的要让现有加密在理论上玩完,必须做到两点:
    1. 对一个问题找出复杂度为P的算法。注意必须证明算法正确并证明复杂度确实为P。
    2. a)证明这个问题是NPC问题,或,b)这个问题刚好是加密中的关键(比如因式分解、椭圆曲线)或与其等价。

    如果做到了2a,那么所有加密告破。如果做到了2b,那么相应类型的加密告破。

    为什么量子计算机一直会在说到加密的场合被提出来,就是因为理论上说,量子计算机可以执行一套本质不同的算法(量子算法),而我们已经确定用特定量子算法搞定因式分解问题的复杂度为P。

    可是这文里,这几条一条都没提到……

  30. 美食家18
    @2 years ago
    2990107

    数据加密再可靠,也比不上蠢人被电信诈骗乖乖交上一辈子的积蓄密码

发表评论


24H最赞