外星人登陆后的密码学

  • 布鲁斯·施奈尔
  • IEEE安全与隐私
  • 2018年9月/10月

量子计算是一种新的计算方法,它允许人类使用当今的计算技术进行根本不可能的计算。它允许快速搜索,这会破坏我们今天使用的一些加密算法。它使我们能够很容易地将大量的数据任何长度的密钥都会破坏RSA密码系统。

这就是密码学家努力设计和分析“抗量子”的原因公钥算法。目前,量子计算还处于初级阶段,密码学家无法确定什么是安全的,什么不是。但即使假设外星人已经充分开发了这项技术,量子计算并不意味着密码学的末日。对称密码学很容易使量子抵抗,我们正在研究抗量子公钥算法。如果基于我们的数学知识和计算能力,公钥密码最终成为一种暂时的异常,我们还可以活下去。如果一些无法想象的外星技术能破解所有的密码术,我们仍然可以根据信息理论进行保密,尽管有很大的能力损失。

在其核心,密码学依赖于数学上的怪癖,有些事情做起来比撤销容易。就像打碎一个盘子比把所有的碎片粘在一起容易一样,把两个素数相乘得到一个大的数要比把这个大的数乘以两个素数容易得多。这种单向函数和陷阱门单向函数的不对称是所有密码学的基础。

要加密消息,我们把它和一个键结合起来形成密文。没有钥匙,逆转这一过程更加困难。不仅仅是有点困难,但天文上更难。现代加密算法速度如此之快,它们可以确保您的整个硬盘安全,而不会出现任何明显的减速,但在宇宙热死之前,这种加密是不能被打破的。

使用对称加密技术,即用于加密消息的加密技术,文件,驱动力——这种不平衡是指数级的,并且随着键的增大而放大。添加一位密钥会使加密的复杂性增加不到百分之一(我在这里手舞足蹈),但会使破坏成本增加一倍。所以一个256位的键可能看起来只有128位键的两倍复杂,但是(根据我们目前的数学知识)是340282366920938463,4633746074431768211456倍更难打破。

公钥加密(主要用于密钥交换)和数字签名更加复杂。因为它们依赖于复杂的数学问题,如因子分解,有更多潜在的技巧可以逆转它们。所以您将看到rsa的密钥长度为2048位,以及384位用于基于椭圆曲线的算法。在这里,虽然,用这些关键长度来逆转算法的成本超出了人类目前的能力。

这种单向性是基于我们的数学知识。当你听说密码破译的时候一个算法,现在的情况是,他们发现了一种新的技巧,可以让倒车变得更容易。密码学者总是发现新的技巧,这就是为什么我们倾向于使用超出严格必要的键长。对称和公钥算法都是如此;我们正在努力使他们不受未来的影响。

量子计算机承诺会推翻许多这一点。因为他们的工作方式,它们擅长于逆转这些单向函数所需的各种计算。对于对称加密,这还不错。格罗弗的算法表明,量子计算机可以加速这些攻击,有效地将密钥长度减半。这意味着256位密钥对量子计算机的攻击强度与128位密钥对传统计算机的攻击强度相当;在可预见的未来,两者都是安全的。

对于公钥密码,结果更加可怕。Shor算法可以很容易地打破所有常用的基于因式分解和离散对数问题的公钥算法。将密钥长度加倍会增加8倍的中断难度。可持续发展的优势还不够。

这两段有很多注意事项,其中最大的问题是量子计算机目前还不存在,没有人知道我们什么时候——甚至是否——能够建造一个。我们也不知道,当我们试图实现Grover或Shor的算法时,除了玩具键大小以外,还会出现什么样的实际困难。(量子计算机上的错误修正很容易是一个无法克服的问题。)另一方面,一旦人们开始使用实际的量子计算机,我们不知道还会发现什么其他技术。我敢打赌,我们将克服工程挑战,未来将会有许多先进的技术和新技术,但它们需要时间去发现和发明。就像我们花了几十年才把超级计算机装进口袋一样,建造足够大的量子计算机所需的所有工程问题都需要几十年才能解决。

