8.3　P=NP下的密码学

如果我们生活在第2章描述的“美妙世界”中，密码学会发生怎样的变化？我们很容易算出5 754 853 343和2 860 486 313是否为质数，以及5 754 853 343×2 860 486 313=16 461 679 220 973 794 359。我们甚至能在几千位或几百万位的数上做这些运算。由于我们可以验证因数分解问题的解，故该问题属于NP。如果P=NP，那么因数分解问题将变得能被高效地计算，我们可以找到几百万位数的质数因子。P=NP将让RSA协议失效。所有基于公钥加密系统的协议也都将失效。P=NP意味着如果不和对方事先联系好，你将无法向任何人发送秘密消息。

难道密码学将在美妙世界中毫无用武之地吗？只有一个方法可行，就是一次性密码本（one-time pad），它的安全性是理论上可被证明的，而且不依赖于NP问题的困难程度。假设艾莉丝有一个12个字符的密码FIDDLESTICKS。所谓的密码本是一个长度相同的随机字符串JXORMQNAMRHC。从密码和字符串中分别取出第一位的字母，F和J，两者分别是字母表中第6个和第10个字母。将两者的排序相加得到16，然后用第16个字母P作为加密的第一个字母。再分别取出第二位的字母，I和X，字母表中序号分别为9和24，相加得到33。字母表中没有33个字母，于是减去26，得到7，然后用第7个字母G作为加密的第二个字母。以此类推，就可得到加密的字符串PGSVYVGUVUSV。艾莉丝把加密的字符串发送给Facebook。Facebook只须减去而不是加上密码本中的每一位，就可解密这条消息。

由于长度为12的一次性密码本和消息一样多，所有加密字符串的概率都是相等的，数学上无法通过密码本对消息本身有任何了解，无论是否P=NP，结论都成立。那为什么我们不都用一次性密码本加密，而要使用更加复杂，而且有可能被破解的因数分解加密方法呢？

使用一次性密码本必须十分小心。顾名思义，一次性密码本只能被使用一次。甚至两个不同的人分别向另外两个不同的人发送秘密消息，都最好不要用同一个密码本，否则不能保证这两条消息的安全性。每个密码本都至少要和消息一样长。没有公钥和私钥之分，只有一份共享的私钥（即密码本JXORMQNAMRHC）。Facebook和艾莉丝都必须知道密码本，但如果窃听者知道了密码本的一小部分，他就能获知部分的消息。Facebook需要把密码本以某种别人看不到的方式交给艾莉丝（反过来也是如此）。由于人们能监听互联网通信，所以Facebook或某个受信任的第三方不得不将密码本存在U盘或者其他物理设备中然后交给艾莉丝。我能想象，美妙世界中的艾莉丝会从杂货店买一个密封的U盘，里面装满了一次性密码本。U盘会由某些受信任的组织来生产（美国政府？），并保证以安全的方式将同样的密码本发送给Facebook或其他公司。

Facebook也可以用量子力学来生成密码本并将其传输给艾莉丝。我们在下一章会讲讲量子密码学，但这个方法可能会因为成本过高而无法被广泛使用。