光量子信使：传递密码的奇思妙想｜量子计算群英会(六)

量子力学与信息科学相结合的量子信息学，包括三个基本方向。除了量子计算之外，还有量子通信以及量子精密测量。在量子通信中，研究和应用较多的是量子密码。开启量子密码学这扇大门的，是三位科学家。他们最早提出了有关量子信息的几个奇思妙想，后来发展为“量子密钥分发”中的BB84协议，这是量子密码学任务中一个著名的例子。

图1：开启量子密码学的科学家

量子粒子与经典事物的区别之一是不能复制又无法测量！那么，有人就想：能不能把光量子印到钞票上以避免假钞呢？他的朋友说：好像很难，光子跑得太快了！于是，他们说：那就让它跑吧，也许可以帮我们传递通信中的密码！后来，就有了量子密钥分发……

量子密钥分发，与其字面上的意思差不多，就是用量子的方式来发送一把“私密钥匙”。具体而言体现在图1中右边两位科学家提出的BB84协议，其中的BB，是两位科学家姓氏的首字母，再加上方案提出的年份84，就是1984年。那么，私密钥匙是个什么钥匙？为什么要发送它？BB84协议又说些啥？为了探索这些问题，我们先简介经典通信，也顺便了解几个加密通信中的专用名词。

01

两种经典加密方法

保密和窃密的概念自古有之，“道高一尺，魔高一丈”，两者间永远进行着不停升级的智力战争【1】。现代保密通信技术的目的，除了保护个人隐私之外，也关系着国家政府及政党间的斗争，以及战争的胜负，国家的存亡等等。

举一个通俗例子：爱丽丝和鲍勃分居于两个远离的城市，且工作繁忙不易见面。但爱丽丝经常给鲍勃送去贵重礼物，她通常将礼物用某种锁锁在牢固的箱子里寄给鲍勃，又用某种方式将开锁的钥匙传递给鲍勃。这样，鲍勃收到箱子后用钥匙将锁打开就得到礼物了。

假设钥匙是偷礼物的唯一方式，这样，所寄物品的安全性就完全取决于钥匙的安全性了。

有人说，这很简单，两个人预先为这把锁定制两个一样的钥匙就可以了，别人没有钥匙，无法偷走礼物。不过，这种办法只能用1、2次，如果久而久之，总用同一把锁同样的钥匙的话，显然是不安全的，小偷可以想办法复制钥匙啊！

又有人出主意啦：可以每次都变更锁和钥匙，然后，花钱雇佣一个可靠的人专门为他们传递钥匙。也就是说，使用第三方作为信使。不过，这也不是什么好办法，如果信使可以传钥匙还不如直接带礼品了。况且，信使也未必就那么可靠啊，有历史为证，叛徒和奸细比比皆是。

所以，我们仍然回到了如何传递“每次变更”的钥匙的问题。

上面描述的方法，爱丽丝和鲍勃用同样的锁和钥匙，是对称的，叫做对称加密，如图2（a）所示。对“每次变更”钥匙和锁的方法，则叫做“一次一密”（one-time pad，OTP）。

聪明的鲍勃想出了第二种办法：鲍勃自己打造一套锁和钥匙。他只将一把打开了的锁寄给爱丽丝，自己保管着配套的钥匙。爱丽丝没有钥匙，但可以很方便地用这个锁将箱子锁上，然后寄给鲍勃。最后，鲍勃用自己保存的钥匙打开箱子，得到礼物。这种方法叫做非对称加密，因为鲍勃有钥匙，爱丽丝没钥匙，双方不对称，如图2（b）所示。

图2：两种常用的密码方法

以上爱丽丝和鲍勃所采取的两种方法，是现代通信中常用的。不同的是，现代通信被加密和解密的是文件，并且使用计算机和网络技术来实现这些操作。在密码学中，需要保密传递的文字被称为‘明文’，将明文用某种方法改造后的文字叫做‘密文’或‘密码’。因此，将明文变成密文的过程就叫‘加密’，反过程则被称为‘解密’。现代通信中，加密解密时使用的方法，指的是某种计算机‘算法’，这些完成特定计算算法中的一组参数，叫做‘密钥’。

对称加密技术中，信息的发出方（爱丽丝）和接收方（鲍勃）共享同样的密钥，解密算法是加密算法的逆算法。这种方法简单、技术成熟，但由于“共享密钥”，所以难以保证密钥的安全传递。

