经典密码学所使用的密码设计和分析方法不是基于数学推理而是依赖密码学家的直觉和灵感。

文章作者:管理一号 | 2019-03-01
字体大小:

 

 

撰文| 王明生 中国科学院信息工程研讨所研讨员

暗码学(Cryptography)是一门陈旧而年青的科学,它的来源能够追溯到古罗马年代约公元110年的恺撒(Caesar)加密。可是,直到1949年Claude Elwood Shannon宣布了《保密体系的通讯理论》这篇划年代的论文,才标志着现代暗码学的诞生。经典暗码学所运用的暗码规划和剖析办法不是根据数学推理而是依托暗码学家的直觉和创意。

凯撒暗码盘

1976 年,Diffie 和Hellman 宣布了一篇影响力巨大的“暗码学新方向”的文章。它标志着公钥暗码学的诞生,从此暗码学走出隐秘范畴,进入揭露研讨范畴。在此之前,人们彻底依托互相同享的隐隐秘钥来完结隐秘通讯,而公钥暗码技能使得通讯两边在没有事前同享任何隐秘信息的情况下能够通讯。在对称密钥加密情况下,两方赞同同享一个可一起用于(任何一方)加密和解密的隐隐秘钥k。公钥加密在这个意义上对错对称的,具体来说,接收方发作一对密钥(pk,sk),被别离称为公钥和私钥,发送方用公钥将音讯加密后发送给接收方,接收方用自己的私钥解密收到的密文。

 

公钥pk可所以通讯发作之前,接收方以明文办法发给发送方。需求着重的是:两方之间的通讯信道可所以揭露的,但假定是认证的,即敌手无法修正接收方发给发送方的公钥(特别是敌手不能用自己发作的密钥去替换),这个问题能够用数字签名处理;也可所以接收方广泛地传达它的公钥pk,比方说经过她的个人网页,将公钥放置在她的名片中,发布在报纸上面,或许是放在某个公共目录使得任何想和接收方隐秘通讯的人都能够查到她的公钥。这种运用模型中,一切通讯中多个发送方能够运用相同的pk与接收方屡次通讯。

因为公钥pk是揭露的,因而公钥加密的安全不依托于公钥的安全性,而只是依托于私钥的安全性。与之比较,对称密钥加密假定了一切密钥的彻底保密性,即通讯两边有必要同享密钥,并且不答应第三方取得此密钥。公钥加密计划可使多个发送者与单个接受者隐秘通讯,与之不同的是,依托两边同享密钥的对称密钥加密只能让两方进行隐秘通讯。公钥加密体系的最首要的缺点是较对称密钥加密而言要慢至少2~3个数量级,因而,假如对称密钥加密是一种挑选(换言之,假如两边能够事前安全地同享一个密钥),它就应当被运用。

公钥加密体系

不同品种的公钥加密算法

自公钥暗码体系面世以来,暗码学家们提出了多种公钥加密计划,它们的安全性都是根据数学根底问题的核算困难性。关于这些数学问题,假如运用已知的求解算法由揭露信息核算出私钥的时刻越长,那么根据这一数学问题的公钥加密体系被以为是越安全。

传统的公钥加密算法,根据所根据的数学困难问题来分类,有以下三类体系现在被以为是安全高效的(不考虑具有量子核算才干的敌手):1。大整数分化体系(代表性的有RSA);2。离散对数体系(代表性的有DSA);3。椭圆曲线离散对数体系(ECC)。

自从1978年RSA体系提出来今后,人们对大整数分化问题的研讨发作了激烈的爱好,并取得了丰厚的效果。在1985年,ElGamal型公钥暗码体系提出今后,学术界又对有限域上离散对数的核算问题发作了稠密的爱好。值得留意的是,大整数分化问题的求解和有限域上离散对数问题的求解在实质上具有某种一起性,因而根据RSA假定的RSA和根据有限域上离散对数假定的DSA的安全强度简直一起。

 

