图片 2

保护信息安全的密码 背后的原理你真懂吗?

1 美国国家安全局的“8.19”声明

一个亿亿次的经典计算需要一百年,但用一个万亿次的量子计算可能只0.01秒的时间。打一个不恰当的比方,我们的有生之年,电子计算机就是马车,量子计算机就是汽车。

神秘的密码学…

2015年7月29日,美国正式对外公布“国家战略计算倡议”。正当人们纷纷猜测该战略倡议中提到的未来新型计算是什么样的时候,二十天后的8月19日,美国国家安全局网站上发布了一则消息,开宗明义指出“由于面临量子计算机的潜在威胁”,国家安全局这个负责统管美国政府和军方密码系统的最高机构决定将联邦政府所使用的“B包密码体制”替换成“抗量子密码体制”。一石激起千层浪。首先,在现实社会当中美国国家安全局一直非常低调和神秘(这也是为什么好莱坞总是喜欢拿它来吸引眼球的原因),而这次美国国家安全局居然一反常态在互联网上公开阐明其最核心的秘密—联邦政府部门所使用的密码系统可能面临的巨大威胁,这件事情本身就非常诡异。美国国家安全局用意何在?“8.19”声明背后是否有什么“阴谋”?其次,什么是“抗量子密码”?它和“量子密码”又是什么关系?此外,量子计算机都还没有研发出来,怎样说明一个密码能够抗击量子计算机的攻击?……

量子计算也正在成为颠覆经典计算的“灰犀牛”。这只“灰犀牛”正在随着谷歌与量子计算机的研发公司D-Wave合作、阿里等巨头着手开发量子计算机而冲向人群,这个大概率的事件也正在给传统金融安全架构带来风险和挑战。

密码学是一门古老而年轻的科学,它的起源可以追溯到古罗马时代约公元110年的恺撒加密。然而,直到1949年Claude
Elwood
Shannon发表了《保密系统的通信理论》这篇划时代的论文,才标志着现代密码学的诞生。经典密码学所使用的密码设计和分析方法不是基于数学推理而是依赖密码学家的直觉和灵感。

我们先来看一看美国国家安全局这个“8.19”声明的要点。国家安全局在密码领域承担了“密码破译”和“密码设计”两大任务。密码破译的工作由国家安全局下属的“信号情报部”(Signals
Intelligence
Directorate,SID)负责,其前身甚至可以追溯到第二次世界大战期间破译日本的“紫密”等工作,中途岛海战大败日本帝国海军,以及日本“战神”三本五十六的座机被击落均是它立下的战功。而密码设计的工作则由美国国家安全局下属的“信息保障局”(Information
Assurance Division,
IAD)负责。信号情报部负责“攻”,信息保障局负责“防”,一矛一盾。此次美国国家安全局的“8.19”声明是指其下属的信息保障局研发的B包密码体制将面临量子计算机的威胁,并要求使用“抗量子密码”来替换它。一句话,这次的“8.19”声明是针对美国联邦政府部门自身的密码升级方案。那么B包密码体制为何不再安全了呢?

无穷破解能力的量子计算正在到来,它正在成为区块链的达摩克利斯之剑,但达摩克利斯之剑又在被Hcash和阔悦科技的“抗量子密码”装入剑鞘。

凯撒密码盘

B包密码体制包括了多种以现代公钥密码为基础的加密算法、数字签名算法、密钥协商算法和随机数生成算法等。而现代公钥密码诞生于上个世纪七十年代中叶,其安全性依赖于数学上的皇冠—数论中的一类困难问题。美国国家安全局组织专家对公钥密码的安全性分析了整整三十年,在确认没有什么安全漏洞之后,才于2005年允许B包密码体制在联邦政府内部的信息系统当中投入使用。根据NSA的相关规定,B包密码体制可以用于联邦政府的机密信息传递,而且和更为神秘的A包密码体制一道,可以用于处理最高密级为绝密级的信息,例如美联储等机构就可以使用B包密码体制来传递敏感信息。

图片 1

1976 年,Diffie 和Hellman
发表了一篇影响力巨大的密码学新方向的文章。它标志着公钥密码学的诞生,从此密码学走出秘密领域,进入公开研究领域。在此之前,人们完全依靠彼此共享的秘密密钥来实现秘密通信,而公钥密码技术使得通信双方在没有事先共享任何秘密信息的情况下能够通信。在对称密钥加密情况下,两方同意共享一个可同时用于加密和解密的秘密密钥k。公钥加密在这个意义上是非对称的,具体来说,接收方产生一对密钥,被分别称为公钥和私钥,发送方用公钥将消息加密后发送给接收方,接收方用自己的私钥解密收到的密文。

