量子密码术为什么有价值？

不通过信使，让通信双方直接分享密钥，这显然是个非常奇妙的能力，是以前想象不到的。不过，这个能力有什么样的意义？这就需要从密码学的基本框架讲起了。

把明文变换成密文，需要两个元素：变换的规则和变换的参数。前者是编码的算法，后者是密钥。密码学的一个基本原则是，在设计算法时，你必须假设敌人已经知道了算法和密文，唯一不知道的就是密钥。

用一个比喻来说，密码学的攻防就好比魔王追公主（魔王：“你喊吧，喊破喉咙也不会有人来救你的！”破喉咙：“公主，我来救你！”）。魔王知道公主运动的规则，但不知道公主运动的参数。魔王的目标是在这种前提下追上公主，公主的目标是在这种前提下摆脱魔王。

我们经常说，没有完美的东西。但在理论的层面上，这话其实不对。有一种很简单的密码体系，就具有“完美的安全性”（perfect security）。这里的“完美安全”是个信息论的术语，意思是攻击方无论有多强的计算能力，都不可能从密文中得出任何信息。

这话听着似乎很玄，实际的意思却很简单。假如你要传一比特的信息（即0和1这两个数中的一个），密钥也有两个选择：0和1。算法非常简单：如果密钥为0，那么密文就等于明文，即把0变成0，把1变成1；如果密钥为1，那么密文就是0和1中不同于明文的那个数，即把0变成1，把1变成0。学过二进制的同学们知道，这个算法就是“模为2的加法”。现在如果你告诉敌人密文是0，那么他能得到什么呢？什么都得不到！他唯一可说的，是明文有一半的可能是0，一半的可能是1。但这是句废话，因为如果密文是1，这句话同样也成立。他不看密文就知道这一点，看了以后也不能增加任何新知识，所以这个密码体系就是不可破译的，具有完美的安全性。

当然，这是个最简单的例子，只适用于明文长度为1比特、只传输一次的情况。把这个办法推广到更长的明文长度、更多次的传输，需要满足三个条件。哪三个条件呢？一，密钥的长度跟明文一样；二，密钥是一串随机的字符串；三，每传送一次密文后都更换密钥，即“一次一密”。满足这三个条件的密钥叫做“一次性便笺”（one-time pad）。信息论的创始人香农（Claude E. Shannon）从数学上证明了：密钥如果满足这三个条件，通信就是完美安全的。这个定理可以称为“系统的安全保密性定理”。

香农

一次性便笺保密的实质，是让密文跟明文完全没有关联，任何的密文都以相等的概率对应相同长度的任何的明文。好比你问一群村民：“李向阳在哪里？”所有人都回答：“我就是李向阳！”在魔王追公主的故事中，就好比公主下一步可以跳到任何地方，“瞻之在前，忽焉在后”，完全无法预测。这让魔王怎么玩？魔王：“算你狠！破喉咙，你把公主带走吧！”破喉咙：“公主已经上天了，我也找不着她……”

这么说起来，保密的问题已经解决了？

其实没有！

真正的难题在于，怎么让双方共享密钥？在量子密码术出现之前，密钥需要第三方的信使来传递。而信使可能被抓（如《红灯记》中的李玉和），也可能叛变（如《红岩》中的甫志高），这麻烦就大了。现在甚至都有技术可以远程读出未通电的硬盘里的数据，传送密钥这活越来越不好干了！

甫志高

因此，在很长时间内，一次性便笺保密法的意义主要是在理论上，用来证明完全保密的系统是存在的，而实践意义很小。道理很明显：一次性便笺密钥跟你要传输的明文一样长，如果你能安全地传输这么多的密钥，那用这个信道直接传输明文不就得了？不就是因为没有这么安全的信道，才需要发展保密方法吗？这就好像周星驰的电影《国产凌凌漆》里那个“有光照才会发光的手电筒”，成了一个一本正经的笑话。

魔王长出一口气：来来来，公主，我们重回赛场！

密码学家们也不会轻易地狗带，他们开辟了另外一个战场，叫做“公钥密码体制”。公钥的意思，就是这个密钥是向全世界公开的，所有人都可以看到。还有一个私钥，只在接收方（以下称为B）手里有，发送方（以下称为A）手里没有。用公钥可以加密，但不能解密，用私钥才能解密。因此，A把明文用公钥加密后，公开传给B，别人截获了没有私钥无法窃密，而B拿到了就可以解密。公钥密码体制也常常被称作“非对称密码体制”，因为双方手里的密钥不一样多。而双方共享同一套密钥的方法就叫做“对称密码体制”，一次性便笺就是其中的一种。

公钥密码体制的关键在于：通过某些数学操作可以方便地从私钥得到公钥，但从公钥却很难得到私钥。也就是说，有些数学问题沿着一个方向操作很容易，沿着相反的方向操作却非常困难，“易守难攻”。