经过人们的不断尽力,跟着核算机运算功率的敏捷进步,现在人们关于这两类问题的求解才干大大地进步,使得根据大整数分化的RSA体系遭到很大的冲击,密钥长度为512比特的RSA不再以为是安全的(关于DSA也是如此),这就迫使RSA体系中运用的模数和根据有限域上离散对数问题的公钥暗码体系中有限域的规划越来越大,一起需求更长的密钥来确保体系安全,这形成运算速度的下降,如DSA体系的运算速度跟着其密钥长度的添加将以指数级下降。

椭圆曲线暗码体系(Elliptic Curve Cryptography,ECC)是1985年由Koblitz和Miller别离提出的,运用根据有限域上椭圆曲线上点组成的加法群结构根据椭圆曲线离散对数问题的暗码体系,二十多年来人们对椭圆曲线离散对数问题的经典求解算法的研讨简直没有实质开展。

椭圆曲线暗码体系的安全性是建立在求椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)难解的根底上。ECC与RSA、DSA比较有许多技能长处:椭圆曲线离散对数问题现在只存在指数时刻的经典算法,而大整数分化和有限域上离散对数问题存在亚指数级的经典算法,这就体现在ECC比RSA的每比特密钥的安全功用更高,密钥长度160比特的ECC与1024比特的RSA、DSA有相同的安全强度,而210比特ECC与2048比特的 RSA、DSA具有相同的安全强度,即到达相同安全强度的ECC的密钥巨细和体系参数与RSA、DSA比较要小得多,意味着它所占的存储空间较小,且ECC的运算速率比RSA、DSA快得多。ECC的上述特色使得它在许多范畴现已替代RSA,成为通用的公钥加密算法,包含作为轻量暗码算法模块和运用于网络传输层协议TLS等。

有必要留意实践工程中完结的暗码不同于教科书式暗码。下面咱们将介绍“教科书式RSA”加密和“教科书式ElGamal”加密,并剖析其不安全性。

“教科书式RSA”加密计划

KeyGen:输入1^n,随机挑选两个n比特的素数p,q,N=pq,∅(N)=(p-1)(q-1),挑选满意gcd(e,∅(N))=1的e,核算d=e^(-1) mod∅(N),输出公钥pk=(N,e),私钥sk=(N,d)。

 

“教科书式ElGamal”加密计划

 

KeyGen:输入1^n,履行多项式时刻算法输出一个循环群G,其阶为q(其间‖q‖=n),生成元为g。然后挑选随机的x←Z_q并且核算h≔g^x。公钥是(G,q,g,h),私钥是(G,q,g,x)。

 

 

上述两个算法加解密的正确性能够简略地验证。在剖析它们的安全性之前,咱们有必要清晰进犯场景。根据敌手的才干,首要有以下几种进犯类型:

(1)唯密文进犯(Ciphertext-only attack),这是最基本的进犯办法,标明敌手只能调查到密文,并且企图断定相应的明文;

(2)已知明文进犯(Known-plaintext attack),这儿敌手学习一个或许多个运用相同密钥加密的明密文对,方针是断定其它密文对应的明文;

(3)挑选明文进犯(Chosen-plaintext attack,CPA),这种进犯中,敌手能够挑选明文,并得到相应的密文,企图断定其它密文对应的明文;

(4)挑选密文进犯(Chosen-ciphertext attack,CCA),这最终一种进犯类型是指敌手乃至能够挑选密文并得到相应的明文,方针依然是断定其他密文的明文。

前两种进犯类型是被迫的,符合实践场景的,唯密文进犯在实践中最简略完结,敌手仅有要做的就是偷听传输密文的公共信道;而已知明文进犯符合实践是因为不是一切加密的音讯都是保密的,至少不是无限期的保密,举个比方,通讯开端是两边或许一般加密“hello”音讯,又或许加密可用来确保某秘要直到揭露的那一天,任何偷听并取得密文的人,将在后来取得相应的明文。