非对称加密技术如图2（b）所示，每个人（作为接收方）产生自己的一对密钥（公钥和私钥）。例如，图中打开的锁是公钥，钥匙是私钥。公钥用于加密，私钥用于解密。加密算法（公钥）是公开传输的，解密算法是保密的。非对称加密在算法上也不对称：从私钥的算法可以容易地得到公钥，而有了公钥却极其难以得到私钥。也就是说，需要一种正向操作容易，逆向操作非常困难的算法。目前常用的RSA密码系统就是为了达到这个目的。

RSA算法是李维斯特（Ron Rivest）、萨莫尔（Adi Shamir）和阿德曼（Leonard Adleman）三人发明的【2】，以他们姓氏中的第一个字母命名。它基于一个简单的数论事实：将两个素数相乘十分容易，反过来，将其乘积进行因式分解而找到构成它的素数却非常困难。例如，计算17×37=629是很容易的事，但是，如果反过来，给你629，要你找出它的因子就困难一些了。并且，正向逆向计算难度的差异随着数值的增大而急剧增大：正向两数乘法运算的时间复杂度顶多是大小的平方，而逆向运算复杂度成指数增长。对经典计算机而言，破解高位数的RSA密码基本不可能。例如，一个每秒钟能做1012次运算的机器，破解一个300位的RSA密码需要15万年！

02

量子信息第一人

RSA密码不容易被经典计算机破解，似乎挺安全的。然而，技术总是在不停地进步，如果有了量子计算机，情况就变得大不一样。量子计算机可以使用Shor算法，只需几秒钟便有可能破解刚才那个现代计算机15万年才能破解的300位的密码。这听起来太可怕了！如果在战争中，敌对方有了量子计算机的话，破解他方的RSA通信密码就将轻而易举不成问题了。虽然通用的量子计算机目前尚未开发出来，但是防火于未燃还是有必要的，这就是为什么各个大国大公司都开始研究量子信息及量子通信技术的原因。

既然量子理论可以用来建造量子计算机，是否也有可能用来进行保密通信呢？最开始提出这个问题，设想量子信息原始思想的，是一位颇为传奇的科学家史蒂芬·威斯纳（Stephen Wiesner，1942—2021）【3】。也不是1984年，而是早在14年前的1970年。那年，哥伦比亚大学的威斯纳写了一篇名为“共轭密码”的论文（图3），指出结合量子力学，可以完成两项经典密码学无法完成之事。一是量子支票，二是两条经典信息合成一条量子信息发送，接受者只能选择接受其中一条。这两项都包含了量子密码的思想。但在当时听起来太匪夷所思，所以论文未被专业杂志接受。

图3：威斯纳和他1970年的论文

威斯纳出生于美国的犹太移民家庭，父亲是电机博士，麻省理工学院教授，当年在该校的辐射实验室从事微波雷达开发工作。二战之后，他在洛斯阿拉莫斯国家实验室短暂工作过，然后于1946年至1961年返回麻省理工学院电子研究实验室。他曾经担任肯尼迪总统的科学顾问，之后又担任麻省理工学院（MIT）理学院院长和第十三任校长。

成长于这样的家庭环境下，威斯纳对量子力学、和电子通信充满兴趣。

1960年，威斯纳进入加州理工学院，正好与1972年首次用实验证明贝尔定理的克劳泽（Clauser，2022诺贝尔物理奖得主）一起上物理实验课并成为好友，经常互相讨论量子力学问题。但威斯纳后来转学到东岸麻州的布兰戴斯大学，不过又与当时在化学系读大三的查理·贝内特（Charles Bennett，1943-）成为室友和好朋友。这份友谊在日后促成了贝内特研究量子密钥分发并提出BB84协议。并且，贝尔（Bell，1928-1990）于1964年，以访问学者的身分来到布兰戴斯大学，就在那年完成了有关贝尔不等式的论文。这些经历，帮助和启发威斯纳萌发了他有关量子信息的想法。

威斯纳于1966年毕业后，到哥伦比亚大学读研究所。两年后他写了那篇题为《共轭编码》(Conjugate Coding)的论文，提出如何利用光子的偏振，打造无法仿冒的“量子货币”（quantum money）。

1969年，威斯纳向IEEE信息论汇刊提交了论文。当时，没有人认为量子理论与信息理论有关系，手稿被拒绝了。他之后没有试图在任何地方重新提交它，而且他从周围的大多数人（包括他的博士导师）那里收到的信息是，这些想法不是“严肃的科学”。尽管威斯纳这项工作十多年来一直未发表，但幸运的是，他将副本发送给了包括查理·贝内特在内的一些同事，使其以手稿形式传播，从此打开了量子信息学之门。

