密码的密码：如何对抗量子解密

　　密码有多重要？当今社会须臾难离。大到国家安全、金融安全，小到个人资金安全、邮件安全，皆离不开密码。

　　人类已经进入互联网时代，在虚拟空间中，每秒钟发生的转账、交易、邮件传输难以计数，是密码保证了这一切的安全进行。

　　有赖于上世纪70年代出现的公钥加密系统，让安全而且高效的互联网传输成为可能。2016年3月2日，公钥加密系统的两位创始人因此获得有“计算机界的诺贝尔奖”之称的图灵奖。

　　然而，反面例子仍然存在。在通信技术如此发达的今天，各国间涉及政治外交、军事安全的大部分机密信件和物品，仍然通过最传统的方式——外交信使来传递。原因是，即便是再高级的保密通信，只要是通过当前的电话线、无线电、光纤等手段，都会面临被破译和窃听的可能。

　　加密与解密的战争从未停止，保密信息背后隐藏着巨大价值，总会让人想方设法攫取这些信息。

　　如今，以“公钥加密系统”为代表的传统密码系统的更大挑战来了——科学界公认，不久之后，量子计算机可能面世，量子计算无疑会带来科技和社会的巨大进步，但其也会让传统密码体系变得不堪一击。

　　传统密码的危机甚至已迫在眉睫。3月上旬，《科学》杂志发表的一篇论文显示，量子计算有史以来第一次以可扩展的方式，初步实现了肖尔（Shor）算法。虽然此次量子计算中只有5个量子比特，但是论文强调其是可扩展的。如果论文所述为实，真正量子计算机的出现只是时间问题，而且不再遥远。

　　换句话说，此事意味着在量子计算机没有出现之前，科学家就已经为它准备好了破解当今密码体系的量子算法，只待量子计算机的真正出现。

　　好消息是，全球密码学界对于量子计算机的出现早已开始未雨绸缪。目前的难题是，应该在现有的加密算法体系上改进，还是改弦更张，拥抱理论上无懈可击的量子密码？

乌云笼罩

　　3月2日，斯坦福大学密码学和网络安全技术专家惠特菲尔德•迪菲（Whitfield Diffie）和马丁•赫尔曼（Martin Hellman）获得美国计算机协会颁发的2015年度图灵奖，并获得由Google公司赞助的100万美元奖金。这两位获奖者的研究，奠定了当今互联网的安全基础。

　　他们提出的“公钥加密系统”构想，让人们在一个完全开放的信道内，无需事先约定，便可进行安全的信息传输。这项发明成为今天公共密码交换系统的基础，被广泛应用于网络通信。

　　在古老的对称加密中，通信的双方必须拥有一个共同拥有的密钥，因此又被称为私钥加密。而在互联网等环境下，如何安全分发密钥是一个大问题。迪菲和赫尔曼提出的设想是，利用非对称加密或者公钥加密来实现密钥分发。

　　在公钥加密中，有一个公钥是公开的，任何知道这个公钥的人都可以利用这个公钥来加密需要传送的信息，但要想对这些信息解密，还需要有一个私钥，该私钥由信息接收者持有。这也就是为什么公钥加密被称为非对称加密。加密密钥与解密密钥在数学上相关，用加密密钥加密后所得的信息，只能用解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的机密性。

　　公钥加密技术，简单来说，就是拿两个很大的质数A和B进行乘积，然后把这个乘积作为公钥进行加密，然后用质数A或B进行解密。虽然得到A和B的乘积很容易，但是要直接从这个乘积分解成两个质数，就非常非常难。

　　现在，每天都有几十亿人在使用迪菲-赫尔曼密钥交换协议与银行、电商网站、电邮服务器以及云服务建立安全链接。

　　迪菲和赫尔曼的理论，启发Ronald Rivest、Adi Shamir和Leonard M. Adleman于1977年提出了著名的RSA密码体制。这三位科学家对RSA密码体制的贡献，让他们在2002年获得了图灵奖。

　　RSA密码体制是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。作为海外信息加密和安全认证领域的龙头企业，RSA公司拥有全球70%的市场份额。但随着计算能力的不断提高，尤其是基于量子计算机的肖尔（Shor）算法的出现，让基于大整数因子分解的公钥加密技术变得越来越脆弱。

　　中国地质大学（武汉）计算机学院副教授程池对财新记者说，目前的公钥方案大都基于数论中的数学困难问题：大整数因子分解和离散对数问题。在日益强大的计算能力面前，尤其是不久的将来可能出现的量子计算机，公钥加密算法也面临巨大挑战。

　　在量子计算机迅速发展的前提下，人们目前所使用的安全体系如何向抗量子计算转移，将是亟待解决的一个问题。

　　1985年，牛津大学的物理学家戴维•德意志（David Deutsch）提出了“量子图灵机”的概念。随后，贝尔实验室的彼得•肖尔（Peter Shor）于1995年提出了量子计算第一个解决具体问题的思路，即Shor因子分解算法。他的算法证明，可以用量子计算机来比较容易地分解大整数。

　　利用量子计算的并行性，Shor算法可以在很短的时间内通过遍历来获得质数因子，从而破解密钥，使RSA加密技术不堪一击。