其实,现代公钥密码不仅仅用于美国或其他国家的政府部门。在人们日常生活或工作当中,在当今互联网的正常运行与维护当中,均离不开现代公钥密码。例如,各种软件版本的自动更新,各种网络设备补丁的下载与升级,政府部门的电子政务,企业的电子商务,个人的网上消费…均依靠现代公钥密码体制来提供虚拟社会各成员之间的相互认证,只不过这些认证工作都是在后台默默的完成,无须人们动手。因此,现代公钥密码构成了网络空间的信任链之锚。可以毫不夸张的讲,人类社会从来没有像今天这样,将如此巨大的资产托付于现代公钥密码体制。所以,一旦网络空间的这个信任锚“基础不牢”,必将“地动山摇”。

量子计算为何会成为达摩克利斯之剑

公钥pk可以是通信发生之前,接收方以明文形式发给发送方。需要强调的是:两方之间的通信信道可以是公开的,但假设是认证的,即敌手无法修改接收方发给发送方的公钥,这个问题可以用数字签名解决;也可以是接收方广泛地传播它的公钥pk,比方说通过她的个人网页,将公钥放置在她的名片中,公布在报纸上面,或者是放在某个公共目录使得任何想和接收方秘密通信的人都可以查到她的公钥。这种应用模型中,所有通信中多个发送方可以利用同样的pk与接收方多次通信。

那么人类对现代公钥密码的安全性如此信任,原因何在呢?

量子计算是对传统计算的革命,已经从实验室初步走向商业化应用。它与传统计算的最大区别在于采用量子比特作为最小的运算单元。传统计算机采用二进制比特,即“0”和“1”,而量子比特计算为“叠加态”。从CPU
的运行来看,CPU一次只能处理一个计算。而量子计算速度大大提升,对1000
位的大数进行因数分解只需要几秒,而传统的计算机则需要1025 年。

由于公钥pk是公开的,因此公钥加密的安全不依赖于公钥的安全性,而仅仅依赖于私钥的安全性。与之相比,对称密钥加密假设了所有密钥的完全保密性,即通信双方必须共享密钥,并且不允许第三方获得此密钥。公钥加密方案可使多个发送者与单个接受者秘密通信,与之不同的是,依靠双方共享密钥的对称密钥加密只能让两方进行秘密通信。公钥加密体制的最主要的缺点是较对称密钥加密而言要慢至少2~3个数量级,因此,如果对称密钥加密是一种选择,它就应当被使用。

四十年前诞生的现代公钥密码体制,无论是RSA算法,ECC椭圆曲线算法,还是DH密钥协商算法,它们的安全根基都系在“一根绳上”—数论中的“大数素因子分解/离散对数”困难问题之上。由于人们相信仅凭现在的计算机(即使是比现有最强大的超级计算机还快千百万倍)都难以在数十年甚至上百年之内破译这些公钥密码算法,因此世人一直高枕无忧。

这种计算能力虽然正在让互联网公司们信心满满,意图以此推动大数据、云计算的迅速落地,但是量子计算同样带来了巨大威胁。区块链技术就是这只灰犀牛所威胁的目标之一。

公钥加密体制

然而,1994年,美国贝尔实验室的数学家Peter
Shor发明了一种破解算法,从理论上证明了这种算法能够在很短的时间内完成对上面的数学困难问题的求解,从而宣布了现代公钥密码已经不再安全。只不过他的这个破解算法有一个前提,那就是必须使用“大规模的量子计算机”,而这在当时纯属天方夜谭。因为在二十多年前,造出一台能够达到破解现代公钥密码水平的量子计算机所面临的困难就如同让一名幼儿园小朋友马上完成博士论文一样不可思议。

区块链技术作为一种去中心化存储技术,建立了去中心化数据库结构,并保证数据的完整性以及安全性。在数据安全性方面,区块链技术采用非对称加密算法保障数据库的可信赖性,使用户在互联网无实名制的背景下防止诈骗。

不同种类的公钥加密算法

但是人类追求技术进步的步伐有时候也超出了自身的预料。进入本世纪之后,特别是2012年之后,设计制造量子计算机的关键技术接二连三取得突破。尽管现在人们研发量子计算机的原动力已经远远超越了破解公钥密码算法,而是更加急迫的希望能够把它用于先进材料、新药设计、基因工程等领域来提升人类社会的生活品质,甚至探索宇宙的终极秘密,如量子场论等。然而,量子计算机一旦真的制造出来,毫无疑问将对现有公钥密码体制带来毁灭性的打击,如果人们不能尽快找到替代方案,那么当今的网络空间也必将荡然无存。一句话,设计“新型抗量子公钥密码”的队伍现在必须和那些研发量子计算机的队伍赛跑。

