用超级计算机来破解2048位经典加密需要花10亿年

投稿人/来源:返朴微信公众号 | 2019-04-15 14:12:06 |

用超级计算机来破解2048位经典加密需要花10亿年。如果大家还不放心,我们可以用100万位密钥,其传送只需几秒。

如果说20世纪是第一次信息革命的时代,那么21世纪的今天,我们将面临第二次信息革命。在过去的半个世纪里,随着互联网的兴起和普及,信息传播速度、传播广度及传播量都得到了不可思议的发展。互联网上每天产生巨量的数据,从中提取有用的信息则需要无比强大的算力。即便如谷歌这样的科技巨头,在面对这些数据时,也只能望而兴叹。更令人悲观的是,算力的发展速度,似乎远不及数据增长的速度。随着未来5G网络的推广,物联网的兴起,信息交互的复杂度更是难以想象。量子计算在这种形势下被寄予厚望,也就在情理之中了。相比破解RSA密码的Shor算法,更为强大的计算能力,才是人们真正追求的圣杯。

今天,我们日常通过手机、电脑、穿戴设备进行频繁的沟通,我们对通信太习以为常以至于几乎忘记了通信的本来面目。本文试图从最原始的通信开始,穿过那些文字、图片、视频,看看通信在背后究竟是干什么的、怎么干的,也试图引导有兴趣的读者思考一下未来的通信应该是什么样子的。以现代通信之庞杂,作为一份极简的科普短文是远不够介绍其全貌的,甚至连管窥也未必做得到。其中的粗疏谬误之处,还望读者不吝指教。

什么是信息?

信息,英文“Information”,在Wikipedia上的定义是“Informationistheresolutionofuncertainty;itisthatwhichanswersthequestionof“whatanentityis”andisthusthatwhichspecifiesthenatureofthatentity,aswellastheessentialityofitsproperties。Informationisassociatedwithdataandknowledge,asdataismeaningfulinformationandrepresentsthevaluesattributedtoparameters,andknowledgesignifiesunderstandingofanabstractorconcreteconcept。”翻译过来是:信息是对不确定性的解析。它回答的是“某个事物(实体)是什么”,也就是关于这个事物属性的说明,以及其属性的本质。信息与数据和知识关联,数据是信息有意义的表达,代表参数赋予的值;而知识表示对抽象或具体概念的理解。再来看看百度百科:信息,指音讯、消息、通讯系统传输和处理的对象,泛指人类社会传播的一切内容。一对比就发现二者描述的深度不一样。

想象这么一个场景,B君去了一趟沙漠,回来之后告诉A君说:我在沙漠里发现一种奇怪的花,白天看是枯草,晚上就开了。这句话传递了什么信息呢?显然他描述了一种沙漠里才有的花,并描述了这种花的属性(白天枯晚上开)。接下来有两种情况:1。如果A君没去过沙漠,没见过这种花,那么B君告诉A君这些信息之后,A君就得到了这些信息,假如他相信B君,那A君还可以基于这些信息建立一定的新知识;2。如果A君去过沙漠,早就见过这些花,了解这种花,那B君告诉他这些还有用吗?显然没有,对A来说这是已知的。因此,B的这句话对A来说包含的信息量就不大了。我们再从另一个角度来看,假如A君是研究这种花的,B君的描述对A的研究而言,就是一个“样本”,或者说“数据”,A如果同时还收集到了更多目击者的类似描述,那么A就可以更加确定这种花的存在及其属性。换句话说,B君的描述,增加了关于花的“知识”的可信度。

从上面这个虚拟的场景我们可以看出,信息是与“观察者”密切相关的,同样的“数据”,对不同的观察者而言得到的信息量是不同的。类似的(有相关性的)“数据”可以增加信息的可信度。草原上的猎豹攻击鹿群时,第一头意识到猎豹即将攻击的鹿迅速跃起,这个动作向其他鹿传递了“有危险”这个信息,当越来越多的鹿意识到这一点并开始奔跑,这个信息就变得很确定了:猎豹攻击了,赶紧逃命!假如有一只猴子在此时好心告诉鹿群有危险,鹿群还会搭理它吗?回答它的一定是那句大俗话:“这不废话吗!”由此可见,信息有时效性,在事件尚未发生之前预见到事件发生,才包含有用信息,对已经发生的事件做预测是没有信息量的。说得更哲学一点,就回到了Wikipedia上的定义:信息是对不确定性的解析。