因数分解就是一个典型例子。把两个质数相乘得到一个合数，是很容易的，而把一个合数分解成质因数的乘积，例如291,311 = 523 × 557（到下一节你就会明白为什么举这个例子），就难得多了。

让我们想想，如何分解一个数字N。最容易想到的算法，是从2开始往上，一个一个地试验能否整除N，一直到N的平方根为止。如果N用二进制表示是个n位数，即N约等于2的n次方，那么尝试的次数大致就是2的n/2次方。指数上出现n，这就麻烦了，这叫做“指数增长”。学过微积分的同学们明白，指数增长是一种极快的增长，比n的任何多项式都快。比如说，2的n次方比n的10000次方增长得还要快。没有学过微积分的同学也不要头晕，看看下面的图就可以明白这个意思。

指数增长的威力。指数函数虽然在最初落后，但很快势不可挡地超越了线性函数和三次方函数，而且越到后面把它们甩得越远

在多项式之间比较，当然是次数越高增长得越快，例如n的三次方比二次方快，二次方比一次方快。但在计算机科学中，多项式内部的这个差别并不太重要，它们只是定量的差别（医生，我觉得我还可以抢救一下），而指数增长与多项式增长的差别是定性的差别（同志，放弃治疗吧……）。因此，计算机科学中把计算量多项式增长的问题称为“可解的”（tractable），把计算量指数增长的问题称为“不可解的”（intractable）。不可解的意思并不是计算机不能算，而是计算量增长得太快，通过扩大问题的规模，很快就能达到“用全世界的计算机算几十亿年都无法得出结果”的程度。

当然，你可以寻找效率更高的算法。对于因数分解，人们发展了很多种比“一个个试”聪明得多的算法。但到目前为止，这些算法的计算量仍然都是指数增长的。

1978年，基于因数分解的困难性，三位密码学家李维斯特（Ron Rivest）、萨莫尔（Adi Shamir）和阿德曼（Leonard Adleman）发明了“RSA密码体系”（这个名字是他们的首字母缩写），这是现在世界上最常用的公钥密码体系之一。

RSA密码体系的三位发明者

除了RSA之外，还有许多其他的公钥密码体系。无论哪种，基本思想都是一样的，安全性来自某个数学问题的困难性。回到魔王与公主的比喻，现在公主不是满世界乱跳了，而是按照某种确定的规则前进。魔王以前是完全无从追起，而现在有可能追上公主了，只要解出某个数学问题就行。但是这个数学问题的计算量是指数增长的，通过扩大问题的规模，很容易就使解题所需的时间变得不可思议的长（指的是计算题，不是五点共圆这种证明题）。魔王：为什么一定要解数学题，我们来比写诗吼不吼啊！

公钥密码体系是个伟大的发明，但它达到完美的安全性了吗？显然没有，因为完美安全性的意思是无论敌方有多强的计算能力都不能破解。

在这个前提下，如果我们退一步，把计算量指数增长作为仅次于完美安全的第二级别安全性，那也可以接受。但在这个台阶上，问题又来了：你怎么能保证对这个数学问题，不会发现多项式计算量的算法呢？

实际上，计算机科学中的一大难题就是：我们可以证明，计算量指数增长的问题有很多，然而，我们几乎无法确定任何一个具体的问题属于这一类！

包括因数分解在内，目前公钥密码体制用到的所有数学问题都是这样，无法排除哪天有人提出破解算法的可能。因此，密码学处于一种无止境的军备竞赛对抗之中，一方提出更强的攻击算法，另一方提出更强的保密算法，无限地循环下去。

算法的进步和硬件的进步，迫使许多公钥密码体系一再升级。例如RSA推荐使用的质数长度，就在不断增加。即使你升级了，也只能保护新的数据，许多历史数据还是可以被破解的，这又是一重头疼。

以上这些，都是基于对公开算法的讨论。但是，只有学术界才会把破解的消息公开。在实际的军事、政治、经济对抗中，对手如果破解了你的密码，会让你知道吗？偷袭珍珠港的策划者山本五十六是因为行程泄露，飞机被美国击落而死的，难道美国会告诉日本“我已经破解了你的密码”吗？

在拍摄此照片几小时后，山本五十六就被击毙

用《三体》的语言说，你无法判断对方是否破解了你的密码，这就构成了“猜疑链”。用美国前国防部长拉姆斯菲尔德的语言说，最可怕的就是“未知的未知”。

拉姆斯菲尔德和“未知的未知”

在量子密码术出现之前，永远的猜疑、无尽的升级和不时的泄密是我们不得不忍受的代价。毕竟，一次性便笺是个中看不中用的银样镴枪头，真正能用的最好的保密方法就是公钥密码体制了。

我的朋友、著名科普作家“奥卡姆剃刀”是一位通信专家，他有一个亲身经历的故事：

“那是一个涉密的科研项目，我们团队发明了一种三重MARS加密算法，我们认为比上级配发的传统加密方法更安全。