相对而言,后两种进犯类型是自动的,敌手能够习惯性地有挑选地恳求加密和解密,这是否代表了一个真实值得重视的实践的仇视要挟?针对挑选明文进犯(CPA),有个二战时期的军事前史说明晰这一点。

在1942年的5月,美国水兵的暗码专家截获了一份通讯音讯,该音讯中包含了一份密文字段“AF”,他们信任这对应着明文“中途岛”,以为日军正计划对中途岛建议进犯,可是华盛顿的指挥者并不信任,一般以为中途岛不或许成为进犯的方针。所以水兵暗码专家指令在中途岛的美军戎行发送一个明文音讯,说他们的淡水供应缺少。日军截获了该音讯,马上报告给其上级“AF”淡水缺少。所以坚信“AF”的确就是中途岛,美军敏捷派三架运输机抵达该方位,结局就是中途岛被解救了,日军遭到了重创,这儿水兵暗码专家就完结了一次经典的挑选明文进犯。

至于挑选密文进犯(CCA),咱们能够想象一个用户和他们的银行通讯的场景,其间一切的通讯都是经过加密的。假如该通讯没有被认证,则敌手能够代表用户发送特定密文,银即将解密这些密文,敌手或许能够从成果中把握某些信息。此外,加密经常在高档其他协议中运用;比方,一个加密计划或许被作为认证协议的一部分来运用,其间一方发送一份密文给对方,对方解密回来成果。在这种情况下,一个诚笃方或许正好扮演了一个解密预言机的人物,所以该计划有必要是CCA安全的。

公式详解“教科书式RSA加密”计划

显着能够看出“教科书式RSA加密”计划是断定性加密,因而不是CPA安全的。尽管“教科书式ElGamal加密“在断定Diffie-Hellman(DDH)假定下被严厉证明是CPA安全的,却简略遭到挑选密文进犯。挑选密文进犯(CCA)安全的一个亲近的相关问题就是密文的可延展性,直观上来解说,即一个加密计划具有这样一个特点:给定不知道音讯m的密文c,能够得到不知道音讯m_1的密文c_1,其间m和m_1具有某种已知的相关。“教科书式RSA”加密就简略呈现上面的进犯,比方说敌手调查到运用公钥〈N,e〉加密的密文c=m^e mod N,则有密文c_1=2^e c mod N,解密为2m mod N,因为〖c_1〗^d≡〖(2^e m^e ) 〗^d≡2^ed m^ed≡2m mod N。关于“教科书式ElGamal加密”,比方说敌手A阻拦了运用公钥pk=(G,q,g,h)加密音讯m的密文c=〈c_1,c_2 〉,这意味着c_1=g^y,c_2=h^y∙m。一些随机挑选的y←Z_q对敌手来说是不知道的,但敌手能够核算〖c_2〗^/=c_2∙m^/,则很简略知道密文c^/=〈c_1,〖c_2〗^/ 〉是音讯m∙m^/的密文,这个调查成果就简略引起挑选密文进犯。有人或许会对立:假如接收者收到两个密文c、c^/,并且密文的前一个元素相同,将发作置疑(的确,关于正常生成的密文,密文的第一个元素相同的概率是可疏忽的)。可是,敌手很简略防止其发作,令c_1,c_2,m,m^/如上面所述,敌手能够挑选随机的y^/←Z_q,并且设〖c_1〗^((2))=c_1∙g^(y^/ ),〖c_2〗^((2))=c_2∙h^(y^/ )∙m^/,简略验证c^((2))=〈〖c_1〗^((2)),〖c_2〗^((2)) 〉是音讯m∙m^/的密文,且密文的第一个元素是彻底随机的。

 

