如果RSA算法被破解，加密的未来是什么？

你是否想过，如果互联网安全层在一夜之间出现了大裂缝怎么办?如果裂缝深入到密码算法的数学基础上怎么办?现在，这种情况似乎已经出现。近日，德国密码学家克劳斯·彼得·施诺尔(Claus Peter Schnorr)在其论文中声称自己已经找到了一种“破解RSA加密系统”的方法。

此事引起密码学界和量子密码界的广泛关注。虽然该论文内容尚未得到验证，但是如果事实果真如此，必然会对很多应用产生安全影响，因为目前许多对信息安全性要求较高的领域都在大量采用RSA非对称加密算法。

面对这种情况，我们不免需要思考两个问题：一是论文的内容是否真实?二是加密的未来是什么?有没有能取代RSA的密码系统，即使在量子计算机时代(后量子密码)也是安全的?

在撰写本文时，数学家和密码学家仍在针对论文内容的真实性进行讨论和验证，而更多的人已经在思考第二个问题，并开始草拟计划以应对这种灾难性的漏洞。他们正在努力创建更牢固的基础，该基础建立在通过多种协议实现的多种算法中，从而使切换变得更简单。

还有一些密码学家正在寻找RSA的替代品。因为无论此次论文结果真实与否，RSA的安全性问题早已引发业界关注。早在2010年7月，美国国家标准与技术研究所(NIST)就曾要求用户在2010年12月31日前停止使用1024位RSA算法。根据RSA负责人的说法，虽然目前没有证据表明RSA 1024位算法已被破解，但破解也只是时间问题，进而引发加密信息泄露、数字签名被伪造以及通信被窃听等后果。

除此之外，随着技术的不断发展以及量子计算机的应用，RSA安全性将再次遭遇挑战。谷歌CEO Sundar Pichai曾预言，

“5-10年间，量子计算将会打破我们如今所知道的加密技术”。

密码学家认为，世界必须变得更加敏捷，因为随时都可能会出现许多潜在的裂缝。

RSA算法面临的挑战

分解大素数

据悉，这份论文名为《通过SVP算法快速分解整数》，作者Claus Schnorr，现年77岁，于2011年从约翰·沃尔夫冈·歌德大学退休。他是一位受人尊敬的密码学家，Schnorr签名算法便是以他的名字命名。在密码学中，Schnorr 签名是由 Schnorr 签名算法产生的数字签名，它是一种数字签名方案，以其简单高效著称，其安全性基于某些离散对数问题的难处理性。由于Schnorr签名算法可以构建更高效和隐私性更强的区块链系统，一直备受区块链开发者们的关注。

而RSA则是另一种历史悠久且应用广泛的算法。它是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)共同提出的一种加密算法。这一算法主要依靠分解大素数的复杂性来实现其安全性，由于大素数之积难被分解，因此该密码就难被破解。

近40年来，RSA算法经历了各种攻击的挑战，根据已披露文件显示，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还未被破解，至少目前尚未有人公开宣布。

据悉，Schnorr最新发布的论文其实是其最近几年发表的一系列论文的补充更新，其重述了将大素数分解为数学家有时所说的“在由小得多的数字定义的多维晶格中搜索正确向量”的问题。由于其论文在很大程度上都是理论性的，这也使很多人怀疑RSA算法的安全性是否果真走到了尽头。不过，到目前为止，尚未有人针对该方法进行具体的公开演示，甚至一些尝试过的人也表示该方法并不起作用。

修复RSA的困难性

解决新发现的攻击带来的问题并不是什么新鲜事。软件公司通常会发布补丁来修复漏洞，并公开征求错误报告，以鼓励人们报告发现的问题。但是Schnorr的论文，如果得到证实，将会暴露出协议基础的弱点，并且没有一家公司对此协议负责。

一家名为“RSA”的公司曾在过去很长一段时间拥有该算法，但其专利已经过期，也就是说现在整个互联网上使用的大多数RSA实现都已经不再是来自他们。许多受欢迎的程序库都是开源的，由社区维护。

更糟糕的是，如果真的存在论文中所说的漏洞，那么根本无法简单地(像许多漏洞或错误那样)通过几行新代码就能解决问题。任何有效的解决方案的发布都可能需要数年时间，因为测试和部署任何算法都需要时间。

而且，切换到新算法的过程可能也并不容易，因为许多加密软件包都支持使用具有不同密钥长度的不同算法选项。更深层次的挑战可能来自更新身份验证基础架构，该基础架构将维护用于验证公钥的证书等级。一些主流浏览器的当前版本都随附着来自不同证书颁发机构的根证书，而它们大多数都依赖RSA算法。

