一个加密方案的选择密文安全性的证明

:2005204227:国家自然科学基金(60302015);信息安全国家重点实验室2004年第1批开放课题(01201).:梅其祥(1973-),男,西南交通大学博士研究生,中南大学讲师,主要研究方向为可证明性安全、密码协议的分析与设计.E2mail:[e-mail]:049026756(2006)0120071207梅其祥1,2,3,何大可1,唐小虎1(1.西南交通大学计算机与通信工程学院,成都610031;2.中国科学院研究生院信息安全国家重点实验室,北京100039;3.中南大学信息工程学院,长沙410075):由带Hash的ElGamal加密与Schnorr签名构成的加密方案尽管从直观上看是抗选择密文攻击的,但以前的证明中或者需要在线知识提取假设,或者只能在更受限制的GenericGroup模型中得以证明,因此,其严格的归约化证明仍然是一个公开问题.作者在GapDiffie2Hellman(GDH)假设下,在RandomOracle模型中,利用了RandomOracleHash函数的特点模仿解密而严格证明了该方案确实达到了这个强安全级别.:加密;选择密文安全性;GapDiffie2Hellman假设;RandomOracle模型;:TP309:A1在公钥密码体制中,攻击者拥有公钥,他可以随便选择明文进行加密,所以一个公钥密码体制起码应该能抗选择明文攻击,但是,攻击者还有机会获得密文,而且还可能利用各种途径来获得解密,为此,公钥密码体制应该不会泄露其他密文的的明文信息,这就要求该密码体制能抗选择密文攻击.抗选择密文攻击密码(CCA2)体制[1]是一种安全性很高的体制.现在它已是被密码学家们普遍接受的概念,研究表明,利用抗选择密文攻击密码体制,可以设计许多安全强度很高的重要的密码协议,如密钥传输,密钥交换,公平交换协议等等[2~4],M.Bellare和P.Rogaway提出的OAEP(1994)[5]体制就成为SET协议的新的加密标准.抗选择密文攻击是当今公钥加密侯选标准的最重要的要求之一,2004年的最新的几个候选标准[6]的原型就是几个重要的抗选择密文攻击公钥加密方案.评价一个加密方案的好坏有很多因素,除了加解密速度和密文长度之外,其安全性是否可以被证明,以及在什么假设和模型下被证明也是重要的因素.因此,对一些高效的且利用已有的攻击方法还未能找出弱点的方案给出严格的归约化证明具有重要的意义.V.Shoup和R.Gennaro[7]曾经试图证明一个高效的加密方案的安全性并以之为基础构造门限加密/解密方案,该方案由带Hash的ElGamal加密[8]和Schnorr签名[9]结合,下面记为TDH0.该方案从直观来说,是抗选择密文攻击的,因为Schnorr签名可以看作是知识证明(proofofknowledge),即证明加密者知道随机数的离散对数,进而知道相应的明文,从而只需考虑Hash的ElGamal加密是抗选择明文攻击的,但是,当V.Shoup和R.Gennaro用知识证明的性质模仿解密时发现,由于需要用到rewinding,而且会由一次rewinding引起另一次rewinding,模仿者的运行时间是指数的,因此不能严格进行证明.我们对TDHO重新进行了分析,在标准的GapDiffie2Hellman假设[10]和RandomOracle模型[11]下,严格证明了它是抗选择密文攻击的.我们之所以能严格证明,是因为我们不是利用知识证明的性质来模仿2006年2月第43卷第1期四川大学学报(自然科学版)JournalofSichuanUniversity(NaturalScienceEdition)Feb.2006Vol.43No.1解密,而是利用了RandomOracleHash函数的性质并借助于DDHOracle来模仿解密.我们的安全性证明为该方案的可供选用性提供了重要的依据.Y.Tsiounis和M.Yung1998年[12]提出了一个加密方案,记为TY,该加密方案是由原始的ElGamal加密(未带Hash)和Schnorr签名结合,并/证明0该方案在决定性Diffie2Hellman假设下是抗选择密文攻击的,但是,正如V.Shoup和R.Gennaro所指出的,他们的证明是非标准的,因为他们需要用在线知识提取假设,即,提取知识不需利用Rewinding,而这个假设是非标准的,否则,若使用标准的知识提取的性质,如前所述,模仿者的运行时间是指数的.2000年,C.P.Schnorr和M.Jakobsson[13]在更强的GenericGroup模型[14]和RandomOracle模型下证明TY方案的安全性,这种假设模型比单纯的RandomOracle模型更强,因为,在GenericGroup模型下,攻击者只能利用通用算法而不能利用群的特殊的编码特性,虽然在这种模型中能排除一大批攻击,但是,不能排除非通用算法,如指数演算法[15],利用群的特殊的性质来进行攻击;此外,C.P.Schnorr和M.Jakobsson还将ElGamal加密推广成带Hash的ElGamal加密(记为HEG),相对原始的ElGamal加密,推广后的方案有如下优点,首先,原始的ElGamal加密所加密的消息必须是群中的元素,而HEG不需要是群中的元素,而且HEG便于加密长消息,原始的ElGamal加密对于群的选择受到很大的限制,要求决定性Diffie2Hellman问题是难解的,而HEG只要求计算性Diffie2Hellman问题是难解的,带HEG加密与Schnorr签名结合后的方案正是TDHO方案,他们也只能在GenericGroup模型下证明其安全性.而我们在标准的数论假设和RandomOracle模型下给出了证明,虽然,GapDiffie2Hellman(GDH)假设比广为接受的计算性Diffie2Hellman(CDH)假设要强,但该假设有较强的合理性,现在已被普遍认同,一方面,在GenericGroup模型中,对于阶存在大的素数因子的群,其计算性与决定性Diffie2Hell2man问题都是难解的,但不存在从决定性Diffie2Hellman问题到计算性Diffie2Hellman问题的多项式时间归约,也就是说,GapDiffie2Hellman假设是成立的,另一方面,存在这样的特殊的群[16],其决定性Diffie2Hellman问题存在多项式时间算法,但计算性Diffie2Hellman问题是难解的(对于通用算法和非通用算法都是难解的),这时,GapDiffie2Hellman假设等价于计算性Diffie2Hellman(CDH)假设.我们的证明说明用决定性Diffie2Hellman问题易解、计算性Diffie2Hellman问题难解的群来实现时,TDHO是安全的,而GenericGroup模型中的安全性证明只能说明当决定性Diffie2Hellman问题难解时该方案是安全的.22.1公钥密码体制按照可能的攻击目标,可以分为:单向性(OW)安全,由密文不能恢复相应的明文;不可区分性(IND)安全,对已知给定的的两个明文,加密者随机一致的选择其中一个进行加密,攻击者无法从密文中知道是对哪个明文的加密;非延展性(NM)安全,攻击者无法构造与已给密文相关的新密文.这些安全性概念依次加强,即NM比IND强,IND比OW强.按照可能的攻击模型可分为:选择明文(CPA)攻击,攻击者可以先适应性选择明文,获得相应的密文;非适应性选择密文(CCA1)攻击,攻击者除了可以适应性选择明文攻击外,在给定Challenge密文前,还可以选择密文获得相应的解密;适应性选择密文(CCA2)攻击,攻击者的唯一限制就是不可以直接用Chal2lenge密文获得相应的明文,即还可以在给定Challenge密文,选择密文获得相应的解密.同时考虑攻击目标和攻击模型,可以获得不同的安全,其中最重要的是IND2CCA2和NM2CCA2安全,而二者被证明是等价的[17],所以通常所说的选择密文安全是指IND2CCA2安全.2.2CDH(Computed2Diffie2Hellman)假设:被随机地给定gx,gy,攻击者计算gxy在计算上不可行.GDH(GapDiffie2Hellman)假设:攻击者的目标也是被随机地给定gx,gy,计算gxy,但攻击者还可以选择gA,gB,gC,询问gC是否等于gAB(即借助于DDHOracle),攻击者实现计算gxy的目标在计算上不可行.这个假设由T.Okamoto和D.Pointscheval2001年[10]正式提出.特别地,当DDH问题易解时,GDH假设72四川大学学报(自然科学版)第43卷等价于CDH假设.2.3RandomOracle在RandomOracle模型中,将密码学Hash函数看作是理想的,用定义域内的某个数询问该Hash函数时,从值域内随机选取一个值作为应答,但若相同的数询问时,用相应的相同值进行应答,而不同的值进行询问时,应答值是完全彼此独立的.由于将Hash函数看作是理想的,在RandomOracle模型中被证明为安全的方案,用实际的密码学Hash函数实现时,不一定是可证明性安全的.但是,这种模型中被证明的方案比那些根本得不到证明的方案被普遍认为好得多,实践中的大多数可证明方案都只能在这种模型中证明.3系统的建立:设G为阶为素数q的循环群,生成元为g,另有两个Hash函数H:Gy{0,1}n,Hc:G@{0,1}n@GyZq,它们在安全性证明时被视为RandomOracle函数.密钥产生:随机选取xIZq,计算h=gx,公私钥对为(h,x);加密:为对mI{0,1}n加密,加密算法随机选取rIZq,sIZq,计算u=gr,c=H(hr)Ým,w=gs,e=Hc(u,c,w),f=s+er,密文为7=(u,c,e,f);解密:首先,解密算法验证/签名0合法性:计算w=gf/ue,验证e=Hc(u,c,w)是否成立,若不成立,输出/@0;否则,计算m=H(ux)Ýc,输出m.44.1为了便于理解,我们先给出直观的分析.该方案可以从两个角度来理解,一个角度是将他看作是(带Hash的)ElGamal加密与对随机数的非交互零知识证明,从这个角度理解时,直观地,该方案是抗选择密文攻击的,因为知识证明是证明知道r,从而知道hr,m,因此,就只需证明抗选择明文攻击,这在RandomOracle模型中是易证的,但是,V.Shoup和R.Gennaro(98,02)指出,当要严格进行证明时,模仿者要模仿解密时,需要用到知识提取,而知识提取需要用到rewinding,而且在这里会由一次rewinding引起另一次rewinding,从而模仿者的运行时间是指数的,因此不能严格进行证明;从另一个角度,该方案可以看作是HEG(HashedElGamal)密钥封装机制与关于公钥u=gr的一次性Schnorr签名的结合,其中HEG方案指由封装C=u(=gr)和解封装K=H(hr)组成(当群G的阶不是素数时,取K=H(ur,hr)),该封装机制在RandomOracle模型和GDH假设下可被证明抗选择密文攻击[18],而抗选择密文攻击的密钥封装机制与抗选择密文攻击的私钥密码系统复合后的方案可以抗选择密文攻击,而抗选择密文攻击的私钥系统可以用抗选择明文攻击的私钥系统与抗存在性伪造攻击的消息认证码结合来实现,这种实现具体到HEG方案正是DHIES方案[19],而TDHO实质上可以看作是将DHIES方案中的消息认证码替换为一次性签名,使得一次性签名起到DHIES中的消息认证码的作用,因而这里的方案可以抗选择密文攻击.由Ran2domOracle的性质,当rXrcmod(ord(G))时,由于群G的阶是素数,有hrcXhr,即使知道了H(hr),不用hr询问HOracle,H(hr)仍然是随机的(R.CramerandV.Shoup在文[13]中证明HEG封装机制的安全性时,正是利用了这个特性,当群G的阶不是素数时,若(u=gr