图片 2

自公钥密码体制问世以来,密码学家们提出了多种公钥加密方案,它们的安全性都是基于数学基础问题的计算困难性。对于这些数学问题,如果利用已知的求解算法由公开信息计算出私钥的时间越长,那么基于这一数学问题的公钥加密系统被认为是越安全。

2 量子密码与抗量子密码的区别

每一个区块的数据中,都包含了所有交易的记录以及账户身份信息,交易信息在区块链中是公开的,账户身份信息是通过非对称加密算法加密的。但是区块链的数据安全性基于非对称加密算法,而当前常用的1024位非对称加密通过量子计算在几秒内即可破译,这大大地威胁到了基于区块链技术的数据库可信任性,采用区块链技术的金融基础架构的安全性也因此受到影响。

传统的公钥加密算法,根据所基于的数学困难问题来分类,有以下三类系统目前被认为是安全高效的:1。大整数分解系统;2。离散对数系统;3。椭圆曲线离散对数系统。

2015年8月19日,美国国家安全局在其官方网站上宣布正式启动“抗量子密码体制”,即“8.19”声明。事隔整整一年之后,2016年8月16号,中国的量子科学实验卫星“墨子号”在酒泉卫星发射中心成功发射,而“量子通信”这一概念落入普通大众的视野,而“量子通信”其实就是密码领域常说的“量子密码”。对此,我们很有必要厘清一下量子密码与抗量子密码的区别。

抗量子密码与量子计算“左右手”赛跑

自从1978年RSA体制提出来以后,人们对大整数分解问题的研究产生了强烈的兴趣,并取得了丰富的成果。在1985年,ElGamal型公钥密码体制提出以后,学术界又对有限域上离散对数的计算问题产生了浓厚的兴趣。值得注意的是,大整数分解问题的求解和有限域上离散对数问题的求解在本质上具有某种一致性,因而基于RSA假设的RSA和基于有限域上离散对数假设的DSA的安全强度几乎一致。

量子密码本身并不是一种密码算法,而是利用量子物理,特别是量子纠缠的神奇特点来实现传统的加密算法的密钥协商,简称量子密钥分发(Quantum
Key
Distribution,QKD)。由于这种特点,QKD主要的应用是不断给用户更新密钥,而不能像公钥密码体制那样进行数字签名和用户身份认证。现阶段世界各国建设的各类量子通信网络,均是指上述的QKD。通信双方在进行保密通信之前,可以依靠QKD系统来“分发”这次加密算法所使用的密钥。由于量子纠缠状态的“不可测性”这一基本物理定律的保障,使得人们从理论上得到了安全性保障,即如果有人企图“偷听”密钥的传递,那么处于纠缠态的量子对就会发生坍塌,从而让通信双方得知此次密钥的传递发生了问题,于是可以再次协商、再次传递…(当然,如果窃听方就是存心捣乱,持续通过这种“偷听方式”来干扰你进行密钥分发,这又带来新的安全隐患)。

四十年前诞生的现代公钥密码体制,无论是RSA算法,ECC椭圆曲线算法,还是DH密钥协商算法,它们的安全根基都系在“一根绳上”—数论中的“大数素因子分解/离散对数”困难问题之上。由于人们相信仅凭现在的计算机(即使是比现有最强大的超级计算机还快千百万倍)都难以在数十年甚至上百年之内破译这些公钥密码算法,因此世人一直高枕无忧。

经过人们的不断努力,随着计算机运算效率的迅速提升,目前人们对于这两类问题的求解能力大大地提高,使得基于大整数分解的RSA体制受到很大的冲击,密钥长度为512比特的RSA不再认为是安全的,这就迫使RSA体制中使用的模数和基于有限域上离散对数问题的公钥密码体制中有限域的规模越来越大,同时需要更长的密钥来保证系统安全,这造成运算速度的降低,如DSA体制的运算速度随着其密钥长度的增加将以指数级下降。