什么是通信?

有了信息的概念,那通信顾名思义就是传递信息了。B君已知了沙漠中的花而A君不知道,那么B告诉A这一信息,A就获得了这一信息。这个过程,B将一定的信息传递给了A。通信在生命活动中是如此常见,以至于它几乎就是生命的终极奥义。生命最核心的部分:基因,就是这样通过生命形式一代代传递下去。动物、植物,他们通过发出声音、分泌激素、做出姿势、发光、变色……各种手段,穷尽所能,相互之间传递信息,代代蕃息。可以说,生命,就是一股巨大的信息流。

人的出现,给了通信更多的含义。智人的进化让他们可以用更为复杂的发音和手势来交换更复杂的信息,这种复杂的通信系统——语言,是人类进化史上最伟大的发明之一。有了语言,智人之间可以进行更高级、更大规模的合作,从而彻底击败那些身体素质远胜的尼安德特人。智人进一步进化,又发明了文字。文字不仅能表达更为抽象的信息,还能记录在介质上,可以传递更远的距离,可以传承得更久远。换句话说,文字使得信息作用的时空范围大大增加了。今天的我们能够了解到几千年前的古人是如何生活的,不就是依靠那些古老的文字记载吗?

随着社会活动的增加,文化的进步,人类又进一步发明了印刷术,大大增加了知识的传播速度和范围。直到今天,文字和印刷为基础的书籍报刊,仍然是人们交换信息和知识的重要媒介。

到了近代,人类发现了电和磁,并发现了其传递信息的能力,从此打开了一个全新的时代。从电报到电话,到互联网,先民们几代人交换的信息量,曾不如今日的一刹那。

以上对人类的通信发展史做了一个极简的回顾。下面我们来看看通信的几个要素。第一,通信一定要有施和受两方,这是显而易见的。现代保密通信中我们往往用Alice和Bob来表示,与上文中的A君和B君是一个意思。第二,通信一定要有对应的“语言”。这里的语言是广义的,不同的通信双方会采用不同的语言,猴子会发出不同的叫声,蚂蚁会释放信息素,熊猫会用尿尿……我们人,当然就是用字面意思的语言,即便这样,不同民族的语言也是千差万别的。文字则是语言的一种映射关系,有时候甚至是语言的进一步抽象。第三,通信一定要有媒介。比如说说话,用的媒介是声音;手势,用的媒介是光。如果没有光,即便对方近在咫尺,任我如何比划,对方也是无法获得信息的。第四,通信还要有畅通的信道。比如我发出了声音,由于空气的存在,这个声音可以传到不远处另一个人的耳朵,引起耳膜振动。我做出手势,由于光的反射,远处的其他人可以看见这个视觉图像。最后一点,存储,这个未必是通信所必要的,但是可以极大地提高信息传播的时空有效性。

什么是保密通信?

当我们希望接受信息的对象在限定范围内时,我们就需要考虑采用保密手段。保密通信的发展,其实与通信的发展是相终始的。事实上,任何通信都是具有保密性的。举例来说,我在广场上说了一句话,周围的人或许能听到,但远在千里之外的曼哈顿大街上行走的行人一定是不知道的。我用中文说一句“我爱你”,完全不懂中文的爪哇人一定是一头雾水。因此,所谓的保密通信,主要还是指如何屏蔽掉“有可能接收到这个信息,但我不希望对方接受到”的受信群体。在保密通信中我们往往用自带邪恶属性的“Eve”来表示。

有了上面总结的通信几大要素之后,如何做好保密通信就有方法可循了。只要切断任一要素,就可以让Eve无法获取信息。第一要素,施信和受信对象,那就把Eve排除在受信方以外就得了。假如我们知道Eve现在在非洲度假,那我们就可以敞开门聊天了。第二要素——语言,我们找一种Eve完全听不懂的语言聊天,他一定摸不着头脑。第三,媒介,用一种Eve无法感知而Bob能够感知的方法通信就可以了。很显然我们完全不能明白两只蚂蚁触须碰碰交换的是什么信息。第四,信道,如果Alice和Bob在一个隔绝声音的房间里聊天,Eve又怎么能听见呢?