威斯纳考虑“量子货币”，最初是想解决伪钞的问题。歹徒总是可以做出就连银行都难辨真假的伪钞。于是，威斯纳便利用量子物理学中的“量子不可克隆定理”，及不确定性原理，想出了这么一个方法，大概意思是说，如果你制造了一个量子态，并且对外界保密，那么任何人都不可能克隆一个跟它一模一样的量子态出来。量子货币除了和一般纸钞一样印有钞票编号，还嵌入和钞票编号对应的偏振光子。银行可以透过偏振片检查是否假钞。

威斯纳后来以弱相互作用方面的论文，于1972年取得博士学位。“共轭编码”的论文也终于在1983年刊载于美国计算机学会的SIGACT刊物上。威斯纳性格内向、害羞，他不关心荣誉，发表论文也不上心。1993年，他选择离开美国，移民到以色列，成为耶路撒冷的一名建筑工人。晚年的威斯纳，极力避开世俗人群，过着极为简朴的生活。2021年，这位量子信息之第一人在耶路撒冷去世，享年79岁。

03

贝内特和布拉萨德

贝内特1943年出生于纽约市，在哈德逊河一带度过童年，后来，有机会接触到最早版本的计算机。不过，他在布兰代斯大学读本科时的第一个兴趣是生物化学，之后，当他成为哈佛大学研究生时，注意力转向了化学物理。美国大学的博士研究生，一般同时会担任某课程的助教。贝内特正好是为詹姆斯·沃森 (James Watson)的课程作助教。这位DNA 领域著名的科学家，自然地经常谈到遗传密码；这使贝内特突然产生了将遗传密码机制与图灵机联系起来的思想。

毕业后，贝内特到芝加哥的阿贡实验室作博士后，又对计算机进行数据分析产生了日益增长的兴趣。在那儿他听到IBM的兰道尔关于计算不可避免的能源成本的演讲，兰道尔表明这是由于逻辑上不可逆的步骤造成的。在兰道尔的鼓励下，贝内特用化学图灵机的想法，用计算机探索这个热力学问题，最后，研究颇有成效，贝内特转到IBM作博士后。

几乎同时，贝内特开始与本科时的好友威斯纳交谈，那正是威斯纳考虑“共轭编码、量子纸币”这些概念的时候。威斯纳对“用量子粒子可以做到而用普通信息无法做到”的事情有一些想法，贝内特将这些想法用当时还不存在的短语“量子信息”来总结，他特别感兴趣的是，如何使用量子通道将两个消息组合在一起传递。

几年后，贝内特在一次信息学国际会议上，碰到加拿大蒙特利尔大学来的一位计算机博士生。吉尔斯·布拉萨德（ Gilles Brassard，1955-）研究密码学，在那次会议上作了一个“相对密码学”的报告，贝内特认为他可能会对量子信息感兴趣，便和他一起讨论这些想法。

两个年轻科学家一见如故，他们的思想经过剧烈碰撞后，发现“量子钞票”的想法也许不实际，因为光子转瞬即逝，很难将其“印”在钞票上装进人们口袋里。但是，光本来就是用来传播信息的，那我们干嘛不发挥它的特长，让它来传递某种“不可伪造”、“不可复制”的重要信息呢？这个方面，作为密码通信的一种新想法，是值得研究的。

于是，他们合作研究，向世人介绍了一个新的理论，叫作“量子密码学”。他们开发了量子密钥分发的一种具体方案，之后被称为 BB84 协议，他们的论文发表在1984年的一次IEEE的会议上。

贝内特和布拉萨德于2018年，荣获沃尔夫物理学奖【4】。

04

量子密钥分发

现在我们回到经典密码学，看看量子论对它能做些什么？我们介绍了常用的两种密码通信系统：对称的和不对称的。前者的想法简单，但问题是安全性取决于“密钥”的传递；后者设计巧妙，典型例子是RSA算法，经典计算机难以在有效的时间内破解，所以因其暂时的安全性而被广泛使用。

科学家们从两个不同的方向将量子概念用于通信技术。一是研发量子计算机，来攻击和破解不对称系统中的RSA算法。第二个方向，就是贝内特和布拉萨德发明的量子密钥分发，它利用量子力学的特殊物理规律，与“一次一密”的加密技术结合，可以在对称系统中实现安全的“密钥”传递。

图4：BB84协议的两个通道

图4是BB84方案的示意图，简单解释一下贝内特和布拉萨德当初设想的通信过程【5】。

