密码学原理与实践(第三版)冯登国 课后习题答案

HomeworkofCryptographyTonyZhuDecember20,20101ClassicalCryptography1.21(c)AneCipherSolution:Sinceintheanecryptosystemonly(26)26=312casesforkeyK=(a;b),listallthecasesbrutallywiththehelpofcomputerandscanquickly,Ifoundonlyonecaseseemsmeaningful:ocanadaterredenosaieuxtonfrontestceintdefleuronsglorieuxcartonbrassaitporterlepeeilsaitporterlacroixtonhistoireestuneepopeedesplusbrillantsexploitsettavaleurdefoitrem-peeprotegeranosfoyersetnosdroitsAfterbreakingthelongsentence,IfounditshouldbetheFrenchversionofCanadanationalanthem:OCanadaTerredenosa¨ıeuxTonfrontestceintdefleuronsglorieux!Cartonbrassaitporterl’´ep´eeIlsaitporterlacroix!Tonhistoireestune´epop´eeDesplusbrillantsexploitsEttavaleur,defoitremp´eeProt´egeranosfoyersetnosdroits1.221Proof.(a)Obviouslyinthecasep1p20;q1q20,thesump1q1+p2q2ismaximized.SupposeS=Pni=1piq0iismaximized,andifthereexistsijsuchthatq0iq0j,permutethepositionsofthetwonumbersand,accordingtothestatementoflastparagraph,wegetS0=P0hnh,i;jphq0h+piq0j+pjq0iS,contradicts.SotheonlyarrangementforSisq01:::q0n.v2Shannon’sTheory2.2Proof.P=C=K=f1;:::;ng:8x2P;8y2CPr[Y=y]=Xk2KPr[K=k]Pr[x=dk(y)]=1=nsoPr[xjy]=Pr[x]Pr[yjx]Pr[y]=Pr[x]1n1n=Pr[x]thatisthisLatinSquareCryptosystemachievesperfectsecrecyprovidedthatev-erykeyisusedwithequalprobability.v2.3Proof.Similarlyas(2.2).v2.5Proof.AccordingtoTheorem2.4,thiscryptosystemprovidesperfectsecrecyieverykeyisusedwithequalprobability1=jKj,andforeveryx2Pandy2C,thereisuniquekeyk2K,suchthaty=ek(x).2Duetoperfectsecrecy,wehavePr[xjy]=Pr[x]=)Pr[x]Pr[yjx]Pr[y]=Pr[x]=)Pr[y]=Pr[yjx]=Prek(x)=y[K=k]=1=jKj:thatiseveryciphertextisequallyprobable.v2.11Proof.(Perfectsecrecy)H(PjC)=H(P)).H(PjC)=Xy2CXx2PPr[y]Pr[xjy]log2Pr[xjy]=Xy2CXx2PPr[y]Pr[x]log2Pr[x]=H(P)Xy2CPr[y]=H(P):(H(PjC)=H(P))Perfectsecrecy).AccordingtoTheorem2.7,H(P;C)H(P)+H(C)withequalityiPandCareindependentrandomvariables.soH(PjC)=H(P)=)H(P;C)=H(P)+H(C)=)PandCareindependentrandomvariables=)8x2P;8y2C;Pr[xjy]=Pr[x];thatisthecryptosystemachievesperfectsecrecy.v2.123Proof.WehaveH(K;P;C)=H(PjK;C)+H(K;C)=H(K;C);soH(K;P;C)H(P;C)=)H(K;C)H(P;C)=)H(KjC)=H(K;C)H(C)H(P;C)H(C)=H(PjC):v2.13Solution:H(P)=12+13log23+16log261:45915:H(K)=log231:58496:Pr[1]=2/9Pr[2]=5/18Pr[3]=1/3Pr[4]=1/6H(C)1:95469:H(KjC)=H(K)+H(P)H(C)1:08942:Pr[K1j1]=3/4Pr[K2j1]=0Pr[K3j1]=1/4Pr[K1j2]=2/5Pr[K2j2]=3/5Pr[K3j2]=0Pr[K1j3]=1/6Pr[K2j3]=1/3Pr[K3j3]=1/2Pr[K1j4]=0Pr[K2j4]=1/3Pr[K3j4]=2/3H(PjC)1:08942:2.14Solution:H(K)=log2216;H(P)=log226;H(C)=log226;H(KjC)=H(K)+H(P)H(C)=log22167:75489:Itiseasytoevaluate:H(KjP;C)=log2123:58496:42.19Proof.AkeyintheproductcipherS1S2hastheform(s1;s2),wheres1;s22Z26,e(s1;s2)(x)=x+(s1+s2):ButthisispreciselythedefinitionofakeyintheShiftCipher.Further,theproba-bilityofakeyinS1S2equals25Pi=0126pi=12625Pi=0=126;whichisalsotheprobabilityofakeyintheShiftCipher.ThusS1S2istheShiftCipher.v2.20Proof.(a)Similarlyas(2.19).(b)ThenumberofkeysinS3equals26lcm(m1;m2).FormthefollowingfactwecanseethatthekeysinS1S2arelesserwhenm1.0(modm2).Noticem2m1;m1.0(modm2)=)m1+m22m1m2gcd(m1;m2)m2=l;wherel,lcm(m1;m2)theequationbelow,whichessentiallygivestherepresentationofthekeysofprod-uctcryptosystemS1S2,would’talwayshasasolution(K1;K2)=(x1;:::;xm1;y1;:::;ym2)2K1K2;foranyselectedkeyK=(z1;:::;zl)2K3;0BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB@Im1Im2Im2::::::Im2Im1Im21CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCA0BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB@x1:::xm1y1:::ym21CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCA=0BBBBBBBBBBBBBBBBBBB@z1::::::zl1CCCCCCCCCCCCCCCCCCCA;becausethecoecientmatrix’scolumnnumberislessthantherownumber.Con-clusively,theremustexistkeyK2K3thatnotinK1K2:v3TheRSACryptosystemandFactoringIntegers5.25Proof.(a)ri=qi+1ri+1+ri+2ri+1+ri+22ri+2:(b)(c)From(a),mlog2a+1logalogb:v5.3Solution:(a)1716(mod101):(b)35711075(mod1234):(c)312511844(mod9987):5.4Solution:8931357=3:5.5Solution:It’seasytoseethat1(x;y;z)=70x+21y+15z(mod105):So1(2;2;3)=17:5.6Solution:Similarlywehave1(x;y;z)=(132627)x+(25227)y+(142526)z(mod252627):So1(12;9;23)=470687:5.7Solution:Similarlywehave1(x;y)=(50101)x+(5199)y(mod99101):13161(mod99);15127(mod101):So8:13x4(mod99)15x56(mod101)()8:x46(mod99)x98(mod101)=)x=7471:65.9Proof..1(modp);isprimitiveelementmodulop()theorderof2Zpis2q:().1(modp);q1(modp):(Becausetheorderofcouldonlybe2,qor2q.)v5.11Proof.Byshowingx(n)=1(modn);8x2Zn;wecanprovetheencryptionanddecryptionarestillinverseoperationsinthismodifiedcryptosystem.SincewehaveZnZpZq;andtheisomorphismis (h)=(h(modp);h(modq));itonlyneedstoshowx(n)=1(modp);andx(n)=1(modq):x(n)(xp1)q1gcd(p1;q1)(modp)(1)q1gcd(p1;q1)(modp)1(modp):Forqisthesame.Socompletetheproof.vSolution:(b)p=37;q=79;b=7:Modifiedcryptosystem.(n)=468;a=67:Originalcryptosystem.(n)=2808;a=2407:5.13Proof.(a)AgainusetheisomorphismZnZpZq;andnotethatxp11(modp)andxq11(modq)forallx,0;wegetZn!ZpZq!Znyd(modn)!(yd(modp);yd(modq))!Mpqxp+Mqpxq(modn)=(ydp(modp);ydq(modq))=(xp;xq)7socompletetheproof.(b)p=1511;q=2003;andd=1234577.Aftersomecalculation,wegetdp=907;dq=1345;Mp=