以上这些手段,在保密通信中均有应用。特别随着军事的发展,保密方法可谓无所不用其极。有一部很有名的电影《风语者》,讲述的是二战时期海军军官保护纳瓦霍族密码员的故事。为什么要用纳瓦霍人做密码员呢?就是因为他们的语言,外族人完全听不懂。京剧《智取威虎山》中,土匪用黑话来做“接头暗号”:一方说“天王盖地虎”,对方答“宝塔镇河妖”,于是双方就知道是自己人了,这也是保密通信中常用的手段。

上面的例子还体现了保密通信与常规通信一个新增的要素,那就是身份认证。由于保密通信是要排除不希望的通信对象Eve的,但在实际通讯中,Alice与Bob往往互相并不太了解。举个例子,我军打算凌晨三点向某高地发起总攻,指挥部派出一名侦察员,往甲阵地传递这个命令。甲阵地的指战员见到这位侦察员之后,他能随意相信这位侦察员吗?或许他是认识总指挥部的上级首长的,但他很可能并不认识这个小兵。为此,作为精明的指战员,一定是要对这个传递命令的小兵做一番身份确认的。古人发明了一种很精巧的身份确认方法:对虎符。一个虎符剖分两半,一半在君,一半在将。君要使将,则命使者携自己的一半前往将之所在,虎符一对,纹理相配,则受君命。可见身份认证的问题在很早就被意识到并想出一定的解决方案了。我们知道技术都是“应运而生”的——有了应用场景,才会催生出相应的技术方案。身份认证,是保密通讯中一个相伴的题目。这里补充说点题外话,一项技术的发展推广,一定要首先思考其应用场景,也就是这项技术的生长土壤。如果有人发明一项在火星吹肥皂泡的技术,我相信当前的地球人都只会把它当做一个趣闻的,如果一位有钱的绅士一定要将这项技术做“成果转化”,我相信这个趣闻一定会变成一个更有意思的趣闻。

让我们回到通信的话题上来。现代信息技术的发展,特别是互联网的诞生和病毒式的扩散发展,为通信出了很多新的题目。前面提到的虎符技术,在现代战争中显然不适用。叙利亚战争中,特朗普总统可以直接指挥前线作战,甚至指挥一位士兵。而且,总统先生可能会频繁地发出新的命令,如果用虎符,前线将士恐怕携带一屋子的虎符也不够用。信息的灵活多变、信息量的大增、通信的网络化、并行化、实时性、安全性,是当前通信发展面临的场景。

对信息进行加密之后传递,收信方按照约定方法,采用特定密钥来解密,从而得到信息明文,这是保密通信最基本的方式。由于密钥只有授信的少数人(Bob们)持有,那些Eves们,即便截获了信件,苦于没有密钥,也不知解密方法,看到的将是一堆乱码。即便这样,在这个过程中,要做好的事情仍然是很多的,比如如何保管密钥,如何传递密文,如何保证信道畅通等等。战争中的双方情报机构,往往为保管/窃取密钥,寻找/破译加密/解密算法(破解密钥),传递/截取密文……做无数的攻守来回,令人胆战心惊,成为电影故事最常见的题材之一。在强大的利益驱使下(战争胜负、商业成败),保密从来都不是一件容易的事。

互联网的出现更是为通信安全提出了新的挑战。无数的终端设备接入其中,终端背后无数的人在交换信息,其复杂程度超越任何其他人造系统。利用得当,信息可以瞬息传遍全球,利用失当,明星隐私也可以瞬间传遍网络。互联网的安全,是伴随其终始的恒久话题。道高一尺,魔高一丈。

