快捷搜索:

安全学阅读报告,后量子密码技术发展分析

2019-09-14 17:56栏目:战术战略
TAG:

[17]重庆大学新闻网:《第一届亚洲抗量子密码论坛在成都举办》,2016年6月10日,网址:

评价和比较后量子 RSA。

主题演讲,上海保交所区块链底层首席架构师 燕宝

在当前的网络通信协议中,使用范围最广的密码技术是RSA密码系统、诸如ECDSA/ECDH等ECC密码系统以及DH密钥交换技术,这些通用密码系统共同构成了确保网络信息安全的底层机制。诸如大数分解(integer factorization)和离散对数等经过长期深入研究的数学问题构建出上述先进加密技术的底层机制,而且此类困难问题在过去数十年间的运行过程中表现出了充分的可靠性。但随着量子计算机技术不断取得突破,特别是以肖氏算法为典型代表的量子算法的提出,相关运算操作在理论上可以实现从指数级别向多项式级别的转变,这些对于经典计算机来说足够“困难”的问题必将在可预期的将来被实用型量子计算机轻易破解。

2015级计算机 网络工程7班  梁格 20152100168

以下为发言实录(经本人审核修改)。

除此之外,欧洲量子密码学术和工业界研究者联合组织“后量子密码”项目也在2015年发布了一份初始报告,在对称加密、对称授权、公钥加密以及公钥签名系统领域都提出了相关标准化建议。针对受到量子计算技术严重威胁的RSA/ECC密码系统,该报告认为麦克利斯密码系统具有发展成为新的公钥加密标准的潜力。

  本文的重点在于加快RSA的标准技术,当被推到极端时,用户的成本和攻击者的成本在合法之间造成更大的差距。具体而言,对于本文的RSA版本,攻击代价在使用成本上基本上是二次的。这些极端情况需要仔细分析量子因子分解算法。

图片 1

一、潜在的量子计算能力将对当前普遍使用的密码系统构成颠覆性威胁

(1)密钥生成,加密,解密,签名和验证是可行的。

一、背景知识

图片 2

在分享量子密码与后量子密码之前,了解一下量子相关的背景知识。先从量子力学说起吧,量子力学里面描述微观物质理论,与相对论一起被认为是现代物理学的两大基础支柱。

微观世界里,粒子嗡嗡跳跃的概率云,它们不只存在一个位置,也不会从一个A点通过一条单一路径到达B点;此外,微观粒子具有波粒二象性。微观体系里的状态的有两种变化,

  • 一种是按运动方程式演进,这种是可逆的变化;
  • 另一种是测量改变体系状态不可逆的变化。

量子就是量子世界中物质客体的总称,他既可以是光子、电子、原子、原子核、基本粒子等微观粒子,也可以是波色-爱因斯坦凝聚、超导体、“薛定谔猫”等宏观尺度下的量子系统,他们的共同特征就是必须遵从量子力学的规律。

后面我们看一下从量子力学里几个重要理论。

  • 第一个理论:量子态叠加原理,量子态是量子力学里边来描述量子系统的状态,其运动规律遵循薛定鳄的方程;量子态也被称为波函数或几率幅,记为|ψ⟩,假定量子客体有两个确定的可能状态0或者1,通常写成|0⟩、|1⟩,由于量子状态是不确定的,它一般不会处于|0⟩或|1⟩的确定态上,只能处于这两种确定态按某种权重叠加起来的状态上,这就是量子世界独有的量子态叠加原理,用数学表示即为:|ψ⟩=|0⟩ |1⟩,其中,为复数,且满足 =1。
  • 第二个理论:海森堡测不准原理,在经典力学中,测量对物理系统本身没有任何影响,可以无限精确地进行;在量子力学中,测量过程本身对系统造成影响;对于两个不同的物理量A和B(如坐标和动量,时间和能量等),不可能同时具有确定的测量值,这是由于测量过程对微观粒子行为的“干扰”,致使测量顺序具有不可交换性。
  • 第三个理论:量子纠缠,对于由多个粒子组成的系统,其每个粒子的状态往往无法被分离出来,因此,单个粒子的状态被称为是纠缠的;纠缠的粒子有惊人的特性,例如:对一个粒子的测量,可以导致整个系统的波包立刻塌缩,因此也影响到另一个、遥远的、与被测量的粒子纠缠的粒子。
  • 第四个理论:量子退相干,当两个粒子互相纠缠时,即使距离遥远,一个粒子的状态变化将会影响另一个粒子的状态变化;量子纠缠是量子技术的重要资源,是量子计算机、量子模拟等重大应用的物理基础;量子纠缠尽管奇妙无比,用途广泛,但它却有天然的致命伤——量子纠缠十分脆弱,环境会破坏其量子特性而使“纠缠”消失掉,即两个纠缠的量子客体最终会演化为不纠缠的状态,非局域关联或完全断开;环境不仅包括经典噪声,诸如热运动、吸收、散射等,还包括量子噪声,即真空起伏。这种环境引起的量子性消失,被称为量子退相干。

基于量子力学的理论基础,后面介绍一下量子通讯、量子计算与量子计算机。

  • 量子通信是指利用量子纠缠效应或海森堡测不准原理进行信息传递的一种通讯方式。
  • 量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。

量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置,该装置处理和计算的是量子信息、运行的是量子算法。

量子计算机使用的是量子比特,量子计算机能秒杀传统计算机得益于两个独特的量子效应:量子叠加和量子纠缠

  • 量子叠加能够让一个量子比特同时具备0和1的两种状态,
  • 量子纠缠能让一个量子比特与空间上独立的其他量子比特共享自身状态,创造出一种超级叠加,实现量子并行计算,其计算能力可随着量子比特位数的增加呈指数增长。