　　西安电子科技大学通信工程学院密码学专业教授王保仓告诉财新记者，自从Shor算法被提出后，密码学界一个公认的事实，就是目前基于大整数分解的RSA密码、基于椭圆曲线随机数的ECC密码，在量子计算机面前肯定会被攻破。“肯定是没办法用了。”他说。

　　从那时候起，密码学界就开始不断提出新的密码算法，这些密码不仅需要能够抵抗量子攻击，功能也要更加强大，实现一些传统加密手段无法实现的功能。

　　Shor算法提出一年后的1996年，同在贝尔实验室的洛夫•格罗弗（Lov Grover）提出了格罗弗算法，即通过量子计算的并行能力，同时给整个数据库做变换，用最快的步骤显示出需要的数据。

　　量子计算的格罗弗搜索算法远远超出了经典计算机的数据搜索速度，这也是互联网巨头们对量子计算最大的关注点之一。

　　3月5日发表在《科学》杂志的一篇论文，让量子计算机的来临显得并不遥远。这是人类第一次以可扩展的方式，用Shor算法完成对数字15的质因数分解。这项研究来自麻省理工学院和奥地利因斯布鲁克大学的合作。报告称，他们设计并搭建了一台在离子陷阱中只有5个原子的“量子计算机”，使用激光脉冲来操纵原子，这个系统的设计允许通过增加原子和激光来搭建更大型更快速、能够分解更大数字的质因数的量子计算机。

　　IBM物理科学高级主管马克•利特（Mark Ritter）表示，Shor算法是第一个不容小觑的量子算法，拥有对经典算法进行指数级加速的潜力。将Shor算法实现出来这件事，能够与经典计算中的“Hello，World” 相提并论。

密码自救

　　面对量子计算机的威胁，人们自然而然可以想到量子密钥。量子密钥是在A和B之间共同生成一串只有两边知道的随机数，然后用这个随机数来加密。

　　上世纪90年代，美国IBM公司沃森实验室的查尔斯•本内特（Charles Bennett）等人提出，由A向B发射一系列不同偏振态的光子，B对其进行随机测量，然后双方通过传统信道进行公开比对，把双方测量基相同时得到的测量结果转换为随机数。在协商密钥的过程中，是否存在窃听行为，可以从测量结果的错误率中发现。

　　中国科技大学量子信息重点实验室韩正甫教授告诉财新记者，量子密码在短时间内、一两百公里距离内，没有太大的问题。量子密码和量子计算机说不清是谁抗谁，因为安全性在一个水平上，相当于现在的密码和计算机。但用量子密码完全取代现有的密码体系，存在不少问题。

　　韩正甫说，量子密码不是一个包打天下的技术，有些方案实现起来还很困难，例如身份认证问题，用起来不像人们想的那么容易。

　　今年全国“两会”期间，在接受《中国青年报》采访时，中国科技大学常务副校长潘建伟透露，中国研制的世界首颗量子通信卫星有望在今年7月发射，相应地，量子保密通信“京沪干线”，也将在下半年全线开通。

　　一位量子密码专家这样形容，用量子的方法来对付传统的方法，比较有优势，但是新的攻击总会出现，有量子的防守，也会有量子的攻击。

　　对于量子层面的攻击，潘建伟曾对财新记者表示，目前在真实的量子通信系统中，系统远远比攻击者强大，科学家假定窃听者具有物理学原理所允许的所有能力，其实现实中可能性不大。

　　程池表示，现有的密码体系范围很广，还包括签名、认证、加密等等。量子密码取代现有密码的主要困难是，从理论到实际，到底安全性如何，还有待时间的考验。

　　密码的理想状况是一次一密，但一次一密成本高、效率低。在王保仓看来，量子密码可以理解成一次一密，通过量子手段产生的随机密码肯定是无法重复使用，否则在名文之间肯定有规律可循。他认为，量子密码的局限性非常大，代价太高，功能也单一。

　　上海大学数学系副教授曹正军进一步指出，通讯的首要目的是稳定性，即接收方能够正确地恢复出发送方发送的信号。在有敌手介入的情况下，量子通讯在阻止敌手获得信号的同时，也无法保证接收方获得正确的信号，就是说信号安全与通讯系统的稳定性是不兼容的。

　　曹正军认为，本内特等人所提出的量子密钥分发，实际上应叫作量子密钥协商，他们没有认识到信号安全与信息安全的差异。“大规模的量子通讯网络是不可行的。”

　　在韩正甫看来，现在的密码体系面临三个威胁：第一是量子计算机；第二，谁都没有办法从理论上证明现在的密码体系是安全的；第三，现在的计算机也越来越快，需要不断加长密码，导致长得没法用。

　　程池介绍，目前公认的能够抗量子计算机的包括基于杂凑函数的签名方案、基于格的密码系统、基于编码的密码系统和基于多变量的密码系统。

　　不过在韩正甫看来，现在学术界所考虑的抗量子密码体系，通常还是数学密码体系，但其实这和现有体系的安全性是一样的，都没法从数学上证明。