想要在浏览器(或其他工具)中替换根证书，往往需要发行新版本才能实现，而且由于根证书功能十分强大，因此问题变得异常棘手。例如，某些攻击涉及插入伪造的证书以帮助攻击者假冒其他站点。截至目前为止，来自诸如Verisign、Amazon、GoDaddy和Entrust的一些主要证书颁发机构的证书都依赖于RSA算法。

量子问题加剧挑战

如何处理量子计算时代带来的挑战，是RSA安全性面临的另一重大问题。密码学界从几年前就已经开始寻找可以抵御量子计算的替代品，因为他们担心量子计算时代可能很快就会到来。这将威胁像RSA这样的算法，因为由彼得·索尔(Peter Shor)开发的量子计算最著名的算法之一就是整数的因式分解。

那么量子计算到底有多强大呢?举个例子，如果我们对四百位整数进行因式分解，现在最快的超级计算机也需要六十万年，如果换做量子计算机，只需要几个小时，甚至有人说几分钟就可以做到。而早在2012年，研究人员就表示他们已经成功地使用了量子计算机将21分解为7和3的乘积，虽然这两个数字并不是特别大。但是鉴于RSA加密算法严重依赖于大整数素因数分解的计算量以及耗费的时间。RSA算法的核心设计就是通过提高破解成本来提高安全性。因此任何能够增加计算速度的方法都会威胁到这种常用加密算法的安全性。而量子计算机可以加速Shor算法，安全专家警告称，总有一天，量子计算能够轻易破解RSA。而我们必须为这一刻做好准备。

寻找一种新的非RSA密码系统

由于担心不法分子会利用量子计算机发动攻击，为了防止协议和算法被攻破，人们开始不断对算法进行强化。NIST的做法是建立一种新的“抗量子”或“后量子”算法集合。目前这种加密竞赛已经拉开了序幕。

NIST在去年夏天宣布了自2016年底开始第三轮竞赛的初步成果。截至目前已经开发出了69种不同的算法，优秀的算法有26种，优中选优的算法为15种。当然在这15种算法中，有7种算法最终突围，另外8种算法将针对特殊的应用程序或是继续进行开发研究或是需要继续完善。

第三轮的7个候选算法，它们分别是：

公钥加密/KEMs

• Classic McEliece
• CRYSTALS-KYBER
• NTRU
• SABER

数字签名

• CRYSTALS-DILITHIUM
• FALCON
• Rainbow

第三轮审查结束后，NIST将继续对上述7名决赛入围算法进行审查，供下一步制定标准参考。由于CRYSTALS-KYBER、NTRU和SABER都是基于格的方案，NIST打算最多选择一个作为标准。签名方案中的CRYSTALS-DILITHIUM 和FALCON也是如此。在NIST看来，这些基于格上困难问题的方案是公钥加密/KEM和数字签名方案中“最有前途的通用算法”。

此外，NIST还选择了由Robert McEliece在1978年开发的一种较旧的签名方法——Classic McEliece。它由Robert McEliece于1978年设计开发，是一种不对称加密算法，基于代数编码理论，使用了一系列纠错代码Goppa。这种加密系统使用Goppa代码作为专用密钥，并将其编码为线性代码作为公共密钥，要想对公共密钥进行解码，就必须知道专用密钥。

McEliece密码系统虽然没有获得普遍采用，但非常强壮和稳定，唯一的缺点就是公共密钥太大，长达219-bit，这就使得加密信息要比明文信息大得多，从而提高了传输过程中的出错几率，另外不对称特性也使得这种技术无法用于数字认证和签名。三十年来针对这种加密系统的攻击和破解一直不断，但它始终稳如泰山。

最后一个决赛入围者被称为Rainbow，它是一种数字签名方案，基于多元多项式结构构造，属于多变量密码体系，而攻击者难以解决这些变量。

RSA的这些新潜在替代品可能无法轻松地实现替代过程。有些速度要慢得多，而另一些可能无法提供相同的选项来生成签名或加密数据。许多还在依赖较大的密钥——可能大于或等于500KB，远远大于很多当前的密钥(可能只有几百个字节)。

帮助创建公钥密码学的密码学家Whitfield Diffie指出，新提案可能需要更多的计算才能建立。另一位数学家马丁·赫尔曼(Martin Hellman)则表示，世界可能希望开发结合了多种不同算法的新协议。该协议不仅要简单地依靠一种算法来创建随机密钥以加密某些数据，还应运行多种算法并将所有算法的密钥组合成一个新密钥(可能通过XOR或可能具有更详尽的单向功能)。

Hellman警告称，即便加密灾难尚未到来，制定灾难恢复计划也可以帮助抵御多年来不断演变加剧的威胁。他表示：

“从今天起50甚至100年后，如今的机密数据仍然应该是机密的。因此，必须警惕任何可能会对如今受保护数据构成威胁的发展趋势，并时刻做好应对准备。”

本文翻