后量子时代密码学和中国的应对布局

4月11-13日在美国佛罗里达州的劳德代尔堡，美国国家标准与技术研究院(NIST)主持召开了首届后量子时代公钥密码标准化的国际会议(First PQC Standardization Conference)。会议受到全世界密码界人士的热烈关注，盛况空前，会议入场卷一票难求。

本次大会的议程已经公布，详见本文的附件。最令人高兴的是国内有三位专家学者参加大会发言，他们分别来自复旦大学、中国科学院和上海交通大学。由复旦大学赵运磊教授团队首创的KCL方案是基于LWE及其变体的后量子时代公钥密码系统，该系统在密钥协商和公钥加密领域具有相当的技术优势。我为我的两所母校在世界密码学研究中的取得的成就感到无比自豪，中国为互联网未来安全布局的积极、进取和合作的态度值得高度肯定。对此我可能会另作专文介绍。

公钥密码的安全性关系着互联网的“建久安之势，成长治之业。”引起专家学者们的关注势所必然。我们在本系列的上篇（TLS1.3将为互联网安全筑起新的长城）中指出：TLS是互联网传输层安全协议，它是互联网数据传输安全的基石。而TLS的核心是有关通信的加密解密、密钥分发、身份认证和电子签名。TLS的这些核心功能分别由对称密码和公钥密码（非对称密码）协同完成的。

对称密码使用共享密钥对数据进行加密解密，保证了数据在公共信道上传输的安全，公钥密码让通信双方在通信初始状态在公共信道上彼此建立信任并获得共享密钥。可以毫不夸张的说，公钥密码为互联网而生，没有公钥密码的互联网安全是不能设想的。

互联网上通信双方远隔千山万水又从未见过面，他们如何取得彼此的信任并协商出共享的密钥，而又不被第三者偷窃，这是对密码学的严峻考验。解决这个难题靠的就是公钥密码。公钥密码算法产生出一对密钥：公钥和私钥，通信双方通过交换公钥作身份验证和协商出共享的对称密钥。公钥密码巧妙地解决了网上通信双方的“第一次”的尴尬，网上安全一日不可无此君。

举个例子，当你使用浏览器访问互联网上的网站，浏览器和网站服务器都会首先调用TLS软件包。TLS制定的算法为通信双方分别产生一对公钥和私钥；然后通过握手程序交换公钥和身份认证信息；接着根据TLS提供的算法验证对方身份并产生共享的对称密钥；最后通信双方使用共享的对称密钥对传输的数据作加密和解密，保证这些数据在公共网络传输过程中不被破解和篡改。以上一连串复杂的过程全由TLS互联网传输层安全协议软件为每个用户自动代理执行的，它们才是互联网上全心全意为用户安全服务的忠诚卫士。

对称密码的安全性是有绝对保证的，那么公钥密码的安全性又如何呢？到目前为止，公钥密码还是安全的，至少与网络上许多其它隐患相比，它的相对安全性是有足够保证的（详见“量子密码工程建设还有太多不确定因素”一文）。但是面对传统电子计算机性能的提升和将来有可能出现的量子计算机的潜在威胁，有必要开发公钥密码的新算法，提高安全性增加灵活性，未雨绸缪为互联网的未来安全作好充分准备。为了互联网的长治久安，加紧研发新一代的公钥密码系统成为了密码学专家学者的共识，并为此取名为“后量子时代密码学”。这就是本星期召开的国际密码学会议的中心议题。

P1)受量子计算机攻击，经对称密钥加密后的数据传输仍是安全的，问题主要出在使用公钥密码作对称密钥分发过程中。     

【后量子时代密码系统的历史回顾】
2012年～ ：美国国家标准与技术研究院(NIST)启动后量子时代密码(PQC)项目，成立了包括12个密码专家的项目成员组；
2015年4月：举行第一次PQC专题研讨会；
2015年8月：美国国家安全局(NSA)就PQC发布声明；
2016年2月：NIST发布PQC工作报告(NISTIR 8105)；
2016年2月：NIST就PQC的标准化提出初步设想；
2016年8月：制定出对PQC新算法的要求和评估标准的初稿，并公开征求意见；
2016年9月：初稿征求意见期结束；
2016年12月：对新算法的要求和评估标准被正式确定，面向全世界征求PQC新算法；
2017年11月30日：提交PQC新算法的截止日期。

【后量子时代密码系统的现状】 到2017年11月30日截止日期前，NIST共收到各种后量子时代公钥密码方案82项，其中59项有关秘钥分发/加密解密，23项有关身份认证/电子签名。这些方案分别来自美国16个州和世界六大洲共25个国家。表面上看方案来自五湖四海，但实际上仍为欧美囯家所把持。中国也提交了一个方案，但与量子密码通信技术完全无关。

在提交的八十多项方案中，有些方案明显受到较多的关注，这里就让几位明日之星先亮亮相，它们都是达到抗量子攻击所必需的安全级别为128位的公钥密码。

NTRUEncrypt：这是后量子密码算法中最受关注的一位，NTRU（发音“en-true”）基于阻格数学原理。它的好处主要是内存占用低和运行速度快。缺点是涉及专利。很可惜，历史上开源项目一般都不会倾情于有专利授权的算法。

McEliece与Goppa：McEliece加密系统是目前密码界的一颗新星，它是第一个在加密过程中使用随机化的算法。它的好处是比RSA更快捷，主要缺点是密钥位数过长。典型的RSA密钥的键长是2048位，而McEliece键长达512千位！比RSA长256倍！

