可证明安全性理论与方法研究

Vol.16,No.10©2005JournalofSoftware1000-9825/2005/16(10)1743∗+((),100080)ResearchonTheoryandApproachofProvableSecurityFENGDeng-Guo+(StateKeyLaboratoryofInformationSecurity(InstituteofSoftware,TheChineseAcademyofSciences),Beijing100080,China)+Correspondingauthor:Phn:[phone],Fax:[phone],E-mail:[e-mail],(10):1743−1756.DOI:10.1360/jos161743Abstract:Thispaperpresentsasurveyonthetheoryofprovablesecurityanditsapplicationstothedesignandanalysisofsecurityprotocols.Itclarifieswhattheprovablesecurityis,explainssomebasicnotionsinvolvedinthetheoryofprovablesecurityandillustratesthebasicideaofrandomoraclemodel.Italsoreviewsthedevelopmentandadvancesofprovablysecurepublic-keyencryptionanddigitalsignatureschemes,intherandomoraclemodelorthestandardmodel,aswellastheapplicationsofprovablesecuritytothedesignandanalysisofsession-keydistributionprotocolsandtheiradvances.Keywords:provablesecurity;cryptosystem;securityprotocol;randomoraclemodel;standardmodel:,:,,RO(randomoracle),,.:;;;RO(randomoracle);:TP309:A:(1),;,10,;(2),,;.:(1),;(2),,.?(,∗SupportedbytheNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.G1999035802((973));theNationalNaturalScienceFoundationofChinaunderGrantNo.60273027():(1965),,,,,,.1744JournalofSoftware2005,16(10)).,“”,“”,[1].,“”:.,,;,“”,“(atomicprimitives,,)”,,“”;(),“”.,,.,“”“”.,,,.:“”,;,,.,,“”:“”.:();,,(DES-ECB).,.,:,.,,,;,,:,,,“Bugs”.:,,(,);“”,..,RSA.RSAP,RSAP,P:P()A,A“”,Q,QRSA.:RSA,Q,P.,,“(PPT)”A,“”.“”,.Goldreich[2].1.1,,,.(),..1().3:(1)K.1k,K(kp,ks),,K.k,k.(2)Σ.m(kp,ks),Σσ,Σ.(3)V.σmkp,Vσmkp,:1745,V.(K,Σ,V),A:A3:();();-().,,,(),.A:.“”,A(,,),.2().(K,Σ,V),A]1),,(:)(),(),1(),Pr[(=←←=ΣσσmkVkAmKkkSuccppkspAsk,.,AOracleskΣ(“”),“”,(m,σ).skΣ3().3:(1)K.1k,K(kp,ks),,K.(2)E.mkp,EmC.E,),;,(rmkEpr.(3)D.Cks,DCm,.,(one-wayness,OW):,AM×ΩE(,M,Ω),]));,(,(:)1(),Pr[(mrmkEkAKkkSuccppkspA=←=.,.4().(K,E,D),1]),,,(:);,(),(),,(),1(),Pr[(2102110−==←←×=bcsmmArmkEckAsmmKkkadvbppkspA,.,A=(A1,A2)2(PPT),(b,r).:(,),.(Oracle):(1)CPA(),;(2)PCA(),Oracle,(m,c);(3)CCA(),Oracle,Oracle,(),Oracle.(,CCA1CCA2).,4,Oracle..1746JournalofSoftware2005,16(10)2RO2080,Goldwasser,MicaliRivest,[3,4].,,,,.2090“(practice-orientedprovable-security)”,BellareRogawayRO(randomoracle,)[5],:,,;:“(concretesecurityorexactsecurity)”,,,.,;CanettiGoldreich[6],(standardmodel).CanettiGoldreich:RO“hash”;,,RO,..,Goldreich,RO,,,RO,.Canetti,RO,;,.Pointcheval[7],RO.[6],“”;RO,;(),“”(hash),RO.,ROhash,(SmartCards),RO,[2].,,RO,“”.,,[3,4],,,.,,RO,:RO,RO.2.1RO[5]:RandomOracle,“”.,P,RO()PR,“”hOracle().,.,,RO,“”:RO.Π(h“”),P,:(1)ΠRO,RO()OracleR;(2)ROΠP;(3)PΠ;:1747(4)hR.,h“”:,;,Oraclehash(2,),.,“”.,h“”Π(,).,h:,;“”.[5],h,()hashh.RO/,CBC-MAC,hash,(DES).2.2,().RO:,PPT();S()(RO),Oracle();().RO.RO.,,“(concreteorexacttreatmentofsecurity)”,“”.():“DES(),236,t,t…”,,.1:[8]CBCMAC,:tqMAC,MACε+(3q2n2+l)/2.,l,n,ε(O(nql)).,,.“”,“”,.2.3RO2.3.11RO,RO.PPTg:1k,(E,D),,D,g.:)(xEyR←,:)(yDxR←.4,ROCPA,CP-()(F,A1),).(2/1]),,(:)(};1,0{);(),();1(),(;2Pr[1110nbmEAmEbEFmmgDERRbRRkµαα+≤=←←←←←∞,ROracle,{0,1}*{0,1}∞,2∞Oracle,“∞”,“”,µ(n).CCA:ARS-,A=(F,A1),OracleROracleDR;F10,mm,A1α,OracleDRα(),A11748JournalofSoftware2005,16(10).gROCCA,RS-(F,A1),:).(2/1]),,,(:)(};1,0{);(),();1(),(;2Pr[10,1,10nbmmEAmEbEFmmgDERRRDRbRDRkµαα+≤=←←←←←∞Bellare[5]ROCCA,,,RO.Bellare,1994OAEP[9],CCA2,RSA.:Padding,OAEPG,H(x,r)=x⊕G(r)||r⊕H(x⊕G(r)).,x,r;EG,H(x)=f(OAEPG,H(x,r)).,f(RSA).“”.2.3.2Bellare[5].f“”,RSA,RSA.[10]RSA:PSS,RSA.PSS,.,,RSA.,.,.,,,FiatShamirRO[11],.,[12]:Fiat-Shamir[11],Fiat-Shamir(E-swap),.[13−15].[15]Diffie-Hellman(CDH),SchnorrEDL,.,,[13]RO,Folklore,,ElGamalMEG.,Oracle(replay),RO,()Oracle(),,(DLP)..3[3,4].,,,.[16]hash,hash;[17]RSA.hashRO.[17]hashRO.3.1paddingRSARSApadding,().[16]:paddingRSARSA.hashRandomOracle,paddingµ;padding..:17493.2Oracle(Hash-and-Sign)[17]RSA(RSA*,nZsn∈,re=smodn(e,r)(e1)),,Hash-and-Sign.RSA,*,nZspqn∈=.:e=h(R,M),σsne;.,[17]hashRO,hash()h(R,M).,R.:RO,OracleRO,hRSA.[17]“”RO,([17]),,,[17].3.3Cramer-ShoupCramerShoup[18]1998,Diffie-Hellman.(),,.G*pZq,p,q,q|p−1,g1g2G.),(21xxx=,),(21yyy=,),(21zzz=0q−1;),(21ggg=,),(21uuu=G;r1q−1,),(2121xxxggg=,),(2121rxrxrxggg=.H.Alice3x,y,z,3,xgc=,ygd=zge=.:m∈G,Bobr,rgu11=,rgu22=,mewr=,),,(21wuuHh=rhrdcv=.Bob),,,(21vwuuAlice.:),,,(21vwuu,Alice),,(21wuuHh=,,hyxu+v(rhrrhyrxhyxdcgu==++).v,Alice;,Alice:wuz,rrxzegu==,mewr=,m.Cramer-Shoup,4,Diffie-Hellman.,Cramer-ShoupElGamal,.ElGamal,Cramer-Shoup,,v,ux+hy=v.,Oracle,.4(SDK),.,,,(SKD).SKD(),.1978NS[19],.,10SKD.,“”:;;.,NeedhamSchroeder:,,.,[20]NSbug,.:,.Burrows,AbadiNeedham[21],BAN.1750JournalofSoftware2005,16(10)Bug,;,,“”,,.SKDBellareRogaway[5].,,,Bug,,SKD.,,,..SKD3:(1).,;(2).;(3).(forwardsecrecy).,,,SKD,,.4.1BR4.1.1BRBellareRogaway19931995SKD[22,23].,SKD,BR.,,().,..I={0,1,2,…,N}(0S),E..P=(Π,ψ,LL),,Π,ψS,LL,[23]..E(),,OracleSji,Πsji,ψ,Sji,ΠijS,sji,ψSi,j.E5Oracle:(SendPlayer,i,j,s,x);(SendS,i,j,s,x);(Reveal,i,j,s);(Corrupt,i,K);(Test,i,j,s).4Oracle,E,,(Test,i,j,s),“”Oracle..(v