1）信号通道有两个：经典通道，传递方法和原来一样，通过无线电或因特网等公共通道实现；另外还有一条特殊的量子通道。其中，发送者利用光子的偏振态来传输信息，光子可以经过光纤或其他介质从发射到。量子通道的目的只是产生和传递“密钥”，相当于图2a中信使的角色。一般来说，假设Eve具备窃听这两个通道信息的能力。

2）实施的传递过程分两步：

第一步，传递和产生可靠的“共享密钥”，使用量子通道为主，经典通道为辅。

第二步，传递用“共享密钥”加密后的文件，这时只用经典通道，与经典情况一样。

3）要点是防止窃听。经典通信中，Alice和Bob无法发现Eve是否在窃听。但量子密钥分发的量子通道，Alice和Bob则可以发现Eve的窃听行为，因为任意获取信息的行为都会改变量子系统，又因量子不可克隆，Eve也不能直接复制信息。传递信息的双方一旦发现第三者的窃听行为，便可以立即停止通信，重置密钥。

4）BB84协议与量子纠缠无关。经典信息的传递对通信的完成是必要的，传递速度由其决定，不存在是否“超光速通信”的疑问。

图5：BB84协议-“密钥分发”示意图

如图5所示，Alice可以采取两种方式来制备偏振态的光子（或者说制备量子比特）：直线基"+"，和对角基"×"。在直线基中，分别用水平偏振（0°）和垂直偏振（90°）来表示0和1。在对角基中，则分别用（45°）偏振和（135°）偏振来表示0和1。

这就好比是有两种产生和测试量子比特0和1的机器，一种机器叫"+"（直线机），一种叫"×"（对角机）。Alice随机地选择用某一种机器产生她的每个量子比特，并将她所用的机器顺序记录存放下来，而只把生成的0和1序列串由量子通道发送出去。相应的，接收者Bob和偷窃者Eve，也都拥有测试这两种量子比特的机器：直线机"+"和对角机"×"。

BB84协议利用了被传输的偏振光量子不可克隆性，以及两种机器生成的光量子的不可区分性。由于不可克隆，一个光量子一旦被测量，它的状态便发生了改变，不再是被测量的数值。由于光量子不可区分，被传输的量子上，并没有贴上产生它的机器的标签，因此测量时，只能将它随机地放入两种机器中的一个，如果刚好放对了，那么测得的结果百分之百准确，如果放错了，那么百分之五十的可能性是正确的。因为是随机放的，所以，测得的结果的准确率应该是放对了的50%，再加上放错了的一半中仍有一半的概率正确（25%），最后得到75%。

Bob收到Alice发送的信息串之后，将每一个光量子随机地放进两种测量机中的一个，并记录下测量结果和机器顺序（图5右边），将机器顺序以及部分比特序列，从经典通道发回给Alice。如果这个信息串半路中没有被拦截的话，根据上一段的分析，它的正确率应该是75%。这时，Alice可以通过比较Bob接受到的机器顺序和部分比特，和她自己发送时的数据，而算出Bob测量结果的正确率。如果这个数值大约是75%，说明信息没有被窃听，这样，Alice就将原来数据中Bob用对了机器的那些量子比特挑选出来，作为通信的密钥，并且将密钥的机器顺序位置发给Bob。

然而，如果量子比特在传输中途被Eve拦截了的话，因为这个量子比特已经被Eve测量过了，不再是原来的数值。所以，因为窃听者的存在将给Bob得到的最后结果引入额外的50%的误差。解释得更详细一点，Eve窃听过的量子比特，有50%的可能性没变（Alice原来的），有50%的可能性改变了。如果Bob测量的这个量子比特，是被Eve窃听过但没改变的，正确率便等于75%*50%=37.5%，如果Bob测量的这个被Eve窃听过但改变了的量子比特，正确率便等于50%*50%=25%。因此，总的正确率等于37.5%+25%=62.5%，小于原来的75%。这样，Alice比对了自己与Bob的数据之后，发现正确率为62.5%左右，就能知道有窃听者存在，便丢弃这次传输的数据不用而采取其它相应的措施。比如，她可以立即换用另外一个量子通道。

BB84是第一个量子密钥分发协议，之后还有其它改进和完善的分发方法。

参考资料：

【1】《碼書》，Simon Singh 著，劉燕芬 譯，台灣商務印書館出版

【2】Stephen Wiesner – Wikipedia

【3】Adi Shamir Ronald Rivest and Len Adleman. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21:120–126, 1978.

【4】维基百科-沃夫物理奖（2018）

【5】维基百科-BB84