根据上述剖析,“教科书式RSA加密”办法简略高效,可是不满意暗码的安全要求。事实上,RSA实验室公钥加密标准PKCS#1v1.5版别,运用了填充加密的原理,关于一个常见办法的公钥pk=〈N,e〉,令k为N的字节长度,即k是一个满意2^8(k-1) ≤N<2^8k的整数,假定要加密的音讯m是一个8比专长的倍数,并且长度最长能够到达k-11字节,现加密一个D字节的音讯核算如下:(00000000‖00000010‖├ r┤‖├ 00000000┤‖m)^e mod N,其间r是随机生成的(k-D-3)字节的字符串,这些字节均不为0(该条件使得音讯在解密的时分没有歧义)。留意到m的最大答应长度能确保r的长度至少为8个字节,这样关于一切随机填充的r值的蛮力搜素是不行行的(杂乱度≥2^64)。

尽管至今还没有根据RSA假定的证明,PKCS#1v1.5依然被以为是CPA安全的,可是对该计划的挑选密文进犯已被证明。因为标准中的填充部分是以特其他办法完结(且不由恣意比特组成),假如密文没有正确的格局,将会回来一个过错音讯,这些过错音讯的存在足以建议挑选密文进犯:给定一个正确生成的密文c,进犯者能够恢复出明文m,办法是经过提交多个密文并且调查哪个密文能成功解密,哪个会发作过错。因为这类信息能够来源于当接收到不正确格局的音讯时,宣布过错音讯的服务器,因而在实践中是可行的。

也就是说,根据RSA假定的高效且CCA安全的计划还不存在。暗码学家们为了进步现有计划的功率,提出新的假定,并且探究运用现有的假定,能够到达的最高功率上界。在实践中取得很大成功的一种办法,是在“彻底严厉的安全性证明”和“没有证明”之间供给一个“中心地带”。该办法就是在证明暗码学计划的安全性中,引入了一个抱负模型,最盛行的比方就是随机预言机(Random Oracle,RO)模型。

依此,暗码学家们结构了随机预言机模型下的CCA安全的RSA加密,进一步,为了消除开始版别计划中密文比Z_N^*中的单个元素要长(即使是加密一个短音讯时)的缺点,结合最优非对称填充(OAEP)技能,结构了RSA-OAEP加密计划,修订了之前的PKCS#1v1.5标准。尽管旧版别因为兼容性依然被广泛运用,但现在新的完结体系应该倾向于这个更新后的版别。

相对来说,“教科书式ElGamal”加密计划不只有用并且能够根据DDH假定证明是安全的,却没有在实践中得到广泛选用,或许因为有限域上存在亚指数算法求解离散对数问题。而工程完结ElGamal式加密时,出于安全和功率的考虑,现在广泛运用ECC,至于完结的标准能够参阅商用暗码算法标准-SM2椭圆曲线公钥暗码算法或许美国国家标准与技能研讨所(National Institute of Standards and Technology,NIST)公布的ECC标准。

 

抗量子核算机进犯的公钥暗码计划提上日程?

前面介绍了网络年代为了维护被传输数据的秘要性(Confidentiality)而广泛运用的公钥加密体系,它们的安全性或许根据大整数分化问题的困难性,或许根据离散对数问题的困难性。可是,1994年美国数学家Peter Shor在量子核算模型下提出一个算法使得处理以上数学困难问题成为或许。Shor算法在量子核算机上能够在多项式时刻内处理大整数分化与离散对数问题。这意味着,一旦量子核算机或许针对大整数分化问题或许离散对数问题的专用量子核算机被制造出来,将会彻底破解根据这些困难问题的公钥加密算法。二零一七年三月三日,谷歌量子AI实验室三名科学家Mohseni、Read和Neven在《天然》杂志上声称“量子核算机五年内将完结商用化”。尽管文章一起指出,真实的量子核算机所需求的技能还需求十年左右的时刻才干完结,但这现已使得传统的公钥暗码体系的安全性存在巨大的危险。因而,迫切需求规划下一代的抗量子核算机进犯的公钥暗码计划。

