如果P=NP的话，安全性将如何改变？

Question

如果我们假设发现了P=NP，那么安全措施需要如何改变呢？

我想知道受影响的主要安全措施，以及需要如何改变这些措施。为了便于论证，我们可以假设密码可以在时间O(n^4)中被黑。

作为我正在寻找的一个例子，我们可能有一个答案，比如1024位的RSA密码需要扩展到500万位，否则SSH就会变得不安全。我想我是在尝试一种科学的方法来衡量应该发生的变化，而不是进入推测的领域。因此，我们可能必须首先确定什么级别的安全性是足够的，然后比较所需的更改。因此，要将此级别作为问题的一部分，我们可以简单地使用当前有效的公共安全实践。

我是IT安全领域的新手，所以我希望有人能帮助我指出在这个场景中什么是重要的。

Answer 1

答案是:视情况而定。

1. 假设我们找到了一个求解NP-完全问题的O(n^4)-time算法，其中由大O符号隐藏的常数不太大。这将杀死几乎所有现代密码学，包括对称密钥密码学和公钥密码学。唯一留下来的就是信息--理论上讲是安全的密码系统，比如一次性便携板和卡特-韦格曼式的消息认证。在这种情况下，一个人也许能够通过设计一个一千万位左右的密钥来做出反应，但是天哪，生活会很糟糕。很难把钥匙转到这么大的地方。而且，要相信由此产生的密码系统具有任何持久的安全性是非常困难的。如果今天有人想出了SAT的O(n^4)算法，你必须假设明年可能会有人想出如何将其改进为O(n^3 log n)或类似的东西。因此，在实践中，如果有人为SAT找到了一个实用的O(n^4)时间算法，那么很多密码学都建立在沙子的基础上，我们将不得不重新思考每一件事。
2. 或者，假设有人找到了像SAT这样的NP完全问题的O(n^100)-time算法.就直接影响而言，这种算法在破解密码学方面是完全无用的。然而，在许多方面，我们将处于最后一段的情况:每个人都会想，明年某个天才是否会把这个改进为O(n^10)，然后再把它改进到O(n^4)，等等。这很容易打击人们对现代密码安全的信心。因此，这也将是一个令人震惊的发现，即使它没有直接的直接影响。
3. 或者，假设有人找到了一个非构造性的证明，证明对于某些NP-完全问题存在一个多项式时间算法，但是没有指示如何将其转化为一个真正的算法，也没有证据表明得到的算法在实践中是有效的。那我们就会陷入混乱状态。没有人会知道我们是在上面的第一颗子弹的世界里，还是在第二颗子弹的世界里，或者是别的什么东西的世界。

尽管如此，我认为在可预见的未来，这些情况都不太可能发生。事实上，我甚至会猜测它们是非常不可能的。我们也可以讨论一下，如果一颗巨大的小行星明年撞击地球，密码学会产生什么样的影响。嗯，影响是毁灭性的--但可能性很小。我认为有更重要的，可能的事情要担心。

所以，如果你想知道你是否应该采取一些措施来保护自己免受某人证明P=NP的可能性:别费心了。那是在浪费时间。把你的精力花在更现实的威胁上。