[2]欧洲电信标准协会(European TelecommunicationsStandards Institute):《量子安全密码与安全》(Quantum Safe Cryptography and Security),2015年6月,网址:

  Shor算法的1994年出版引起了普遍的说法,定量计算机将会破坏密码学,或者至少是公钥密码学。然而,这些说法远远超出了Shor算法的实际限制,对量子密码分析的后续研究几乎没有缩小差距。量子计算机将杀死RSA和ECC,但不会杀死基于哈希的密码学,基于代码的密码学,基于格子的密码学或多元二次方程式密码学。传统的看法是Shor算法将RSA公钥考虑在内几乎和合法的RSA用户一样可以解密, 其实,今天在互联网上,所有已知的量子攻击算法在加密时都是不可行的,解密仍然可行。

近日,由中国金融科技50人论坛(CFT50)与证券信息技术研究发展中心(上海)举办的“区块链里的密码学技术”闭门研讨会议,在上海证券大厦举行。

量子加密技术是量子通信科学发展的成果之一,又被称为量子密钥分发(QuantumKey Distribution)。依靠包括叠加态、量子纠缠和不确定性等在内的量子物理独特性质,量子密钥分发技术能够实现传统密钥交换的功能,并且可以检测和规避窃听企图。但这种方案也面临着包括成本和传播距离等因素在内的限制,而且攻击者还能够通过拒绝服务式攻击严重削弱量子密钥分发的效率。尽管上述两种加密手段目前都处于发展阶段,依然存在诸多问题需要解决,但是未来量子安全措施必然包含这些解决方案的恰当组合。

  本文还介绍了使用量子的GEECM(Grover plus EECM)计算机如下加速相同的EECM计算。与传统计算机的搜索算法相比,Grover算法在量子搜索算法上有二次方的提速。我们不确定Grover算法是否有实际意义,若有,则将密钥规模增大一倍即可保证安全。此外,指数级提速的搜索算法已经被证明不可能存在,故在量子时代对称密码算法和散列函数仍然是可用的。GEECM结果是后量子RSA参数选择的主要制约因素之一。

二、量子密码与后量子密码

图片 3

第二阶段,大家简单分享一下量子密码和后量子密码知识。

Shannon证明,若密钥为长度不小于待加密的明文长度的随机序列,且任何一密钥仅使用一次,该加密体制(C=PK)是无条件安全的(Perfect Secrecy)。

为何“一次一密”密码迄今未被广泛使用呢?主要原因是,“一次一密”要大量消耗“密钥”,需要通信双方不断地更新密码本,而“密码本”的传送(称为“密钥分配”)是关键问题所在。

  • 量子密码体系采用量子态作为信息载体,经由量子通道在合法的用户之间传送密钥;
  • 量子密码的本质是用于解决密钥分配问题 ,从该意义上说,量子密码即为量子密钥分配,为“一次一密”加密体制在公开信道进行安全、高效的密钥分配提供很好的解决方案。

量子密码的安全性由量子力学原理所保证,具体来说,其安全性依赖于:

  • 1)量子不可克隆性:窃听者无法克隆出正确的量子比特序列;
  • 2)海森堡测不准原理:基于单光子量子信道的量子密码
  • 3)量子纠缠:基于量子相关信道的量子密码。

量子密码在理想状态下可以确保密钥的安全性,但实际上量子密码系统绝对达不到理想状态,例如单粒子探测效率不是百分百的,它会产生传输损耗,各种器件不完善等等问题,这些非理想漏洞就可能被窃听者用来窃取密钥,但却不会被合法用户发现。同时,量子密码体系必须确保安全密钥的生成率足够高,以达到信息“一次一密”加密的需求。

目前,在百公里范围的城域网,量子密码体系可以做到密钥分配在现有的各种攻击下是安全的,安全密钥生成率在25公里内可确保高清视频“一次一密”。

量子攻击方法可分为非相干攻击和相干攻击。

  • 非相干攻击:攻击者独立地给每一个截获到的量子态设置一个探测器,然后测量探测器中的粒子,从而获取信息;
  • 相干攻击:攻击者通过某种方法使多个粒子比特关联,从而可相干地测量或处理这些粒子比特,进而获取信息。

安全学阅读报告,后量子密码技术发展分析。由于量子信息的奇妙特性,使得量子计算具有天然的并行性,且其计算能力可随着量子比特位数的增加呈指数增长;量子计算机的这种超强计算能力,使得基于某些数学难题的传统公钥密码的安全受到挑战;然而,量子计算机并不能解决电子计算机难于求解的所有数学问题。基于量子计算机不擅长计算的那些数学问题构造密码,就可以抵抗量子计算的攻击,我们称能够抵抗量子计算机攻击的密码为抗量子计算密码,或后量子密码

出于对抗量子计算密码需求的紧迫性,国际上从2006年开始举办"抗量子计算密码学术会议(Post-QuantumCryptography)",每两年举行一次,至今已举办了4届,已经产生了一批重要的研究成果,让人们看到了抗量子计算密码的新曙光。

  • 2015 年 8 月,美国国家安全局公开宣布由于面临量子计算的威胁,其计划将联邦政府各部门目前使用的ECC/RSA 算法体系向后量子算法进行迁移。
  • 而负责标准制定的美国国家标准与技术局也在2016 年 2 月正式面向全球公开了后量子密码标准化的路线图,并在同年秋正式公布征集密码系统建议的计划,其中包括公钥密码、数字签名以及密钥交换算法,建议征集的截止日期定于2017年12月;此后,国家标准与技术局会利用3-5年时间分析这些建议并发布相关分析报告,最终的标准拟制工作也将耗时1-2年。
  • 换言之,国家标准与技术局后量子密码算法标准最终将在2021-2023年出台;而考虑到其具备较好的安全性能以及国际互联网工程任务组已经着手展开了标准化工作,基于哈希算法的签名标准可能会更快地推出。
  • 除此之外,欧洲量子密码学术和工业界研究者联合组织“后量子密码”项目(PQCrypto)也在2015年发布了一份初始报告,在对称加密、对称授权、公钥加密以及公钥签名系统领域都提出了相关标准化建议。
  • 针对受到量子计算技术严重威胁的RSA/ECC密码系统,该报告认为麦克利斯密码系统具有发展成为新的公钥加密标准的潜力。