在现阶段,量子密码QKD面临的主要技术障碍有两个:一个是纠缠态的量子对的传输距离有限,需要进行“中继传输”,就像奥运火炬一样一棒一棒的接力下去。这就要求每一个“火炬手/二传手”都必须是可靠、可信的。如果某个火炬手“狸猫换太子”,那么整个通信安全就受到破坏。因此如何解决“二传手”本身的可信问题?目前一种解决办法是用公钥密码来对量子通信的各个节点进行“身份认证”。一个典型的例子是世界上着名的量子通信产品生产厂商,瑞士的IQD公司所生产的量子通信设备,就是使用现代公钥密码来对传输节点进行身份认证的。但如果现代公钥密码在量子计算机面前不堪一击,那么节点的身份依然可能被冒充。事实上,人们正在考虑使用抗量子公钥密码来替换上一代公钥密码,为量子通信网络中的各个节点提供身份认证。

然而,1994年,美国贝尔实验室的数学家Peter
Shor发明了一种破解算法,从理论上证明了这种算法能够在很短的时间内完成对上面的数学困难问题的求解,从而宣布了现代公钥密码在理论上已经不再安全。只不过他的这个破解算法有一个前提,那就是必须使用“大规模的量子计算机”。

椭圆曲线密码体制是1985年由Koblitz和Miller分别提出的,利用基于有限域上椭圆曲线上点组成的加法群构造基于椭圆曲线离散对数问题的密码体制,二十多年来人们对椭圆曲线离散对数问题的经典求解算法的研究几乎没有本质进展。

第二个问题是兼容性。现阶段用于传递密钥的量子通信网络是一个独立运行的、中继节点必须是可信的通信网络。而人类社会在过去三十多年来投入了巨大的软硬件资源建设了另一张网络:基于TCP/IP协议的计算机网络,而且还在不断快速扩张当中,如移动互联网、物联网等等。这张网最大的特点就是“天生不可信”。因此人们一直以来就以“网络环境不安全为前提假设”来追求计算机网络通信的安全,例如采用上面提到的现代公钥密码来提供网络成员之间的相互信任问题,从而解决“不可信环境下的可信认证问题”。因此在量子通信获得更广泛的应用之前,如何解决“可信的量子网络”与“不可信的互联网”这两张网的兼容问题?或者说如何解决量子通信的标准问题?这对于量子通信产业化是必不可少的。还需要指出的是,无论从工程造价以及全球网络互联互通的角度来看,世界上任何一个国家都不可能废弃现有的计算机网络,而花费巨资来重新打造一张“纯量子通信网络”。因此,在可以预见的未来,这两张网必定会共生共存,相互补充。

而这在当时纯属天方夜谭。因为在二十多年前,造出一台能够达到破解现代公钥密码水平的量子计算机所面临的困难就如同让一名幼儿园小朋友马上完成博士论文一样不可思议。

椭圆曲线密码体制的安全性是建立在求椭圆曲线离散对数问题难解的基础上。ECC与RSA、DSA相比有很多技术优点:椭圆曲线离散对数问题目前只存在指数时间的经典算法,而大整数分解和有限域上离散对数问题存在亚指数级的经典算法,这就体现在ECC比RSA的每比特密钥的安全性能更高,密钥长度160比特的ECC与1024比特的RSA、DSA有相同的安全强度,而210比特ECC与2048比特的
RSA、DSA具有相同的安全强度,即达到相同安全强度的ECC的密钥大小和系统参数与RSA、DSA相比要小得多,意味着它所占的存储空间较小,且ECC的运算速率比RSA、DSA快得多。ECC的上述特点使得它在许多领域已经取代RSA,成为通用的公钥加密算法,包括作为轻量密码算法模块和应用于网络传输层协议TLS等。

顺便说一句,人们有时候也将量子密码称为“硬密码”,主要是说它依赖于量子物理的铁律,以及在实现它的时候需要大量专用硬件设备。与之相对的是“软密码”,即我们人类历史上延续了数千年并且将继续传承下去的“数学密码”。四十年前诞生的第一代公钥密码就是“软密码”家庭中的“新生成员”。遗憾的是,它们即将退出历史舞台,新一代公钥密码—抗量子密码呼之欲出了。

但是人类追求技术进步的步伐有时候也超出了自身的预料。进入本世纪之后,特别是2012年之后,设计制造量子计算机的关键技术接二连三取得突破。尽管现在人们研发量子计算机的原动力已经远远超越了破解公钥密码算法,而是更加急迫的希望能够把它用于先进材料、新药设计、基因工程等领域来提升人类社会的生活品质,甚至探索宇宙的终极秘密,如量子场论等。

必须注意实际工程中实现的密码不同于教科书式密码。下面我们将介绍教科书式RSA加密和教科书式ElGamal加密,并分析其不安全性。