关于某些问题,经研讨标明量子算法相关于传统算法并没有显着的优势。现在,首要的抗量子核算机进犯的公钥暗码计划的候选有根据格的、根据编码的、根据哈希函数的、根据多变量的暗码体系等。其间,格上的若干困难问题,如最短向量问题(Shortest Vector Problem,SVP)、独立最短向量问题(Shortest Independent Vector Problem,SIVP)等,还没有发现能够在多项式时刻内处理的量子算法,因而被以为其能够反抗量子核算进犯。

另一方面,格上的困难问题之间存在均匀景象困难性(Average-case Hardness)与最差景象困难性(Worst-case Hardness)之间的归约联系(简略来说,Worst-case Hardness归于核算杂乱性理论范畴,暗码计划直接运用的暗码学原语(cryptographic Primitive)咱们期望是Average-case Hardness),且在格上的数学运算首要是矩阵向量乘法,核算简略高效,可并行完结。此外,比较于根据编码、哈希函数、多变量等其他的抗量子核算进犯的公钥计划,以格为根底的数学结构,不只能够结构加密计划,也能够结构签名计划、密钥洽谈计划。这意味着,根据格的公钥体系能够布置多个公钥暗码计划模块,有利于整个公钥暗码体系在通讯网络体系上的功用整合。归纳上述许多优势,根据格的加密计划现已成为抗量子核算进犯的最有期望的候选算法之一。

现在,已有的根据格的加密计划首要分为两大类,一类是NTRU暗码体系,其计划的完结功率较高,但缺少可证明安全性。另一类是根据格上均匀景象下的困难问题如带差错学习问题(Learning with Errors, LWE),环上带差错学习问题(Ring Learning with Errors, RLWE)等的加密计划,也是根据格的加密体系的一个抢手研讨范畴。根据均匀景象下困难问题的首要加密计划包含根据一般格的最早的Regev 加密计划、对偶Regev(dual-Regev)加密计划以及根据抱负格的RLWE的加密计划等。在这儿,咱们就不深化介绍了。

 

截止2017年11月30日,NIST现已完结了第一轮后量子暗码(Post-Quantum Cryptography,PQC)(也被称为是抗量子的或量子安全的暗码)算法的搜集。到现在为止,23个PKE/KEM的格暗码提案,有3个计划(Compact-LWE,HILA5,Odd Mantattan)现已被攻破,4个计划被进犯候已提出处理办法,还有2个计划存在其它问题;5个Signature的格签名提案的Comments较少,现在没有被攻破。

正如NIST所说:“后量子标准化的开展进程不该该被视为竞赛,某些情况下,或许不或许作出一个候选计划优于另一个计划的具有杰出支撑的判别。相反,NIST将以揭露和通明的办法对提交的算法进行深化全面的剖析,并鼓舞暗码团队一起进行剖析和评价。这种结合的剖析办法将影响NIST对后量子标准化的后续开展的决议计划。

NIST估计将进行多轮评价,为期3至5年,并且因为现在科学关于量子核算才干的认知还远远不够全面,这个评价进程将比SHA-3和AES的评选更为杂乱。此外,一些候选后量子暗码体系或许有彻底不同的规划特点和数学根底,不同类型之间的候选算法的比较将是困难乃至不或许的。尽管间隔大规划地运用量子核算机还有一段路要走,但因为从传统公钥暗码体系到后量子暗码的过渡不太或许是一个简略的“drop in”,开发、标准和布置新的后量子暗码体系将需求支付极大的尽力。因而,应当及早地进行这个过渡。”

现在到未来几年时刻,正是后量子暗码标准化的黄金阶段,感爱好的研讨人员应当捉住这个机会,积极地参加其间!

Copyright © 2009-2018 外星探索www.ufo-1.cn 版权所有 关于我们| 法律声明| 免责声明| 隐私条款| 广告服务| 在线投稿| 联系我们| 不良信息举报