图片 4

在后面和大家分享一下四种主流的后量子密码算法及其优缺点。

第一种是基于哈希算法签名(Hash-based signatures),安全依赖于底层的哈希函数的抗碰撞性;
优点:安全要求是最小的;
缺点:只能用于量子签名方案(签名/验签)。

第二种是基于多元二次方程式密码(Multivariate-quadratic-equations-cryptography),多变量密码体制(MPKC)被认为是能够抵御基于量子计算机攻击的新型公钥密码体制之一,利用减扰动方法构造出了一种基于MPKC的新型签名方案,其计算效率,主要指中心映射求逆的效率高于两个著名的多变量签名体制Sflash和Quartz;
优点:与基于hash的签名方案相比,签名较短;
缺点:与传统的RSA、ECC等系统相比,密钥非常大;还有在MPKCs的可证明安全性没有实质性的结果。

第三种是基于编码密码(Code-basedcryptography),算法原语(底层单向函数)使用纠错码,第一个基于编码密码(公钥加密方案)是由Robert J. McEliece在1978年提出的;
优点:加解密速度快;
缺点:大型公钥大小(100KBS-几MBS),签名/验签成本大,

“基于编码密码体系没有实际应用是知道”;二元Goppa码是安全的(似乎是),而其他基于编码密码体系适用应仔细考虑,有些方案看上去并不是很牢靠的。

第四种是基于格密码(Lattice-basedcryptography),安全性是基于最坏情况下格问题的困难,Ajtai在1996年提出“Collision-ResistantHash Function”,Goldreichet al.在1997年提出“PKE and signature schemes”,Ajtai和Dwork在1997年提出“PKE scheme”;
优点:可证明安全:基于最坏情况硬度的强安全性证明;相对高效的实现;非常简单;多用途,许多先进的密码体制的提出,例如:IBE、ABE、FHE;
缺点:暂无。

现在密码学术界,对于后量子密码的方案基本上是基于哈希函数签名基于格密码两者结合的,基于哈希函数签名用于抗量子密码体系的签名/验签,基于格密码用于抗量子密码体系的加密/解密。

欢迎订阅知远防务快讯 我们在第一时间报导全球最新防务动态,关注世界热点事件,追踪防务发展方向。

建议我们的批量生成算法建议,以帮助减少能源消费和保护环境,RSA的所有用户

包括用户,传统的预量子RSA应该将他们的密钥生成计算委托给NIST或另一个可信的第三方。允许用户更频繁地生成新的RSA密钥并擦除旧的RSA密钥,限制了重点盗窃的危害。


2、相关技术

量子加密技术:是量子通信科学发展的成果之一,又被称为量子密钥分发(QuantumKey Distribution)。依靠包括叠加态、量子纠缠和不确定性等在内的量子物理独特性质,量子密钥分发技术能够实现传统密钥交换的功能,并且可以检测和规避窃听企图。但这种方案也面临着包括成本和传播距离等因素在内的限制,而且攻击者还能够通过拒绝服务式攻击严重削弱量子密钥分发的效率。尽管上述两种加密手段目前都处于发展阶段,依然存在诸多问题需要解决,但是未来量子安全措施必然包含这些解决方案的恰当组合。

后量子密码:后量子密码(post-quantumcryptography),又被称为抗量子密码(quantum-resistantcryptography),是被认为能够抵抗量子计算机攻击的密码体制。此类加密技术的开发采取传统方式,即基于特定数学领域的困难问题,通过研究开发算法使其在网络通信中得到应用,从而实现保护数据安全的目的。后量子密码的应用不依赖于任何量子理论现象,但其计算安全性据信可以抵御当前已知任何形式的量子攻击。尽管大数分解、离散对数等问题能够被量子计算机在合理的时间区间内解决,但是基于其他困难问题的密码体制依然能够对这种未来威胁形成足够防御能力。更为重要的是,它们还可以与当前网络系统实现较高程度的兼容,从而会减小当前密码系统向后量子密码迁移可能面临的阻力。

