-
袁岚峰:量子保密通信好与坏?别把“李鬼”当“李逵”!
关键字: 量子通信量子保密量子纠缠算法密码术金融安全体系RSA由于密码算法的使用必须得到国家和军队某委员会的批准,因此我们向他们提出了鉴定申请,结果却被驳回。
若对此不服,给他们说:你们凭什么认为我这个算法不够安全,有本事你们破解试试?
他们的回答是:我们没本事破解,但不代表敌人没本事破解,你给我证明下敌人无法破解。
然后我就懵逼了,最后只能继续使用上级配发的加密算法,这样即使出了问题也没我的责任。
加密算法就是这样,你很难证明它安全,也很难证明它不安全。
加密算法的强度依赖的是数学难题的难度,即使是大家公认的极难解决的数学难题,也备不住躲在阴暗角落的某个天才数学家已经破解,而数学问题的破解就如同窗户纸一样,一捅破就全完了。
很可能敌方已经据此设计了完美的破解方法,这种可能虽然可能性极小,但终归无法杜绝!因此,在传递绝密信息时,谁都不敢拍胸脯保证,只能去赌概率,这是令人非常非常痛苦的!”
现在,我们的主角出场了。量子密码术,改变了密码攻防的基本格局。
我就是美貌与智慧并重,英雄与侠义的化身:唐伯虎
不通过信使,让通信双方直接分享密钥,这意味着什么呢?意味着原本只具有理论意义的一次性便笺保密法起死回生了,变成一个可以实用的方法了!这种保密方法,封死了通过数学破解密码的可能性!
因此,“奥卡姆剃刀”在讲完上面那个故事之后,结论是:
“而量子通信解决了这个问题,它从理论和实践上都证明了不可破解,令人把悬着的心放回肚里,这是上千年密码术的重大突破,功莫大焉!”
回到魔王与公主的比喻,现在公主又变成了满世界乱跳,而且这次可以放心大胆地这么做了!魔王彻底失去了追上公主的希望,无论他的计算能力再强都无济于事。因为,这压根就不是计算的事儿。
魔王:算你狠,我举白旗还不行吗?我看看还有没有其他的办法……
量子密码术的出现,并不意味着信息安全的问题已经完全解决了。最明显的,策反情报人员这一招就仍然存在。我的朋友、美国新墨西哥大学数学与统计系助理教授黄宏年博士认为,现在网络安全体系最大的弱点并不在于密码,在这方面增强不能解决主要问题。现在的操作系统过于复杂,许多地方用溢出攻击等粗浅的手段就可以攻破。
我的理解是,信息安全问题是个很长的链条,量子密码术只是保证了其中一个环节的安全,即密钥分享和密文传送这一环,敌方仍然可以去攻击其他的环节。但是,能保证一个环节的安全已经是相当重大的进步了,至少你泄密时可以排除这方面的问题,集中排查其他方面。正如中国工程院院士邬江兴所说:中国的网络安全几乎是“裸奔”,量子密码术给它穿上了一条内裤。
如果你问我,量子密码术有什么缺点?最明显的,就是慢。由于密钥是通过单光子的发射和接收产生的,条件十分苛刻,所以生成密钥的速度目前都是在每秒多少k的量级。在一次性便笺加密中,明文跟密钥一样长,所以传输信息的速度就等于生成密钥的速度。每秒不到一兆的速度就像回到了拨号上网用“猫”的时代,只能传送少量最重要的文本。如果用AES、DES之类不等长加密的对称密码算法(用一段密钥加密一个长得多的文件),速度倒是上去了,但又有可能被数学破解了。此外,量子密码术的成本应该也不低,虽然我没有具体数据。
除了慢和贵之外,作为一个新技术,量子密码术的问题想必还有许多。不过我既不是工程专家,也没有打算自学成一个工程专家(估计学也学不成),我的兴趣主要在理论方面,因此对我来说,最重要的是:量子密码术的安全性是能在原理层面证明的,而目前其他的密码体系都不能。这就是量子密码术无可替代的价值。
由此还可以引出一点值得强调的:量子密码术从来没有说要完全代替传统的密码术。作为一个新生事物,量子密码术不是一上来就宣布“这个鱼塘我承包了”(正经的科技工作者不会这样说话的),而是“我有这样一个能力,可能对保密有用,欢迎大家一块来讨论,看看什么地方能用上”。你可以列举一千个不适合用量子密码术的地方,这都没问题,但只要有一个地方适合用量子密码术,就算是进步了。用了量子密码术,也不意味着排斥经典密码术,双方完全可以结合使用,取长补短。
用不用量子密码术的选择权,当然在于用户。如果你对保密的要求高于一切,那么量子密码术是你的好选择。如果你没有高价值的秘密需要保护,那有什么理由像某些企业宣传的那样,花很高的成本去追逐“量子小镇”之类的噱头呢?
量子计算机对这幅图景有什么影响?
基本的回答是:非本质的影响。你看,我前面说了那么多,压根就没提到“量子计算机”这个词嘛!
传统计算机的基本单元是比特(bit),指的是一个体系有且仅有两个可能的状态,往往用0和1来表示。而量子计算机的基本单元是量子比特(quantum bit,缩写为qubit或qbit),指的是一个体系可以处于两个状态|0>和|1>以及它们的任何叠加态a|0> + b|1>。这里的|>叫做狄拉克符号,在其中填入数字或文字,就可以表示量子状态。
做一个比喻:经典比特是“开关”,只有开和关两个状态,而量子比特是“旋钮”,有无穷多个状态。因此,量子计算机可以做到所有的经典计算机可以做的事,还有可能做到一些经典计算机做不了的事。
这里需要强调一点,常有文章把量子计算机描写成无所不能,都快成神了,这是重大的误解。量子计算机仍然是需要算法的,而只对于某些特定的问题,人们才设计出了超越经典计算机的算法。因此,量子计算机不是因为普遍性的算得快,所以干什么都比经典计算机强,而是针对某些特定的问题算得快,只在这些问题上比经典计算机强。
到目前为止,人类找到的这样的问题并不是很多。但在这为数不多的能够让量子计算机大展拳脚的问题中,其中一个恰恰就是——因数分解。
前面说对因数分解,迄今还没有能在多项式时间内分解的算法,但那指的是经典计算机。1994年,肖尔(Peter Shor)发明了一种量子算法,把因数分解的计算量减少到了多项式级别。这是一个革命性的进步!分解300位和5000位的数字,量子算法会把所需时间从15万年减到不足1秒钟,从50亿年减到2分钟!在理论上,RSA已经被量子计算机攻克了!
不过这只是理论上,因为真正能用的量子计算机还没有造出来。到目前为止,在实验上分解的最大的数是291,311 = 523 × 557,是由中国科学技术大学的杜江峰院士和彭新华教授等人在2017年实现的。这离分解上千位的密码还远着呢。
量子计算机是当前全世界的科研热门。许多研究机构和企业在激烈地竞争,纷纷放出风来要在近年内实现“量子制霸”,实际意思就是前面说的,对于某些问题超越现有的经典计算机。有发展的眼光的人,都会关注这方面的消息。
显然,量子计算的进步,增加了人们对量子密码术的需求。但是,如果没有量子因数分解算法,甚至压根没有量子计算机的概念,量子密码术是不是就没有价值了呢?
当然不是!
量子密码术的基本价值来自它的完美安全性,这是其他任何密码体系都没有做到的。无论计算技术有没有进步,这个价值始终存在。量子因数分解或者任何其他的计算技术进步,只是起到锦上添花或者说“补一刀”的作用,对这个基本图景并没有影响。
徐令予老师在文章中说:
“为什么要开发量子保密通信技术?因为从理论上讲,如果未来量子计算机建成,如果建成的量子计算机有足够的Qbit和足够的稳定性,那么今天密码系统中的公钥密码RSA有可能被破解。”
根据以上的分析,我们知道这个理解是错误的。实际上,最早的量子密码术协议BB84是在1984年发明的,而量子因数分解算法是在10年之后的1994年发明的。难道在1994年之前,人们会觉得BB84协议没有意义吗?
《后量子RSA》说了些什么?
徐老师在文章中对这篇论文的介绍是:
“数月前出现这样一篇论文:‘后量子时代的RSA’[2],该文发表后被多家相关杂志转载和引用,这些文章给出的共同结论是:目前使用的非对称性密码RSA不会因为量子计算机的出现而消亡。”
如前所述,经过饶有兴味的研读之后,我大致理解了此文的框架。此文的四位作者Daniel J. Bernstein、Nadia Heninger、Paul Lou、Luke Valenta(以下简称为BHLV)表现出了很强的数学功力和创意,令我十分敬佩。那么,BHLV实际说了些什么呢?
他们说的是:目前版本的RSA在量子算法面前不堪一击,他们提出了一种改进的版本,在某种意义上可以对抗已知的量子算法。
在什么意义上呢?合法用户加密解密也是需要计算量的,而肖尔的量子算法强大到了这种程度:破解RSA跟合法用户解密几乎一样快,具体而言,计算量都大约是n的平方(n是要分解的那个合数的二进制位数)。对RSA密码体系来说,这简直是输得连底裤都快没有了。
传统的RSA是把两个质数相乘。BHLV提出,通过一系列数学技巧(快速的乘法以及随机生成质数的方法等等),可以把加密解密的计算量都控制在正比于n,然后把非常多的质数相乘,使得n非常大,就可以让破解的计算量显著地超过加密解密的计算量。简而言之,就是把加密解密的计算量(n)降低到了破解的计算量(n的平方)之下。他们把这种改进版RSA称为后量子RSA。
呃……原来我们说的是,破解的计算量指数增长才算安全。现在标准降得这么低,破解的计算量比加密解密增长得快就算安全,——这几乎是可以定义的最低级别的安全性了。
原文对此说得很清楚:
“Post-quantum RSA does not qualify as secure under old-fashioned security definitions requiring asymptotic security against polynomial-time adversaries. However, post-quantum RSA does appear to provide a reasonable level of concrete security.”
【翻译:在老派的安全性定义下,即面对多项式时间敌手时的渐近安全性的定义下,后量子RSA没有达到安全的标准。然而,后量子RSA看起来确实提供了一个合理水平的具体的安全性。】”
后面还有一个更具体的解释:
“Note that, for theoretical purposes, it is possible that (1) there are no public-key encryption systems secure against polynomial-time quantum adversaries but (2) there are public-key encryption systems secure against, e.g., essentially-linear-time quantum adversaries. Post-quantum RSA is a candidate for the second category.”
【翻译:请注意,对于理论的目的,以下两点是有可能的:(1) 没有任何公钥密码体系在多项式时间的量子敌手的面前是安全的;但是(2)有公钥密码体系在比如说基本上是线性时间的量子敌手的面前是安全的。后量子RSA是第二类的一个候选者。】”
如果你看不懂,我来简单解释一下。给定问题的规模n,如果你允许量子计算机运行对n的任意高阶多项式的时间,那么大概所有的公钥密码体系都会被击败。而如果你只允许量子计算机运行n的时间,那么就可能有公钥密码体系扛得住。后量子RSA是后一类中的一个候选者。为什么只说是候选者,而不是直接就是呢?因为你无法保证人们不发展出新的量子算法甚至是经典算法,在n的时间内破解后量子RSA。
从破解跟解密一样快,改进到加密解密比破解快,这个进步好比赢回了一条底裤。或者这么说:一个低手跟一个高手下围棋,从分先到让先,到倒贴目,到让二子,到让三子,一路被打得降级,现在提高了棋艺,在让三子的情况下赢了一盘,回到了让二子。这当然可喜可贺,不过如果把这理解成他可以跟高手分庭抗礼,甚至超过了高手,那就大错特错了。
用网络语言说:BHLV对RSA使用挽尊卡,为RSA挽回了尊严!效果:密码术经验+5。
对于后量子RSA的价值,原文有一个生动的比喻:
“RSA has enough flexibility to survive the advent of quantum computers — beaten, bruised, and limping, perhaps, but not dead.”
【翻译:RSA有足够的柔韧性来挺过量子计算机的来临——被打击,被挫伤,一瘸一拐地走,都有可能,但不是死亡。】”
再来看看BHLV用什么样具体的例子演示后量子RSA。目前常用的RSA是用两个质数相乘,每个质数用二进制表示是1024位或2048位。他们生成了2的31次方(2,147,483,648,即大约21亿)个质数,每个质数用二进制表示有2的12次方(即4096)位。这21亿个质数乘起来,得到了2的43次方(8,796,093,022,208,即大约8.8万亿)长度的一个密钥,也就是1 T字节长度的一个数字。想想看1 T容量足够放下多少部电影,现在居然只是用来存放一个数字!
处理如此巨大的数字,加密解密当然也很不容易。生成21亿个随机的质数,花费了一个1400核的机群4个月的时间。看起来这是最耗时间的一步,后边的质数相乘、加密、解密等步骤,花费的时间都是以天计,而不是以月计的。徐老师的文章说“费时一共为五天”,大概是只看了其中的一步。
根据BHLV的估算,肖尔的量子算法分解这个1 T字节长度的数字,需要的量子比特操作数是2的100次方。2的43次方平方就得到2的86次方了,再考虑到其他一些细节,2的100次方是可以理解的。徐老师在这里似乎出现了一个硬伤,把量子比特操作的数目看成了量子比特的数目,然后以此为根据做了一番讨论:
“假设量子计算机已经建成,再假设量子计算机的量子位(Qbit)可以无限扩展,进一步假设该量子计算机的运行成本与现在通用电子计算机的成本可以相比,用这样一台超级想象出来的量子计算机来破解长度为Terabyte(太字节,等于1024 GB)的RSA非对称密钥需要量子计算机的Qbit为2^100(2的100次方)。
2^100是一个什么概念?这个数大于我们星球上所有生物细胞的总数!而今天为了建成两位数Qbit的量子计算机,专家们已经弄得焦头烂额,多年来一筹莫展。当然使用长度为Terabyte的RSA公钥确实也有点离谱,但论文作者在今日的电子计算机上产生了这样的公钥,并用它来加密和解密,费时一共为五天。按目前的技术水平,长度为Terabyte的RSA公钥虽然并不实用,至少还是可以实现的,但是还在纸上的量子计算机即使明天就建成,要破解这样的RSA公钥也无一线希望。”
其实原文是“2100 qubit operations”,不是“2100 qubits”。这个错误的性质,相当于认为一个量子比特只能操作一次,然后就报废了。这当然是不对的。因此,拿2的100次方去跟细胞的总数相比,跟专家想建成多少位的量子计算机相比,都对错号了。
- 原标题:量子保密通信好与坏?别把“李鬼”当“李逵”! 本文仅代表作者个人观点。
- 责任编辑:武守哲
-
重庆通报“燃气费异常”:燃气集团党委书记被免职 评论 396“伊以都在降调”,国对国直接打击结束? 评论 112以色列“有限复仇”:选在了伊朗核计划中心 评论 356以色列“报复”开始:伊朗多地传出爆炸声 评论 5895.3%,一季度“开门红”能转化为“全年红”吗? 评论 158最新闻 Hot
-
以色列“有限复仇”:选在了伊朗核计划中心
-
5.3%,一季度“开门红”能转化为“全年红”吗?
-
两大家族开撕?菲第一夫人公开指责副总统:不道歉,这事就没完
-
美国一票否决,多方回应
-
李迅雷:发展服务业与做强制造业不矛盾,可参照德国、日本
-
欧盟跟着泼脏水:中国不仅坐山观虎斗,还下场了
-
美国积极促成沙以和好,“可以限制中国”
-
“这是拜登政府首次挑起加税,中方反制不会手软”
-
“预计今年将推出一揽子政策,旨在解决问题而非刺激经济”
-
美以私下做了个交易?美方紧急撇清
-
特朗普变口风:乌克兰的存亡对美国很重要,欧洲麻利点
-
“未来几年,这是各方关注中国市场的一个重要指标”
-
应韩企要求,美国拟恢复一项涉华关税
-
菲律宾“倒打一耙”
-
“以色列精心策划俩月,但严重低估了伊朗反应”
-
“你们愿意中国提前登月?不愿意?那就打钱”
-