如果我们假设发现P=NP，那么需要如何改变安全措施？
我想知道受影响的主要安全措施，以及需要如何更改它们。为了争论，我们可以假设密码可以在 O(n^4) 时间内被破解。
作为我部分寻找的一个例子，我们可能有一个答案，比如 1,024 位的 RSA 密码需要扩展到 500 万位，否则 SSH 将变得不安全。我想我正试图在不进入猜测领域的情况下对应该发生的变化进行科学衡量。因此，我们可能必须首先确定足够的安全级别，然后比较必要的更改。因此，要将这个级别作为问题的一部分，我们可以简单地使用当今有效的常见安全实践。
我在 IT 安全领域有点新手，所以我希望有人可以帮助指出在这种情况下需要了解的重要内容。
答案是：视情况而定。
假设我们为像 SAT 这样的 NP 完全问题找到了 O(n^4) 时间算法，其中被大 O 表示法隐藏的常数不是太大。这将扼杀几乎所有现代密码学，包括对称密钥密码学和公钥密码学。唯一剩下的就是信息理论上安全的密码系统，比如一次性密码和卡特-韦格曼式的消息认证。
在那种情况下，一个人也许可以通过设计一个大约 1000 万位密钥的密码系统来做出回应，但是天哪，生活会很糟糕。在这么大的密钥周围传输是非常困难的。并且很难相信由此产生的密码系统具有任何持久的安全性。如果今天有人提出了一个 O(n^4) 的 SAT 算法，你必须假设明年有人会想出如何将它改进到 O(n^3 log n) 或类似的东西。因此，在实践中，如果有人为 SAT 找到了一个实用的 O(n^4) 时间算法，那么很多密码学都建立在沙子的基础上，我们必须重新考虑一切。
或者，假设有人为像 SAT 这样的 NP 完全问题找到了 O(n^100) 时间算法。就直接影响而言，这样的算法对于破解密码学完全没有用处。然而，在很多方面我们都会遇到上一段的情况：每个人都会想知道明年是否有天才会将其改进到 O(n^10)，然后在之后的一年将 O(n^4)，并且很快。这很容易打击人们对现代密码学安全性的信心。因此，即使它没有直接的直接影响，这也将是一个非常具有开创性的发现。
或者，假设有人找到了一个非建设性的证据，证明存在针对某个 NP 完全问题的多项式时间算法，但没有说明如何将其转化为真正的算法，也没有证据表明生成的算法在实践中是有效的. 那么我们只会陷入混乱。没有人会知道我们是在上面的子弹 1 的世界里，还是在子弹 2 的世界里，或者完全是别的什么东西。
综上所述，我认为在可预见的未来，这些情况都不太可能发生。事实上，我什至猜测它们不太可能。如果明年有一颗巨大的小行星撞击地球，我们也可以谈谈对密码学的影响。嗯，影响将是相当毁灭性的——但可能性很小。我认为还有更多相关的、可能的事情需要担心。
因此，如果您想知道是否应该采取一些措施来保护自己免受有人证明 P=NP 的可能性：不要打扰。那是浪费时间。将精力花在更现实的威胁上。