传统的对称加密系统,尽管安全性较高,但完全不能适应互联网的发展。所谓对称加密系统,是指一方采用特定算法、特定密钥,对信息进行加密;对方采用相同算法、相同密钥,对信息进行解密。双方一旦握手协商好算法,并各自持有一份密钥,就可以放心通信了。不过由于通信内容往往包含重复信息,加上密文随机性不足,一份密码多次使用后,即便Eve不知道加密算法,也可以通过密文不同部分之间的相关性来推测出原文。比如早期用得较多的字典替换法,随着截获密文的累积,破译者就可以从那些经常重复出现的词语(信件往来中的“阁下”、“致礼”等词汇)中找到对应关系。即便是被奉为传奇的“Enigma”机,在大量应用,大量密文被截获,乃至Enigma机被复制之后,终于被数学家从密码头上的六个加密字母中找到了破解契机。

对称加密有一个基本条件,就是通信双方需要至少一次“接触”,也就是握手环节。在这个环节中,双方建立互信,约定算法,交换密钥。到了互联网时代,这样的加密方式显然不适用。为什么呢?互联网的特点是网状结构,有无数的终端,而且这些终端时而接入,时而断开,不断有新的节点加入,旧的节点撤销。总之一句话:复杂,多变。在这样的体系中,要想建立点对点的通讯是臃肿笨拙的,而且成本高昂。一个终端与另一个终端可能相隔万里,通信双方可能老死不会相见。那他们之间如何建立可靠通信呢?在这种应用场景下,一种新的、绝妙的通信方式——公钥系统,或者说非对称加密系统提供了解决方案。

顾名思义,非对称加密系统中加密方和解密方是不对称的,无论是算法还是密钥。Bob想从Alice那里收取信息,他首先用公钥算法生产一对密钥——公钥和私钥,并通过网络向外发出公钥,自己仔细保管好私钥,而算法则是公开的,任何具备相关知识的人,就可以获取算法和公钥,当然,这其中一定包含Alice和Eve。Alice拿到公钥之后,就可以与Bob通信了:她用公钥加密信息,然后发布到网络上,Bob(当然也包括Eve)接收到信息之后,用私钥轻易地解密并获取了明文信息。而Eve呢?虽然他可以轻易地获取密文,他也可以轻易地获取密钥——公钥,但很可惜,用公钥加密的信息,用公钥不能解开。反过来,用私钥加密的信息,也只能用公钥才能解开。这一特点,正好完美解决了身份认证的环节,也就是实现所谓数字签名。

前面已经讲到过身份认证的重要性,其作用不下于加密本身。试想,如果Alice连通信的对方是Bob还是Eve都分不清,怎么能保证通信的安全性?要知道伪装是截获情报最重要的手段之一。除此之外,要想保证通信的安全性,还要考虑信息是否被篡改。假如我送的信半路上被人悄悄加几句话,很容易就被误导了。为了防止这种事情发生,在通信中常用的办法就是签名,盖戳,并在信封上加漆印,这样的情节在很多影视剧中相信大家都见过。即便这样,伪造笔迹,伪造签名的事情也难免。小李子和“阿甘“演过一部猫捉老鼠的电影《逍遥法外》,小李子就是靠伪造各种支票骗过了大批银行职员(多为女性),被抓后成为FBI的假支票鉴定专家。

互联网上身份认证怎么做呢?最常用的办法是数字签名,这是公钥密码系统中非常重要的一环。数字签名不仅能进行身份认证,还可以对所传递的信息做校验,保证信息的完整性和不可篡改性。具体的做法是,发信方用一个哈希函数(比如MD5)对信息内容生成一个摘要,然后用私钥加密这个摘要,与加密后的信息(用对方公钥)一同传给对方。对方用公钥解开摘要,用自己的私钥解开信息,并用相同的哈希函数生成信息摘要,然后与发送过来的摘要做对比,相同则说明信息没被篡改过且是完整的。由于公钥私钥一定是成对的,因此上述过程就完成了身份验证、信息真实性和完整性验证。

