抗量子密码技术漫谈
2019/6/18 20:06:41路献辉 中国科学院北京分院
受持续升温的量子技术的影响，抗量子密码也成为人民大众经常谈起的话题。在正式的内容展开之前，让我们先从两个小故事来建立必须的基本概念。
故事1：一日去国家密码管理局开会，行至门口遇到两位散步的老两口盯着门口的牌子在聊天。老爷爷说：“都说很多国家部门人浮于事，这次我算涨见识了，连密码都要有一个专门局来管理”。老奶奶回复说：“嗯，这也算是国家为老百姓着想，否则像咱们这样经常忘记密码的人该多痛苦啊，下次再忘了银行存折的密码就来这个部门寻求帮助好了”。
概念区分1-密码与口令：对于非密码专业的人们，一般说到的密码是指的我们登陆电脑、邮箱、微信、QQ等系统或应用的口令，或者银行卡、网上转账等交易的口令。口令技术本身是一种基本的身份认证技术，用于识别用户的合法性。在复杂的安全协议中，口令经常作为密码算法的安全要素之一进行使用。本文介绍的密码技术是一种基于数学或物理技术的信息变换技术，主要用于保护信息的机密性和完整性。通俗的说，就是防止坏人偷看我们的信息，防止坏人冒充好人进行通信或交易。密码是一门古老的技术，其起源可以追溯到公元前四世纪，在两千多年的发展历程中一直是一种披着神秘面纱的军事技术。随着信息技术的不断进步，在民用和商用领域强大需求的推动下，密码技术逐渐走下神坛，从一种只有极少数人掌握的专用技术变成一种几乎无所不在的信息防护之盾。从我们日常生活中的身份证、银行卡、公交卡、手机、安防摄像头，到工作中的电脑、数字政务系统、数字办公系统、门禁，再到国家的基础设施中的电力、交通等，信息技术所到之处均需要密码技术的保驾护航。
故事2：今年科技周我们在军事博物馆摆了个展位科普抗量子密码技术，一位来参观的科技爱好者盯着我们简陋的科普幻灯片认真思索了片刻之后向我询问到：“潘院士已经修了京沪量子干线，发射了墨子号量子卫星，你们为什么还要做量子密码呢？”
概念区分2-抗量子密码与量子密码：我们通常所说的抗量子密码是指传统密码中可以抵抗量子计算攻击的密码算法，其安全性一般基于数学困难问题设计，目前主要包括格密码、基于编码的密码、多变量密码、基于散列函数的密码、同源密码等类型。而量子密码是指基于量子力学的物理原理设计的密码，其安全性基于不可克隆、测不准原理等物理原理，目前主要包括量子密码交换(QKD)。在应用方面二者最显著的区别是抗量子密码算法可以运行于经典的计算机和通信系统之上，而量子密码需要部署于量子通信和计算系统之上。
量子计算机为什么能够攻破现在的密码？
作为一种攻防对抗型的技术，基本哲学原理决定了不存在绝对安全的密码技术，所有的安全性都有其前提条件。当前应用最广泛的密码算法之一RSA，基于的前提条件是大整数分解问题的困难性。虽然我们读小学的时候已经掌握了因子分解的技能，可以把一个整数拆解为一些素数的乘积，然而当这个整数非常大的时候，这个问题就变得非常复杂。
举个例子，如果一个600位的十进制大整数包含了两个300位左右的素因子，我们要找到这两个素因子，即使动用每秒能算10亿亿次的神威太湖之光巨型计算机也需要计算10亿年的时间才能找到答案。
量子计算机与传统的电子计算机的最大区别在于量子态叠加性质使得单个量子比特可以同时表示0和1两种状态，随着量子比特数的增加其能够表达的数据呈现指数级增加，例如1024个量子比特可以同时表达2^1024个数据。这就使得量子计算天然具备指数级的并行计算能力，可以轻松解决指数级数据空间的搜索问题。因此，基于量子计算的Shor算法可以轻松破解原本非常困难的因子分解问题和离散对数问题，从而攻破目前使用的RSA算法和ElGamal算法。
量子计算机什么时候能够攻破现有的密码？
按照最原始的Shor算法估计，破解2048比特的RSA算法需要2048*3个量子比特的通用量子计算机。根据公开的数据，目前技术进展最顺利的超导量子计算机还停留在20-70个量子比特之间，而且尚未完成纠错和全纠缠等运行Shor算法需要的功能。提升量子比特的数目和量子纠错都带来巨大的技术挑战。根据谷歌最新公布的纠错技术估计，破解2048位的RSA算法需要2千万个物理比特。因此，目前尚无法精确预测量子计算机什么时候能够真正破解RSA。
然而，密码算法的生命周期非常长，例如根据欧盟的标准数据需要50年的保密期，再考虑到制订和推广密码算法标准需要5-10年时间，因此我们需要考虑的是量子计算机60年之后是否可以破解RSA。
三体小说中描述的故事告诉我们，智慧文明在科技的发展过程中会发生爆炸式增长，因此60年内能发生的技术进步是难以精确预测的。这就是欧美等国家决定启动抗量子密码算法标准征集来应对量子计算威胁的原因。
D-Wave 2000Q
IBM Q System One
目前的抗量子密码技术是否已经成熟？
虽然量子计算表面上具备了指数级的计算能力，可以对任何困难问题进行暴力搜索求解，但是最终想要的计算的结果也淹没在指数级的数据之中，必须设计精巧的量子算法才能得到正确的结果。
目前对密码算法产生影响的主要是Shor,Simon和Grover等算法，其中威胁最大的是Shor算法对公钥密码算法的多项式级破解。因此，目前国际上对抗量子密码算法的研究主要集中在公钥密码领域。
在公钥密码领域除了工业界熟悉的RSA和ElGamal两个类型的密码算法之外，还有许多其他的类型，其中有五种类型的公钥密码算法尚未发现有效的量子计算攻击，它们被统一称为后量子密码算法，包括：格密码、基于编码的密码、多变量密码、基于散列的数字签名、同源密码。
这些密码算法中基于编码的密码和基于散列的数字签名已经有40年的研究历史，多变量密码已经发展了30多年，格密码和同源密码已经发展了20多年。这些密码算法的设计与分析理论已经取得了许多成果，在量子计算复杂性分析方面尚未完全成熟，经典安全性和效率已经接近实用化需求。在国际标准化需求的大力推动下有望在未来3-5年内取得较大发展，最终形成实用化的密码算法标准。
在抗量子密码技术方面我们与国际先进水平相差有多大？
在抗量子密码领域欧美起步早，做出了大量原创性成果，我国在该领域起步较晚，缺乏原创性成果，这些差距很难用精确的距离来描述。需要指出的是，缺乏原创性成果并不会从根本上阻碍我国推动抗量子密码算法的标准化和产业应用，正如我国在移动通信领域的原创性成果缺乏并未阻碍华为公司在5G应用方面的国际领先地位。
目前，在抗量子密码算法标准制订和产业推广方面美国NIST走在最前面，美国NIST于2009年发布了后量子密码算法的综述，2012年正式启动后量子密码算法标准项目，2016年发布后量子密码算法征集公告，评估工作分为3轮进行，每轮18个月左右，预计2024年之前完成。
在征集过程中，NIST共收到来自全球的82份提案，经过审查有69个算法符合要求进入第一轮评估，2019年初发布了进入第二轮评估的26个算法。这些候选算法来自全球各国，其中欧洲是最大的来源地，欧盟的PQCRYTO项目是该领域的旗舰型项目，第一轮的69个候选算法有22个来自该项目组，第二轮的26个有15个来自该项目。
欧美之间的合作非常密切，所以很多算法是来自欧美公司、科研机构、高校联合设计的。中国团队是首次参加这类活动，短时间内无法完成设计、分析、实现的全部工作，因此最终只有3个团队提交了算法，只有1个算法进入了第二轮评估。
美国NIST后量子项目
欧盟ETSI量子安全计划
量子计算会对整个密码领域带来什么样的影响？
从公元前四世纪到二战的机械密码，到电子计算机兴起之后的现代密码再到目前量子计算技术推动的抗量子密码，密码学的发展一直与整个人类的科技进步密切相关。从密码学科发展的角度来看，量子计算是图灵炸弹之后推动密码学发展的又一次里程碑式的事件。
虽然通用大规模量子计算机的研制还困难重重，但是量子计算对基础复杂性理论带来的革命性变化足以促使密码算法设计与分析理论迎来一次大的飞跃。从基础的计算复杂性理论到形式化的安全性证明理论都将受到量子计算的影响，密码学家需要在量子计算环境下重新构建密码学的大厦。
作者：路献辉 / 中国科学院信息工程研究所
来源：中科院信工所供稿
http://weixin.100md.com
返回 中国科学院北京分院 返回首页 返回百拇医药