　　以格密码为例，它的思想是每个格子都跟周边相互作用，在数学上非常困难，所以被认为能够抗量子计算。韩正甫在好几次会议上跟数学家“抬杠”，他的理由是，这是因为量子计算的原始推动力，就是希望解决模拟结晶的过程，这是量子模拟的最重要目标。如果量子模拟能够解决结晶问题，那么量子计算机破解格密码也不在话下。

　　在物理学家和量子密码专家眼中，目前的抗量子密码，只是数学家的一个想法，还拿不出证据证明量子计算机真的解密不了这些抗量子密码。量子计算现在只有Shor算法和Grover算法，这两个算法解决不了，不代表未来没有更多的算法被发明出来。

　　王保仓坦言，目前这些新的抗量子密码，从理论上证明能够抵抗量子计算机确实非常困难，但是这个问题是跟RSA、ECC密码所面临的问题是不一样的，至少现在还没有可以在量子计算机上针对这些密码的更快算法。

　　“两边还在竞争中。”韩正甫说，即便是比较公认的候选密码，是不是真的能抗量子计算，有科学家还是持怀疑态度。

斗智斗勇

　　实际上，就算是没有量子计算机，目前的密码体系依然存在隐患。

　　来自中国山东大学的王小云教授就曾经发现了破解RSA公钥算法的方法，导致美国技术标准局强烈建议把RSA公钥从1024位提高到2048位，这也大大增加了加密工作的负担，甚至导致密码长得没法用。

　　面临来自量子计算机的严峻挑战，新技术研发更是刻不容缓。那么，量子计算机究竟还有多远？

　　对于《科学》杂志上发表的利用量子计算实现Shor算法的论文，有中国科学家提出了异议。

　　实际上，早在2015年7月这篇论文在预印本网站发表的时候，曹正军就发表了一篇质疑的文章。这篇文章指出，要实现利用Shor算法分解15，根据Shor算法的条件需要用12个量子比特，其中第一个寄存器要用到8个量子比特，低于这个数目就无法实现Shor算法的关键步骤——连分式展开。

　　但在这篇文章描述的实验中，只实现了对5个量子比特的操控，它把第一步所需的8个量子比特缩减到了1个。曹正军认为，这在实现Shor算法的条件上本身就不满足，不是真正的Shor算法。如果这个计算方法真实可信，那么也应该是一种新的算法。

　　不过，在马克•利特看来，这支团队是通过循环利用量子比特的方式将量子系统所需的资源降低了三分之一——这是通往扩大量子计算规模的路上很小却很重要的一步。

　　实际上，单纯就15进行分解而言，不只很多量子算法做得到，经典计算机也做得到。真正应当关心的，是能否真正实现Shor算法。只有这种算法真正实现了，将来破解成百上千位的大整数才有可能。

　　这篇文章所提出的量子计算机实现方法的可扩展性，在韩正甫看来，也存在疑问。他们其实用的是一种离子计算体系，这种方法的特点是，用激光束操纵离子点，像弹钢琴一样，这在理论上比核磁共振算法好，理论上可以操控很多离子，所以说可扩展，但是它其实并没有半导体方式、超导方式更具有可扩展性。用这种方法实现Shor算法，不见得和其他量子计算体系有什么优势。

　　真正的量子计算机何时以何种形式出现，仍是未知数。即使按专家们保守预测，量子计算机的实际应用也还要再等10年到15年，但寻找新的密码系统，特别是开发密钥分配的新技术已经刻不容缓。

　　目前，对抗量子计算解密的研究已成全球热点。已有包括欧盟支持的“PQCrypto and SAFEcrypto”研究计划和日本的 “CREST Crypto-Math”研究计划。

　　自2006年开始举办的抗量子计算密码学会议，从最初的隔年一办到目前的每年一办，所吸引的参加人员也越来越多。从2013年开始，欧洲电信标准协会已经连续举办了三次“Quantum-Safe Cryptography”（量子安全密码学）研讨会。

　　此外，工业界也开始把目光投向抗量子计算的领域。在2016年2月举办的第七届抗量子计算密码学会议上，除了美国国家标准与技术研究院（NIST）向全球宣布要公开征集抗量子计算的密码学算法，还有包括Intel、Google等公司人员参与。Intel还在会上宣布，从2020年开始，公司所有的产品在安全方面都将具有抗量子计算的能力。

　　当然，对中国来说，还要考虑另外一个问题。目前国内使用的大多数算法都来源于国外，国家担心国外安全机构拥有某些未公开发表的破解方式，亟须不断推出自己的国产算法。

　　2013年路透社曾经报道，美国国安局曾与RSA公司达成协议，要求在其移动鉴证产品广泛使用的加密技术中放置后门。这一传闻大大推动了各国信息安全和认证行业的“国产化”进程。

　　对于这一状况，在密码升级换代的前夜，中国应如何应对？

　　程池表示，如果NIST此次能够真的以公开、公正的方式进行抗量子密码的标准选取，国际上认可度还是很高的。他认为，中国在商业密码方面应尽可能按照国际标准来行事，就像通信领域的4G标准一样，积极主动参与标准设定，作出自己应有的贡献。■