绝大多数用户在使用互联网的时候,并没有意识到公钥系统在保护着我们,但实际上它无处不在。不知道大家注意到没有,现在的网页已经很少有http开头的(国内很多网站除外),都是https开头了,google浏览器甚至已经不再支持http网页浏览。这里多了个s,就表明网站内容经过加密了,这样你就可以放心在网站上输入个人信息、用户名密码而不用担心被人盗取。其中用到的加密技术,正是公钥密码。尽管HTTPS并非绝对安全,掌握根证书的机构、掌握加密算法的组织同样可以进行中间人形式的攻击,但HTTPS仍是现行架构下最安全的解决方案。我们用支付宝、微信、银行网银做的每笔交易,背后都是公钥系统在保驾护航。

二十世纪末诞生了两个伟大的思想:利用量子力学原理来进行保密通信——量子通信,和利用量子力学原理来进行计算。这两类基于量子力学的技术,可以统归于量子信息技术,代表着未来信息处理技术的发展方向。尽管都是用到量子力学原理,不过二者是有很大差别的,并非相近相类技术。我经常被人问及量子通信的专业话题,弄得我很尴尬——其实我对量子通信了解并不深。我相信同样地有很多量子通信专家会被问及量子计算的专业话题。因为是接着公钥密码系统的话题,所以这里先讲讲量子计算。

上世纪90年代一个数学家彼得·肖,发现一种基于量子逻辑的算法——Shor算法,这种算法最吸引人的地方是,它能够将质因数分解问题的复杂度,从指数难度降低到近多项式难度。熟悉计算机科学的人一定知道,一个多项式复杂度的问题,对目前的计算机而言,就是“可解”的。换句话说,问题的复杂度增加,并不会带来所需计算资源的灾难性增加。这种问题称之为P问题。其反面就是NP问题:不确定多项式问题。这里的不确定,意味着在当前的数学水平下无法得到多项式复杂度的算法。在数学界,有很多人为证明“NP=P?”这个问题奋战争论很多年,到目前没有结论,甚至少有线索。普遍的观点是接受NP≠P的。

质因数分解问题在经典计算中是一个NP问题,到目前为止没有低于指数难度的算法。互联网上最常用的公钥密码——RSA密码,就是基于质因数难分解而易验证的原理。RSA密码自问世以来,有记录的破解有三次,分别是1999年的RSA-155、2002年的RSA-158及2009年的RSA-768,其中RSA-768用了768位(二进制位)密码。目前流行的RSA-1024从未有被破解过,考虑到768已经比较接近1024,且计算机发展速度飞快,已有人建议采用RSA-2048。有人评估过,在经典计算机上破解RSA-2048需要10亿年(以超算能力进行估计,这个数字会随着技术进步而不断缩小。不过这并不重要,即便将摩尔定律无限外延,10亿年要缩短到年也需要60年,这还是在假定RSA密码在这段时间里原地踏步的情况)。

RSA-2048密码破解所需时间之估算

