量子计算和密码学

量子计算是一种新的计算方式，可以让人类使用当今的计算技术执行根本不可能的技术。它允许非常快速的搜索，这会破环我们今天使用的一些加密算法。

本文由格密链社区的刘天成翻译。

量子计算可以很容易地计算大数，这会破坏任何密钥长度的RSA密码系统。这就是密码学家努力设计和分析“量子抗性”公钥算法的原因。目前，量子计算还处于起步阶段，密码学家无法确定哪些是安全的，哪些不是安全的。但即使假设外星人已经充分发挥了这项技术的作用，量子计算也并不意味着密码学的世界末日。对称加密很容易产生量子抗性，我们正致力于量子抗性公钥算法。如果根据我们的数学知识和计算能力，公钥加密最终只是一个暂时的异常，我们仍然可以生存。如果一些不可思议的外星技术可以打破所有的密码学，我们仍然可以基于信息理论保密 - 尽管能力有很大的损失。

 

密码学的核心依赖于数学上的技巧，即有些事情比撤消更容易做。就像粉碎一块钢板比将所有碎片粘合在一起更容易一样，将两个素数相乘以获得一个大的数字比把这个大数字再分解成两个素数要容易得多。这种不对称 - 单向函数和陷阱门单向函数 - 是所有密码学的基础。

 

为了加密消息，我们将它与密钥组合以形成密文。没有密钥，逆转过程就更加困难了。不仅有点困难，而且是非常的难。现代加密算法如此之快，以至于它们可以保护您的整个硬盘驱动而不会出现任何明显的减速，但是在宇宙爆炸之前，加密是无法打破的。

 

使用对称加密，来用于加密消息，文件和驱动器，这种不平衡性是指数级的，并且随着密钥的增大而被放大。添加一位密钥会使加密的复杂程度增加不到百分之一（略过不证明），但打破成本却增加了一倍。因此，256位密钥看起来只有128位密钥的两倍，但是（根据我们目前的数学知识），破解256位的秘钥比破解128位的秘钥要困难340, 282, 366, 920, 938, 463, 463, 374, 607, 431, 768, 211, 456倍。

 

公钥加密（主要用于密钥交换）和数字签名更加复杂。因为它们依赖于诸如因子分解之类的困难的数学问题，所以有更多潜在的技巧来反推它们。因此，您将看到RSA的密钥长度为2,048位，基于椭圆曲线的算法的密钥长度为384位。但是，在这里，用这些密钥长度反转算法的成本超出了人类目前的承受能力。

 

这种单向性基于我们的数学知识。当你听说密码学家“打破”一个算法时，发生的事情就是他们找到了一个新的技巧，使反推变得更容易。密码学家一直在发现新的技巧，这就是为什么我们倾向于使用长度超过严格要求的密钥长度。这对于对称和公钥算法都是如此; 我们正在努力证明它们的未来。

 

量子计算机有望颠覆这一切。由于它们的工作方式，它们擅长扭转这些单向函数所需的各种计算。对于对称密码学，这不是太糟糕。Grover的算法表明量子计算机可以加速这些攻击，从而有效地将密钥长度减半。这意味着256位密钥与量子计算机一样强，就像128位密钥与传统计算机相比; 两者在可预见的未来都是安全的。

 

对于公钥加密而言，结果更加可怕。Shor的算法可以很容易地破解所有常用的基于因式分解和离散对数问题的公钥算法。密钥长度加倍会增加破解难度的难度。可这还不足够持久这样。

 

这两个段落有很多值得注意的地方，其中最大的一点是能够做这样的事情的量子计算机目前还不存在，没有人知道什么时候会出现 - 或者即使 - 我们能够建立一个。当我们尝试实现Grover或Shor的算法时，除了密钥大小之外，我们也不知道会出现什么样的实际困难。（量子计算机上的纠错很容易成为一个不可逾越的问题。）另一方面，一旦人们开始使用实际的量子计算机，我们不知道会发现什么其他技术。我敢打赌，我们将克服工程挑战，并将有许多进步和新技术，但他们将花时间去发现和发明。就像我们花了几十年的时间才能把超级计算机装进口袋一样，要花上几十年的时间才能解决建造大型量子计算机所需的所有工程问题。

 

从短期来看，密码学家在设计和分析量子抗性算法方面付出了相当大的精力，而这些算法可能在几十年来都保持安全。这是必然是一个缓慢的过程，因为良好的密码分析转换标准需要时间。幸运的是，我们还有时间。实用的量子计算似乎总是在“未来十年”中，这意味着没有人可以知道。

 

然而，在那之后，这些算法总是有可能落入具有更好量子技术的外星人。我不太担心对称加密，其中Grover的算法基本上是量子改进的上限，而不是基于数论的公钥算法，这种算法感觉更脆弱。量子计算机有可能在某一天摧毁所有这些计算机，即使是那些今天就具有量子抗性的计算机。

 

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

 

这是一个奇怪的未来。也许基于数论加密的整个概念，这是我们现代公钥系统的基础，是基于我们不完整的计算模型的暂时的迂回。现在我们的模型已经扩展到包括量子计算，我们可能最终回到20世纪70年代末和80年代初的水平：对称加密，基于密码的加密，Merkle哈希签名。这既有趣又具有讽刺意味。

 

是的，我知道量子密钥分配是公钥加密的潜在替代品。但是，拜托 - 是否有人希望系统需要专门的通信硬件和电缆才能用于除小众应用之外的任何其他应用？未来是移动，永远是嵌入式计算设备。这些软件的任何安全性都必须仅限于软件。

 

还有一个未来的方案需要考虑，一个不需要量子计算机的方案。虽然有几种数学理论支持我们在密码学中使用的单向性，但证明这些理论的有效性实际上是计算机科学中一个重大的开放性问题。正如聪明的密码学家有可能找到一种新技巧，可以更容易地破解特定算法，我们可以想象有足够数学理论的外星人可以打破所有加密算法。今天对我们来说的话，这也太荒谬了。公钥密码学是所有数论，并且可能容易受到数学倾向的外星人的影响。对称密码学是如此多的非线性混乱，因此容易变得更加复杂，并且容易增加密钥长度，这种未来是不可想象的。考虑具有512位块和密钥大小以及128循环的AES变体。除非数学与我们目前的理解有根本不同，否则在计算机由物质以外的东西构成并占据除空间之外的东西之前，这将是安全的。

 

但是，如果这种难以想象的事情发生了，那我们将只有完全基于信息理论的加密：一次性密码本及其变体。这将是对安全的巨大打击。一次性密码本可能在理论上是安全的，但实际上它们不能用于除专门的小众应用之外的任何东西。今天，只有破解者才会试图建立基于一次性密码本的通用系统 - 密码学家嘲笑他们，因为他们用密钥管理和物理安全问题（更加困难）取代了算法设计问题（简单）。在我们陌生的科幻未来中，我们可能一无所有。

 

对于这些神一般的外星人，密码学将是我们唯一可以肯定的技术。我们的核武器可能会拒绝引爆，我们的战斗机可能会从空中坠落，但我们仍然能够使用一次性密码本安全地进行通信。这里面有一种乐观主义。