在短期内,密码学家正投入大量精力来设计和分析抗量子算法,而且这些措施可能会在数十年内保持安全。这是一个必然的缓慢过程,因为好的密码分析转换标准需要时间。幸运的是,我们有时间。实际的量子计算似乎总是“未来十年”。也就是说没人知道。

之后,虽然,这些算法总是有可能落入拥有更好量子技术的外星人手中。我不太担心对称密码术,格罗弗算法基本上是量子改进的上限,比我所说的基于数论的公钥算法,感觉更脆弱。量子计算机有可能有一天会将它们全部破坏,即使是今天的量子电阻。

如果发生这种情况,我们将面临一个没有强大的公钥密码技术的世界。这将是对安全的巨大打击,并会破坏我们目前所做的许多事情,但我们可以适应。在20世纪80年代,Kerberos是一个全对称的身份验证和加密系统。最近,GSM蜂窝标准只使用对称密码进行认证和密钥分发(按比例)。对,这些系统有集中的信任点和故障点,但有可能设计其他同时使用秘密拆分和秘密共享的系统,以将这种风险降到最低。(想象一下,两个通信者从五个不同的密钥服务器中的每一个获得一个会话密钥。)如今,通信的普及也使事情变得更容易了。我们可以使用带外协议,例如,您的手机可以帮助您为计算机创建密钥。我们可以使用当面注册来增加安全性,也许在你购买智能手机或初始化互联网服务的商店。硬件的进步也可能有助于在这个世界上保护密钥。我不想在这里设计任何东西,只是要指出有很多设计的可能性。我们知道密码学是关于信任的,我们拥有比互联网早期更多的管理信任的技术。一些重要的特性,如前向保密性,将被削弱并变得更加复杂,但只要对称密码术仍然有效,我们还有保安。

这是一个奇怪的未来。也许是基于数论加密的整个思想,这就是我们现代的公共密钥系统,是基于我们不完全计算模型的临时迂回道。现在我们的模型已经扩展到包括量子计算,我们可能会回到上世纪70年代末80年代初的水平:对称密码学,基于代码的密码学,Merkle哈希签名。这既有趣又讽刺。

对,我知道量子密钥分发是公钥密码术的一个潜在替代品。但是,拜托,有人期望一个需要专门的通信硬件和电缆的系统对除利基应用以外的任何东西都有用吗?未来是移动的,不间断,嵌入式计算设备。这些安全性必须仅限于软件。

还有一个未来的场景需要考虑,不需要量子计算机的。虽然有几个数学理论支持我们在密码学中使用的单向性,证明这些理论的有效性实际上是计算机科学中一个重大的开放性问题。就像一个聪明的密码学家有可能找到一个新的诀窍,使破解一个特定的算法变得更容易一样,我们可以想象外星人有足够的数学理论来破解所有的加密算法。对我们来说,今天,这是荒谬的。公钥密码学是全数字理论,而且很容易受到数学倾向更高的外星人的攻击。对称密码学是如此的非线性混乱,很容易让事情变得更复杂,很容易增加键长,这是不可想象的未来。考虑一个带有512位块和密钥大小的AES变量,和128发子弹。除非数学与我们目前的理解有根本不同,这将是安全的,直到计算机是由物质以外的东西构成,并占据空间以外的东西。

但是如果不可想象的事情发生了,这将使我们只剩下基于信息理论的密码术:一次性密码本及其变体。这将是对安全的巨大打击。一次性护垫理论上是安全的,但在实际应用中,除了专门的利基应用之外,它们是不可用的。今天,只有疯子才会试图建立基于一次性密码本的通用系统,而密码学家们嘲笑他们,因为它们用密钥管理和物理安全问题(很多,更加困难)。在我们的外星科幻未来,我们可能没有别的了。

对抗这些神一般的外星人,密码技术将是我们唯一能确定的技术。我们的核武器可能不会引爆,我们的战斗机可能会从空中坠落,但是我们仍然能够使用一次性的垫子安全地通信。这是乐观的。

类别:电脑及资讯保安

布鲁斯·施奈尔的照片,Per Ervland。

Schneier on Security是一个个人网站。betway88必威官网备用表达的意见不一定是IBM弹性.