Ring Learning with Errors：另一个很有希望的后量子密钥分发方法是“带错的环学习”（RLWE）。它与场/集合理论中的问题有关，可以用于同态加密，这是密码界的另一个热点。 RLWE使用7,000位的密钥，比McEliece密钥短得多，与现在常用的RSA密钥长度在同一数量级。

CECPQ1: 这是密码界新杀出的一匹黑马。它是谷歌在RLWE基础上研发出了一种创新的密码算法并且作了实际测试，这是经典的椭圆曲线算法（Curve 25519）和被称为“New Hope”的RLWE变体的一种组合算法。谷歌使用一小部分Chrome浏览器和谷歌自已的服务器（可以有效地控制TLS通信的双方，谷歌做起来得心应手）测试了CECPQ1密钥分发功能。测试除了发现增加了1毫秒的延迟外，并没有发现任何其它的障碍，这可能是与密钥的大小有关。谷歌的实验已经结束，正在等待IETF的最后评判。

为后量子时代挑选合格的公钥密码有点像红楼梦剧组寻找林黛玉，在众多的美女演员中找来找去，初看个个千娇百媚，走近一看发现她们每个人都有这样哪样的瑕疵，不知天上什么时候才会掉下一个十全十美的林妹妹。

【后量子时代密码系统的展望】
2017年12月：NIST公布所有提交的新算法；
2018年4月：召开第一届PQC算法标准化全会，由算法提交方作陈述，并听取专家意见，这就是本星期大会的主要内容；
对第一轮候选PQC算法进行16～18个月评估和分析；
2019年9月：召开第二届PQC算法标准化全会；
对第二轮候选算法作出进一步评估和分析；
估计在2022年或稍后，PQC算法的标准草案正式公布并开始征求意见。

P2)后量子时代密码系统未来进程。     

对后量子时代密码系统的要求和评估标准 1）安全性。这一点容易理解，保证数据传输的安全隐秘当然是考核评估的先决条件和首要标准。对公钥密码新算法的安全性评估不仅要考虑量子计算机的攻击，还必须考虑到传统电子计算机的攻击，在今后相当长时间内，后者的威胁可能更为实在。 2）运行性能。这一点往往被外行们所忽视，这也是量子通信工程的一大问题。评价密码系统只谈安全而不讲效率和速度实质上毫无意义。从工程角度来看，世界上本无绝对的信息传输安全，也不需要绝对安全，所有信息的重要性也都有时间性。密码系统所要做的就是以最低的代价保证信息在其有效期内不被敌方破解，或者至少让敌方为了破解必须付出难以忍受的代价。高效率低成本是选择后量子时代新公钥密码的重要考量。 3）兼容性。新的密码系统必须与今日互联网的物理没备和各种通信协议兼容，与上文提及的TLS无缝衔接是必须的。仅仅为了应对仍停留在纸上的量子攻击，而丢弃所有现成的通信安全技术，建设所谓的“量子互联网”，是非常不成熟的行为。 4）还要解决互联网安全的一些老问题和新矛盾，诸如解密出错、PFS和侧道攻击等等。这些问题并不常见而且太过专业，本文就不作进一步讨论了。

在确定后量子时代密码新标准时，NIST对密码系统的成本和效能作了明确的要求：
1）要求密码新标准必须能运行在传统计算机平台上；
2）密码新标准能在尽量多种多样的操作系统上运行，并满足不同应用程序的需求；
3）新标准可能会选择多种算法，利用它们的各自优势去满足不同的需求，在这场标准化竞争中，胜出者很有可能不止一种算法；
4）为提高效能易于平行化运行的密码算法会得到优先考虑。

通过以上对TLS通信安全协议和后量子时代密码学的分析，我们可以清楚地看到，对TLS不断改善升级同时研发全新的公钥密码算法是保卫互联网安全的唯一可行路线，这是由互联网安全的态势、技术的可行性和兼容性所决定的。

我们必须认识到今天互联网安全的主要威胁根本不在公钥密码系统上，公钥密码在可预见的将来是安全的。企图仓促启动量子通信工程来代替公钥密码不仅毫无必有要，而且也没有可能，因为量子通信在组网等关键技术上远未成熟。缺乏对互联网安全形势的全面深入的了解，采取草率过激的反应，有意或无意中夸大量子通信的重要性，只会误导大众、自乱阵脚，其结果必然是浪费资源。

更为关键的问题是技术的兼容性。我们一定要明白，所谓的量子通信不是一种新的通信技术，量子通信事实上也不是一种新的完整的密码技术，确切地说它仅能提供公钥密码中的一部分功能——即对称密钥的分发功能。通信和密码是皮和毛的关系，密码是毛，它只能依附在通信这张皮上为皮服务的。皮之不存毛将焉附，甩开传统互联网这张皮，量子通信这撮毛何以安身立命？

从更长远的角度来看，任何技术都需要更新和完善，公钥密码技术当然也不例外。但是更新后的系统必须与互联网的总体框架协调，升级换代的过程也要稳步有序地推进。密码系统牵动整个互联网的生态环境，这是一个比操作系统远为庞大复杂的生态系统，对于这种牵一发而动全身的技术更新，我们千万不能异想天开、草率行事，进入误区。

在不断改善升级TLS的同时，研发全新的公钥密码算法，这条提升互联网安全的路线把技术的可行性和兼容性放在评估标准的首位，这是一条稳妥、可靠、行之有效的路线。这条路线也是一条开放合作的路线，所有的协议细节和密码算法全部公开放在桌面上讨论分析，所以也取得了世界大多数国家有关专家的认同和支持，开放和合作是推动互联网稳步向前发展的基础。

P3)远征启航——寻求后量子时代新的密码标准。     

首届后量子时代公钥密码标准化的国际会议的大会议程
   Agenda-PQC2018.pdf