舒尔算法(Shor's algorithm):以应用数学家彼得·舒尔(Peter Williston Shor)命名,针对整数分解问题的量子算法 (在量子计算机上面运作的算法)。

RSA可扩展性:很明显,后量子RSA公钥n需要相当大抵御第2节中描述的攻击。本节分析的可扩展性,可用于RSA密钥生成,加密,解密,签名生成和签名验证。在最初的RSA文件[43]中,e是一个随机数,有很多位作为n。拉宾在[42]建议,而不是使用一个小常数e,并说e = 2是“几百倍”。拉宾的加速因子增长为Θ(lg n),这对本文所考虑的大尺寸的n值尤其重要。


3、相关算法伪代码

Shor算法:

将暂存器初始化成x从0到Q − 1。所以这一个初始态是Q 个状态的叠加。

建立量子函式版本的f(x) ,并且应用于上面的叠加态, 得到 .这里仍旧是Q个状态的叠加。

对输入暂存器进行量子傅立叶变换。这个变换(操作于二的幂次--Q = 2q个叠加态上面) 使用一个Qth单位根例如将任意给定态的振幅平均分布在所有Q个态上。另一个方法是对于每个不同的x: 。由此得到最终状态: .这是一个远多过Q个状态的叠加态,但是远低过Q2个。虽然在和中有Q2项,但只要x0 和 x的值相同,态就可被提出来。令 为 Qth 的一个单位根,r 为 f 的周期,x0为一个产生相同 f(x) 的 x 的集里面的最小元素(我们已经有x0 < r),以及b在0到之间使得。那么则是复平面的一个单位向量(是一个单位根,r 和 y 是整数),而在最终状态下的系数则为 。这一求和的每一项代表一个获得相同结果的不同路径,而量子干涉发生。在单位向量几乎与复平面指向同一方向(要求指向正实数轴)时,干涉将是相长的。

进行测量。我们由输入寄存器取得结果y,由输出寄存器取得。 而既然f 是周期,对某对y和 进行测量的概率则由 给出。 分析显示这个概率越高,单位向量就越接近正实数轴,或者yr/Q就越接近一个整数。除非r是2的乘方,否则它不会是Q的因子。

对y/Q进行连分数展开来计算其近似值,并生成满足下列两个条件的c/r′: A: r′

检查f(x) = f(x r′) 。 如果成功了,我们就完成了。

否则,以接近y左右的数值作为r的候选,或者说多取几个r′. 如果任何候选成功了,我们就完成了。

否则,回到第一步骤(也就是全部重新作一次)。

 

 

Grover算法:

图片 5

RSA算法:

图片 6


4、发展方向

除量子公钥密码外,后量子公钥密码都是基于不能转换成离散傅立叶变换的数学难题而建立,主要有以下几种类型。

(1)基于hash算法构造的Merkle型签名算法基于hash算法构造的签名体制,最经典的是Merkle hash树签名体制[6],由传统的hash函数和任意的一次性签名算法,共同构造出一个完全二叉树来实现数字签名。

(2) 基于编码的公钥算法基于编码理论构造的公钥体制,其理论基础是解码问题的困难性,即仅在已知生成矩阵的情况下,在码空间中寻找一个码字与已知码的Hamming距离最短。

(3) 基于格的公钥算法基于格的公钥密码是指在大维数的格上,基于最短向量问题(S V P)和最近向量问题(CVP)等数学难题而构造的公钥密码体制。

(4)基于多变量的公钥算法多变量公钥密码体制(M u l t i v a r i a t e-q u a d r a t i c-p o l y n o m i a l s P u b l i c K e y Cryptosystem,简称MQ或MPKC)是一大类各具特色的公钥密码算法的统称,也是近年来后量子公钥密码的研究热点。这类体制主要基于有限域上的多元二次多项式方程组的难解性。与RSA、DH、ECC相比,多变量公钥密码的安全性很难被证明等价于一个已知的可简单表述的数学难题,因而也被认为是很难找到相应量子攻击算法的难题,从而被看成具有抗量子计算的性能。

  值得一提的是,除了上述几种公钥算法外,国内也由管海明、张焕国等在多变量体制的基础上自主提出了基于有理分式的公钥算法。3后量子公钥密码研究新的特点目前,国际上关于后量子公钥密码的研究趋势有以下几个明显的特点。一是研究步伐逐步加快。这从近几年召开的后量子密码会议可见一斑。2006年,在比利时的Leuven召开了第一届国际后量子密码学会议,2008年在美国的Cincinnati召开了第二届,2010年在德国的Darmstadt召开了第三届,基本上是两年一届。但今年,将在中国台北召开第四届,且以后将每年一届,时间节奏明显加快。二是更加注重相关基础研究。例如对近年提出的后量子算法的数学理论基础有了更多的探讨,加强了对算法的安全性分析,对与抗量子性能相关的量子复杂性理论的研究也越来越多。三是更加注重算法的有效性与可用性。因为可实用的量子计算机的问世已越来越迫近,可用性与效率都是无法回避的问题。四是各国政府的支持力度也越来越大。表面上看,后量子密码的研究属于学术领域,但背后往往有政府的参与,因为这是涉及未来若干年国家安全的重大学术问题 。

2017-12-01 上海保交所 燕宝 量子密码和后量子密码

随着计算能力的发展,密码系统也需要做出调整和改进,从而确保其计算安全性继续成立。例如,IBM公司和美国国家安全局在20世纪70年代开发出了使用56位密钥的DES密码系统(DataEncryption Standard),即计算机需要在256的搜索空间内寻找可能的密钥,这对于当时以及此后相当长一段时间内的计算机来说都是不可能完成的任务。但到了90年代,先进的超级计算机已经开始能够在合理的时间内遍历DES密码系统的密钥空间。因此,在计算安全性遭到破坏的情况下,DES密码系统也很快被至少使用128位密钥的AES密码系统(AdvancedEncryption Standard)所取代。

1.文章主要思想和工作:

三、区块链世界里的密码攻击以及量子密码破译算法

第三阶段,和大家分享一下在区块链世界里的密码攻击以及量子密码破译算法。针对现有区块链技术,攻击主要集中在四个方面:

  • 第一,针对区块链基础设施的攻击
  • 第二,针对智能合约的攻击
  • 第三,针对热钱包的攻击
  • 第四,针对冷钱包的攻击,代表性的攻击事件如图所示。

图片 7

目前,可用于密码破译的量子计算算法主要有Grover算法Shor算法

对于密码破译来说,

  • Grover算法的作用相当于把密码的****密钥长度减少一半
  • Shor算法适用于解决大整数分解、离散对数求逆等困难数学问题,对目前广泛使用的RSA、EIGamal、ECC公钥密码和DH密钥协商协议可以进行有效攻击。

因此,在量子计算环境下,RSA、EIGamal、ECC公钥密码和DH密钥协商协议将不再安全

我们设计新区块链底层的时候,着重考虑数据隔离、数据安全防护以及隐私保护方面。今天准备并不是非常充分,简单大家分享到此,非常感谢!

[10]埃里克·乔杜因:《驾驭下一代前沿力量:量子计算基本知识》(Straddlingthe Next Frontier Part 1: Quantum Computing Primer),网址:

  关于后量子因子分解,对于RSA的每个现代变体,包括本文中考虑的变体,已知的最好的攻击是分解算法。本节分析后整数分解的量子复杂度。有两个重要的分解算法类。 第一类由算法组成在寻找小素数方面特别快速。第二类由同余组合算法组成。

《区块链技术体系中的加密技术 - 量子密码和后量子密码》

非常感谢CFT50论坛提供一个区块链技术交流的平台,白老师(白硕)、王老师(王励成)的演讲都非常精彩,我在这里跟大家简单分享一下我们近期的在区块链技术的研究方向。

我们在实际应用当中,碰到了很多像白老师前面讲解内容一样的需求,特别突出是在数据安全防护、身份和交易数据的隐私保护方面。在某些应用案例中,银行方面提出

“区块链中的数据是通过现有的加密算法是保证安全,目前是安全的,但不代表一直是安全的;数据多方存储(分布式存储),存在潜在的安全风险”。

在交流的过程中,他们提出了量子计算攻击和后量子密码算法方面的意见和看法,我们就和上海交大-密码与计算机安全实验谷老师的团队,针对于这方面去做了一些深入的交流和研究,今天将我们学习研究的内容跟大家简单分享一下。

首先和大家介绍一下分享的议程,

  • 第一阶段,背景知识(量子力学、量子通信、量子计算与量子计算机);
  • 第二阶段,量子密码与后量子密码(量子密码体系、量子攻击方法、后量子密码标准化、主流的后量子密码);
  • 第三阶段,区块链世界里的攻击与密码破译的量子算法(针对区块链基础设施、智能合约以及冷热钱包的攻击、密码破译的Grover算法、Shor算法)。

[16]欧洲电信标准协会:第4届量子安全密码工作组会议,网址:

内容:

图片 8图1:量子计算能力威胁时间不等式图解

 

在2015年的报道中,《自然》杂志引用荷兰情报与安全总局(DutchGeneral Intelligence and Security Service)负责人的观点认为,不法攻击者现在开始拦截和存储金融交易数据、个人电子邮件及其他互联网加密流量行为,“并不会让人感到意外”。除此之外,大规模数据收集毫无疑问已经成为某些国家政府组织的例行性工作。根据斯诺登揭露的资料,美国和英国情报机构正在通过“上游”计划,利用海底光缆登陆站毫无遗漏地收集约占全球联网流量99%的光缆通信信息。《连线》杂志早在2012年就披露美国国家安全局已经开始在犹他州新建一座数据中心,其有能力将互联网自诞生以来产生的所有流量全部保存下来,从而使其成为一种战略资源,供美情报机构在掌握量子计算能力后进行开发。因此,虽然量子计算机的出现可能还需要数十年,但这种能力本身已经具有了现实性威胁。

关键词:

任何密码系统的应用都需要在安全性和运行效率之间做出平衡,密码算法只要达到计算安全要求就具备了实用条件,并不需要实现理论上的绝对安全。在其1945年发布的《密码学的数学原理》中,美国数学家克劳德·E·香农严谨地证明了一次性密码本或者称为“弗纳姆密码”具有无条件安全性(unconditionallysecure)。但这种绝对安全的加密方式在实际操作中需要消耗大量资源,不具备大规模使用的可行性。事实上,当前得到广泛应用的密码系统都只具有计算安全性,即通过计算暴力破解密文所花费的时间远大于该信息的有效时间,并且破解密文的成本远高于加密信息的价值。

后量子密码,RSA可扩展性,Shor算法,ECM,Grover算法,RSA再次成功

后量子密码与量子加密技术构成了抵御量子威胁的组合方案

比较两个机制:三重加密与基于代码的密码学,基于格子的密码学和后量子对于负担得起的用户,RSA提供了更高的信心。后量子RSA在允许后量子加密,签名和更高级的加密功能方面也是非常不寻常的。

2015年 8 月,美国国家安全局公开宣布由于面临量子计算的威胁,其计划将联邦政府各部门目前使用的ECC/RSA算法体系向后量子算法进行迁移。而负责标准制定的美国国家标准与技术局也在 2016 年 2 月正式面向全球公开了后量子密码标准化的路线图,并在同年秋正式公布征集密码系统建议的计划,其中包括公钥密码、数字签名以及密钥交换算法,建议征集的截止日期定于2017年12月;此后,国家标准与技术局会利用3-5年时间分析这些建议并发布相关分析报告,最终的标准拟制工作也将耗时1-2年。换言之,国家标准与技术局后量子密码算法标准最终将在2021-2023年出台;而考虑到其具备较好的安全性能以及国际互联网工程任务组已经着手展开了标准化工作,基于哈希算法的签名标准可能会更快地推出。

本文主要讨论后量子RSA。

亚洲密码研究学者也在积极跟踪相关技术发展的最新形势。2016年6月,首届亚洲抗量子密码论坛我国成都顺利召开。鉴于该领域研究工作的飞速发展,下一届东道主韩国首尔大学决定将原定于2017年召开的第二届亚洲抗量子密码论坛也提前到2016年11月。韩国国防部、韩国国家网络发展局、以及主管科技教育的政府部门和产业界,如三星电子等均派高级主管参会。

其次,本文介绍了一种新的量子分解算法,它比Shor的算法快得多,比预量子分解算法快得多。

[责任编辑:蒋佩华]

首先,本文提出RSA参数

后量子密码技术标准制定和迁移工作逐步受到政府组织的重视

  后量子RSA 3推导出一种新的算法来生成大批独立的均匀随机数,比任何已知算法更有效地生成这样的素数。RSA参数的初始实施结果很大,足以将所有已知的量子攻击推到2100 qubit操作以上。 这些结果包括成功完成后期量子RSA中最昂贵的操作,即生成1TB的公钥。

[4]米凯利·莫斯卡:《量子世界中的网络安全》(Cybersecurityin the Quantum World),网址:

(2)所有已知的攻击都是不可行的,即使是高度可扩展的量子计算机也是如此。

表1:量子计算能力对于当前通用加密系统的影响

摘要:

尽管主流的密码系统目前依然能够有效运行,但是在量子计算技术的潜在冲击下,几乎所有的加密算法都需要进行改进甚至必须进行迁移。在2016年4月的内部报告中,美国国家标准与技术局对当前主要的密码技术将受量子计算能力影响的情况进行了预测。其他研究者也普遍认为,尽管对于某些对称密钥加密技术来说,增加密钥长度可能是对抗量子威胁的有效手段;但对于RSA和ECC密码系统来说,上述做法显然不足以继续确保其安全性,密码开发人员需要在公钥密码系统中运用生成密钥的全新方法。

评估:后量子RSA不符合安全,老式的安全定义需要渐进的安全性多项式时间对手。 然而,后量子RSA似乎提供了一个合理的具体安全水平。

国际后量子密码学研究始终都在稳步推进

真正全功能型量子计算机何时才能出现尚没有准确的预期,但研究者普遍认为如果当前不采取实质性预防措施,网络安全体系的崩溃很可能就是不远将来的确定性事件,而且量子计算威胁的前溯性还将使网络安全防御者面临更加复杂的局面。

从以往的密码系统标准化发展历史来看,任何密码系统都必须在应用过程中增强和完善性能,后量子密码也不例外。因此,通过新型密码产品的商业化推广使用活动,企业界能够不断积累和分析用户数据,从而促进后量子密码系统安全性能和运行效应的提升。

作为密码学的分支领域,国际后量子密码理论和技术研究一直以来都得到了各国的普遍关注,相关学术交流活动不仅在数量和频度上逐年增加,而且影响范围还在向更多国家和领域辐射。作为学术和企业界研究者的联合组织,成立于1982年的国际密码逻辑研究联合会(InternationalAssociation for Cryptologic Research)在2006年就已经开始举办第一届后量子密码技术国际会议。此次会议的成果在集中汇总于2008年出版的《后量子密码》,该书详细介绍了后量子密码研究的几乎全部潜在领域,在此之后,国际后量子密码技术的发展也基本上遵循着该书构建的技术框架。目前这项会议已经在北美、欧洲、东亚等地区连续举办7届,并且通过建立夏季或冬季培训营等形式在各国研究者之间交流和增强密码技术的发展。

欧洲电信标准协会与加拿大滑铁卢大学量子计算中心联合举办的量子安全密码工作组会议(IQC/ETSIQuantum-Safe Crypto Workshop)也在国际后量子密码研究领域产生了重要影响。这项会议开始于2013年,参会代表来自于数学、密码学、物理学、计算机等不同研究领域,目标是实现标准化和部署下一代密码基础设施,特别是抵御量子计算能力威胁的冲击。

[13]丹尼尔·J·伯恩斯坦等编着:《后量子密码》(PostQuantum Cryptography),Springer出版社,2008年,第1页,网址:

美国电气和电子工程师协会早在2008年就将NTRU加密算法确定为正式标准。作为一种基于格加密解决方案,NTRU算法具备抵抗已知量子计算威胁的能力。在随后的2010年,其又被认可标准委员会(AccreditedStandards Committee X9)批准为可用于数据防护的新型加密标准。美国国家标准学会X9.98标准具体明确了金融交易通过公钥/私钥加密系统如何利用诸如NTRU等格加密算法的方式。虽然在实际应用过程中也面临着特定的漏洞威胁,NTRU算法依然是当前得到全面开发和批准的后量子公钥密码加密解决方案。

后量子密码的主要研究领域

密码系统的标准化工作是其大规模应用的前提。当前,多种后量子加密算法都已经在技术上具备了进行标准化的基本条件,并且包括美国国家标准与技术局在内的标准机构也开始发布后量子密码发展和迁移指导和实施计划。尽管密码标准体系的建立需要国际社会通过交流合作活动达成共识,但在密码研究领域取得领先的国家无疑将在标准制定过程中占据更多的主动权。

图2:引入前溯变量R的量子计算能力威胁时间不等式图解

多元加密系统的底层数学困难问题是求解有限域内的多元多项式,其可以应用于公钥密码系统及数字签名。多元密码系统中发展潜力最大的是简单矩阵密码体制。在这种密码系统中,所有计算都在一个有限域中完成,而解密过程只包含线性系统计算,从而使这种密码体制具备较高的运行效率。在多元加密签名系统中,所有计算操作都在单一有限域内完成的单域密码体制最具发展潜力,其中的典型代表包括UOV和Rainbow签名体制。

[12]欧洲电信标准协会(EuropeanTelecommunications Standards Institute):《量子安全密码与安全》(QuantumSafe Cryptography and Security),2015年6月,

[14]莉莉·陈等:《后量子密码报告》,2016年4月,第4页。

[6]米凯利·莫斯卡:《密码学面临的量子威胁》(Thequantum threat to cryptography),密码标准工作组会议,奥地利,维也纳,2016年5月8日,网址:

[9]詹姆斯·班福德:《国家安全局正在建设全国最大的间谍中心》(TheNSA Is Building the Country’s Biggest Spy Center ,《连线杂志》,2012年3月15日,网址:

在目前大量应用的密码算法中,已知的量子计算威胁对非对称密码影响更加显着。与对称密码系统不同,非对称密码——又被称为公钥密码系统——使用两种独立的密钥,分别用于加密和解密信息。作为一种发展历史较短的加密方式,非对称密码系统有效解决了对称密码面临的安全密钥交换问题,因而广泛应用于公钥基础设施、数字签名、联合授权、公共信道密钥交换、安全电子邮件、虚拟专用网以及安全套接层等大量网络通信活动之中。不幸的是,随着肖氏算法的提出,包括RSA密码、ECC密码系统以及DH密钥交换技术等非对称密码算法已经从理论上被证明彻底丧失了安全性。相对于对称密码系统还可以采取升级措施应对量子威胁,非对称密码系统必须采取全新方法进行重建,因而其也就成为后量子密码技术发展的重点领域。

基于哈希算法密码系统能够在哈希函数的基础上提供一次性签名机制,其原理基于特定加密哈希函数的抗碰撞性。拉尔夫·默克尔在1979年引入了这种密码原理研究方法,但是其在效率方面存在签名过长以及生成速度太慢等诸多短板。经过多年的发展,XMSS和SPHINCS哈希签名体制因其在签名长度和运行速度方面的优势得到较多关注,国际互联网工程任务组(InternetEngineering Task Force)当前还在试图推进并完成XMSS签名的标准化工作。

后量子密码技术发展的重点是非对称密码系统

美国安全创新公司注册并拥有NTRU算法的专利,其提供两种授权选项:开源GNUGPL v2授权以及商业授权。从2011年起,该公司还发布了多种实现NTRU算法的软件库,其中包括安全套接字协议层和ARM7/9处理器库等。NTRU工程网站中已经存在使用NTRU加密算法的Java和C程序应用。目前,NTRU算法已经在处理能力有限的移动设备以及大容量服务器中得到应用。

计算安全性是密码系统正常运行的基本前提

[18]NTRU工程网站:

[1]克劳德·E·香农(Claude Elwood Shannon):《密码学的数学原理》(A mathematical theory ofcryptography),国际密码逻辑研究联合会(International Association for CryptologicResearch)网站,1945年,第83页,网址:

[3]理查德·P·费曼:《利用计算机模拟物理》(SimulatingPhysics with Computers),《国际理论物理》(InternationalJournal of Theoretical Physics),第21卷,1982年;保罗·贝尼奥夫:《图灵机的量子力学汉密尔顿模型》(Quantummechanical hamiltonian models of turing machines),《统计物理》(Journal of StatisticalPhysics),第29卷,第3期,第515页,1982年。

[7]克里斯·塞萨雷:《网络安全准备迎接量子革命:密码改进者准备迎接未来主义计算机的来临》(Onlinesecurity braces for quantum revolution: Encryption fix begins in preparationfor arrival of futuristic computers),自然网站,2015年9月8日,网址:

[20]网址:

一般情况下,密码系统在开发过程中都会考虑破解计算技术发展的速度和水平,因此,现代密码系统的应用都存在特定生命周期。然而,任何基于计算安全性密码系统面临的致命威胁是:计算能力出现远超正常预期的大幅跃升,而当前量子计算机技术的发展正在加速使这种隐现的威胁成为现实。

三、世界后量子密码技术研究发展现状

密码技术是网络安全的根基。在网络行为已经渗透到社会生活每个领域的今天,无论是网上银行、电子商务还是电子邮件、即时消息服务,密码技术无时无刻不在保护着用户的信息安全。如果当前普遍运用的密码系统遭到根本性威胁,所有网络活动的安全性无疑都将面临严峻挑战。事实上,具有强大密码破解能力的量子计算机近年来已经不断取得实质性进展,研究者们普遍认为应该尽早部署能够抵御这种威胁的后量子密码技术,从而将全球信息网络系统面临的总体风险降至最低。

纠错码长期以来就在通信技术中发挥着重要作用,而从罗伯特·麦克利斯在1978年首次提出基于纠错码的加密技术概念以来,这项理论已经得到大量深入研究。此类密码系统加密过程速度非常快,而且解密速度也相对合理,阻碍其取得实际应用的最大问题是密钥长度。2001年,库尔图瓦、菲尼亚斯和桑垂尔又提出基于纠错码的数字签名体制CFS,其突出优势是签名长度短并且验证速度非常快,但其与麦克利斯密码系统一样,其面临的突出问题是密钥长度的限制。

进入2016年,美国两家主要信息技术公司在后量子密码应用领域的活动引起了外界关注。微软公司于4月发布了基于格密码库,这种可移植软件的底层机制是基于环上带误差学习问题(RingLearning With Errors)。无论对于使用经典计算机或者量子计算机的攻击者,该软件库至少能够实现128位安全性能。而且,此次发布的软件只是微软公司部署具备抗量子能力密码系统计划的初始措施,在积累足够使用数据后,软件的应用性和安全性也会不断提高。紧随微软公司之后,谷歌公司也于2016年7月在官方安全博客上宣布其将开始进行后量子密码技术的测试活动。在对当前后量子密码技术发展进行调查后,谷歌决定应用这种被称为“新希望”的基于环上带误差学习问题密钥交换协议。虽然谷歌宣称测试工作只是在有限的用户群体中展开,而且其并不意在建立某种安全标准,但在此时实际测试后量子密码技术无疑将促使该公司发展形成全新的核心竞争力,而且在谷歌公司对互联网行业影响力的作用下,后量子密码技术的应用也势必得到有力的推进。

图片 9

加密算法都是建立在特定数学难题的基础之上,但是这些数学问题的困难性可能会因新型计算能力或者算法的出现而削弱。由于量子计算机技术取得了出人意料的快速发展,大量仅能抵御经典计算机暴力破解的密码算法面临被提前淘汰的困境。

[15]国际密码逻辑研究联合会:第7届国际后量子密码会议网站,日本,福冈市,2016年2月,网址:

[11]莉莉·陈等:《后量子密码报告》,2016年4月,第3页。

根据密钥类型的不同,密码技术通常可以划分为对称密码和非对称密码系统。在对称密码系统中,通信的双方使用完全相同的密钥,诸如DES、AES和3DES密码等都是典型的对称密码系统。这类密码通常具有良好的加密和解密运算效率,但对称密码系统的应用首先需要在通信双方之间建立并交换密钥。关于对称密码系统面临的量子计算威胁,目前仅有洛夫·格罗弗在1996年提出的量子算法将对AES等对称密码系统产生影响,而且与经典计算机的破解速度相比,其能够产生效率优势仅仅是一般方法的平方。通过密钥长度加倍的措施,这种威胁可以得到有效化解。

量子计算的前溯性威胁使部署后量子密码技术需求更加紧迫

[19]网址:

根据是否基于量子物理原理,量子安全选项可划分为两种基本类型,即后量子密码与量子加密技术。后量子密码(post-quantumcryptography),又被称为抗量子密码(quantum-resistantcryptography),是被认为能够抵抗量子计算机攻击的密码体制。此类加密技术的开发采取传统方式,即基于特定数学领域的困难问题,通过研究开发算法使其在网络通信中得到应用,从而实现保护数据安全的目的。后量子密码的应用不依赖于任何量子理论现象,但其计算安全性据信可以抵御当前已知任何形式的量子攻击。尽管大数分解、离散对数等问题能够被量子计算机在合理的时间区间内解决,但是基于其他困难问题的密码体制依然能够对这种未来威胁形成足够防御能力。更为重要的是,它们还可以与当前网络系统实现较高程度的兼容,从而会减小当前密码系统向后量子密码迁移可能面临的阻力。

[5]莉莉·陈、史蒂芬·乔丹、刘一凯、贾斯汀·穆迪、芮内·佩拉尔塔、雷·珀尔纳和丹尼尔·史密斯-托恩:《后量子密码报告》(Reporton Post-Quantum Cryptography),美国国家标准与技术局,2016年4月,网址:

在此基础上,网络安全领域研究者还应该考虑“现在拦截,将来破解”(interceptnow, decrypt later)的威胁模式。如果现在的通信网络流量遭到窃听并被存储下来,未来潜在的对手利用量子计算能力,就能对这些通常处于加密状态的信息进行破解,从而在多年以后将威胁范围追溯到当前。因此,在上述时间不等式模型的基础上,应该引入量子计算技术的前溯性威胁时间范围变量R。由于秘密收集信息工作的开始时间并不确定,当前很难判断量子计算技术的前溯性威胁时间范围,但假设潜在对手已经或者准备着手进行相关工作并非无稽之谈。

图片 10

造成这种现象的根本原因是,当现在普遍使用的密码系统被提出之时,所谓量子计算只是存在于世界上少数几位物理学家头脑中的设想,当前大多数密码系统在开发过程中都没有考虑量子算法威胁的因素。例如,罗恩·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼在1977年就了提出RSA公钥密码解决方案,而此时距离理查德·P·费曼和保罗·贝尼奥夫分别从理论上提出驾驭量子物理属性进行计算操作的方案尚有5年时间,贝尔实验室科学家彼得·肖直到1994年才提出了解决大数分解问题的肖氏算法。

当前,国际后量子密码研究主要集中于基于格密码(Lattice-basedcryptography)、基于编码(Code-basedcryptosystems)的密码系统、多元密码(Multivariatecryptography)以及基于哈希算法签名等领域。

在2016年的“密码标准工作组”(AWorkshop About Cryptographic Standards, AWACS)会议上,量子计算和密码学专家米凯利·莫斯卡用一组时间不等式反映了部署后量子密码技术的紧迫需求。假设当前密码系统的生命周期为X,从当前密码系统迁移至后量子密码系统的时间为Y,实用型量子计算机研制的时间为Z;其得到的结论是:只有X Y<Z成立才能确保密码系统安全的底线,即现行密码生命周期与系统迁移时间之和必须小于量子计算机投入实际应用的时间;如果Y>Z,即迁移时间大于量子计算机研制时间,那么网络安全系统必将面临崩溃。

在向后量子密码系统迁移势在必行的情况下,相关领域的研究已经在国家之间引发“军备竞赛”。近年来,欧洲国家的“后量子密码”和“安全密码”项目和日本的CREST密码数学项目都取得了显着成果,美国也在相关政府机构和企业界的推动下,处于后量子密码研究和应用领域的领先地位。

二、后量子密码是量子安全选项的重要组成部分

企业界将在后量子密码发展应用过程中发挥重要影响力

除了上述四种主要研究方向以外,近年来还出现了其他新型加密算法思路。尽管在量子计算机上运行肖氏算法可以有效解决离散对数问题,但对于超奇异椭圆曲线上的同源问题,能够使其丧失安全性的类似攻击方法目前尚未出现。除此之外,共轭搜索问题(conjugacysearch problem)以及辫群中的相关问题也受到研究者关注,但对共安全性的研究目前还处于初始阶段。

作为功能对立的两个领域,量子计算能力与量子安全选项的发展呈现出双螺旋上升的趋势,一方的显着进步必然带动另一方的迫切需求。在量子计算机发展受到业内广泛关注的当前,量子安全选项的研究与开发也被多国相关机构提上议事日程。

在所有被认为具有抵御量子威胁潜力的计算问题中,基于格密码系统在过去十年中得到了最为广泛的关注。与大数分解和离散对数问题不同,目前没有量子算法可以借助量子计算机对其进行破解。而且,格密码系统在最坏情况假设条件下依然具备安全性。在诸如RSA等公钥密码系统中,生成密钥需要选择2个既是质数又能形成分解困难问题实例的随机大数,但是这个过程中存在选择错误数字而导致安全性下降的可能性。而在格密码系统中,所有可能的密钥选择方式都能够形成足够的困难性。基于格加密的核心问题是最短向量问题(ShortestVector Problem, SVP),即在格系统内找到最短的非零向量。目前,NTRU密码以及带错误学习问题(LearningWith Error, LWE)是基于格密码系统发展实用前景最好的两种方式。

量子计算能力对于现行密码系统的潜在冲击

版权声明:本文由澳门太阳娱乐集团官网发布于战术战略,转载请注明出处:安全学阅读报告,后量子密码技术发展分析