为了破解一个以RSA密码为基础的证书(比如由DigiCert所提供的),我们必须对组成RSA模数的一个超级大数做质数分解。当所用电脑达到了证书相关的RAS模数分解的平均时间[换句话说,它(分解)可能发生在第1年,也可能发生在第6万亿年,平均时间可能是尝试所有可能性所需总时间的一半],我们就认为这个证书被“破解”了。2009年12月,Lenstra等人声称破解了一个768比特的RSA模数(见:http://eprint.iacr.org/2010/006.pdf)——这是一个232位(十进制)的数,是当时(很可能到现在也是)分解的最大的一般整数。

分解一个大数最有效的方法——也是上面的破解纪录所用的方法——是通过数字场筛选,这个方法比暴力破解(试遍所有组合)要快得多,所以暴力破解将耗费与之相比更多的时间。Lenstra小组估算了一下,破解一个1024位(二进制,后面如无说明均指二进制数)的RSA模数要比他们破解768位数困难1000倍。也就是说,在相同的硬件设备和条件下,破解耗费的时间要长1000倍。他们同时也估计了一下,如果将处理能力归一化到当时的一台标准台式电脑配置(含一个2.2GHzAMD羿龙处理器,具有2G内存),那么他们实现的纪录需时为1500年。所以换句话说,按照Lenstra等人的估计,破解1024位RSA密码在普通台式机上需要150万年。目前的超级计算机的计算能力是普通台式机的百万倍以上。即使用超级计算机解密也需花一年左右时间。

DigiCert基于的标准是采用2048位密码的SSL安全证书。这比Lenstra等人所尝试破解过的任何密码都要强大得多。事实上,它需要破解一个617位(十进制)的数。RSA实验室声称(见:http://www.rsa.com/rsalabs/node.asp?id=2004),2048位密码的破解要比1024位密码困难2的32次方倍(232=4,294,967,296),或者差不多说43亿倍,因此破解一个DigiCert2048位SSL证书将需要比1024位长43亿倍的时间(采用相同的普通台式处理器)。可以估算,利用普通台式处理器的计算能力,破解一个DigiCert2048位SSL证书需要4,294,967,296x1,500,000年,或者说,略大于6400万亿年(以2009年破解RSA-768时的标准台式机算力估计)。

我们估计宇宙的年龄是13,751,783,021年,或者说137.5亿年。那就是说,如果你打算用一台常规电脑破解DigiCert2048位的SSL证书,并且你从时间的起点就开始算,经过了137亿年,你终于算到了今天,而你仍需要重复这个时间468,481次,一直到未来的未来的未来,你才总算达到破解这个证书的平均时间。事实上到那时宇宙本身估计早已寂灭了。当然如果用超级计算机来破解2048位密钥,我们只需要花64亿年,不需要等宇宙寂灭。如果大家还不放心,我们可以用100万位密钥,其传送只需要几秒时间(点对点只需一毫秒)。

本资料翻译自https://www.digicert.com/TimeTravel/math.htm

假如有了量子计算机呢?这个时间可以降低到几分钟。于是有人开始恐慌了:一旦量子计算机问世,公钥系统立即就崩溃了!这是一件多可怕的事情!我银行里的钱怎么办?我的隐私怎么办?这种恐慌,到了21世纪的今天被放大了很多,实际上从未发生。那量子计算机在短期的未来会出现吗?我的回答是,技术是具有不确定性的,这也是其魅力所在。但一台能准确运行Shor算法的量子计算机,我可以很大胆地估计:未来十至二十年不会出现。因为Shor算法对量子比特错误率要求太严格,技术上只能做量子纠错后形成逻辑量子比特才可能满足要求。而逻辑量子比特需要巨大的开销,以表面编码量子纠错算法为例,实现寿命为年计的逻辑量子比特需要数千个物理量子比特。假如我们用数千个逻辑比特来实现Shor算法,需要的物理比特数上百万,这在工程技术上无疑是无比巨大的挑战!要知道半导体晶体管,一种比量子比特鲁棒得多的器件,集成度达到百万量级都花了二十年时间!

总有人问假如上述的恐慌真的成了现实怎么办?毕竟发生的概率不为零。到时候现找替代的保密通讯方案肯定不现实,我们需要从现在开始研究“后量子计算机时代密码学”。量子通信由于其不可复制、可实时察觉监听者等特性,成为有力的竞争者,特别在国内拥护者很多。量子通信作为一种由量子力学原理保证的密钥分发(协商)技术,其科学性、前沿性是毫无疑问的。但不得不说的是,保密通信是一项复杂的系统性技术,其中有很多环节需要注意,认为密钥安全了通信就安全了是很肤浅的。量子通信还有很多技术有待解决和完善,比如中继技术。此外,量子密钥分发,在保持其声称的绝对安全条件下,效率是极低的。在经典公钥密码仍然工作完美,且在可预见未来中无破解危险情况下,量子通信很难找到合适的应用场景。就像我前面说的,任何一项技术的发展,首先要想的是应用场景。这种应用场景一定是实实在在,与市场、与大众利益和趋势一致的,而不可是虚构的。

总之,无论经典密码、量子计算、量子通信,在未来信息革命中都将面临巨大的挑战。你,准备好了吗?

《返朴》,致力好科普。国际著名物理学家文小刚与生物学家颜宁联袂担任总编,与几十位学者组成的编委会一起,与你共同求索。关注《返朴》(微信号:fanpu2019)参与更多讨论。二次转载或合作请联系fanpu2019@outlook.com。