P= NP和当前密码系统

Question

我最近听到一些人说，如果P= NP这一事实得到证实，大多数(全部？)目前被认为像RSA那样安全的密码算法在安全系统中是不可用的。

我的问题是：

1.如果今天证明了P= NP，那么RSA密钥(比方说3072位)是否仍然足以确保一定的安全性。

2.如果没有，我们能做些什么来保证至少同等数量的安全(使用更大的密钥长度？一个更强的算法？)

Answer 1

我以前在如果P=NP的话，安全性将如何改变？ (在我们的姐妹站点IT安全堆栈Exchange上)回答过这个问题。此外，有关这个主题的更多信息，请参见如果P= NP用于RSA算法，情况会是怎样的？的答案。

简单的回答是，P=NP并不一定意味着所有密码系统在实践中都是不安全的--这意味着我们需要重新仔细评估我们的密码方案的安全性基础。如果不知道我们是如何了解P=NP的具体情况，就很难说得太多。

但是读一下这些问题的答案，他们会很深入地讨论它。

Answer 2

以下是20年前关于为什么P=NP与密码学无关的帖子：

http://theworld.com/~reinhold/p=np.txt