密码学与网络安全 (Behrouz A.Forouzan 著) 清华大学出版社 课后答案 123页

'课后答案网您最真诚的朋友www.hackshp.cn网团队竭诚为学生服务，免费提供各门课后答案，不用积分，甚至不用注册，旨在为广大学生提供自主学习的平台！课后答案网：www.hackshp.cn视频教程网：www.efanjy.comPPT课件网：www.ppthouse.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER1Introduction(SolutiontoPracticeSet)ReviewQuestions1.Thethreesecuritygoalsareconfidentiality,integrity,andavailability.khdaw.comßConfidentialitymeansprotectingconfidentialinformation.ßIntegritymeansthatchangestotheinformationneedtobedoneonlybyauthorizedentities.ß课后答案网Availabilitymeansthatinformationneedstobeavailabletoauthorizedenti-ties.www.hackshp.cn2.ßInapassiveattack,theattacker’sgoalisjusttoobtaininformation.Thismeansthattheattackdoesnotmodifydataorharmthesystem.Examplesofpassiveattacksaresnoopingandtrafficanalysis.ßAnactiveattackmaychangethedataorharmthesystem.Attacksthatthreatentheintegrityandavailabilityareactiveattacks.Examplesofactiveattacksaremodification,masquerading,replaying,repudiation,anddenialofservice.3.Wementionedfivesecurityservices:dataconfidentiality,dataintegrity,authenti-cation,nonrepudiation,andaccesscontrol.ßDataconfidentialityistoprotectdatafromdisclosureattack.ßDataintegrityistoprotectdatafrommodification,insertion,deletion,andreplaying.ßAuthenticationmeanstoidentifyandauthenticatethepartyattheotherendoftheline.ßNonrepudiationprotectsagainstrepudiationbyeitherthesenderorthereceiverofthedata.ßAccesscontrolprovidesprotectionagainstunauthorizedaccesstodata.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！24.Eightsecuritymechanismswerediscussedinthischapter.encipherment,dataintegrity,digitalsignature,authenticationexchange,trafficpadding,routingcon-trol,notarization,andaccesscontrol.ßEnciphermentprovidesconfidentiality.ßThedataintegritymechanismappendsashortcheckvaluetothedata.Thecheckvalueiscreatedbyaspecificprocessfromthedataitself.ßAdigitalsignatureisameansbywhichthesendercanelectronicallysignthedataandthereceivercanelectronicallyverifythesignature.ßInauthenticationexchange,twoentitiesexchangesomemessagestoprovetheiridentitytoeachother.ßTrafficpaddingmeansinsertingsomebogusdataintothedatatraffictothwarttheadversary’sattempttousethetrafficanalysis.ßRoutingcontrolmeansselectingandcontinuouslychangingdifferentavail-khdaw.comableroutesbetweenthesenderandthereceivertopreventtheopponentfromeavesdroppingonaparticularroute.ßNotarizationmeansselectingathirdtrustedpartytocontrolthecommunica-课后答案网tionbetweentwoentities.ßAccesscontrolusesmethodstoprovethatauserhasaccessrighttothedataorresourcesownedbyasystem.www.hackshp.cn5.ßCryptography,awordwithorigininGreek,means“secretwriting.”Weusedthetermtorefertothescienceandartoftransformingmessagestomakethemsecureandimmunetoattacks.ßSteganography,awordwithorigininGreek,means"coveredwriting."Stega-nographyreferstoconcealingthemessageitselfbycoveringitwithsome-thingelse.Exercises6.a.Aregularmailguaranteesnosecurityservices.Itisthebest-effortdeliveryser-vice.Themailcanbelost,alteredinthemail,openedbysomebodyotherthantheintendedrecipient.b.Aregularmailwithdeliveryconfirmationcanonlyshowthatthemailhasbeendelivered.Thiscanonlygivepeaceofmindtothesenderthatthepacketisnotlost.However,sincethereisnosignaturefromtherecipient,itdoesnotguaran-teeanyofthesecurityservices.c.Aregularmailwithdeliveryconfirmationandtherecipientsignaturecanpro-videnonrepudiationserviceonlyatthemaillevel,notthecontentslevel.Inotherwords,therecipientofthemailcannotdenythatshehasnotreceivedthemail,butshecandenythatthemailcontainedsomespecificinformation.Forkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！3example,ifAlicesendsamailwith$100cashinsidetoBobviathistypeofmail,Bobcannotdenythathehasreceivedthemail,buthecandenythatthemailcontainedsomecashinside.Insomecases,thesenderisanauthorityanditisenoughthatBobacceptshehasreceivedthemail.Inthiscase,ifthereisadispute,thecourtacceptthetestimonyofthesenderaboutthecontents.d.Acertifiedmailisactuallythesameastheregularmailwithdeliveryconfirma-tionandtherecipientsignature.e.Amailcanbeinsured.However,thisisnotsecurityinthesensewearetalkinginthischapter.Securedmailcanonlyprovidecompensationifthemailislost.f.Aregisteredmailisdifferentfromallofthepreviousdeliverymethods.Areg-isteredmailiscarriedbythepostofficeunderthetightsecurity.Thismeansthattheconfidentialityandintegrityofthemailisguaranteed.Sincearegisteredmailnormallyincludesthesignedreceipt,thenonrepudiationisalsoguaran-teed.However,nonrepudiationisonlyatthemaillevel,notthecontentlevel.khdaw.comTherecipientoftheregisteredmailcannotdenythatthemailhasbeendeliv-ered,butitcandenythatitcontainedaspecialmessageoranitemofsomevalue.7.课后答案网a.Thisissnooping(attacktotheconfidentialityofstoreddata).Althoughthecon-tentsofthetestisnotconfidentialonthedayofthetest,itisconfidentialbeforethetestday.www.hackshp.cnb.Thisismodification(attacktotheintegrityofdata).Thevalueofthecheckischanged(from$10to$100).c.Thisisdenialofservice(attacktoavailability).Sendingsomanye-mailsmaycrashtheserverandtheservicemaybeinterrupted.8.a.Thisprovidesaccesscontrolmechanism.Theprocessistoprovethatthestu-denthasrighttoaccesstheschoolresources.b.Thiscanprovideroutingcontrol.Theschoolmaybedoingthistopreventastu-dentfromeavesdroppingonaparticularroute.c.Thiscanbeauthenticationexchangemechanism.Theprofessorneedstoauthenticatethestudentbeforesendingthegrade.Thepreassignedidentifica-tionisasecretbetweenthestudentandtheprofessor.d.Themechanismissimilartodigitalsignature.Itcanbeusedfortwopurposes.Ifthesignatureofthecustomerischeckedagainstasignatureonthefile,itcanprovideauthentication.Thesignatureonthewithdrawaldocumentdefinitelyisservedasthenonrepudiation.Thecustomercannotlaterdeniesthatshehasnotreceivedthecash.9.a.Thisissteganography.Theanswerstothetesthasnotbeenchanged;theyhavebeenonlyhidden.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！4b.Thisiscryptography.Thecharactersinthemessagearenothidden;theyarereplacedbyanothercharacters.c.Thisissteganography.Thespecialinkhidestheactualwritingonthecheck.d.Thisissteganography.Thewatermarkshidestheactualcontentsofthethesis.10.Asignatureonadocumentislikeadigitalsignatureonamessage.Itprotectstheintegrityofthedocument,itprovidesauthentication,anditprotectsnon-repudia-tion.khdaw.com课后答案网www.hackshp.cnkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER2MathematicsofCryptographyPartI(SolutiontoPracticeSet)ReviewQuestions1.ThesetofintegersisZ.Itcontainsallintegralnumbersfromnegativeinfinitytokhdaw.compositiveinfinity.ThesetofresiduesmodulonisZn.Itcontainsintegersfrom0ton−1.ThesetZhasnon-negative(positiveandzero)andnegativeintegers;thesetZnhasonlynon-negativeintegers.TomapanonnegativeintegerfromZtoZn,weneedtodividetheintegerbynandusetheremainder;tomapanegativeintegerfrom课后答案网ZtoZn,weneedtorepeatedlyaddntotheintegertomoveittotherange0ton−1.2.Wementionedfourproperties:www.hackshp.cnßProperty1:ifa|1,thena=±1.ßProperty2:ifa|bandb|a,thena=±b.ßProperty3:ifa|bandb|c,thena|c.ßProperty4:ifa|banda|c,thena|(m×b+n×c),wheremandnarearbi-traryintegers.3.Thenumber1isanintegerwithonlyonedivisor,itself.Aprimehasonlytwodivi-sors:1anditself.Forexample,theprime7hasonlytwodivisor7and1.Acom-positehasmorethantwodivisors.Forexample,thecomposite42hasseveraldivisors:1,2,3,6,7,14,21,and42.4.Thegreatestcommondivisoroftwopositiveintegers,gcd(a,b),isthelargestpos-itiveintegerthatdividesbothaandb.TheEuclideanalgorithmcanfindthegreat-estcommondivisoroftwopositiveintegers.5.AlinearDiophantineequationoftwovariablesisoftheformax+by=c.Weneedtofindintegervaluesforxandythatsatisfytheequation.Thistypeofequationhaseithernosolutionoraninfinitenumberofsolutions.Letd=gcd(a,b).Ifddoesnotdividecthentheequationhavenosolitons.Ifddividesc,thenwehaveaninfi-nitenumberofsolutions.Oneofthemiscalledtheparticularsolution;therest,are/.calledthegeneralsolutions.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！26.ThemodulooperatortakesanintegerafromthesetZandapositivemodulusn.Theoperatorcreatesanonnegativeresidue,whichistheremainderofdividingabyn.Wementionedthreepropertiesforthemodulooperator:ßFirst:(a+b)modn=[(amodn)+(bmodn)]modnßSecond:(a−b)modn=[(amodn)−(bmodn)]modnßThird:(a×b)modn=[(amodn)×(bmodn)]modn7.Aresidueclass[a]isthesetofintegerscongruentmodulon.Itisthesetofallinte-gerssuchthatx=a(modn).Ineachset,thereisoneelementcalledtheleast(non-negative)residue.ThesetofalloftheseleastresiduesisZn.8.ThesetZnisthesetofallpositiveintegerbetween0andn−1.ThesetZn∗isthesetofallintegersbetween0andn−1thatarerelativelyprimeton.EachelementinZnhasanadditiveinverse;eachelementinZn∗hasamultiplicativeinverse.TheextendedEuclideanalgorithmisusedtofindthemultiplicativeinversesinZn∗.khdaw.com9.Amatrixisarectangulararrayofl×melements,inwhichlisthenumberofrowsandmisthenumberofcolumns.Ifamatrixhasonlyonerow(l=1),itiscalledarowmatrix;ifithasonlyonecolumn(m=1),itiscalledacolumnmatrix.Asquarematrixisamatrixwiththesamenumberofrowsandcolumns(l=m).Thedeterminantofasquarematrix课后答案网Aisascalardefinedinlinearalgebra.Themultipli-cativeinverseofasquarematrixexistsonlyifitsdeterminanthasamultiplicativeinverseinthecorrespondingset.www.hackshp.cn10.Alinearequationisanequationinwhichthepowerofeachvariableis1.Alinearcongruenceequationisalinearequationinwhichcalculationsaredonemodulon.Anequationoftypeax=b(modn)canbesolvedbyfindingthemultiplicativeinverseofa.Asetoflinearequationscanbesolvedbyfindingthemultiplicativeinverseofamatrix.Exercises11.a.Itisfalsebecause26=2×13.b.Itistruebecause123=3×41.c.Itistruebecause127isaprime.d.Itistruebecause21=3×7.e.Itisfalsebecause96=25×3.f.Itisfalsebecause8isgreaterthan5.12.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！3a.gcd(88,220)=44,asshowninthefollowingtable:qr1r2r0882208822208844288440440b.gcd(300,42)=6,asshowninthefollowingtable:qr1r2r73004267426060khdaw.comc.gcd(24,320)=8,asshowninthefollowingtable:qr1r2r0243202413320248课后答案网3248080www.hackshp.cnd.gcd(401,700)=1(coprime),asshowninthefollowingtable:qr1r2r04017004011700401299140129910222991029511029571395741743143133101013.a.gcd(a,b,16)=gcd(gcd(a,b),16)=gcd(24,16)=8b.gcd(a,b,c,16)=gcd(gcd(a,b,c),16)=gcd(12,16)=4c.gcd(200,180,450)=gcd(gcd(200,180),450)=gcd(20,450)=10d.gcd(200,180,450,600)=gcd(gcd(200,180,450),600)=gcd(10,600)=10khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！414.a.gcd(2n+1,n)=gcd(n,1)=1b.gcd(201,100)=gcd(2×100+1,100)=1gcd(81,40)=gcd(2×40+1,40)=1gcd(501,250)=gcd(2×250+1,250)=115.a.gcd(3n+1,2n+1)=gcd(2n+1,n)=1b.gcd(301,201)=gcd(3×100+1,2×100+1)=1gcd(121,81)=gcd(3×40+1,2×40+1)=1khdaw.com16.a.Weusethefollowingtable:qr1r2rs1s2st1t2t课后答案网0474101010174301−110114311−1201−1www.hackshp.cn3310−12−71−14102−7−14↑↑↑gcdstgcd(4,7)=1→(4)(2)+(7)(−1)=1b.Weusethefollowingtable:qr1r2rs1s2st1t2t6291423910101−614239301−11−671339301−114−67−9730−1147−97↑↑↑gcdstgcd(291,42)=3→(291)(−1)+(42)(7)=3khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！5c.Weusethefollowingtable:qr1r2rs1s2st1t2t084320841010103320846801−310118468161−3−401−1468164−34−191−15416404−1980−15−2140−19805−21↑↑↑gcdstgcd(84,320)=4→(84)(−19)+(320)(5)=4d.Weusethefollowingtable:khdaw.comqr1r2rs1s2st1t2t6400604010101−6160402001−11−67课后答案网2402001−13−67−20200−147−20↑↑↑www.hackshp.cngcdstgcd(400,60)=20→(400)(−1)+(60)(7)=2017.a.22mod7=1b.291mod42=39c.84mod320=84d.400mod60=4018.a.(273+147)mod10=(273mod10+147mod10)mod10=(3+7)mod10=0mod10b.(4223+17323)mod10=(4223mod10+17323mod10)mod10=(3+3)mod10=6mod10c.(148+14432)mod12=(148mod12+14432mod12)mod12=(4+8)mod12=0mod12d.(2467+461)mod12=(2467mod12+461mod12)mod12=(7+5)mod12=0mod12khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！619.a.(125×45)mod10=(125mod10×45mod10)mod10=(5×5)mod10=5mod10b.(424×32)mod10=(424mod10×32mod10)mod10=(4×2)mod10=8mod10c.(144×34)mod10=(144mod10×34mod10)mod10=(4×4)mod10=6mod10d.(221×23)mod10=(221mod10×23mod10)mod10=(1×3)mod10=3mod1020.a.amod10=(an+…+a1+an×101×100)mod10=[(an)mod10+…+(a1)mod10+an×101×100mod10]mod10=[0+…+0+a0mod10]=a0mod10b.amod100=(an+…+a1+akhdaw.comn×101×100)mod10=[(an)mod100+…+(a1)mod100+an×101×100mod10]mod10=[0+…+0+(a1)mod100+a1×100mod100]=(a1)mod100+a1+a1×100mod100=[a1×100]mod100.c.Similarly课后答案网amod1000=[a2+a1+a2×101×100]mod1000.21.amod5=(an+…+a1+an×101×100)mod5=[(an)mod5+…+(a1)mod5+an×101×100mod5]mod5www.hackshp.cn=[0+…+0+a0mod5]=a0mod522.amod2=(an×10n+…+a1×101+a0)mod2=[(an×10n)mod2+…+(a1×101)mod2+a0mod2]mod2=[0+…+0+a0mod2]=a0mod223.amod4=(an+…+a1+an×101×100)mod4=[(an)mod4+…+(a1)mod4+an×101×100mod4]mod4=[0+…+0+(a1)mod4+a1+a1×100mod4]=(a1×100)mod424.amod8=(an×10n+…+a2×102+a1×101+a0)mod8=[(an×10n)mod8+…+(a2×102)mod8+(a1×101)mod8+a0mod8]mod8=[0+…+0+(a1×102)mod8+(a1×101)mod8+a0mod8]=(a2×102+a1×101+a0)mod425.amod9=(an+…+a1+an×101×100)mod9=[(an)mod9+…+(a1)mod9+an×101×100mod9]mod9=(an+…+a1+a0)mod926.amod7=(an+…+a1+an×101×100)mod7=[(an)mod7+…+(a1)mod7+an×101×100mod7]mod7=…+a5×(−2)+a4×(−3)+a3×(−1)+a2×(2)+a1×(3)+a0×(1)]mod7Forexample,631453672mod13=[(−1)6+(2)3+(1)1+(−2)4+(−3)5+(−1)3+(2)6+(3)7+(1)2]mod7=3mod7khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！727.amod11=(an+…+a1+an×101×100)mod11=[(an×10n)mod11+…+(a1×101)mod11+a0mod11]mod11=…+a3×(−1)+a2×(1)+a1×(−1)+a0×(1)]mod11Forexample,631453672mod11=[(1)6+(−1)3+(1)1+(−1)4+(1)5+(−1)3+(1)6+(−1)7+(1)2]mod11=−8mod11=5mod1128.amod13=(an×10n+…+a1×101+a0)mod13=[(an)mod13+…+(a1)mod13+an×101×100mod13]mod13=…+a5×(4)+a4×(3)+a3×(−1)+a2×(−4)+a1×(−3)+a0×(1)]mod13Forexample,631453672mod13=[(−4)6+(−3)3+(1)1+(4)4+(3)5+(−1)3khdaw.com+(−4)6+(−3)7+(1)2]mod13=3mod1329.a.(A+N)mod26=(0+13)mod26=13mod26=Nb.(A课后答案网+6)mod26=(0+6)mod26=6mod26=Gc.(Y−5)mod26=(24−5)mod26=19mod26=Twww.hackshp.cnd.(C−10)mod26=(2−10)mod26=−8mod26=18mod26=S30.(0,0),(1,19),(2,18),(3,17),(4,16),(5,15),(6,14),(7,13),(8,12),(9,11),(10,10)31.(1,1),(3,7),(9,9),(11,11),(13,17),(19,19)32.a.Weusethefollowingtable:qr1r2rt1t2t4180382801−411828101−45228108−45−14110825−14194820−1419902019gcdtgcd(180,38)=2≠1→38hasnoinverseinkhdaw.comZ180.若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8b.Weusethefollowingtable:qr1r2rt1t2t25180750117521−252521−2526221026−7710−77180gcdtgcd(180,7)=1→7−1mod180=−77mod180=103mod180.c.Weusethefollowingtable:khdaw.comqr1r2rt1t2t11801324801−1213248361−131483612−13−4课后答案网3361203−415120−415www.hackshp.cngcdtgcd(180,132)=12≠1→132hasnoinverseinZ180.d.Weusethefollowingtable:qr1r2rt1t2t7180241201−72241201−715120−715gcdte.gcd(180,24)=12≠1→24hasnoinverseinZ180.33.a.Wehavea=25,b=10andc=15.Sinced=gcd(a,b)=5dividesc,thereisaninfinitenumberofsolutions.Thereducedequationis5x+2y=3.Wesolvetheequation5s+2t=1usingtheextendedEuclideanalgorithmtogets=1andt=−2.TheparticularandgeneralsolutionsareParticular:x0=(c/d)×s=3y0=(c/d)×t=−6General:x=3+2×ky=−6−5×k(kisaninteger)b.Wehavea=19,b=13andc=20.Sinced=gcd(a,b)=1anddividesc,thereisaninfinitenumberofsolutions.Thereducedequationis19khdaw.comx+13y=20.We若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！9solvetheequation19s+13t=1togets=−2andt=3.Theparticularandgen-eralsolutionsareParticular:x0=(c/d)×s=−40y0=(c/d)×t=60General:x=−40+13×ky=60−19×k(kisaninteger)c.Wehavea=14,b=21andc=77.Sinced=gcd(a,b)=7dividesc,thereisaninfinitenumberofsolutions.Thereducedequationis2x+3y=11.Wesolvetheequation2s+3t=1togets=−1andt=1.TheparticularandgeneralsolutionsareParticular:x0=(c/d)×s=−11y0=(c/d)×t=11General:x=−11+3×ky=11−2×k(kisaninteger)d.Wehavea=40,b=16andc=88.Sinced=gcd(a,b)=8dividesc,thereisankhdaw.cominfinitenumberofsolutions.Thereducedequationis5x+2y=11.Wesolvetheequation5s+2t=1togets=1andt=−2.Theparticularandgeneralsolutionsare课后答案网Particular:x0=(c/d)×s=11y0=(c/d)×t=−22General:x=11+2×ky=−22−5×k(kisaninteger)www.hackshp.cn34.a.Sincegcd(15,12)=3and3doesnotdivide13,thereisnosolution.b.Sincegcd(18,30)=6and6doesnotdivide20,thereisnosolution.c.Sincegcd(15,25)=5and5doesnotdivide69,thereisnosolution.d.Sincegcd(40,30)=10and10doesnotdivide98,thereisnosolution.35.Wehavetheequation39x+15y=270.Wehavea=39,b=15andc=270.Sinced=gcd(a,b)=3dividesc,thereisaninfinitenumberofsolutions.Thereducedequationis13x+5y=90.Wesolvetheequation13s+5t=1:s=2andt=−5.TheparticularandgeneralsolutionsareParticular:x0=(c/d)×s=180y0=(c/d)×t=−450General:x=180+5×ky=−450−13×kTofindanacceptablesolution(nonnegativevalues)forxandy,weneedtostartwithnegativevaluesfork.Twoacceptablesolutionsarek=−35→x=5andy=5k=−36→x=0andy=1836.Ineachcase,wefollowthreestepsdiscussedinSectkhdaw.comion2.4ofthetextbook.若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！10a.Step1:a=3,b=4,n=5→d=gcd(a,n)=1Sinceddividesb,thereisonlyonesolution.Step2:Reduction:3x≡4(mod5)Step3:x−1×4)(mod5)=20=(3b.Step1:a=4,b=4,n=6→d=gcd(a,n)=2Sinceddividesb,therearetwosolutions.Step2:Reduction:2x≡2(mod3)Step3:x−1×2)(mod3)=1xkhdaw.com0=(21=1+6/2=4c.课后答案网Step1:a=9,b=12,n=7→d=gcd(a,n)=1Sinceddividesb,thereisonlyonesolution.Step2:Reduction:9x≡12(mod7)www.hackshp.cnStep3:x0=(9−1×12)(mod7)=(2−1×5)(mod7)=4d.Step1:a=256,b=442,n=60→d=gcd(a,n)=4Sinceddoesnotdivideb,thereisnosolution.37.a.3x+5≡4(mod5)→3x≡(−5+4)(mod5)→3x≡4(mod5)a=3,b=4,n=5→d=gcd(a,n)=1Sinceddividesb,thereisonlyonesolution.Reduction:3x≡4(mod5)x0=(3−1×4)(mod5)=2khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！11b.4x+6≡4(mod6)→4x≡(−6+4)(mod6)→4x≡4(mod6)a=4,b=4,n=6→d=gcd(a,n)=2Sinceddividesb,therearetwosolutions.Reduction:2x≡2(mod3)x−1×2)(mod3)=10=(2x1=1+6/2=4c.9x+4≡12(mod7)→9x≡(−4+12)(mod7)→9x≡1(mod7)a=9,b=1,n=7→d=gcd(a,n)=1khdaw.comSinceddividesb,thereisonlyonesolution.Reduction:9x≡1(mod7)x−1×1)(mod7)=4课后答案网0=(9d.www.hackshp.cn232x+42≡248(mod50)→232x≡206(mod50)a=232,b=206,n=50→d=gcd(a,n)=2Sinceddividesb,therearetwosolutions.Reduction:116x≡103(mod25)→16x≡3(mod25)x−1×3)(mod25)=80=(16x1=8+50/2=3338.a.Theresultofmultiplyingthefirsttwomatricesisa1×1matrix,asshownbelow:23710+4(3+2++7+410+12)mod161012khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！12b.Theresultofmultiplyingthesecondtwomatricesisa3×3matrix,asshownbelow:3462018011118+1101111583524114139.a.ThedeterminantandtheinverseofmatrixAareshownbelow:30A3mod10−17mod10=det(A)=(det(A))=khdaw.com111070A−1=7A−1=+9331课后答案网adj(A)b.MatrixBhasnoinversebecausedet(B)=(4×1−2×1)mod=2mod10,www.hackshp.cnwhichhasnoinverseinZ10.c.ThedeterminantandtheinverseofmatrixCareshownbelow:346113mod10−17mod10C=8det(C)=(det(C))=583322C−1=934123Inthiscase,det(C)=3mod10;itsinverseinZ10is7mod10.ItcanprovedthatC×C−1=I(identitymatrix).40.Althoughwegivethegeneralmethodforeverycaseusingmatrixmultiplication,incasesaandc,thereisnoneedformatrixmultiplicationbecausethecoefficientofy(ina)orx(inc)isactually0inthesetwocases.Thesecasescanbesolvedmucheasier.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！13a.Inthisparticularcase,theanswercanbefoundeasierbecausethecoefficientofyis0inthefirstequation.Thesolutionisshownbelow:−1354xx354+==+21y3y213x2043x=3mod5y=11+3=2y=2mod5b.Thesolutionisshownbelow:−1325xx325khdaw.com+==+46y4y464x2455x=5mod7课后答案网y=11+4=2y=2mod7www.hackshp.cnc.Thesolutionisshownbelow:−1733xx733+==+42y5y425x1236x=6mod7y=50+5=1y=1mod7d.Thesolutionisshownbelow:−1235xx235+==+16y3y163x6555x=5mod8y=72+3=1y=1mod8khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！14khdaw.com课后答案网www.hackshp.cnkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER3TraditionalSymmetric-KeyCiphers(SolutiontoPracticeSet)ReviewQuestions1.Symmetric-keyenciphermentusesasinglekeyforbothencryptionanddecryp-khdaw.comtion.Inaddition,theencryptionanddecryptionalgorithmsareinverseofeachother.2.Traditionalsymmetric-keycipherscanbedividedintotwobroadcategories:sub-stitutionciphersandtranspositionciphers.Asubstitutioncipherreplacesonechar-课后答案网acterwithanothercharacter.Atranspositioncipherreordersthesymbols.3.Substitutioncipherscanbedividedintotwobroadcategories:monoalphabeticciphersandpolyalphabeticciphers.Inmonoalphabeticsubstitution,therelation-www.hackshp.cnshipbetweenacharacterintheplaintextandthecharactersintheciphertextisone-to-one.Inpolyalphabeticsubstitution,therelationshipbetweenacharacterintheplaintextandthecharactersintheciphertextisone-to-many.4.Symmetric-keycipherscanalsobedividedintotwobroadcategories:streamciphersandblockciphers.Inastreamcipher,encryptionanddecryptionaredoneonesymbolatatime.Inablockcipher,symbolsinablockareencryptedtogether.5.Astreamcipherisamonoalphabeticcipherifthevalueofkidoesnotdependonthepositionoftheplaintextcharacterintheplaintextstream;otherwise,thecipherispolyalphabetic.6.Inablockcipher,eachcharacterinaciphertextblockdependsonallcharactersinthecorrespondingplaintextblock.Thecipher,therefore,isapolyalphabetic.7.Theadditiveciphers,multiplicativeciphers,affineciphers,andmonoalphabeticsubstitutioncipheraresomeexamplesofmonoalphabeticciphers.8.Theautokeycipher,Playfaircipher,Vigenerecipher,Hillcipher,rotorcipher,one-timepad,andEnigmamachinearesomeexamplesofpolyalphabeticciphers.9.Therailfencecipheranddoubletranspositioncipherareexamplesoftranspositionciphers.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！210.Brute-forceattack,statisticalattack,patternattack,andKasiskitestareexamplesofattacksontraditionalciphers.Exercises11.a.Thenumberofkeys=n×(n−1)/2=(100×99)/2=4950.b.Only100keysareneeded:Thereshouldbeonesecretkeybetweenthepresi-dentandeachmember.c.Only100keysareneeded:Thereshouldbeonesecretkeybetweenthepresi-dentandeachmembertocreatethesessionsecretkey.Afterthesessionkeyisestablished,thetwomemberscanusetheone-timesessionkey.khdaw.com12.Thesentenceinthetabletanditstranslationservesasaknownplaintext/ciphertextpair.Thisisaknown-plaintextattack.13.Doubleencryptionheredoesnothelp.Encryptionwithk1followedbyencryptionwith课后答案网k2isthesameasencryptionwithk=(k1+k2)mod26.C=[(P+k1)mod26)+k2]mod26=(Pmod26+k1mod26+k2)mod26C=(Pmod26)mod26+(k1mod26)mod26+k2mod26C=Pmod26+k1mod26+k2mod26=(P+k1+k2)mod26www.hackshp.cnC=(P+k)mod26,wherek=(k1+k2)mod2614.a.Thecompressioningeneralcreatesatextwhichisnotinthesourcelanguage(Englishforexample).Thismeansthatthecompressedplaintextdoesnotpre-servethefrequencyofcharacters.IthelpsAliceinthiscase.b.Compressionbeforeencryptioncanbemoreefficientbecauseencryptionisnormallytimeconsumingifthemessageisverylong.15.a.Thesizeofthekeydomainis26+10=36.Themodulusisalso36.AliceneedstousethesetZ36.b.Thesizeofthekeydomainis12;thedomainis(1,5,7,11,13,17,19,23,25,and29).Themodulusis36.AliceneedstousethesetZ36∗.c.Thekeydomainis36×12=432.Themodulusisstill36.However,AliceneedstouseZ36foradditionandZ36*formultiplication.16.a.Thesizeofthekeydomainis29.b.Thesizeofthekeydomainis28because29isaprimenumber.khdaw.comc.Thesizeofthekeydomainis29×28=812.若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！317.a.RandomswitchingbetweensubstitutionandtranspositionisasdifficultforAliceandBobasitisforEvetodiscoverwhichmethodisbeingused.IfAliceandBoddonothaveasecurechanneltoinformeachotherwhichmethodtheyareusing(whichisnormallythecase),theyneedtotossacoin.Evecandothesame.However,AliceandBobcanuseapattern(forexample,threesubstitu-tionsandtwotranspositions),butusinganypatternisakindofweaknessinsecrecy.b.Thesameargumentusedinpartacanbeusedhere.However,ifEveknowsthatcipherisasubstitution,shecanusemoretoolstofindoutthewhichtype.Forexample,ifshecaneasilybreakthecodeusingbrute-forceattackonthekey,sheknowsthattheyareusingeitheradditiveormultiplicativecipher.c.Thesameargumentusedinpartacanbeusedhere.However,ifEveknowsthatthecipheristransposition,shecanusethepatternattacktofindthesizeofthekhdaw.comsection.18.a.Inadditivecipher,Ci=(Pi+k)mod26.Thismeansthatifonecharacterintheplaintextischangedonlyonecharacterintheciphertextischanged.C课后答案网idependsonlyPi.b.Inmultiplicativecipher,Ci=(Pi×k)mod26.Thismeansthatifonecharacterwww.hackshp.cnintheplaintextischangedonlyonecharacterintheciphertextischanged.CidependsonlyPi.c.Inaffinecipher,Ci=(Pi×k1+k2)mod26.Thismeansthatifonecharacterintheplaintextischangedonlythecorrespondingcharacterintheciphertextischanged.CidependsonlyPi.d.InVigenerecipher,Ci=(Pi+ki)mod26.Although,thevalueofkimaychange,butthechangedoesnotdependonthepreviousornextcharacters;thechangedependsonlyonpositionoftheplaintextcharacter.Ifonlyonecharacterintheplaintextischanged,onlyonecharacterintheciphertextwillbechanged.e.Inautokeycipher,Ci=(Pi+ki)mod26=(Pi+Pi−1)mod26.Thismeanseachciphertextcharacter(exceptthefirst)dependsonthecorrespondingplaintextcharacterandthepreviousplaintextcharacter.Therefore,changingonesinglecharacterintheplaintextwillchangeallcharactersintheciphertextwhichcomesafterthatcharacter.Inotherwords,ifwechangecharacter21intheplaintext,characters22,23,24,…willbechanged.f.Inone-timepad,thekeystreamisusedonlyonce.Eachciphertextcharacter,however,dependsonlythecorrespondingplaintextciphertext.Ifonlyonechar-acterintheplaintextischanged,onlyonecharacterintheciphertextwillbechanged.g.Therotorcipherisakindofmonoalphabeticsubstitutioncipher,inwhichthemappingtablewillbechangedfromonecharactertothenext.Eachciphertextkhdaw.comcharacter,however,dependsonlythecorrespondingplaintextcharacter.Ifonly若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！4onecharacterintheciphertextischanged,onlyonecharacterintheplaintextwillbechanged.h.TheEnigmamachineisbasedontherotorcipher.Therefore,Ifonlyonecharac-terintheplaintextischanged,onlyonecharacterintheciphertextwillbechanged.19.a.Singletranspositiononlyreordersthecharacters.Ifonecharacterischangedintheplaintext,itaffectsonlyonecharacterintheciphertext.b.Doubletranspositiononlyreordersthecharacters.Ifonecharacterischangedintheplaintext,itaffectsonlyonecharacterintheciphertext.c.InthePlayfaircipher,encryptionistwocharactersatatime.Ifonecharacterintheplaintextischanged,itnormallychangesoneortwocharactersintheciphertext.However,ifthechangedcharacteristhesameasthepreviousorkhdaw.comnextcharacter,weneedtoaddoneboguscharacterintheplaintextthatmaychangeseveralcharactersintheciphertext.20.a.ThePlayfairisablockcipher;encryptionisdonetwocharacteratatime.课后答案网b.Theautokeycipherisastreamcipher;encryptionisdoneonecharacteratatime.www.hackshp.cnc.Theone-timepadcipherisastreamcipher;encryptionisdoneonecharacteratatime.d.Therotorcipherisastreamcipher;encryptionisdoneonecharacteratatime.e.TheEnigmamachineisaisastreamcipher;encryptionisdoneonecharacteratatime.21.CipherPlaintextCiphertextAdditive,key=20ThisisanexerciseNBCMCMUHYRYLWCMYMultiplicative,key=15ThisisanexerciseZBQKQKANIHIVEQKIAffine,key=(15,20)ThisisanexerciseTVKEKEUHCBCPYKEC22.CipherPlaintextCiphertextVigenereThehouseisbeingsoldtonightWVPSOLKHWDMEZFJGZWDKGQWRSTAutokeyThehouseisbeingsoldtonightAALLVIMWMATFMVTYGZOWHBVONAPlayfairThehouseisbeingsoldtonightWECEXIOHNOEIFIHKXBBWSIRBEW23.PlaintextCiphertextLifeisfullofsurpriseSMFPBZMYLWHMZYPPKPZIkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！524.Weusethefollowingkey:GUI/JDANCEBFHKLMOPQRSTVWXYZWeneedtoaddthreeboguscharacter,x’s,toseparatetwod’sandtwoo’sandoneattheendtomakethenumberofcharacterseven.Thetransformedplaintextisactually"thekeyishidxdenunderthedoxorpadx".PlaintextCiphertextkhdaw.comThekeyishiddenunderthedoorpadPOKLBXDRLGIYIBCGBGLXPOBILZTLGTIY25.Weaddtheboguscharacter,"z"totheendoftheplaintexttomakethenumberofcharactersmultipleof2.Theplaintextmatrix,thekeymatrix,andciphertextmatrixareshownbelow:课后答案网820224210118www.hackshp.cn518214113813131301311381332221218457214220K19101746122214271711425325CPTheciphertextisthen"IUVAFSLDNNLDWMCOTKGMCHEZ",inwhichthelastcharacterisaboguscharacter.26.Thisisknown-plaintextattack.Johnsknowsaplaintext/ciphertextpair(yes→CIW).Heknowsthatthealgorithmisshiftcipherandthekey=4.Whenhegetsaccesstotheciphertext"XVIEWYVT",hedecryptsitas"treasure".27.a.Eveislaunchingachosen-plaintextattack.b.Thelengthofthemessageis10.Since10khdaw.com=2×5,Thenumberofcolumnscanbe1,2,5or10.Thefirstorthelastguessisunlikely,sothenumberofcolumns若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！6iseither2or5.28.Wecantrythekeys13,12,14,11,15whichareclosetoAlice’sbirthday.Whenweusethekey=11,theplaintextmakessense.Key=11Ciphertext:NCJAEZRCLASJLYODEPRLYZRCLASJLCPEHZDTOPDZQLNZTYPlaintext:cryptographyandsteganographyaretwosidesofacoin29.Weknowthat"ab"→"GL".Thismeansthat00→06and01→11Wecanconstructtwoequationsfromthesetwopiecesofinformation:khdaw.com00×k1+k2≡06(mod26)01×k1+k2≡11(mod26)Solvingthesetwoequationsgiveusk1=5andk2=6.Thismeans,−1课后答案网P=((C−k2)×k1)mod26=((C+20)×21)mod26Ciphertext:XPALASXYFGFUKPXUSOGEUTKCDGFXANMGNVSwww.hackshp.cnPlaintext:thebestofafightismakingupafterwards30.Wecanfindthesingle-characterfrequencyoflettersinthisciphertextasshownbelow:CharacterOHBGWNVEJCULRFrequency4444322211111Thisstatistic,however,isnotveryusefulbecauseofseveralreasons:a.Thelengthoftheciphertextisveryshortforthisanalysis(only30characters).b.Only10outof26charactersinthealphabetisused.Whenmonoalphabeticsub-stitutionisused,weneedtohaveallormostofthecharacterstobepresentintheciphertext.c.Thefrequenciesarenotdistributed.Wehaveonlyfour4’s,one3,three2’s,andfive1’s.Withsomemoreguessing,wecanfindthemappingas:ONHOVEJHWOBEVGWOCBWHNUGBLHGBGR↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓oneofthemostfamousmenwasceasarThisgivesustheplaintextthatmakessense:khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！7Plaintext:OneofthemostfamousmenwasCeasar.31.a.Sinceeachentrycanbeoneofthe29characters,thetotalnumberofpotentialkeysare294=707,281.b.Outofthese707,281keys,only682,080ofthemareusable.32.Wecanfindthesingle-characterfrequencyoflettersinthisciphertextasshownbelow:CharacterBQMAVLZITWPFrequency181514121110109997CharacterEGNCOUXJSKDkhdaw.comFrequency66554432111Although"B"and"Q"havethehighestfrequencies,ifweassumethat"B"or"Q"arethedecryptionof"e",theplaintextdoesnotmakesense.Weassumethat"M"isthedecryptionof"e".Inthiscase12isdecryptedas04课后答案网sothekey=8.UsingthiskeytheplaintextisPlaintext:www.hackshp.cnGlowofyouthistarnished,byrollingtime’sheavyrustWinterdrapedspring,indeepsnowanddarkfrost,Birdofdelightnamedyouth,swiftlyleftthenestAlas,couldn’ttameit,whileitwasinmytrust.ItistheEnglishtranslationofapoembyKhayyam,thePersianpoet,phi-losopher,andmathematicianofthetwelvecentury.33.ThisisanexamplethatKasiskitestcannothelpus.Thereasonisthattheplaintexthasbeenencryptedlinebyline.Theciphertextisalsocreatedlinebyline,buteachlineistooshortforKasiskitest.Theencryptionalgorithmusesa5-characterword"apoet"toencryptthetextwithoutaddinganypaddingattheendofthelastseg-ment.makenomentionofroughtimesforgetabouteventspastMPYIGOBSRMIDBSYRDIKATXAILFDFKXTPPSNTTJIGTHDELTtimeyettocomeisunrevealedandbeingrevealedwillnotlastTXAIREIHSVOBSMLUCFIOEPZIWACRFXICUVXVTOPXDLWPENDHPTSIdontdwellondaysofyournorbuildonhereafterDDBXWWTZPHNSOCLOUMSNRCCVUUXZHHNWSVXAUHIKlifetotodayandthistoowillwhiskawayasblastLXTIMOICHTYPBHMHXGXHOLWPEWWWWDALOCTSQZELTkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8Afteraddingthepunctuation,wegetanotherEnglishtranslationofapoembyKhayyam,thePersianpoet,philosopher,andmathematicianofthetwelvecentury.Makenomentionofroughtimes,forgetabouteventspast.Timeyettocomeisunrevealed,andbeingrevealedwillnotlast,Don’tdwellondaysofyour,norbuildonhereafter,Lifetotodayandthistoowillwhiskawayasblast.34.WefollowtheprocessshowninFigure3.23ofthetext.Encryptionkeykhdaw.com326154326154Key123456Index课后答案网123456Key326154Indexwww.hackshp.cn421653421653KeyDecryptionkey123456Index35.WefollowtheideashowninFigure3.24ofthetext.EncryptionkeyDecryptionkey326154421653000100001000010000010000100000000001000001Transpose:100000000010Changerow000010tocolumn00100000010036.Thelengthofthemessageis12.Thesizeoftheblockneedstodivide12.Thismeansthatthesizeoftheblockcanbe1,2,3,4,6,12.Sincethefirstandthelastkhdaw.comsizeistrivial,wecanignorethem.Weneedtotrytheblocksizes2,3,4,and6.若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！9However,thesizeofmessage(12)doesnotallowustotestforthematricesofsize4or16.Ifthesizeofthekeymatrixis4,weneedatleasttheplaintext/ciphertextofsize16.Ifthesizeofthekeymatrixis6,weneedtohaveaplaintext/ciphertextofsize36.Ouronlychoicesaretotestforthekeymatricesofsize2and3.a.Letusfirsttrytheblocksize2.FollowingExample3.21inthetext,wecanmakeaplaintext/ciphertextpairofthefirstfourofthegivenplaintextandgivenciphertext(letu→HBCD).Inthiscasetheplaintextmatrixandciphertextare11040701P=C=19080203SincePisnotinvertibleinmodulo26arithmetic,wecannotproceed.khdaw.comb.Letusnowtrytheblocksize3.FollowingExample3.21inthetext,wecanmakeaplaintext/ciphertextpairofthefirstninecharacterofthegivenplaintextandgivenciphertext(letusmeet→HBCDFNOPI).Inthiscasetheplaintextandciphertextmatricesare课后答案网110419070102www.hackshp.cnP=201812C=030513040419141508SincePisnotinvertibleinmodulo26arithmetic,wecannotproceed.Thismeansthatwecannotsolvetheproblemwiththeinformationgiven.37.Wecanusearowmatrixofsizemforadditionmatrix,butweneedtouseasquarematrixformultiplication(tobereversible).a.Fortheadditivecipherwehave1m1m1mCPk1m1m1mPCkkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！10b.Fortheaffinecipherwehave1m1mmm1mCPk2k1−11m(1m−1m)mmPCk2k138.Thefollowingshowstheencryptionprocess.Thepositionandthevalueofeachcharacterintheplaintext(P.Text)isfound.Themultiplicationandadditionkeys(k1andk2)arelisted.Thenumericresultofencryptionforeachcharacteriscalcu-khdaw.comlated(P×k1+k2),andfinallytheciphertextcharacters(C.Text)aredeterminedandlisted.P.TextcryptographisfunPosition课后答案网012345678910110123Values21724151914617015781852013www.hackshp.cnk113579111517192123251357k20123456789101112131415results20184193181081215342104C.TextCASETDSKIMPDECKE39.IntheHillcipher,C=P×K.IftheplaintextistheidentitymatrixI,thenwehaveC=K.ThismeansthatifcanaccesstotheAlicecomputerandlaunchachosenplaintextattackusingthetrivialidentitymatrix,Evecanfindthekey.ThisshowsthattheHillcipherisveryvulnerabletothechosen-plaintextattack.40.TherelationshipbetweentheplaintextandciphertextisP+C=25orC=(25−P)mod26.PlaintextCiphtertextanexerciseZMVCVIXRHVkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1141.Weusethefollowingkey:123451zqpfe2yrogd3xsnhc4wtmi/jb5vulkaTheplaintextandciphertextareshownbelow:PlaintextCiphtertextanexercise(5,5),(3,3),(1,5),(3,1),(1,5),(2,2),(3,5),(4,4),(3,2),(1,5)khdaw.com课后答案网www.hackshp.cnkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！12khdaw.com课后答案网www.hackshp.cnkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER4MathematicsofCryptographyPartII:AlgebraicStructures(SolutiontoPracticeSet)ReviewQuestions1.Thecombinationofthesetandtheoperationsthatareappliedtotheelementsofkhdaw.comthesetiscalledanalgebraicstructure.Wehavedefinedthreecommonalgebraicstructures:groups,rings,andfields.2.Agroupisasetofelementswithabinaryoperationthatsatisfiesfourproperties:closure,associativity,exis课后答案网tenceofidentity,andexistenceofinverse.Acommuta-tivegroup,alsocalledanabeliangroup,isagroupinwhichtheoperatorsatisfiesthefourpropertiesforgroupsplusanextraproperty,commutativity.3.Aringisanalgebraicstructurewithtwooperations.Thefirstoperationmustsat-www.hackshp.cnisfyallfivepropertiesrequiredforanabeliangroup.Thesecondoperationmustsatisfyonlythefirsttwo.Inaddition,thesecondoperationmustbedistributedoverthefirst.Acommutativeringisaringinwhichthecommutativepropertyisalsosatisfiedforthesecondtheoperation.4.Afieldisacommutativeringinwhichthesecondoperationsatisfiesallfiveprop-ertiesdefinedforthefirstoperationexceptthattheidentityofthefirstoperation(sometimescalledthezeroelement)hasnoinverse.Afinitefieldisafieldwithafinitenumberofelements.Aninfinitefieldisafieldwithaninfinitenumberofelements.5.AGaloisfield,GF(pn),isafinitefieldwithpnelements.Ifn=1,thefieldissome-timesreferredtoasGF(p).6.AnexampleofagroupisG=.Theidentityelementis0;theinverseofanelementais−a.7.AnexampleofaringisR=.Forthefirstoperation,theidentityelementis0;theinverseofanelementais−a.Neithertheidentifyelementnortheinverseofanelementisdefinedforthesecondoperation.8.AnexampleofafieldisF=.Forthefirstoperation,theidentityele-mentofis0;theinverseofanelementais−a.Forthesecondoperation,theiden-khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！2tityelementis1andtheinverseofanelementaisa−1.Theidentityelementofthefirstoperation,however,hasnoinversewithregardtothesecondoperation.9.Apolynomialofdegreen−1withcoefficientinGF(2)canrepresentann-bitwordwithpowerofeachtermdefiningthepositionofthebitandthecoefficientsofthetermsdefiningthevalueofthebits.10.InGF(2n),areduciblepolynomialofdegreenisapolynomialwithcoefficientinGF(2)thatcannotbefactoredintoapolynomialwithdegreeoflessthann.Areduciblepolynomialissometimesreferredtoasaprimepolynomial.Exercises11.ThegroupG=hasonlyfourmembers:0,1,2,and3.a.Foralla’sandb’smembersofG,weneedtoprovethata+b=b+a.Thefol-khdaw.comlowingshowstheproof(alloperationsaremodulo4).(0+1)=(1+0)(0+2)=(2+0)(0+3)=(3+0)(1+2)=(2+1)(1+3)=(3+1)课后答案网(2+3)=(3+2)b.www.hackshp.cn(3+2)mod4=1mod4(3−2)mod4=−1mod4=3mod412.ThegroupG=hasonlytwomembers:1and5.a.Foralla’sandb’smembersofG,weneedtoprovethata×b=b×a.Sincethisgrouphasonlytwomembers,wecanseethat(1×5)mod6=(5×1)mod6.b.(5×1)mod6=5mod6(1÷5)mod6=(1×5−1)mod6=(1×5)mod6=5mod6c.Thereisnoneedtoworryaboutdivisionbyzerointhisgroup,because0isnotthememberofthisgroup.13.Assumethattheoperationis(♦).Wecansaythat(x♦y)isthesameasx•(−y),inwhich(−y)istheinverseofywithrespecttooperation(•).UsingTable4.1,wecancreatethefollowingtable:♦abcdaadcbbbadcccbadddckhdaw.comba若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！3AnotherwaytosolvetheproblemistothinkaboutsimilaritybetweenthegrouprepresentedinTable4.1andthegroupG=.MakethetableforsubtractionoperationinthegroupG=andreplace0witha,1withb,2withc,and3withd.14.Itisenoughtoproveonesinglecase(a°b≠b°a):[132]°[213]=[312]but[213]°[132]=[231]15.Weuseonlytwocases:a.Wefirstprovethat([132]°[213])°[312]=[132]°([213]°[312])khdaw.com([132]°[213])°[312]=[312]°[312]=[231][132]°([213]°[312])=[132]°[321]=[231]b.Wethenprovethat课后答案网([123]°[213])°[312]=[123]°([213]°[312])www.hackshp.cn([123]°[213])°[312]=[213]°[312]=[321][123]°([213]°[312])=[123]°[321]=[321]16.Thefollowingshowsthecompositionwithidentifyelements.°[12][21][12][12][21][21][21][12]17.Theresultof([132]°[321])°[213]=[321].Bobcanusethepermu-tation[321]toreversetheoperation.Thisprovesthatdoubleormultiplepermu-tationdoesnothelp;Alicecouldhaveusedonesinglepermutation.18.a.Inthiscase,|G|=16,whichmeanstheorderofeachsubgroupshoulddivide16.Wecanhavesubgroupswithorders1,2,4,8,16.Thefollowingshowssomeofthesesubgroups.|H|=1→H=<{1},×>|H|=2→H=<{1,7},×>H=<{1,9},×>H=<{1,15},×>|H|=4→H=<{1,3,9,11},×>H=<{1,7,9,15},×>|H|=8→H=Gkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！4b.Inthiscase,|G|=23,whichmeanstheorderofeachsubgroupshoulddivide23.Wecanhavesubgroupswithorders1and23.Thefollowingshowssomeofthesesubgroups.|H|=1→H=<{0},+>|H|=23→H=Gc.Inthiscase,|G|=8,whichmeanstheorderofeachsubgroupshoulddivide8.Wecanhavesubgroupswithorders1,2,4,8.Thefollowingshowssomeofthesesubgroups.|H|=1→H=<{1},×>|H|=2→H=<{1,7},×>H=<{1,9},×>H=<{1,15},×>|H|=4→H=<{1,3,9,11},×>H=<{1,7,9,15},×>khdaw.com|H|=8→H=Gd.Inthiscase,|G|=16,whichmeanstheorderofeachsubgroupshoulddivide16.Wecanhavesubgroupswithorders1,2,4,8,16.Thefollowingshowssomeofthesesubgroups.课后答案网|H|=1→H=<{1},×>|H|=2→H=<{1,16},×>www.hackshp.cn|H|=4→H=<{1,4,13,16},×>|H|=16→H=G19.a.Theorderofthegroupis|G|=18.Theorderofpotentialsubgroupsshoulddivide18,whichmeans|H|canbe1,2,3,6,9,and18.b.Theorderofthegroupis|G|=29.Theorderofpotentialsubgroupsshoulddivide29,whichmeans|H|canbe1and29.c.Theorderofthegroupis|G|=4.Theorderofpotentialsubgroupsshoulddivide4,whichmeans|H|canbe1,2,and4.d.Theorderofthegroupis|G|=18.Theorderofpotentialsubgroupsshoulddivide18,whichmeans|H|canbe1,2,3,6,9,and18.20.a.ForG=,wehaveord(0)=0ord(1)=8ord(2)=4ord(3)=8ord(4)=2ord(5)=8ord(6)=4ord(7)=8b.ForG=,wehavekhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！5ord(0)=0ord(1)=7ord(2)=7ord(3)=7ord(4)=7ord(5)=7ord(6)=7c.ForG=,wehaveord(1)=0ord(2)=6ord(4)=3ord(5)=6ord(7)=3ord(8)=2d.ForG=,wehaveord(1)=0ord(2)=3ord(3)=6ord(4)=6ord(5)=6ord(6)=221.Theelements0,g0,g1,g2,andg3canbeeasilybegenerated,becausetheyarethe4-bitrepresentationsof0,1,x2,andx3.Weusetherelationƒ(g)=g4+g3+1=0tokhdaw.comgenerateotherpowers.Usingthisrelation,wehaveg4=g3+1.Weusethisrela-tiontofindthevalueofallelementsas4-bitwords:0=0=0=0−−→0=(0000)g0课后答案网=g0=g0=g0−−→g0=(0001)g1=g1=g1=g1−−→g1=(0010)g2=g2=g2=g2−−→g2=(0100)g3=g3=g3=g3−−→g3=(1000)www.hackshp.cng4=g4=g4=g3+1−−→g4=(1001)g5=g(g4)=g(g3+1)=g3+g+1−−→g5=(1011)g6=g(g5)=g(g3+g+1)=g3+g2+g+1−−→g6=(1111)g7=g(g6)=g(g3+g2+g+1)=g2+g+1−−→g7=(0111)g8=g(g7)=g(g2+g+1)=g3+g2+g−−→g8=(1110)g9=g(g8)=g(g3+g2+g)=g2+1−−→g9=(0101)g10=g(g9)=g(g2+1)=g3+g−−→g10=(1010)g11=g(g10)=g(g3+g)=g3+g2+1−−→g11=(1101)g12=g(g11)=g(g3+g2+1)=g+1−−→g12=(0011)g13=g(g12)=g(g+1)=g2+g−−→g13=(0110)g14=g(g13)=g(g2+g)=g3+g2−−→g14=(1100)22.Thefollowingshowsafewexamplesofadditionandsubtraction.Notethatmodu-lusfortheexponentis2n−1or15.a.Weshowtwoexamplesofaddition(usingtheresultsofExercise21):g3+g12=g3+(g+1)=g3+g+1→(1011)=(1000)+(0011)g10+g12=(g3+g)+(g+1)=g3+1→(1001)=(1010)+(0011)b.Weshowtwoexamplesofsubtraction(usingtheresultsofExercise21):g3−g9=g3−(g2+1)=g3+g2+1→(1101)=(1000)−(0101)g10−g4=(g3+g)−(g3+1)=g+1khdaw.com→(0011)=(1010)−(1001)若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！623.a.Weshowtwoexamplesofmultiplication(usingtheresultsofExercise21):g3×g12=g15mod15=g0=1→(0001)=(1000)×(0011)g10×g12=g22mod15=g7=g2+g+1→(0111)=(1010)+(0011)b.Weshowtwoexamplesofdivision(usingtheresultsofExercise21):g3÷g9=g−6mod15=g9=g2+1→(0101)=(1000)÷(0101)g10÷g4=g6mod15=g6=g3+g2+g+1→(1111)=(1010)−(1001)24.a.GF(12)isnotaGaloisfield,because12cannotbewrittenintheformpn.b.GF(13)isaGaloisfield;13canbewrittenintheformpn(p=13andn=1).khdaw.comc.GF(16)isaGaloisfield;16canbewrittenintheformpn(p=2andn=4).d.GF(17)isaGaloisfield;17canbewrittenintheformpn(p=17andn=1).25.a.x4课后答案网+xb.xwww.hackshp.cnc.x5+1d.x+126.a.0101b.00101c.011d.1000000027.a.5+3=8mod7=1mod7b.5−4=1mod7c.5×3=15mod7=1mod7d.5÷3=5×(3−1)=5×5=25mod7=4mod728.Apolynomialf(x)ofdegreenisirreducibleiff(x)=g(x)×h(x),wheregandharetwopolynomials,eachwiththedegreegreaterthanzero.Accordingtothisdefini-tionwehavedegree(f)=degree(g)+degree(h).Basedonthis,wecanprovethateverypolynomialofdegree1isareduciblepolynomialbecausetheinteger1can-notbesumoftwointegersgreaterthan0.Sincetheonlytwopolynomialsofdegree1aref1(x)=xandf2(x)=x+1,thesetwopolynomialsareirreducible.29.Apolynomialf(x)ofdegreenisirreducibleiff(x)=g(x)×h(x),wheregandharetwopolynomials,eachwiththedegreegreaterthanzero.Accordingtothisdefini-khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！7tionwehavedegree(f)=degree(g)+degree(h).Basedonthis,areduciblepoly-nomialofdegree2canbefactoredonlyastwopolynomialsofdegree1(2=1+1).Inotherwords,afactorsofareduciblepolynomialofdegree2canbeonlyxor(x+1)(theonlytwopolynomialsofdegree1).Wecancheckallpolynomialsofdegree2toseewhichonecanbefactoredassuch.(x2)=(x)×(x)→(x2)isreducible(x2+1)=(x+1)×(x+1)→(x2+1)isreducible(x2+x)=(x)×(x+1)→(x2+x)isreducible(x2+x+1)cannotbefactored.→(x2+x+1)isirreducibleItcanalsobeprovedthat2f(x)=x+x+1cannotbeevenlydividedbyxorx+1becausethisimpliesthatx=0orx=−1mustbetherootofthef(x),whicharenot(f(0)=1andf(−1)=1.khdaw.com30.Apolynomialf(x)ofdegreenisirreducibleiff(x)=g(x)×h(x),wheregandharetwopolynomials,eachwiththedegreegreaterthanzero.Accordingtothisdefini-tionwehavedegree(f)=degree(g)+degree(h).Basedonthis,areduciblepoly-nomialofdegree3canbefactoredonlyastwopolynomialsofdegree1and2(3=1+2).Inotherwords,oneofthefactors课后答案网ofareduciblepolynomialofdegree3mustbexor(x+1)(theonlytwopolynomialsofdegree1).Wecancheckallpoly-nomialsofdegree3toseewhichonecanbefactoredassuch.www.hackshp.cn(x3)=(x)×(x2)→(x3)isreducible(x3+1)=(x+1)×(x2+x+1)→(x3+1)isreducible(x3+x)=(x)×(x2+1)→(x3+x)isreducible(x3+x+1)cannotbefactored→(x3+x+1)isirreducible(x3+x2)=(x2)×(x+1)→(x3+x2)isreducible(x3+x2+1)cannotbefactored→(x3+x2+1)isirreducible(x3+x2+x)=(x)×(x2+x+1)→(x3+x2+x)isreducible(x3+x2+x+1)=(x+1)×(x2+x+1)→(x3+x2+x+1)isreducibleItisclearthatf(x)31=x+x+1cannotbefactoredas(x)or(x+1)because(x)3neither0nor−1aretherootforthispolynomial.Thisistrueforf2=x+x2+1.31.WefirstwriteeachnumberasapolynomialwithcoefficientinGF(2).Wethenmultiplythepolynomials.Finally,weconverttheresulttothebinarypattern.a.(x+1)×(x+1)→(x2+x+x+1)→(x2+1)→101b.(x3+x)×(x3)→(x6+x4)→1010000c.(x4+x3+x2)×(x4)→(x16+x7+x6)→1000000001100000032.Theonlyirreduciblepolynomialofdegree2isx2+x+1.Wecanguessthattheinverseof1is1andtheothertwopolynomialsareinversesofeachother,butweusetheextendedEuclideanalgorithmtofindthem.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8a.Theinverseof1is1,asshowninthefollowingtable.qr1r2rt1t2tx2+x+1x2+x+1100111011b.Theinverseofxisx+1,asshowninthefollowingtable.qr1r2rt1t2tx+1x2+x+1x101x+1xx101x+11khdaw.com10x+11c.Theinverseof课后答案网x+1isx,asshowninthefollowingtable.qr1r2rt1t2txx2+x+1x+1101xwww.hackshp.cnx+1x+1101x110x133.Theinverseisx3+x,asshownbelow(usingtheextendedEuclideanalgorithm).qr1r2rt1t2tx+1x5+x2+1x4+x3+1x3+x2+x01x+1xx4+x3+1x3+x2+xx2+11x+1x2+x+1x+1x3+x2+xx2+11x+1x2+x+1x3+xx2+1x2+110x2+x+1x3+x110x3+x134.Weusetheirreduciblepolynomial(x4+x3+1).khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！9a.Thefollowingshowstheadditiontable.Wehaveusedhexadecimalvaluestomakethetableshorter.⊕0123456789ABCDEF00123456789ABCDEF11032547698BADCFE223016745AB89EFDC332107654BA98FEDC445670123CDEF89AB554761032DCFE98BA667452301EFCDAB89776543210FEDCBA98889ABCDEF01234567khdaw.com998BADCFE10325476AAB89EDCD23016745BBA98FEDC32107654CCDEF89AB45670123课后答案网DDCFE98BA54761032EEFCDAB8967452301FFEDCBA9876543210www.hackshp.cnb.Thefollowingshowsthemultiplicationtable.Wehaveusedhexadecimalval-uestomakethetableshorter.⊗0123456789ABCDEF0000000000000000010123456789ABCDEF202468ACE9BDF135730365CFA91274DEB84048C9D15BF3726AE505AFD872369CED41606CA17DB24E835F9707E952BCAD43F81680891B32AF76E4CD5909B2F64D7EC5813AA0AD739E46CB15F82B0BF47C83E51A926DC0C1D2E3F48596A7BD0D3E6B58C1F2A794E0E5BA4F1D386792CF0F78E1965A2DB4C3khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1035.WeuseTable4.10tofindthemultiplicativeinverseofthesecondword.Wethenusethesametabletomultiplythefirstwordwiththeinverseofthesecondword.a.(100)÷(010)=(100)×(010)−1=(100)×(110)=(010)b.(100)÷(000)→Τhisoperationisimpossiblebecause(000)hasnoinverse.c.(101)÷(011)=(101)×(011)−1=(101)×(100)=(011)d.(000)÷(111)=(000)×(111)−1=(000)×(101)=(111)36.WeletP2+1),P3+x2+x+1),andmodulus=(x4+x3+1).Thefollow-1=(x2=(xingtableshowstheprocess.Notethatweonlyneedtoaddthemoduluswiththenewresult(ifthedegreeoftheresultisgreaterthanthedegreeofthemodulus);nodivisionisneeded.khdaw.comPowersOperationNewResultReductionx0⊗P2x3+x2+x+1No1⊗322xP2x⊗(x+x+x+1)x+x+1Yes课后答案网x2⊗P2x⊗(x2+x+1)x3+x2+xNo023232www.hackshp.cnP1⊗P2=(x⊗P2)⊕(x⊗P2)=(x+x+x+1)⊕(x+x+x)=(1)Theresultis(1),whichcanbeprovedusingmultiplicationanddivisionbythemodulus.37.WeletP1=(10000),P2=(10101),andmodulus=(100101).Thefollowingtableshowstheprocess:PowersShift-LetOperationExclusive-Orx0⊗P210101x1⊗P0101001010⊕00101=011112x2⊗P21111011110x3⊗P1110011100⊕00101=110012x4⊗P1001010010⊕00101=101112P⊗P=(x4⊗P=10111122)Theresultis42(10111)or(x+x+x+1),whichcanbeprovedusingmultipli-cationanddivisionbythemodulus.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER5IntroductiontoModernSymmetric-KeyCiphers(SolutiontoPracticeSet)ReviewQuestions1.Thetraditionalsymmetric-keyciphersarecharacter-orientedciphers.Themodernkhdaw.comsymmetric-keyciphersarebit-orientedciphers.2.Toberesistanttoexhaustive-searchattack,amodernblockcipherneedstobedesignedasasubstitutioncipherbecauseinatranspositioncipherwehavethesamenumberof1sintheplaintextandciphertext,whichmakesexhaustive-search课后答案网attacksimpler.3.Atranspositionisdefinitelyapermutationofbits.Asubstitutionofbitscanbewww.hackshp.cnthoughtofapermutationifweadddecodingandencodingtotheoperation.4.Wementionedseveralcomponentsofamodernblockciphersinthischapter:P-boxes,S-boxes,theexclusive-oroperation,theswapoperation,thecircularshiftoperation,thesplitoperation,andthecombineoperation.5.AP-box(permutationbox)transposesbits.WehavethreetypesofP-boxesinmodernblockciphers:straightP-boxes,expansionP-boxes,andcompressionP-boxes.AstraightP-boxisinvertible;theothertwoarenot.6.AnS-boxisanm×nsubstitutionunit,wheremandnarenotnecessarilythesame.Thenecessaryconditionforinvertibilityisthatmshouldbeequalton.7.Aproductcipherisacomplexciphercombiningsubstitution,permutation,andothercomponentsdiscussedinthischapter.Wediscussedtwoclassesofproductciphers:Feistelandnon-Feistelciphers.8.Diffusionhidestherelationshipbetweentheciphertextandtheplaintext.Confu-sionhidestherelationshipbetweentheciphertextandthekey.9.AFeistelblockcipherusesbothinvertibleandnoninvertiblecomponents.Anon-Feistelblockcipherusesonlyinvertiblecomponents.10.AdifferentialcryptanalysisisbasedonanonuniformdifferentialdistributiontableoftheS-boxesinablockcipher;itisachosen-plaintextattack.Alinearcryptanal-khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！2ysisisbasedonalinearapproximationofanS-box;itisaknown-plaintextattack.11.Inasynchronousstreamcipherthekeystreamisindependentoftheplaintextorciphertext.Inanonsynchronousstreamcipherthekeystreamissomehowdepen-dentontheplaintextorciphertext.12.Afeedbackshiftregisterismadeofashiftregisterandafeedbackfunction.Wediscussedtwovariations:linearfeedbackshiftregister(LFSR)andnonlinearfeed-backshiftregister(NLFSR).Exercises13.Theorderofthegroupis10!=3,626,800.Thekeysizeis⎡log2(10!)⎤=22bits.Notethatakeyof22bitscanselect222=4,194,304differentpermutations,butonly3,626,800ofthemareusedhere.khdaw.com14.Theorderofthegroupis(210)!=1024!Thekeysizeis⎡log2(1024!)⎤=8770bits.Notethatakeyof8770bitscanselect28770differentpermutations,butonly(1024!)ofthemareusedhere.15.课后答案网a.CircularLeftShift3(10011011)→11011100www.hackshp.cnb.CircularRightShift3(11011100)→10011011c.TheoriginalwordinPartaandtheresultofPartbarethesame,whichshowsthatcircularleftshiftandcircularrightshiftoperationsareinversesofeachother.16.a.Swap(10011011)→10111001b.Swap(10111001)→10011011c.TheoriginalwordinPartaandtheresultofPartbarethesame,whichshowsthatswappingisaself-invertibleoperation.17.WeshowthecomplementofAwithA.a.(01001101)⊕(01001101)=(00000000)→(A⊕A=All0s)b.(01001101)⊕(10110010)=(11111111)→(A⊕A=All1s)c.(01001101)⊕(00000000)=(01001101)→(A⊕All0s=A)d.(01001101)⊕(11111111)=(10110010)→(A⊕All1s=A)18.a.Thevalueof0102=2,whichcanbedecodedasthe8-bitword(0000100).b.The8-bitword(00100000)hasa1inposition5,whichcanbeencodedas(101)2.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！319.Usingeightbitsforeachcharacter,|M|=8×2000=16,000bits.Therefore,wehave|M|+|Pad|=0mod64→|Pad|=−|M|mod64→|Pad|=−16,000mod64=0Thismeansnopaddingisneeded.Themessageisdividedinto250blocks.20.Thepermutationtableis[25413].21.Thepermutationtableis[135].22.Thepermutationtableis[13312].23.Seethefigurebelow:12345678khdaw.comStraightP-box课后答案网12345678www.hackshp.cn24.ItisanexpansionP-boxwith4inputsand6outputsasshownbelow:1234ExpansionP-box12345625.ItisacompressionP-boxwith7inputsand5outputsasshownbelow:1234567CompressionP-box12345khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！426.ItisastraightP-boxwith6inputsand6outputsasshownbelow:12345678StraightP-box1234567827.Weusethefollowingprocedure:a.Wefirstfindtheinput/outputrelationbasedonthegivenS-box:Input:00011011khdaw.comOutput:01111000b.Wethenfindtheinverseinput/outputrelation(sortedoninput):课后答案网Input:00011011www.hackshp.cnOutput:11001001c.NowwecreatethetablefortheinverseS-box(theleftrowdefinesthefirstinputbit,thefirstcolumndefinesthesecondinputbit,andtheentriesdefinetheoutput):01011001100128.Thecharacteristicpolynomialisx5+x2+1=0.Thefeedbackfunctioncanbefoundasx5=x2+1.ThefollowingfigureshowstheLFSR.x5=x2+1x5x4x3x2x1x0Output(k)iThecharacteristicpolynomialx5+x2+1or(25)16isbothaprimitivepolynomial(seeAppendixG).However,thecorrespondingnumberofcellsis5,whichisodd.Thismeansthatperiodislessthan31(2m−1).khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！529.Thecharacteristicpolynomialisx4+x3+x2+1or(11101)2or(1D)16.Thepoly-nomialisnotprimitive(seeAppendixG).Themaximumperiodisthenlessthan24−1orlessthan15.30.Thefollowingtableshowstheinitialstate(seed)andthenexttwentystates.Statesb4b3b2b1b0kiInitial11110010111100200111103000111041000110501000106001000071001000811001009011001khdaw.com1010110011010110121010111311010114111010课后答案网15111101160111101700111118000111www.hackshp.cn1910001120010001Theinitialstateintheabovetableisthesameasthestate11inTable5.6.Thenext9statesarealsothesame;state09intheabovetableisthesameasthestate20inTable5.6.Therestofthestatesaredifferentinthetwotables.31.Tohaveamaximumperiodof32,thecharacteristicpolynomialshouldbeofdegree6because25−1=31<32.However,ifthecharacteristicpolynomialisprimitive,themaximumperiodis26−1=63.Buttheproblemsaysthatthemaxi-mumperiodis32,therefore,thecharacteristicpolynomialisnotprimitive.Inotherwords,wehaveanLFSRofdegree6,with6cells(6-bitregister)whosecharacter-isticpolynomialisnotprimitive.32.Weassumethatbitsarenumberedb0tob5fromrighttoleft.Otherassumptionsyielddifferentresults.Input:110010→Leftbit=1⊕0⊕1=0Rightbit=1⊕0⊕0=1→Output:01Input:101101→Leftbit=1⊕1⊕0=0Rightbit=0⊕1⊕1=0→Output:0033.Input:1011→Leftrotate→Output:110Input:0110→Rightrotatekhdaw.com→Output:011若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！634.split(word[0…n],n){i←1while(i≤n/2){rightWord[i]←word[i]leftWord[i]←word[i+n/2]i←i+1}return(rightWord,leftWord)}35.khdaw.comcombine(rightWord[1…m],leftWord[1…m],m){i←1课后答案网while(i≤m){word[i]←rigthWord[i]word[i+m]←leftWord[i]www.hackshp.cni←i+1}return(word[1…n])//n=2m}36.swap(word[1…n],n){i←1while(i≤n/2){temp[i+n/2]←word[i]temp[i]←word[i+n/2]i←i+1}return(temp[0…n])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！737.circularShift(shift,word[1…n],n,k){i←1while(i≤k){if(shift=left)word←circularShiftLeft(word,n)elseword←circularShiftRight(word,n)i←i+1}return(word[1…n])khdaw.com}circularShiftLeft(word[1…n],n){temp←word[n]课后答案网j←n−1while(j≥0){www.hackshp.cnword[j+1]←word[j]j←j−1}word[1]←tempreturn(word[0…n])}circularShiftRight(word[0…n],n){temp←word[1]j←1while(j≤n){word[j−1]←word[j]j←j+1}word[n]←tempreturn(word[0…n])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！838.P-box(inputBits[1…n],Table[1…m],n,m){i←1while(i≤m){outputBits[i]←inputBits[Table[i]]i←i+1}return(outputBits[1…n])}39.Thetablecanbedesignedinmanydifferentways.Weassume,wehavealineartableofncells,inwhicheachcellcontainsavalueofmbits.Theinputdefinesthekhdaw.comcellnumber,thecontentsofthecelldefinestheoutput.Withthisconfiguration,theroutinelooksliketheoneshownbelow:S-box(inputBits[1…n],Table[1…n],n,m){课后答案网index←binaryToDecimal(inputBits)value←Table[index]www.hackshp.cnoutputBits←decimalToBinary(value)return(outputBits[0…m])}40.WeassumethatthekeymixerapplytheXORoperationontheinputandtheroundkey.Thefollowingshowsthegeneralidea.Non_FeistelRound(inputBits[1…n],roundKey[1…n],n,PermuteTable){temp←inputBits⊕roundKeytemp←substitute(temp,SubstituteTables)outputBits←permute(temp,PermuteTable)return(outputBits[1…n])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！941.FeistelRound(inputBits[1…n],roundKey[1…n],n){(tempLeft,tempRight)←split(word,n)tempLeft←tempLeft⊕function(tempRight,roundKey)(tempLeft,tempRight)←swap(tempLeft,tempRight)outputBits←combine(tempLeft,tempRight)return(outputBits[1…n])}42.LFSR(initialState[0…n−1],n)khdaw.com{b[n]←f(initialState)i←n课后答案网while(i>0){b[i−1]←b[i]i←i−1www.hackshp.cn}return(b[0])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！10khdaw.com课后答案网www.hackshp.cnkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER6DataEncryptionStandard(DES)(SolutiontoPracticeSet)ReviewQuestions1.TheblocksizeinDESis64bits.Thecipherkeysizeis56bits.Theroundkeysizekhdaw.comis48bits.2.DESuses16rounds.3.Inthefirstapproach,DESuses16mixersand15swappersinencryptionordecryptionalgorithm;inthesecond(alter课后答案网nativeapproach),DESuse16mixersand16swappersinencryptionordecryptionalgorithm.4.InDES,encryptionordecryptionuses16×2+2=34permutations,becauseeachmixerusestwopermutationsandtherearetwopermutationsbeforeandafterthewww.hackshp.cnrounds.Theround-keygeneratoruses17permutationoperations:oneparitydropand16compressionpermutationoperationsforeachround.5.Thetotalnumberofexclusive-oroperationsis16×2=32,becauseeachroundusestwoexclusive-oroperations(oneinsidethefunctionandoneoutsideofthefunction).6.Theinputtothefunctionisa32-bitword,buttheround-keyisa48-bitword.Theexpansionpermutationisneededtoincreasethenumberofbitsintheinputwordto48.7.ThecipherkeythatisusedforDESincludetheparitybits.Toremovetheparitybitsandcreatea56-bitcipherkey,aparitydroppermutationisneeded.Notonlydoestheparity-droppermutationdroptheparitybits,italsopermutestherestofthebits.8.Aweakkeyistheonethat,afterparitydropoperation,consistseitherofall0s,all1s,orhalf0sandhalf1s.Eachweakkeyistheinverseofitself:Ek(Ek(P))=P.Asemi-weakkeycreatesonlytwodifferentroundkeysandeachofthemisrepeatedeighttimes.Thesemi-weakroundkeyscomeinpairs,whereakeyinthepairistheinverseoftheotherkeyinthepair:Ek1(Ek2(P))=P.Apossibleweakkeyisakeythatcreatesonlyfourdistinctroundkeys;inotherwords,thesixteenroundkeysaredividedintofourgroupsandeachgroupismadeoffourequalroundkeys.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！29.DoubleDESusestwoinstancesofDESciphersforencryptionandtwoinstancesofreverseciphersfordecryption.Eachinstanceusesadifferentkey,whichmeansthatthesizeofthekeyis112bits.However,doubleDESisvulnerabletomeet-in-the-middleattack.10.TripleDESusesthreestagesofDESforencryptionanddecryption.TwoversionsoftripleDESareinusetoday:tripleDESwithtwokeysandtripleDESwiththreekeys.IntripleDESwithtwokeys,thereareonlytwokeys:K1andK2.ThefirstandthethirdstagesuseK1;thesecondstageusesK2.IntripleDESwiththreekeys,therearethreekeys:K1,K2,andK3.Exerciseskhdaw.com11.a.课后答案网Input:110111→3,11→Output:03(0011)b.www.hackshp.cnInput:001100→0,6→Output:09(1001)c.Input:000000→0,0→Output:04(0100)d.Input:111111→3,15→Output:09(1001)12.Thefollowingtableshowstheoutputfromallboxes.Nopatterncanbefound:InputBox1Box2Box3Box4Box5Box6Box7Box80000001110111110100111001011000100110113.Thefollowingtableshowstheoutputfromallboxes.Nopatterncanbefound:InputBox1Box2Box3Box4Box5Box6Box7Box81111111101100111001110khdaw.com0011001111011011若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！314.a.Thefollowingshowsthat3bitswillbechangedintheoutput.Input:000000→00,00→Output:10(1010)Input:000001→01,00→Output:13(1101)b.Thefollowingshowsthat2bitswillbechangedintheoutput.Input:111111→03,15→Output:09(1001)Input:111011→03,14→Output:14(1100)15.khdaw.coma.Thefollowingshowsthat2bitswillbechangedintheoutput.Input:001100→00,06→Output:03(0011)课后答案网Input:000000→00,00→Output:15(1111)www.hackshp.cnb.Thefollowingshowsthat2bitswillbechangedintheoutput.Input:110011→03,09→Output:06(0110)Input:111111→03,15→Output:09(1001)16.a.Thefollowingshowsthattwooutputsaredifferent.Input:001100→00,06→Output:09(1001)Input:110000→02,08→Output:15(1111)b.Thefollowingshowsthattwooutputsaredifferent.Input:110011→03,09→Output:04(0100)Input:001111→01,07→Output:03(0011)khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！417.Thefollowingtableshows32inputpairsand32outputpairs.Thelastcolumnisthedifferencebetweentheoutputs.InputpairsOutputpairsd000000000001001011101100000010000011110010110111000100000101010000100110000110000111000111001111001000001001011101000011001010001011101001111001001100001101101111010110001110001111011000010111010000010001100001011101010010010011010100000101khdaw.com010100010101001111111100010110010111111110100101011000011001110100111110课后答案网011010011011000010011001011100011101111010000110011110011111100101101111100000100001011010111101www.hackshp.cn100010100011001010001010100100100101000111001101100110100111101101111100101000101001101000011011101010101011110111100011101100101101011100100101101110101111100011010101110000110001111101101001110010110011100111110110110100110101110000001100110110110111010110011100111000111001011010101100111010111011001101000111111100111101000001010101111110111111111000111101Ifwesortthetableonlastcolumn(outputdifferences),wegetthefollowing:two(0011)’s,five(0101)’s,four(0110)’s,three(0111)’s,three(0111)’s,one(1010),one(1011),one(1100),five(1100)’s,four(1101)’s,one(1110),andtwo(1111)’s.Noneofthegrouphasasizelargerthaneight.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！518.ForS-Box7,wesetthefirst(leftmost)inputbitto0.Wechangetheotherfiveinputbits.Wethenobserveoneoftheoutputbits(wehavechosenthethirdbitfromthelet)andcounthowmany0’sandhowmay1’sweobtainforthisbit.Thesetwocountmustbeclosetoeachother.Thefollowingtableshowsinputsandoutputs.InputOutputThirdbit0000000100000000111010000010101110000110000000010000101000101101110001101110100011101111khdaw.com001000111110010010100000101000000课后答案网00101110000001100100000011010001000111011010www.hackshp.cn0011111010101000000111010001111010100101100001001100111010100100100101010101001011001111010111110000110000101001100100101011010101010110111111101110000000011101100000111100001001111101101Asthetableshowswehave170’sand151’s;closeenough.19.FigureS6.19showsthesituation.TheinputstoS-box7inround2comesfromsixdifferentS-boxesinround1.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！6FigureS6.19SolutiontoExercise19S-1S-2S-3S-4S-5S-6S-7S-8Round1060913192230StraighP-box282426252927(Round1)2425282924252829ExpansionP-box(Round2)3742khdaw.comS-1S-2S-3S-4S-5S-6S-7S-8Round2a.ThesixinputstoS-box7inround2comefromsixoutputs(37,38,39,40,41,42)ofexpansionpermutationbox.b.Theabovesixoutputscorrespondtothesi课后答案网xinputs(24,25,26,27,28,29)intheexpansionpermutationbox(SeeTable6.2inthetextbook).c.Theabovesixinputscorrespondtothesixinputs(09,19,13,30,06,22)inputswww.hackshp.cninthestraightpermutationbox(SeeTable6.11inthetextbook).d.TheabovesixinputscorrespondtotheoutputsofsixdifferentS-Boxes(S-3,S-5,S-4,S-8,S-2,andS-6)inround1.20.FigureS6.20showsthesituation.TheinputstoS-box7inround2comesfromsixS-boxesinround1.FigureS6.20SolutiontoExercise20S-1S-2S-3S-4S-5S-6S-7S-8Round3010515172326StraighP-box091310081112(Round3)0809121308091213ExpansionP-box(Round4)1318S-1S-2S-3S-4S-5khdaw.comS-6S-7S-8Round4若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！7a.ThesixinputstoS-box3inround4comefromsixoutputs(13,14,15,16,17,18)ofexpansionpermutationboxinround4.b.Theabovesixoutputscorrespondstothesixinputs(08,09,10,11,12,13)intheexpansionpermutationboxinround4(SeeTable6.2inthetextbook).c.Theabovesixinputscorrespondtothesixinputs(17,01,15,23,26,05)inputsinthestraightpermutationbox(SeeTable6.11inthetextbook).d.TheabovesixinputscorrespondtotheoutputsofsixdifferentS-Boxes(S-5,S-1,S-4,S-6,S-7,andS-2)inround3.NoneofthemcomefromS-3.21.FigureS6.21showsthesituation.TheoutputsfromS-box4inround3gotofourS-boxesinround4.FigureS6.21SolutiontoExercise21khdaw.comS-1S-2S-3S-4S-5S-6S-7S-8Round31316StraighP-box课后答案网(Round3)01102026www.hackshp.cnExpansionP-box(Round4)02152933S-1S-2S-3S-4S-5S-6S-7S-8Round4a.ThefouroutputsfromS-box3inround4gotosixoutputs(26,20,10,01)ofstraightpermutationbox(SeeTable6.1).b.Theabovefouroutputscorrespondtofouroutputs(33,29,15,02)intheexpan-sionpermutationbox(SeeTable6.11).c.TheabovefourinputscorrespondstotheinputsoffourdifferentS-Boxes(S-6,S-5,S-3,andS-1)inround4.22.FigureS6.22showsthesituation.TheoutputsfromS-box6inround12goestofourdifferentS-boxesinround13.NoneofthemgotoS-box6.Sothecriterioncannotactuallybetestedbytheseexercise,butitdoesnotviolatethecriterioneither.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8FigureS6.22SolutiontoExercise22S-1S-2S-3S-4S-5S-6S-7S-8Round122124StraighP-box(Round12)04111929ExpansionP-box(Round13)05162842khdaw.comS-1S-2S-3S-4S-5S-6S-7S-8Round1323.FigureS6.23showsthesituation.Weassume课后答案网j=5.FigureS6.23SolutiontoExercise23J−2J−1JJ+1www.hackshp.cnS-1S-2S-3S-4S-5S-6S-7S-8Round10101424StraighP-box(Round10)161920161920ExpansionP-box(Round11)252829S-1S-2S-3S-4S-5S-6S-7S-8Round11Ja.OneoutputfromS-box3(output10)goestothefirstinputofS-box5(input25).b.AnoutputfromS-box4(output14)goesonethelasttwoinputsofS-box6(input29).c.AnoutputfromS-box6(output24)goestooneofthemiddleinputofS-box5(input19).khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！924.ThesolutioncanbefoundinFigureS6.24.TheoutputsofS-4isdistributedbetweenS-1,S-3,S-5,andS-7inthenextround.FigureS6.24SolutiontoExercise24S-1S-2S-3S-4S-5S-6S-7S-8Round31316StraighP-box(Round3)01102026ExpansionP-box(Round4)khdaw.com02152933S-1课后答案网S-2S-3S-4S-5S-6S-7S-8Round4a.Theoutput16goestobit2(oneofthefirsttwobitsofS-box1).www.hackshp.cnb.Theoutput14goestobit29(thelastbitofS-box5).c.Theoutput15goestobit15(oneofmiddlebitofS-box3).d.Theoutput13goestobit33(oneofthemiddlebitofS-6).25.FigureS6.25willhelpusinthisproblem.FigureS6.25SolutiontoExercise25S-1S-2S-3S-4S-5S-6S-7S-8Round4181920StraighP-box(Round4)31425ExpansionP-box(Round5)42138S-1S-2S-3S-4S-5khdaw.comS-6S-7S-8Round5若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！10a.Onlyoutput19formS-box5(inround4)goestoS-box7(inround5).How-ever,theinput38isnotamiddleinput,sothecriteriondoesnotapply.Thisanswersthequestionaboutthisexercise,butwedosomemoreinvestigations.b.Output18fromS-box5goesamiddleinput(21)inS-box4inthenextround.Tocheckthecriteria,weneedtoseeifanyinputfromS-box4goestoamiddleinputinnextround.LookingatFigureS6.24,wecanseethatthisisnotthecase.Thecriterionapplieshere.c.Wealsoobservethatoutput19fromS-box5goesamiddleinputinS-box1(input4).However,noneoftheinputsfromS-box1inround4goestoamiddleinputofS-box5inthenextround.OnlyoneoutputfromS-box1(output2goestoS-box5,input26,butitisnotamiddleinput).Thecriterionapplieshere.26.FigureS6.26showsthealternativeapproach.khdaw.comFigureS6.26SolutiontoExercise2664-bitplaintext64-bitplaintext课后答案网InitialpermutationFinalpermutationwww.hackshp.cnfRound1K1fRound16fRound16K16fRound1FinalpermutationInitialpermutation64-bitciphertext64-bitciphertextkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1127.FigureS6.27showsathree-roundcipher.WeprovetheequalitiesbetweentheL’sandR’sfrombottomtotop.WehavelabeledeachleftsectionintheencryptionLiandinthedecryption(Li)’;wehavelabeledeachrightsectionsRiintheencrypt-ingand(Ri)’indecryption.FigureS6.27SolutiontoExercise2764-bitplaintext64-bitplaintextInitialpermutationFinalpermutationL0R0(L0)’(R0)’fK1fRound3khdaw.comRound1fK2Round2课后答案网fRound2www.hackshp.cnfK3Round1fRound3L3R3(L3)’(R3)’FinalpermutationInitialpermutation64-bitciphertext64-bitciphertexta.Sincefinalpermutationandinitialpermutationsareinverseofeachother(ifthereisnocorruptionduringtransmission),wehave(L3)′=(L3)(R3)′=(R3)b.Usingthepreviousequalitiesandtherelationsinthemixers,wehave(L2)′=(R3)′=R3=R2(R2)′=(L3)′⊕f[(R3)′,K3](R2)′=L3⊕f[R3,K3](R2)′=L2⊕f[R2,K3]⊕f[R2,K3](L2)′=R2khdaw.com(R2)′=L2若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！12c.Usingthepreviousequalitiesandtherelationsinthemixers,wehave(L1)′=(R2)′=L2=R1(R1)′=R2⊕f[L2,K2](R1)′=R2⊕f[R1,K2](R1)′=L1⊕f[R1,K1]⊕f[R1,K1](L1)′=R1(R1)′=L1d.Usingthepreviousequalitiesandtherelationsinthemixers,wehave(L0)′=(L1)′⊕f[(R1)′,K1](R0)′=(R1)′=L1=R0(L0)′=R1⊕f[L1,K1](L0)′=L0⊕f[L0,K1]⊕f[L0,K1](L1)′=L0(R0)′=R0khdaw.comWehaveprovedthat(L1)′=L0and(R0)′=R0.Sincethefinalpermutationandini-tialpermutationareinverseofeachother,theplaintextcreatedatthedestinationisthesameastheplaintextstartedatthesource.课后答案网28.Ifwecreateatableofinputandoutput,wecananswersthethreequestions.www.hackshp.cnInOutInOutInOutInOut140123134125443717021914522649381103121531273939240404163728564001052617472934410506081855305342030716193031464328080720403242441509272151335045061020224534364621111323333529471012022448363248a.Themissinginputsare09,18,22,25,35,38,43and54.b.Fromabovetable,wecanseethattheleft24bitscomefromtheleft28bits(exceptbits09,18,22,and25,whichareblocked).c.Fromtheabovetable,wecanseetheright24bitscomefromtheright28bits(exceptbits35,38,43,and54,whichareblocked).29.Thefollowingshowstheresult:(1066009900880088)khdaw.com16若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1330.Thefollowingshowstheresult:(0F55AAFF0F55AAFF)1631.Thefirstroundkeyis(143740133784)1632.Thefollowingshowstheeffect:OriginalsComplementsPlaintext:0000000000000000FFFFFFFFFFFFFFFFKey:0000000000000000FFFFFFFFFFFFFFFFkhdaw.comCiphertext:080802AAAA02A8AAF7F7FD5555FD5755Whenwecomplementtheplaintextandthekey,theciphertextiscomplemented.33.FigureS6.33showstheencryptionusing3DESwithtwokeys,inwhichXorYare课后答案网theintermediatetexts.www.hackshp.cnFigureS6.33SolutiontoExercise33K1K2K1PDESXYDESDESCcipherciphercipherEncryptionVanOorschotandWienerhavedevisedameet-in-the-middleattackontheaboveconfiguration.Theattackisbasicallyaknown-plaintextattack.Itfollowsthestepsshownbelow:a.Eveinterceptsnplaintext/ciphertextpairsandstorestheminatablewhichissortedonvaluesofPasshownbelow:PlaintextCiphertextP1C1P2C2……PnCnTable1:nP/Cpairskhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！14b.EvenowchoosesavalueforX(seeFigureS6.33)andusesthedecryptionalgo-rithm,andall256possibleK1’s56differentPvaluesasshownvaluestocreate2below:P561=D(K11,X)P2=D(K12,X)…Pm=D(K1m,X)wherem=2c.IfavalueofPcreatedinstepbmatchesoneofthevalueofPinTable1,EveusesthecorrespondingvalueforK1(fromthelistinstepb)andthevalueofCfromTable1andcalculatesavalueforsecondintermediatetextY=D(K1,C).NowEvecreatesasecondtable,Table2,whichissortedonthevalueofY.EvehasnowrpossiblecandidateforK1keys.YK1Y1K11khdaw.comY2K12……YrK1r课后答案网Table2:rY/K1pairsd.EvenowsearchesforK2.Foreach256possiblevaluesofK2,EveusesthedecryptionalgorithmandthevalueofXchoseninstepbtocreate256differentwww.hackshp.cnvaluesforY’s.Y561=D(K21,X)Y2=D(K22,X)…Ym=D(K2m,X)wherem=2IfavalueofYicreatedinthisstepmatchesoneofthevalueinTable2,Evehavefoundapairofkeys:K1isextractedfromTable2andK2isextractedfromthedecryptionalgorithmthatmatchesthevalueofYinTable2.e.NowEvetestspairsofK1/K2valuesonmoreinterceptedplaintext/ciphertext.Ifthereismatching,Evehasfoundthekeys;ifthereisnomatch,EveneedstorepeatstepbtoeusingadifferentvalueofX.34.permute(n,m,inBlock[1…n],outBlock[1…m],permutationTable[1…m]){i←1while(i≤m){outBlock[i]←inBlock[permutationTable[i]]i←i+1}return}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1535.split(n,m,inBlock[1…n],leftBlock[1…m],rightBlock[1…m]){i←1while(i≤m){leftBlock[i]←inBlock[i]rightBlock[i]←inBlock[i+m]i←i+1}return}khdaw.com36.combine(n,m,leftBlock[1…n],rightBlock[1…n],outBlock[1…m]){课后答案网i←1while(i≤m){www.hackshp.cnoutBlock[i]←leftBlock[i]outBlock[i+m]←rightBlock[i]i←i+1}return}37.exclusiveOr(n,firstBlock[1…n],secondBlock[1…n],outBlock[1…n]){i←1while(i≤n){outBlock[i]←firstBlock[i]⊕secondBlock[i]i←i+1}return}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1638.cipher(plainBlock[1…64],RoundKeys[1…16][1…48],cipherBlock[1…m64]){permute(64,64,plainBlock,inBlock,InitialPermutationTable)split(64,32,inBlock,rightBlock,leftBlock)for(round=1to16){mixer(leftBlock,rightBlock,RoundKey[round])swapper(leftBlock,rightBlock)}swapper(leftBlock,rightBlock)combine(32,64,leftBlock,rightBlock,outBlock)permute(64,64,outBlock,cipherBlock,FinalPermutationTable)khdaw.com}39.Wehaveaddedoneextraparamete课后答案网rED(encrypt/decrypt).IfED=E,wedoencryption;ifED=D,wedodecryption.cipher(ED,plainBlock[1…64],RoundKeys[1…16][1…48],cipherBlock[1…m64])www.hackshp.cn{permute(64,64,plainBlock,inBlock,InitialPermutationTable)split(64,32,inBlock,rightBlock,leftBlock)for(round=1to16){if(ED=E)mixer(leftBlock,rightBlock,RoundKey[round]if(ED=D)mixer(leftBlock,rightBlock,RoundKey[16−round]if(round!=16)swapper(leftBlock,rightBlock)}combine(32,64,leftBlock,rightBlock,outBlock)permute(64,64,outBlock,cipherBlock,FinalPermutationTable)}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER7AES(SolutiontoPracticeSet)ReviewQuestions1.ThecriteriadefinedbyNISTforselectingAESfallintothreeareas:security,cost,khdaw.comandimplementation.2.Thefollowingtableliststheparameters:课后答案网VersionBlockKeyRound-keysizeNumberofsizesizeroundsAES-12812812812810www.hackshp.cnAES-19212819212812AES-256128256128143.Thenumberofroundkeysandthenumberoftransformationdependonthenum-berofrounds.Thefollowingtablelisttheinformation.Notethatthereisonetrans-formationforpre-round.Alsonotethatthelastroundusesonlythreetransformations.VersionNumberofNumberofNumberofroundsroundkeysTransformationsAES-12810111+9×4+3=40AES-19212131+11×4+3=48AES-25614151+13×4+3=564.DESisbit-oriented;AESisbyte-oriented.InDES,anS-boxtakes6bitsandtrans-formsitto4bits;inAES,SubBytestransformationtakesabyteandchangeittoanotherbyte.InDES,P-boxestransposebits;inAEStheShiftRowstransforma-tiontransposesbytes.Toprovidemixingofbitsinsideabyte,AESusestheMix-Columnstransformation.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！25.Beforeandaftereachstage,thedatablockisreferredtoasastate.States,likeblocks,aremadeof16bytes,buttheyarenormallytreatedasmatricesof4×4bytes.Thefollowingtableshowsthenumberofstatesusedineachversion.Wehaveusedtwoextrastates:onebeforethepre-roundandoneafterthelastround.Ifyoudonotconsiderthis,thenumberofstatesisreducedbytwo.VersionNumberofNumberofroundsStatesAES-12810(1)+1+9×4+3+(1)=42AES-19212(1)+1+11×4+3+(1)=50AES-25614(1)+1+13×4+3+(1)=586.TheSubBytes,MixColumns,andAddRoundKeytransformationchangethecon-tentsofbytes;theShiftRowstransformationdoesnot.khdaw.com7.SubstitutioninDESisdonebyS-boxes.Eachboxsubstitutesa6-bitvaluewitha4-bitvalue.WeneedeightS-boxestocreatea32-bithalfblock.SubstitutioninAESisdonethroughSubBytestransformationthattransformsawholestatetoanotherstate.However,wecansaythatSubBytesactuallysubstitutes16byteswithnew16bytes.课后答案网8.PermutationinDESisappliedintwosteps:beforesubstitutionandaftersubsitu-tion.Thefirstisanexpansionpermutationtocreatea48-bithalfblockoutofa32-www.hackshp.cnbithalfblock.Thisisneededbecausetheroundkeyis48bitslong.PermutationinAESisstraightpermutationofbytes.Sincethesizeoftheblockandthesizeoftheroundkeyarethesame,thereisnoneedforanexpansionpermutation.9.InDES,thesizeoftheblockis64bits,butthesizeoftheroundkeyis48bits.InAESthesizeoftheblockandtheroundkeyareboth128bits(forallversions).10.InDES,permutationisbit-oriented;inAES,permutationisbyteoriented.Toper-mutethebitsinsideabyte,AESusestheMixColumnstransformation.Exercises11.ThedisadvantageofusingkeyedS-boxesisthatitmakesthedesignoftheciphermoredifficult.Inparticular,itismoredifficulttocreateS-boxesthatareinverseofeachotherintheencryptionanddecryptioncipher.TheadvantageofusingkeyedS-boxesisthatakeyedS-boxisnormallynon-linear,whichprotectthecipheragainstlinearcryptanalysis.12.Alargerblocksizecreatesmoremixingofbitsineachblock.Inacipherwithablocksizeof64,eachbit,inaverage,isdependentononly32otherbits;inablocksizeof128bits,eachbitdepends,onaverage,on64bits.Thisisdefinitelyanadvantage.Onedisadvantageisthatthelargeblocksizecreatesanoverheadofaddingmorepaddingtothelastblock.Inparticular,ifthesizeofthemessageisverysmallandlessthanthesizeofablock,mostoftheplaintextismadeofpad-ding.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！313.Havingdifferentnumberofroundshastheadvantagethatnewversionsofcipherwithmorenumberofroundscanbeused,withoutchangingthestructureofcipher,ifthecipherisattackedbydifferentialandlinearcryptanalysis(orotherattacksthatdependonthenumberofrounds).Forexample,wecanuseAESwith10roundsaslongasitisnotsecured.Ifitisattacked,wecanmovetotheversionwith12or14roundswithoutchangingthestructureofthecipher.14.Havingdifferentkeysizehastheadvantagethatnewversionsofcipherwithlargerkeysizecanbeused,withoutchangingthestructureofcipher,ifthecipherisattackedbybrute-forcecryptanalysis.Forexample,wecanuseAESwitha128-bitcipherkeyaslongasitisnotattacked.Ifitisattacked,wecanmovetotheversionwith192-bitor256-bitcipherkey.15.Acipherinwhichthesizeoftheroundisthesameasthesizeoftheroundkeyiseasiertodesignbecausewedonothavetouseexpansion(orcompression)permu-tationtomatchthesizeoftheblocktothesizeoftheroundkey.Thisenableustokhdaw.commakethenon-Feistelciphers.16.a.Thestatehas16byteswhicharepermutedbyShiftRowstransformationusingthefollowingpermutationtable:课后答案网01020304060708051112091016131415b.Thestatehas16byteswhicharepermutedbyInvShiftRowstransformationwww.hackshp.cnusingthefollowingpermutationtable:01020304080506071112091014151613c.WecanprovethattwotransformationareinverseofeachotherbyapplyingthetheprocesswelearnedinChapter3.Weaddindexes,weswapindexesandcon-tents,andthensortthetableaccordingtotheindexes.WestartwiththeShiftRowstabletogetInvShiftRowstable.Afteraddingtheindex,wehave0102030406070805111209101613141501020304050607080910111213141516Afterswappingthecontentsandtheindexes,wehave0102030405060708091011121314151601020304060708051112091016131415Aftersortingthetableaccordingtotheindex,wehavethefollowingtablewhichisthesameastheInvShiftRowstablefoundinpartb.010203040805060711120910141516130102030405060708091011121314151617.Weusetwoplaintextsthatdifferonlyinthefirstbit:khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！4P1:(00000000000000000000000000000000)16P2:(80000000000000000000000000000000)16a.ApplyingtheSubBytestransformationtoP1andP2,weget:T1:(63636363636363636363636363636363)16T2:(CD636363636363636363636363636363)16T2andT1differonlyin5bits.b.ApplyingtheShiftRowstransformationtoP1andP2,weget:T1:(00000000000000000000000000000000)16T2:(80000000000000000000000000000000)16khdaw.comT2andT1differonlyin1bit.ApplyingtheMixColumntransformationtoP1andP2,weget:T1:(00000000000000000000000000000000)16课后答案网T2:(1B80809B000000000000000000000000)16T2andT1differin9bits.www.hackshp.cnc.ApplyingtheAddRoundKeyof1280-bittransformationtoP1andP2,weget:T1:(00000000000000000000000000000000)16T2:(80000000000000000000000000000000)16T2andT1differonlyin1bit.Notethatwehaveusedaroundkeywith1280’s,buttheresultisthesameifweuseanykey.18.WehaveSubBytes(0x57⊕0xA2)=SubBytes(0xF5)=0xE6SubBytes(0x57)⊕SubBytes(0xA2)=0x5B⊕0x3A=0x61Definitely,thetwoaredifferent;theSubBytetransformationisnon-linear19.a.TheSubBytestransformationisrepeatedineachround.SowehaveNrofthistransformation.b.TheShiftRowstransformationisrepeatedineachround.SowehaveNrofthistransformation.c.TheMixColumnstransformationisrepeatedineachroundexceptthelastround.Sowehave(Nr−1)ofthistransformation.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！5d.TheAddRoundKeytransformationisrepeatedineachround.Inaddition,wehaveoneofthistransformationinthepre-roundsection.Sowehave(Nr+1)ofthistransformation.e.ThetotalnumberoftransformationisTotalnumberoftransformation=Nr+Nr+(Nr−1)+(Nr+1)=4×Nr20.a.FigureS7.20ashowsthekeyexpansioninAES-192.FigureS7.20aSolutiontoExercise20.aCipherk0k1k2k3k4k5k6k7k8k9k10k11k12k13k14k15k16k17k18k19k20k21k22k23keykhdaw.comw0w1w2w3w4w5t6w6w7w8w9w10w11t42课后答案网w42w43w44w45w46w47t48w48w49w50w51www.hackshp.cnRCon[i/6]Wi–1RotWordSubWordtiMakingofti(temporary)wordsi=6Nrb.FigureS7.20bshowsthekeyexpansioninAES-256FigureS7.20bSolutiontoExercise20.bCipherkey(32bytes)w0w1w2w3w4w5w6w7t8w8w9w10w11u12w12w13w14w15t48w48w49w50w51u52w52w53w54w55t56w56w57w58w59u60w60RCon[i/8]Wi–1RotWordSubWordtiWi–1SubWorduiMakingofti(temporary)wordsi=8Nrkhdaw.comMakingofuiwordsi=8Nr+4若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！621.a.Wecanuse(x11−1modprime)and(x12−1modprime),inwhichtheprimeisthetheirreduciblepolynomial(x8+x4+x3+x+1),tofindthefirsttermsofRCon[11]andRCon[12].ThefollowingshowstheconstantsforAES-192.Round(RCon)Round(RCon)Round(RCon)1(01000000)165(10000000)169(1B000000)162(02000000)166(20000000)1610(36000000)163(04000000)167(40000000)1611(6C000000)164(08000000)168(80000000)1612(D8000000)16b.Wecanuse(x13−1modprime)and(x14−1modprime),inwhichtheprimeisthetheirreduciblepolynomial(x8+x4+x3+x+1),tofindthefirsttermsofkhdaw.comRCon[13]andRCon[14].ThefollowingshowstheconstantsforAES-256.Round(RCon)Round(RCon)Round(RCon)1(01000000)166(20000000)1611(6C000000)16课后答案网2(02000000)167(40000000)1612(D8000000)163(04000000)168(80000000)1613(AB000000)16www.hackshp.cn4(08000000)169(1B000000)1614(4D000000)165(10000000)1610(36000000)1622.a.Thepre-roundoperationneedsafour-wordroundkey.ThecipherkeyinAES-192issixwords;onlythefirstfourwordsofitisusedinthepre-roundopera-tion.b.Thepre-roundoperationneedsafour-wordroundkey.ThecipherkeyinAES-256iseightwords;onlythefirstfourwordsofitisusedinthepre-roundopera-tion.23.Theresultisanidentitymatrixasshownbelow.Notethattheadditionandmulti-plicationofelementsareinGF(2).10001111001001011000000011000111100100100100000011100011010010010010000011110001101001000001000011111000×01010010=00001000011111000010100100000100001111101001010000000010000111100100101000000001−1−1X×XXXkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！724.Theresultisanidentitymatrixasshownbelow.Notethattheadditionandmulti-plicationofcoefficientsareinGF(2).xx×111x3×x2×xx3×x×1x3×x2×1x3×110001xx×11x3×1x3×x2×xx3×x×1x3×x2×10100×=11xx×1x3×x2×1x3×1x3×x2×xx3×x×10010x×111xx3×x×1x3×x2×1x3×1x3×x2×x0001CC−1C×C−1Theidentitymatrixcanbeeasyfound.Forexample,ifwemultiplythefirstrowofCbythefirstcolumnofC−1,wegetkhdaw.com(x)(x3+x2+x)+(x+1)(x3+1)+(1)(x3+x2+1)+(1)(x3+x+1)=1ButifwemultiplythesecondrowofCbythefirstcolumnofC−1,weget课后答案网(1)(x3+x2+x)+(x)(x3+1)+(x+1)(x3+x2+1)+(1)(x3+x+1)=025.Mostofthecodematches,linebyline,withthestepsintheprocess.Theonlysec-www.hackshp.cntionthatneedssomeexplanationistheloop.Theiterationsoftheloopgivesusc0=b0⊕b4⊕b5⊕b6⊕b7→c0=b0⊕b4⊕b5⊕b6⊕b7c1=b1⊕b5⊕b6⊕b7⊕b0→c1=b0⊕b1⊕b5⊕b6⊕b7c2=b2⊕b6⊕b7⊕b0⊕b1→c2=b0⊕b1⊕b2⊕b6⊕b7c3=b3⊕b7⊕b0⊕b1⊕b2→c3=b0⊕b1⊕b2⊕b3⊕b7c4=b4⊕b0⊕b1⊕b2⊕b3→c4=b0⊕b1⊕b2⊕b3⊕b4c5=b5⊕b1⊕b2⊕b3⊕b4→c5=b1⊕b2⊕b3⊕b4⊕b5c6=b6⊕b2⊕b3⊕b4⊕b5→c6=b2⊕b3⊕b4⊕b5⊕b6c7=b7⊕b3⊕b4⊕b5⊕b6→c7=b3⊕b4⊕b5⊕b6⊕b7Therearrangedcodeistheresultofmatrixmultiplicationc=X×bifweignorethezeroterms.Aftereachlineiscreatedd=c+yismade.26.a.TheinvByteroutinecallstwootherroutine:multiplyandquotation.Thefirstroutinemultipliestwobytes;thesecondroutinefindsthequotientofdividingthefirstbytebythesecond.Thequotationroutinecallsthedegreeroutinewhichfindsthedegreeofabyte(asapolynomial)khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8invByte(byte){if(byte=0)returnbyter1←(11B)16//modulusr2←bytet1←(00)16t2←(01)16while(r2>(00)16){q←quotation(r1,r2)r←r1⊕multiply(q,r2)khdaw.comt←t1⊕multiply(q,t2)r1←r2r2←rt1←t2t2←t}课后答案网returnt1}www.hackshp.cnmultiply(byte1,byte2){i←(00)16res←(00)16while(byte2≠(00)16){if[(byte2AND(01)16)=(01)16]res←res⊕shiftLeft(i,byte1)byte2←shiftRight(1,byte2)}returnres}Quotation(byte1,byte2){degreeDiff←degree(byte1)−degree(byte2)while(degreeDiff≥0){temp←shiftLeft(degreeDiff,1)khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！9byte1←byte1⊕shiftLeft(degreeDiff,byte2)res←resORtemp}returnres}degree(byte){deg←−1while(byte>0){deg←deg+1khdaw.combyte←shiftLeft(1,byte)}returndeg}课后答案网b.ByteToMatrix(byte,matrix)www.hackshp.cn{for(r=7downto0){matrix[r]←bytemod2byte←byte/2//integerdivision}}c.MatrixToByte(matrix,byte){byte←0for(r=7downto0){byte←byte×2+matrix[r]}}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1027.InvSubBytes(S[0…3][0…3]){for(r=0to3)for(c=0to3)S[r][c]←invsubbyte(S[r][c])return(S)}invsubbyte(byte){d←ByteToMatrix(byte)khdaw.comc←d⊕ByteToMatrix(0x63)b←X−1×ca←MatrixToByte(b)课后答案网return(a−1)}28.TheShiftRowsalgorithmcallstheshiftrowroutinethreetimes(thefirstrowisnotwww.hackshp.cnshifted)toshifteachrow.Thefollowingshowshowshiftingisdone:Firstcalln=1c=0row3←t0c=1row0←t1c=2row1←t2c=3row2←t3Secondcalln=2c=0row2←t0c=1row3←t1c=2row0←t2c=3row1←t3Thirdcalln=3c=0row3←t0c=1row2←t1c=2row0←t2c=3row1←t329.CopyRow(row[0…3],t[0…3]){for(c=0to3)t[c]←row[c]}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1130.InvShiftRows(S[0…3][0…3]{for(r=0to3)invshiftrow(S[r],r)}invshiftrow(row[0…3],r){CopyRow(row,t)for(c=0to3)row[(c+n)mod4]←t[c]khdaw.com}31.TheMixColumnsalgorithmcallsthemixcolumroutinefourtimes,onceforeachcolumnoftheoldstatetocreatethecorrespondcolumnofthenewstate.Themix-column课后答案网routineactuallyperformsthefollowingmatrixmultiplicationcol=C×t,inwhichcolisthenewcolumnmatrix,tistheoldcolumnmatrix,andtheCisthesquareconstantmatrix.Wecanwritethecodeinthemixcolumnroutineaswww.hackshp.cncol0←C00•t0⊕C01•t1⊕C02•t2⊕C03•t3col1←C10•t0⊕C11•t1⊕C12•t2⊕C13•t3col2←C20•t0⊕C21•t1⊕C22•t2⊕C23•t3col3←C30•t0⊕C31•t1⊕C32•t2⊕C33•t332.CopyColumn(column[0…3],t[0…3]){for(r=0to3)t[r]←column[r]}33.MixColumns(S[0…3][0…3]{for(c=0to3)mixcolumn(S[c])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！12mixcolumn(col[0…3]){CopyColumn(col,t)col[0]←MultField(0x02,t[0])⊕MultField(0x03,t[1])⊕t[2]⊕t[3]col[1]←t[0]⊕MultField(0x02,t[1])⊕MultField(0x03,t[2])⊕t[3]col[2]←t[0]⊕t[1]⊕MultField(0x02,t[2])⊕MultField(0x03,t[3])col[3]←MultField(0x03,t[0])⊕t[1]⊕t[2]⊕MultField(0x02,t[3])}34.InvMixColumns(S[0…3][0…3]{for(c=0to3)khdaw.cominvmixcolumn(S[c])}invmixcolumn课后答案网(col[0…3]){CopyColumn(col,t)www.hackshp.cncol[0]←0x0E•t[0])⊕(0x0B•t[1])⊕(0x0D•t[2])⊕(0x09•t[3])col[1]←0x09•t[0])⊕(0x0E•t[1])⊕(0x0B•t[2])⊕(0x0D•t[3])col[2]←0x0D•t[0])⊕(0x09•t[1])⊕(0x0E•t[2])⊕(0x0B•t[3])col[3]←0x0B•t[0])⊕(0x0D•t[1])⊕(0x09•t[2])⊕(0x0E•t[3])}35.Thealgorithmusesaloopthatiteratesfourtimes,oneforeachcolumnofthecur-rentstate.Ineachiteration,acolumnoftheoldstateisexclusive-oredwithakeywordtocreateanewcolumn.S[c]←S[c]⊕W[4×round+c]Forexample,inround5,wehaveS[0]←S[0]⊕W[20]S[1]←S[1]⊕W[21]S[2]←S[2]⊕W[22]S[3]←S[3]⊕W[23]36.a.ThesubbyteroutinecalledbytheSubWordistheonedefinedinthetext.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！13SubWord(W[0…3]){for(i=0to3)W[i]←subbyte(W[i])return(W)}b.RotWord(W[0…3]){CopyRow(W,t)for(i=0to3)khdaw.comW[(i+3)mod4]←t[i]return(W)}37.课后答案网a.www.hackshp.cnKeyExpansion(Key[0…23],W[0…51]{for(i=0to5)W[i]←Key[4i]|Key[4i+1]|Key[4i+2]|Key[4i+3]for(i=6to51)if(imod6=0){t←subword(rotWord(W[i−1])⊕Rcon[i/6]W[i]←t⊕W[i−6]}elseW[i]←W[i−1]⊕W[i−6]}b.KeyExpansion(Key[0…31],W[0…59]){for(i=0to7)W[i]←Key[4i]|Key[4i+khdaw.com1]|Key[4i+2]|Key[4i+3]for(i=8to59)若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！14if(imod8=0){t←subword(rotWord(W[i−1])⊕Rcon[i/8]W[i]←t⊕W[i−8]}if(imod8=4){t←subword(W[i−1])W[i]←t⊕W[i−8]}elseW[i]←W[i−1]⊕W[i−8]khdaw.com}38.Thefollowingalgorithmmodifiesthekeyscreatedfortheoriginaldesigntocreatetheroundkeysforthealternatedesign.KeyExpansionAlternative课后答案网(Key[0…15]){KeyExpansion(Key[0…15],W[0…43])www.hackshp.cnfor(rnd=1to9){for(r=0to3)t[r]←W[rnd×4+r]W[rnd×4+0]←0x0E•t[0]⊕0x0B•t[1]⊕0x0D•t[2]⊕0x09•t[3]W[rnd×4+1]←0x09•t[0]⊕0x0E•t[1]⊕0x0B•t[2]⊕0x0D•t[3]W[rnd×4+2]←0x0D•t[0]⊕0x09•t[1]⊕0x0E•t[2]⊕0x0B•t[3]W[rnd×4+3]←0x0B•t[0]⊕0x0D•t[1]⊕0x09•t[2]⊕0x0E•t[3]}return(W[0…43])}39.InvCipher(InBlock[0…16],outBlock[0…16],W[0…43]{BlockToState(Inblock,S)S←AddRoundKey(S,W[40…43])for(r=1to10)khdaw.com//rdefinestheround若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！15{S←InvShiftRows(S)S←InvSubBytes(S)S←AddRoundKey(S,W[(10−r)×4…(10−r)×4+3)if(r≠10)S←InvMixColumns(S)}StateToBlock(S,outBlock)}40.InvCipherAlternate(InBlock[0…16],outBlock[0…16],W[0…43]{khdaw.comBlockToState(Inblock,S)S←AddRoundKey(S,W[40…43])for(r=1to9)//rdefinestheround课后答案网{S←InvSubBytes(S)S←InvShiftRows(S)www.hackshp.cnS←InvMixColumns(S)S←InvAddRoundKey(S,W[(10−r)×4…(10−r)×4+3)}S←InvSubBytes(S)S←InvShiftRows(S)S←AddRoundKey(S,W[0…3])StateToBlock(S,outBlock)}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！16khdaw.com课后答案网www.hackshp.cnkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER8EnciphermentUsingModernBlockCiphers(SolutiontoPracticeSet)ReviewQuestions1.Modernblockciphersencryptanddecryptsmallblocks.DESusesablocksizeofkhdaw.com8bytes(characters)andAESusesablocksizeof16bytes(characters).Inreallife,weneedtoencryptordecryptlargerunitsofdata.Forexample,aone-pagedocu-mentisnormallymorethan1000characters.Modeofoperationsaredesignedtoallowustorepeatedlyuseamodernblockcipherforencryptionanddecryption.2.Wediscussedelectroniccodebook(ECB)课后答案网,cipherblockchaining(CBC),cipherfeedback(CFB),outputfeedback(OFB),andcounter(CTR)modes.3.Intheelectroniccodebook(ECB)mode,theplaintextisdividedintoNblocks.www.hackshp.cnEachblockisnbits.Thesamekeyisusedtoencryptanddecrypteachblock.ßAdvantages.Thismodehastwoobviousadvantages.First,itissimple.Sec-ond,transmissionerrorisnotpropagatedfromoneblocktotheother.ßDisadvantages.Thismodehassomesecurityproblems.First,patternsattheblocklevelarepreserved.Second,blockindependencycreatesopportunitiesforEvetosubstitutessomecipherblockswithsomecipherblocksofherown.4.Inthecipherblockchaining(CBC)mode,eachplaintextblockisexclusive-oredwiththepreviousciphertextblockbeforebeingencrypted.Aphonyblockcalledtheinitialvector(IV)isusedtoserveasC0.Thesamekeyisusedtoencryptanddecrypteachblock.ßAdvantages.Thismodehasoneobviousadvantage.Eachciphertextblockdependsonpreviousciphertextblocks.Patternsattheblocklevelarenotpre-servered.Evecannotreordertheciphertextblocks.ßDisadvantages.Thismodehassomesecurityproblems.First,iftwomes-sagesareequal,theirenciphermentisthesameiftheyusethesameIV.Sec-ond,Evecanaddsomeciphertextblocksattheendofthemessage.Themodealsohassomeerror-propagationproblem:asinglebiterrorinoneciphertextblockmaycreateserrorsinthecorrespondingplaintextblockandthenextplaintextblock.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！25.Inthecipherfeedback(CFB)mode,thesizeoftheplaintextorciphertextblockisr,wherer≤n.TheideaistouseDESorAES,notforencryptingtheplaintextordecryptingtheciphertext,buttoencryptordecryptthecontentsofashiftregister,S,ofsizen.Dataencryptionisdonebyexclusive-oringanr-bitplaintextblockwithrbitsoftheshiftregister.Datadecryptionisdonebyexclusive-oringanr-bitciphertextblockwithrbitsoftheshiftregister.Foreachblock,theshiftregisterSiismadebyshiftingtheshiftregisterSi−1(previousshiftregister)rbitstotheleftandfillingtherightmostrbitswithCi−1.ßAdvantages.OneadvantageofCFBisthatnopaddingisrequiredbecausethesizeoftheblocks,r,isnormallychosentofitthedataunittobeencrypted.Anotheradvantageisthatthesystemdoesnothavetowaituntilithasreceivedalargeblockofdatabeforestartingtheencryption.ßDisadvantages.OnedisadvantageofCFBisthatitislessefficientthanCBCorECB,becauseitneedstoapplytheencryptionfunctionofunderlyingblockkhdaw.comcipherforeachsmallblockofsizer.AnotherdisadvantageisthatEvecanaddsomeciphertextblocktotheendofthestream.6.Theoutputfeedback(OFB)modeisverysimilartoCFBmode,withonediffer-ence:eachbitintheciphertextisindependentofthepreviousbitorbits.Thisavoidserrorpropagation.Ifanerroroccurs课后答案网intransmission,itdoesnotaffectthebitsthatfollow.LikeCFB,boththesenderandthereceiverusetheencryptionalgorithm.www.hackshp.cnßAdvantages.OneadvantageofOFBisthatnopaddingisrequiredbecausethesizeoftheblocks,r,isnormallychosentofitthedataunittobeencrypted.Anotheradvantageisthatthesystemdoesnothavetowaituntilithasreceivedalargeblockofdatabeforestartingtheencryption.ßDisadvantages.OnedisadvantageofOFBisthatitislessefficientthanCBCorECB,becauseitneedstoapplytheencryptionfunctionofunderlyingblockcipherforeachsmallblockofsizer.AnotherdisadvantageisthatEvecanaddsomeciphertextblocktotheendofthestream.7.Inthecounter(CTR)mode,thereisnofeedback.Thepseudorandomnessinthekeystreamisachievedusingacounter.Ann-bitcounterisinitializedtoapre-determinedvalue(IV)andincrementedbasedonapredefinedrule(mod2n).Toprovideabetterrandomness,theincrementvaluecandependontheblocknumbertobeincremented.Theplaintextandciphertextblockhavethesameblocksizeastheunderlyingcipher(e.g.,DEAorAES).Plaintextblocksofsizenareencryptedtocreateciphertextblocksofsizen.ßAdvantages.OneadvantageofCTRisthatitcanbeusedtocreaterandomaccessfileaslongasthevalueofthecounterisrelatedtotherecordnumberinthefile.ßDisadvantages.OnedisadvantageofCTRisthatthesizeofblockisthesameasthesizeoftheunderlyingcipher(DESorAES).Encryptionordecryptionneedstobedonen-bitatatime;theprocessneedstowaituntilnbitofdataisaccumulated.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！38.FirstGroup:ECBandCBCSecondGroup:CFB,OFB,andCTR9.FirstGroup:ECBandCBCSecondGroup:CFB,OFB,andCTR10.FirstGroup:ECBandCBCSecondGroup:CFB,OFB,andCTR11.RC4usesastateofbytesforkeygeneration.Eachkeyinthekeystreamisaper-mutationofakeystate.A5/1usestheresultofthreeLFSR’stocreateakeybit.WecansaythatkeygenerationinRC4isbyte-oriented,butthekeygenerationinA5/1khdaw.comisbit-oriented.Theothermaindifferenceisencryptionanddecryption.RC4encryptsanddecryptsacharacteratatime;A5/1encryptsanddecryptsaframeatatime.12.ThesizeofdatainRC4isnormally8bits;课后答案网dataisnormallyencryptedordecryptedabyteatatime.ThesizeofdatainA5/1is228bits;dataisencryptedordecryptedaframeatatime.13.ECBcanbeusedforparallelprocessingbecauseeachblockisencryptedorwww.hackshp.cndecryptedindependently.14.ECBcanbeusedforenciphermentofblocksinarandom-accessfilebecausetheencryptionanddecryptionofeachblockisindependentfromtherestoftheblocks.Exercises15.InCFBmode,thekeygeneratorforblockiusesCi−1,theciphertextcreatedinblock(i−1).AccordingtoourdefinitioninChapter5,thisisanonsynchronousstreamcipher.InOFBmode,thekeygeneratorforblockiusespartofthekeyfromthepreviousblock,butitisindependentfromtheplaintextandciphertextinthepreviousblock.AccordingtoourdefinitioninChapter5,thisisasynchronousstreamcipher.16.InCFB,ciphertextistransmittedinblocksofrbits.Asinglebiterrorinacipher-textblockaffectsthecorrespondingbitplaintextblock.However,thecorruptiondoesnotstophere.Thecorruptedciphertextblockinthereceiversiteenterstheshiftregisterandcorruptsthesubsequentplaintextblocksuntilitfallsofftheshiftregister.Ingeneral,asinglebiterrorinciphertext,maycorrupt(n/r+1)blocksoftheplaintext.Toseetherelations,assumetheunderlyingcipherisDES(n=64)andencryption/decryptionisdoneabyteatatime(r=8).Imaginethesecondbitinciphertextblock5iscorruptedduringtransmission.Whenthisblockisdecrypted,onlythesecondbitinplaintextblock5isinerror.However,thiscipher-textblockenterstheshiftregisterandremainsinthereuntilthenext8blockskhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！4arrives.Thisresultsinthepossiblecorruptionofallbitsinthenext8plaintextblocks.Inotherwords,9blocksmayhavebeencorrupted.17.InECB,eachblockisdecryptedindependently.However,sincethedecryptionisdoneablockatatime(DESorAES),thecorruptedbit17inciphertextblock8mayaffectallnbitsinplaintextblock8.18.InCBC,ifbits17and18inciphertextblock9arecorrupted,allnbitsinplaintextblock9maybecorrupted(decryptionisoneblockatatime).However,bits17and18inciphertextblock9arealsoexclusive-oredwithbits17and18ofthenextblock(block10).Therefore,n+2bitsmaybecorrupted;nbitsinblock9and2bitsinblock10.Noneofthebitsofotherblocks(block11…)areaffected.Thesystemrecoversitselfafterblock11.19.AsdiscussedinthesolutiontoExercise16,acorruptedciphertextblockinCFBaffectsthecorrespondingplaintextblockandthefollowingn/rplaintextblocks.Ifweassumen=64,thefollowingplaintextblocksmaybecorrupted:block11(bitskhdaw.com3to6)andblock12to19(allbits).20.InCRTmode,thereisnofeedback.Ifciphertextblocks3and4arecorrupted,onlyplaintextblocks3and4willbecorrupted.21.InOFBmode,thefeedbackisonlyinthekey-generationsystem.Ifciphertextblock11iscorrupted,onlyplaintextblock11maybecorrupted.课后答案网22.InCFBmode,itisobviousthatifkiusedattheBob’ssiteisthesameaskiusedattheAlice’ssite,then(Pi)′createdbyBobisthesameasPisentbyAlice(assumingwww.hackshp.cnnocorruptionintransmission):(Pi)′=(Ci)′⊗ki=Pi⊗ki⊗ki=Pi⊗0=PiHowever,wealsoneedtoprovethatkiusedbyAliceandBobarealsothesame.IfthereisnocorruptionintransmissionandtheIV’susedbyAliceandBobarethesame,then(Si)′=Si.Now,wecanprove(ki)′=ExtractLeftr[EK(Si)′]=ExtractLeftr[EK(Si)]=ki23.InOFBmode,itisobviousthatifkiusedattheBob’ssiteisthesameaskiusedattheAlice’ssite,then(Pi)′createdbyBobisthesameasPisentbyAlice(assumingnocorruptionintransmission):(Pi)′=(Ci)′⊗ki=Pi⊗ki⊗ki=Pi⊗0=PiThekiusedbyBobisdefinitelythesameaskiusedbyAliceifbothAliceandBobusethesameIV’s.24.InCRTmode,itisobviousthatifkiusedattheBob’ssiteisthesameaskiusedattheAlice’ssite,then(Pi)′createdbyBobisthesameasPisentbyAlice(assumingnocorruptionintransmission):(Pi)′=(Ci)′⊗ki=Pi⊗kkhdaw.comi⊗ki=Pi⊗0=Pi若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！5ThekiusedbyBobisdefinitelythesameaskiusedbyAliceifbothAliceandBobusethesameIV’sforthecounter.25.FigureS8.25showsboththeencryptionanddecryption.Itispossibletocanceltheunderlyingencryptionforthefirstblockandexclusive-ortheIVdirectlywithP1.FigureS8.25SolutiontoExercise25IVC1CN−1KEKEKEnbitsk1nbitsk2nbitskNnbitsnbitsnbitsnbitsnbitsnbitsP1C1P2C2PNCNEncryptionkhdaw.comIVC1CN−1KEKEKE课后答案网nbitsk1nbitsk2nbitskNnbitsnbitsnbitsnbitsnbitsnbitsC1P1C2P2CNPNwww.hackshp.cnDecryption26.FigureS8.26showsboththeencryptionanddecryption.Itispossibletocanceltheunderlyingencryptionforthefirstblockandexclusive-ortheIVdirectlywithP1.FigureS8.26SolutiontoExercise26IVk1kN−1KEKEKEnbitsk1nbitsk2nbitskNnbitsnbitsnbitsnbitsnbitsnbitsP1C1P2C2PNCNEncryptionIVk1kN−1KEKEKEnbitsk1nbitsk2nbitskNnbitsnbitsnbitsnbitsnbitsnbitsC1P1C2P2CNPNDecryptionkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！627.Thefollowingshowstheprocess:X=DK(CN−1)→PN=headm(X)Y=CN|tailn−m(X)→PN−1=DK(Y)28.FigureS8.28showsthediagramforencryptionanddecryption.FigureS8.28SolutiontoExercise28nmn−mmn−mnbitsbitsbitsbitsbitsbitsPN−1PNTPNTPN−1KEKEKDKDkhdaw.comCNTCN−1CN−1CNTmn−mnnmn−mbitsbitsbitsbitsbitsbits课后答案网EncryptionDecryption29.Thefollowingshowstheprocess:www.hackshp.cnU=DK(CN−1)X=U⊕[CN|Padn−m(0]→PN=headm(X)Y=DK[CN|tailn−m(X)]→PN−1=CN−2⊕Y30.FigureS8.30showsthediagramforencryptionanddecryption.FigureS8.30SolutiontoExercise30nmn−mmn−mnbitsbitsbitsbitsbitsbitsPN−1PN0’smn−mPNTPN−1bitsbitsCN−2CN0’sCN−2KEKEKDKDCNTCN−1CN−1CNTmn−mnnmn−mbitsbitsbitsbitsbitsbitsEncryptionDecryptionkhdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！731.CFB,OFB,andCRTarestreamciphers,inwhichthesizeoftheblockisusuallyfixed(onecharacter).Thereisnoneedforpadding.Thismeansthereisnoneedforcipherstealingtechnique.32.Inthiscase,theerrorpropagationisthesameasthecasewheretheCTStechniqueisnotusedexceptforthelasttwoblocks.IfCN−1iscorrupted,itcorruptsbothPN−1andPN.IfCNiscorrupted,itcorruptsonlyPN−1.33.Inthiscase,theerrorpropagationisthesameasthecasewheretheCTStechniqueisnotusedexceptforthelasttwoblocks.IfCN−1iscorrupted,itcorruptsbothPN−1andPN.IfCNiscorrupted,itcorruptsonlyPN−1.34.FigureS8.34showstheBCmode.FigureS8.34SolutiontoExercise34khdaw.comP1P2P3PNnbitsnbitsnbitsnbitsC0课后答案网(IV)KEKEKEKEnbitsnbitsnbitsnbitswww.hackshp.cnC1C2C3C2EncryptionP1P2P3PNnbitsnbitsnbitsnbitsC0(IV)KDKDKDKDnbitsnbitsnbitsnbitsC1C2C3C2Decryption35.FigureS8.35showsthePCBCmode.InPCBCanerrorinaciphertextblockcor-ruptsallplaintextblockthatfollows.ThismodewasusedinKerberos(SeeChap-ter15)tocreatebothencryptionandintegrityofblocks.Ifablockwascorrupted,allpreviousblockswerediscarded.36.FigureS8.36showstheCBCCmode.InCBCCanerrorinaplaintextblockcor-ruptsallciphertextblockthatfollows.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8FigureS8.35SolutiontoExercise35P1P2PNP1P2PNnbitsnbitsnbitsnbitsnbitsnbitsP0PN−1P0PN−1C0CN−1C0CN−1KEKEKEKDKDKDnbitsnbitsnbitsnbitsnbitsnbitsC1C2CNC1C2CNEncryptionDecryptionkhdaw.comFigureS8.36SolutiontoExercise36课后答案网P1P2P3PNnbitsnbitsnbitsnbitsP0www.hackshp.cn(IV)KEKEKEKEnbitsnbitsnbitsnbitsC1C2C3C2EncryptionP1P2P3PNnbitsnbitsnbitsnbitsP0(IV)KDKDKDKDnbitsnbitsnbitsnbitsC1C2C3C2Decryption37.WehavewrittenaprogrambasedonAlgorithm8.6ofthetextbook.Theresultis416322121275520118251242175821332541801072303224157khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！938.Thissituationisimpossiblebecausea.Ifthestatemustremainthesameafterthesecondstep,itisneededthatS[i]hasthesamevalueforeachi=0to255(forexampleall0’s,all1’s,all2’s,…)becauseonlyinthesecasesthepermutationinthefollowingstepscannotchangethevalues.b.Buttheaboveconditioncanneverhappenbecause,beforethesecondstep,wehaveS[0]=0,S[1]=1,…,S[255]=255andtheswappingcannevermakethemthesame.39.ThisproblemcanbesolvedusingtheclassicalthirdbirthdayproblemthatwereviewinAppendixE.Wehaveasamplesetofkvalues,inwhicheachsamplecantakeoneoftheNvalues.Whatistheminimumsizeofksuchthatitisprobable(withprobabilityP≥1/2)suchthatatleasttwosamplesarethesame.Theanswerisk=1.18N1/2.InthiscaseN=2128possiblekeys,whichmeansk=1.18×264.40.Accordingtotheliterature,allofthethreecharacteristicpolynomialsareirreduc-khdaw.comibleandthenumberoftapsareeven,sothemaximumperiodcanbefoundusingtheformula2m−1.19a.ForLFSR1,wehave2−1.22b.ForLFSR2,wehave课后答案网2−1.23c.ForLFSR3,wehave2−1.www.hackshp.cn41.a.Majority(1,0,0)=0.Therefore,LFSR2andLFSR3whoseclockingbitsmatcheswiththevalueoftheMajorityfunctionareclocked.b.Majority(0,1,1)=1.Therefore,LFSR2andLFSR3whoseclockingbitsmatcheswiththevalueoftheMajorityfunctionareclocked.c.Majority(0,0,0)=0.ThereforeallthreeLFSR’sareclocked.d.Majority(1,1,1)=1.ThereforeallthreeLFSR’sareclocked.42.IfthethreebitsintheMajorityfunctionsarecalleda,b,andcrespectively,thenMajority(a,b,c)=(aANDb)⊕(bANDc)⊕(cANDa)43.ECB_Decryption(K,C[1…N]){for(i=1toN){P[i]←DK(C[i])}return(P[1…N])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1044.CBC_Decryption(IV,K,C[1…N]){C[0]←IVfor(i=1toN){temp←DK(C[i])temp←temp⊕C[i−1]}return(P[1…N])}45.WeuseavariablePre_Ctoholdthepreviouscipherblock.Inthisway,wedonotkhdaw.comhavetokeepanarrayofciphertextblocks.CFB_Decryption(IV,K,r){课后答案网i←1while(moreblockstodecrypt){input(C)www.hackshp.cnif(i=1)S←IVelse{Temp←shiftLeft(r,S)S←concatenate(Temp,Pre_C)}T←EK(S)k←selectLeft(r,T)P←C⊕koutput(P)Pre_C←Ci←i+1}}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1146.WeuseavariablePre_ktoholdthepreviouskey.Inthisway,wedonothavetokeepanarrayofk’s.OFB_Decryption(IV,K,r){i←1while(moreblockstodecrypt){input(C)if(i=1)S←IVelse{Temp←shiftLeft(r,S)khdaw.comS←concatenate(Temp,Pre_k)}T←EK(S)k←selectLeft(r,T)课后答案网P←C⊕koutput(P)Pre_k←kwww.hackshp.cni←i+1}}47.WehavewrittenthedecryptionalgorithmassumingallNblocksarereadyfordecryptiontomatchtheencryptionalgorithminthetext.However,asdescribedinthetext,thealgorithmcanbewrittenifciphertextblocksarereadyonlyoneatatime.CTR_Decryption(IV,K,C[1…N]){Counter←IVfor(i=1toN){Counter←(Counter+i−1)mod2Nki←EK(Counter)P[i]←C[i]⊕k[i]}return(P[1…N])}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1248.shiftLeft(r,S[1…n]){for(i=ndowntor)S[i]←S[i−r]for(i=0tor)S[i]←0returnS}49.concatenate(X[1…n],Y[1…r]){khdaw.comfor(i=1tor)X[n−r+1]←Y[i]returnX}课后答案网50.www.hackshp.cnselectLeft(r,X[1…n]){for(i=1tor)Y[i]←X[i]returnY}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER9MathematicsofCryptography:Part3(SolutiontoPracticeSet)ReviewQuestions1.Apositiveintegerisaprimeifandonlyifitisexactlydivisiblebytwointegers,1khdaw.comanditself.Acompositeisapositiveintegerwithmorethantwodivisors.2.Twopositiveintegers,aandb,aresaidtoberelativelyprime,orcoprime,ifgcd(a,b)=1.3.课后答案网a.Thefunctionπ(n)findsthenumberofprimessmallerthanorequalton.b.Euler’sphi-function,φ(n),whichissometimescalledtheEuler’stotientfunc-www.hackshp.cntion,findsthenumberofintegersthatarebothsmallerthannandrelativelyprimeton.4.TheSieveofEratosthenesisamethodtofindallprimeslessthann.Wewritedownalltheintegersbetween2andn.Wecrossoutallintegersdivisibleby2(except2itself).Wecrossoutallintegersdivisibleby3(except3itself).Andsoon.Whenwehavecrossedoutallintegersdivisiblebyallprimeslessthann,theremainingintegersareprimes.5.WediscussedtwoversionsofFermat’slittletheorem.Thefirstversionsaysthatifpisaprimeandaisanintegersuchthatpdoesnotdividea,thenwehaveap−1≡1(modp).ThesecondVersionremovestheconditionona.Itsaysthatifpisaprimeandaisaninteger,thenap≡a(modp).Twoimmediateapplicationsofthistheoremistofindsolutionstoexponentiationandmultiplicativeinverseswhenthemodulusisaprime.6.Euler’sTheoremisageneralizationofFermat’slittletheorem.ThemodulusintheFermattheoremisaprime,themodulusinEuler’stheoremisaninteger.Weintro-ducetwoversionsofthistheorem.Thefirstversionsaysthatifaandnarecoprime,thenaφ(n)≡1(modn).Thesecondversionsaysifn=p×q,ahasprimitiveroots.Theprimitiverootscanbethoughtasthebaseoflogarithm.Givenx=loggyforanyelementyintheset,thereisanotherelementxthatisthelogofyinbaseg.Thistypeoflogarithmiscalleddiscretelog-arithm.Exercises13.a.Thenumberofprimesbetween100,000and200,000canbefoundasπ(200,000)−π(100,000).UsingtheupperandlowerlimitsdevisedbyGaussandLagrange,wehave16385<π(200,000)<17985→π(200,000)≈172008688<π(100,000)<9587→π(100,000)≈9138π(200,000)−π(100,000)≈17200−9138≈8062b.Thenumberofcompositesbetween100,000and200,000is100,000−8062≈91938c.Theratioofprimestocompositesintheaboverangeis8062/91938orapproxi-mately8.77percent.Thisratiofornumbersbetween1to10(withoutconsidering1and10)is4/4or100percent.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！314.a.Allofthesenumbershavethesamelargestprimefactor,because100=(2×5)2=22×52→Largestfactoris51000=(2×5)3=23×53→Largestfactoris510,000=(2×5)4=24×54→Largestfactoris5100,000=(2×5)5=25×55→Largestfactoris51,000,000=(2×5)6=26×56→Largestfactoris5b.However,whenweadd1toeachinteger,thelargestprimefactorchangesunpredictably.101=1×101→Largestfactoris1011001=7×11×13→Largestfactoris1310,001=73×137→Largestfactoris137khdaw.com100,000=11×9091→Largestfactoris90911,000,000=101×9901→Largestfactoris990115.Whenanintegerisdividedby4,theremainderiseither0,1,2,or3.Thismeansthatanintegercanbewrittenas(4课后答案网k+0),(4k+1),(4k+2),or(4k+3),inwhichkisthequotient.Anintegerintheform(4k+0)or4kisnotaprimebecauseitisdivisibleby4.Anintegerintheform(4k+2)canbeaprimeonlyifk=0(theinte-geris2anditisthefirstprime).Theothertwoforms,(4k+1)and(4k+3),canwww.hackshp.cnrepresentaprimeoracomposite.Thismeansthatanyprimecanbeeitherintheformof(4k+1)or(4k+3).However,thisdoesnotmeanthatanyintegerinoneoftheseformsisaprime.16.Weshowsomeprimesforeachform:a.p=5k+1:k=2→p=11k=6→p=31k=8→p=41k=10→p=51b.p=5k+2:k=0→p=2k=1→p=7k=3→p=17k=7→p=37c.p=5k+3:k=0→p=3k=2→p=13k=4→p=23k=8→p=43d.p=5k+4:k=3→p=19k=5→p=29k=9→p=49k=11→p=5917.a.φ(29)=29−1=28(29isaprime)b.φ(32)=φ(25)=25−24=16(2isaprime)c.φ(80)=φ(24×51)=(24−23)×(51−50)khdaw.com=8×4=32(2and5areprimes)若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！4d.φ(100)=φ(22×52)=(22−21)×(52−51)=2×20=40(2and5areprimes)e.φ(101)=101−1=100(101isaprimes)18.a.(224−1)=(212−1)×(212+1).Becausenoneofthefactorsis1,(224−1)isacomposite.b.(216−1)=(28−1)×(28+1).Becausenoneofthefactorsis1,(216−1)isacomposite.c.Ingeneral,ifapositiveintegercanbewrittenintheform(2n−1)andnisanevenintegergreaterthan2,then(2n−1)=(2n/2−1)×(2n/2+1).Ifn=2,thenwehave(2n−1)=3,aprime.19.Wehave(10=3+7),(24=11+13),(28=11+17),and(100=11+89).20.Someoftheseprimesareshownbelow.Wecanalwayschecktheprimenessusingkhdaw.comAppendixH.n=1→(n2+1)=2n=2→(n2+1)=5n=4→(n2+1)=17n=6→(n2+1)=37n=10→(n2+1)=101n=14→(n2+1)=197n=16课后答案网→(n2+1)=257n=20→(n2+1)=401n=24→(n2+1)=577n=26→(n2+1)=677www.hackshp.cn21.a.(515mod13)=[(52mod13)×(513mod13)]mod13=[(−1mod13)×(5mod13)]mod13=−5mod13=8mod13b.(1518mod17)=[(15mod17)×(1517mod17)]mod17=[(−2mod17)×(−2mod17)]mod17=4mod17c.(45617mod17)=(456mod17)=14mod17d.(145102mod101)=[(145101mod101)×(145mod101)]mod101=[145×145]mod101=[44×44]mod101=17mod10122.Weknowthatifpisaprime,x−1modp=xp−2modp.a.5−1mod13=513−2mod13=511mod13=8mod13b.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！515−1mod17=1517−2mod17=1515mod17=8mod17c.27−1mod41=2741−2mod41=2739mod41=38mod41d.70−1mod101=70101−2mod101=7099mod101=13mod10123.Weknowthatifnisaninteger,x−1modn=xφ(n)−1modn.a.12−1mod77=12φ(77)−1mod77=1259mod77=45mod77b.khdaw.com16−1mod323=16φ(323)−1mod323=16287mod323=101mod323c.课后答案网20−1mod403=20φ(403)−1mod403=20359mod403=262mod403d.www.hackshp.cn44−1mod667=44φ(667)−1mod667=44615mod667=379mod66724.ForeachMersennenumber,Mp=2p−1,wetrysomeintegersintheform2kp+1tofindapossibledivisor.a.M23−1=8,388,607isnotaprime.Whenk=2,2kp+1=47dividesthe23=2number:8,388,607=47×178,481.M23isacompositeb.M29−1=536,870,911isnotaprime.Whenk=4,2kp+1=233divides29=2thenumber:536,870,911=233×1,103×2,089.M29isacompositec.M31=231−1=2,147,483,647isaprime.Ifthisnumberisacomposite,itmusthaveadivisorlessthan46,341(thesquarerootofM31),whichmeansthatkin2kp+1mustbelessthan748.Wetriedallk=0to747withnosuccess.M31isaprime.25.Itcanbecheckedthatif2n−1isaprime,thennisaprime.However,therearesomevaluesofnforwhich2n−1isacomposite,butnisaprime(n=11,forexample).Inotherwords,ifnisaprime,2n−1mayormaynotbeaprime;if2n−1isaprime,thennisaprime.ThisistosaythatnotallMersennenumbersareprimes.SinceMersenne’sideacannotbeusedforprimalitytest,thefactstatedinthisproblemcannotbeusedforprimalitytest.22−1=3isaprime→n=2isaprime23−1=7isaprime→n=3isaprime24−1=15=3×5isacomposite→n=4isacomposite25−1=31isaprimekhdaw.com→n=5isaprime若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！626−1=63=3×5isacomposite→n=6isacomposite27−1=127isaprime→n=7isaprime28−1=255=5×51isacomposite→n=8isacomposite29−1=511=7×73isacomposite→n=9isacomposite210−1=1023=3×341isacomposite→n=10isacomposite211−1=2047=23×89isacomposite→n=11isaprime26.ThefollowingshowstheresultsoftheFermattestonthisgroupofintegers.Notethatiftheintegerdoesnotpassthetest,itisdefinitelyacomposite;ifitpassesthetest,itmaybeaprime.Thelasttwointegerspassthetest,butweknowthattheyarecomposite.n=100→2n−1modn=88(notpassed)→compositen=110→2n−1modn=72(notpassed)→compositen=130→2n−1modn=88(notpassed)→compositekhdaw.comn=150→2n−1modn=88(notpassed)→compositen=200→2n−1modn=88(notpassed)→compositen=250→2n−1modn=62(notpassed)→compositen=271→2n−1modn=1(passed)→primen=课后答案网341→2n−1modn=1(passed)→compositen=561→2n−1modn=1(passed)→compositewww.hackshp.cn27.TheflowintheMiller-RabinalgorithmmaybebetterunderstoodusingthechartinFigureS9.27.Wefollowthechartineachcase.FigureS9.27SolutiontoExercise27ChooseabaseFindmandkTammodn[T=+−1]PseudoprimeLoopTT2modn[T=+−1][Allk’stested?]T=+1:CompositeCompositeT=−1:Pseudoprimea.n=100→100−1=99×20→m=99andkhdaw.comk=0.若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！7Pre-loop→T=299mod100=88Loopisby-passedbecausek=0→Composite(100isaneveninteger)b.n=109→109−1=27×22→m=27andk=2.Pre-loop→T=227mod109=33k=1→T=T2mod109=108mod109=(−1)mod109LoopisbrokenbecauseT=−1→Pseudoprime(109isactuallyaprime)c.n=201→201−1=25×23→m=27andk=3.Pre-loop→T=225mod201=95k=1→T=T2mod201=181mod2012k=2→T=Tmod201=199mod201Loopisterminated→Composite(201=3×67)khdaw.comd.n=271→271−1=135×21→m=135andk=1.Pre-loop→T=2135mod271=1mod271课后答案网T=+1intheinitializationstep→Pseudoprime(271isactuallyaprime)e.n=341→341−1=85×22→m=85andk=2.Pre-loop→T=285mod341=32www.hackshp.cnk=1→T=T2mod341=1mod341LoopisbrokenbecauseT=+1→Composite(341=11×31)f.n=349→349−1=87×22→m=87andk=2.Pre-loop→T=287mod349=213k=1→T=T2mod349=348mod349=(−1)mod349LoopisbrokenbecauseT=−1→Pseudoprime(349isactuallyaprime)g.n=2047→2047−1=1023×21→m=1023andk=1.Pre-loop→T=21023mod2047=1mod2047T=+1intheinitializationstep→Pseudoprime(but2047=23×89)Inthiscase,thetestdeclarestheinteger2047asapseudoprime,whichisactu-allyacomposite.28.WeusethechartinFigureS9.28tofollowtherecommendedprimalitytestthatincludeseveralinstancesofMiller-Rabintest,eachwithadifferentbase.Foreachnumberweusethebaseset(2,3,4).khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8FigureS9.28SolutiontoExercise28[Divisiblby3,5,...?]CompositeFindmandkandchoosebasesLoopMiller-Rabintestfornextbase[Testfailed?][Allbasestested?]khdaw.comCompositePseudoprimea.n=271isnotdivisibleby3,5,7,11,13,17,19,23.WestartMiller-Rabintests.Theteststellsusthat271isapseudoprime;itisinfactaprime.课后答案网Initialization:271−1=135×21→m=135andk=1a=2→T=a135mod271=1a=3→T=a135mod271=−1a=4→T=a135mod271=1www.hackshp.cnThenumberpassesthreeMiller-Rabintests→Pseudoprimeb.n=3149isnotdivisibleby3,5,7,11,13,17,19,23.WestartMiller-Rabintests.Thisintegerfailsthetest;itisdefinitelyacomposite(3149=47×67).Initialization:3149−1=787×22→m=787andk=2a=2→T=a787mod3149=2523T=T2mod3149=140ThenumberfailstheMiller-Rabintestfora=2→Compositec.n=9673isnotdivisibleby3,5,7,11,13,butisdivisibleby17.ItiscompositeandnoMiller-Rabintestsareneeded(9673=17×569).29.a.Wetesttheclaimusing(3−2)pmodp=(3p−2)modpwithx=3,a=2,andsomesmallprimes.p=2(3−2)2mod2=1(32−2)mod2=1p=3(3−2)3mod3=1(33−2)mod2=1p=7(3−2)5mod7=1(37−2)mod7=1b.Wealsotesttheclaimusingx=7,a=3,andsomeprimes.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！9p=2(7−3)2mod2=0(72−3)mod2=0p=5(7−3)5mod5=4(75−3)mod5=4p=17(7−3)17mod17=4(717−3)mod17=430.Generally,pn>n×lnn.Thefollowingshowssomeprimesandtheirapproxima-tions.Asnbecomeslarger,theratiooferrorbecomessmaller.n=1pn=2n×lnn=0n=25pn=97n×lnn=80.47n=168pn=997n×lnn=860.80n=668pn=4999n×lnn=4344.86n=10,000pn=104,729n×lnn=92103,4031.a.khdaw.coma1=2m1=7a2=3m2=9→M=63M−1=9−1mod7=4;M−1=7−1mod9=41=9M12=7M2课后答案网x=(2×9×4+3×7×4)mod63=30b.a1=4m1=5a2=10m2=11→M=55M−1=11−1mod5=1;M−1=5−1mod11=9www.hackshp.cn1=11M12=5M2x=(4×11×1+10×5×9)mod55=54c.a1=7m1=13a2=11m2=12→M=156M1=12M2=13M1=12M1−1=12−1mod13=12;M2=13M2−1=13−1mod12=1x=(7×12×12+11×13×1)mod156=5932.ThefollowingshowQRsandQNRsineachcase.a.QRsandQNRsinZ13∗QRs:1,3,4,9,10,12QNRs:2,5,6,7,8,11b.QRsandQNRsinZ17∗QRs:1,2,4,8,9,13,15,16QNRs:3,5,6,7,10,11,12,14c.QRsandQNRsinZ23∗QRs:1,2,3,4,6,8,9,12,13,16,18QNRs:5,7,10,11,14,15,17,19,20,21,2233.a.Theinteger4isaQRinZ7∗.Since7=4×k+3withk=1,wecanusethefollowingexpressionstofindthesolutions.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！10x:4(7+1)/4mod7=2x:−4(7+1)/4mod7=−2b.Theinteger5isaQRinZ11∗.Since11=4×k+3withk=2,wecanusethefollowingexpressionstofindthetwosolutions:x:5(11+1)/4mod11=4x:−5(11+1)/4mod11=−4c.Theinteger7isnotaQRinZ13∗(seeExercise32).Thisequationhasnosolu-tions.d.Theinteger12isnotaQRinZ17∗(seeExercise32).Thisequationhasnosolutions.34.a.n=14=2×7→p1=2andp2=7.Thefournewequationsarekhdaw.comx2≡4(mod2)→x≡±0(mod2)x2≡4(mod7)→x≡±2(mod7)Wehavefoursetsofequations:Thesolutiongivesusx=2andx=12.Set1:x≡+0(mod2)x≡+2(mod7)课后答案网Set2:x≡+0(mod2)x≡−2(mod7)Set3:x≡−0(mod2)x≡+2(mod7)Set4:x≡−0(mod2)x≡−2(mod7)www.hackshp.cnb.n=10=2×5→p1=2andp2=5.Thefournewequationsarex2≡1(mod2)→x≡±1(mod2)x2≡0(mod5)→x≡±0(mod5)Wehavefoursetsofequations:Thesolutiongivesusx=5.Set1:x≡+1(mod2)x≡+0(mod5)Set2:x≡+1(mod2)x≡−0(mod5)Set3:x≡−1(mod2)x≡+0(mod5)Set4:x≡−1(mod2)x≡−0(mod5)c.n=33=3×11→p1=3andp2=11.x2≡1(mod3)→x≡±1(mod3)x2≡7(mod11)→nosolutionsSincethesecondequationhasnosolution,theequationx2=7mod33hasnosolution.d.n=34=2×17→p1=2andp2=17.Thefournewequationsarex2≡12(mod2)→x≡±0(mod2)x2≡12(mod17)→NosolutionsSincethesecondequationhasnosolution,theequationx2=12mod34hasnosolution.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1135.WeusetablesbasedonFigure9.7.Wefirstcalculateallpowersofa’s.a.y=2124mod8→a=21,x=24=110002.Shadedareasrepresentnomoutipli-cations.Allcalculationsareinmodulo8.Theanswerisy=1.a’sxiy=1mod8a1=5mod80y=1mod8a2=1mod80y=1mod8a4=1mod80y=1mod8a8=1mod81y=1×1mod8=1mod8a16=1mod81y=1×1mod8=1mod8xiThetableshowsthatwecanstopwheneverabecomes1.b.y=32023mod461→a=320,x=23=101112.Shadedareasrepresentnomul-khdaw.comtiplications.Allcalculationsareinmodulo461.Theanswerisy=373.a’sxiy=1mod461a1=320mod4611y=1×320mod461=320mod461a课后答案网2=58mod4611y=320×58mod461=120mod461a4=137mod4611y=120×137mod461=305mod461www.hackshp.cna8=329mod4610y=305mod461a16=367mod4611y=305×367mod461=373mod461c.y=177641mod2134→a=1776,x=41=1010012.Shadedareasrepresentnomultiplications.Allcalculationsareinmodulo2134.Theanswerisy=698.a’sxiy=1mod2134a1=1776mod21341y=1×1776mod2134=1776mod2134a2=124mod21340y=1776mod2134a4=438mod21340y=1776mod2134a8=1918mod21341y=1776×1918mod2134=504mod2134a16=1842mod21340y=504mod2134a32=2038mod21341y=504×2038mod2134=698mod2134khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！12d.y=200135mod2000→a=2001,x=35=1000112.Shadedareasrepresentnomultiplications.Allcalculationsareinmodulo2001.Theanswerisy=1.a’sxiy=1mod2000a1=1mod20001y=1×1mod2000=1mod2000a2=1mod20001y=1×1mod2000=1mod2000a4=1mod20000y=1mod2000a8=1mod20000y=1mod2000a16=1mod20000y=1mod2000a32=1mod20001y=1×1mod2000=1mod2000xiThetableshowsthatwecanstopwheneverabecomes1.khdaw.com36.a.Theorderofthegroupisφ(19)=18.b.Thefollowingshowstheorderofeachelement:课后答案网ord(1)=1ord(2)=18ord(3)=18ord(4)=9ord(5)=9ord(6)=9ord(7)=3ord(8)=6ord(9)=9ord(10)=18ord(11)=3ord(12)=6www.hackshp.cnord(13)=18ord(14)=18ord(15)=18ord(16)=9ord(17)=9ord(18)=2c.Thenumberofprimitiverootsisφ(φ(19))=φ(18)=6.d.Theprimitiverootsarethoseelementwithorder18.Theyare2,3,10,13,14,and15.e.Weknowthatthegroupiscyclicbecause19isaprime.Anyoftheprimitiverootcangenerateallelementsofthegroup.Forexample,ifwechooseg=2asthegenerator,wecangenerateallelementsasshownbelow(allcalculationsareinmodulo19).g1→2g2→4g3→8g4→16g5→13g6→7g7→14g8→9g9→18g10→17g11→15g12→11g13→3g14→6g15→12g16→5g17→10g18→1f.Wecancreateatableofdiscretelogarithmsforbases2,3,10,13,14,and15.x123456789101112131415161718L2(x)181132161463817121557114109L3(x)187114486321112151713510169L10(x)181751624121510163131171489L13(x)181117414101215167631513829L14(x)181378102631451215111171649L15(x)18511108161215khdaw.com4136371712149若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1337.a.Tosolvetheequationx5≡11(mod17),weneedtofindaprimitiverootinthegroupG=andthediscretelogarithmtableforthatroot.Thefirstprimitiverootinthisgroupis3(primitiverootsare3,5,6,7,10,11,12,and14).Thediscretelogarithmtableforthisroot(base)canbefoundasx12345678910111213141516L3(x)16141125151110237134968WethenapplythefunctionL3tobothsidesofthecongruence.Notethattheworkingmodulusisφ(17)=16andL3(11)=7(fromthetable).L3(x5)≡L3(11)(mod16)→5×L3(x)≡7(mod16)→5×L3(x)≡7(mod16)Nowweneedtosolvethecongruenceequation5×L3(x)≡7(mod16).Recallkhdaw.comfromChapter2thatthisequationhasonlyonesolutionbecausegcd(5,16)=1.L−1×7(mod16)≡11(mod16)3(x)≡5Nowwecanusethetabletofind课后答案网xifL3(x)=11;theanswerisx=7,whichcanbecheckedas75≡11(mod17).Wecanalsowriteaprogramtotestallofvaluesofxfrom1to17toseeifanyofthisvaluessatisfiestheequation.Wedidso;theonlyvalueisx=7.www.hackshp.cnb.Tosolvetheequation2x11≡22(mod19)or2x11≡3(mod19),weneedtofindaprimitiverootinthegroupG=andthediscretelogarithmtableforthatroot.Thefirstprimitiverootinthisgroupis2(seeExercise36).Thedis-cretelogarithmtableforthisroot(base)canbefoundasx123456789101112131415161718L2x181132161463817121557114109WethenapplythefunctionL2tobothsidesofthecongruence.Notethattheworkingmodulusisφ(19)=18,L2(2)=1andL2(3)=13.L2(2x11)≡L2(3)(mod18)→L2(2)+11×L2(x)≡L2(3)(mod18)→1+11×L2(x)≡13(mod18)→11×L2(x)≡12(mod18)Nowweneedtosolvethecongruenceequation11×y≡12(mod18).RecallfromChapter2thatthisequationhasonlyonesolutionbecausegcd(11,18)=1.11×y≡12(mod18)→y≡11−1×12(mod18)≡5×12(mod18)≡6(mod18)NowwecanusethetabletofindxifL2(x)=6;theanswerisx=7,whichcanbecheckedas2×711≡3(mod19).Wecanalsowriteaprogramtotestallofvaluesofxfrom1to19toseeifanyofthisvaluessatisfiestheequation.Wedidso;theonlyvalueisx=7.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！14c.Theequation5x12+6x≡8(mod23)cannotbesolvedusingthediscreteloga-rithmdiscussedinthischapterbecausethereisnopropertyofdiscreteloga-12+6xrithmtoallowsusextractL(x)fromL(5x).However,wecanwriteaprogramtotestallofvaluesofxfrom1to22toseeifanyofthisvaluessatis-fiestheequation.Wedidso,butfindnovalueofxsatisfyingthecongruence;thecongruencehasnosolution.38.Onemillionoperationspersecondmeans3,600,000,000operationsperhour.a.Ifweassumethatthecomplexityofdivisibilitytestis2nb(whichisveryunreal-istic),then2nb=3,600,000,000→2nb≈232n≈32bThismeansn<232b.ThecomplexityofASKis(log12.2nb)(log12=3,600,000,000→log6.25→nkhdaw.com2nb)2nb=6.25→nb≈2b≈76Thismeansn<276c.ThecomplexityofFermatis课后答案网nbifweuseFastExponentiationalgorithm.nb=3,600,000,000www.hackshp.cnThismeansn<23,600,000,000However,asweknowthealgorithmisprobabilistic.Wearenotsureiftheresultiscorrect.d.Thecomplexityofsquareroottestisnor2nb2nb=3,600,000,000→2nb≈232n≈32bThismeansn<232Howeverthetestisnotdeterministic.Wearenotsureiftheresultiscorrect.e.ThemainoperationinMiller-RabintestisFermattest,sothecomplexityissomehowmorethanFermat.However,thetestisnotdeterministic.39.Onemillionoperationspersecondmeans3,600,000,000operationsperhour.a.Thecomplexityoftrialdivisionmethodisexponential(2nb).2nb=3,600,000,000→2nb≈232n≈32bThismeansn<232b.ThecomplexityofFermatmethodissubexponentialor2p(log2nb).Forsimplicity,weassumethecomplexitytobe2(log2nb)2.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！152(log2nb)2=3,600,000,000→2(log2nb)2≈232→(log2≈322nb)→(logn5.7→522nb)≈5.7→b≈2Thismeansn<252c.ThecomplexityofPolardrhomethodisexponentialor(2nb/4).2nb/4=3,600,000,000→2nb/4≈232n≈128bThismeansn<2128d.ThecomplexityhereiseCwhereC=(lnnlnlnn)1/2.Sinceitisverydifficulttocalculateninthiscase,weassumethatC=lnn)1/2orC=(lnn).elnn=3,600,000,000→lnn=3,600,000,000khdaw.comThismeansn0){if(xmod2=1)y←y×amodn//notneededinthelastrounda←a2modnx←x/2//integerdivision}khdaw.comreturny}43.FermatPrimalityTest课后答案网(a,n)//Wecanusedifferentbases{y←Square_and_Multiply(a,n−1,n)//SeeAlgorithm9.7inthetextwww.hackshp.cnif(y=1)return(nisprobablyaprime)return(nisacomposite)}44.SquareRootPrimalityTest(n){for(a=2ton/2+1)//nisnormallyodd{x←a2modny←(−a)2modnif(x=1modn)or(y=1modn)return(nisacomposite)}return(nisprobablyaprime)}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1745.ChineseRemainderTheorem(k,a[1…k],m[1…k]){M←1for(i=1tok)M←M×m[i]for(i=1tok){M[i]←M/m[i]−1InvM[i]←M[i]modm[i]}x←0for(i=1tok)x←[x+(a[i]×M[i]×InvM[i])]modMreturnxkhdaw.com}46.FindQuadraticResidues(p)//pisaprime{课后答案网for(a=2ton/2+1)//nisnormallyodd{x←Square_and_Multiply(a,(p−1)/2,p)if(x=1modp)www.hackshp.cninsertainQRListelseinsertainQNRList}returnQRListandQNRList}47.FindFirstPrimitiveRoot(p)//pisaprime{for(a=2top−1){i←1while(aimodp≠1){i←i+1}if(i=p−1)//ordera=φ(p)returna}}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1848.FindAllPrimitiveRoots(p)//pisaprime{for(a=2top−1){i←1while(aimodp≠1){i←i+1}if(i=p−1)//ordera=φ(p)InsertatoPrimitiveRootList}returnPrimitiveRootListkhdaw.com}49.FindAllDiscreteLogs课后答案网(p)//pisaprime{PrimitiveRootList←FindAllPrimitiveRoots(p)//SeeExercise48CreateaDiscreteLogTablesortedonywww.hackshp.cnfor(eachginPrimitiveRootList){for(x=1top−1){y←gxmodpinsertxtoLgrowofDiscreteLogTableunderycolumn}}returnDiscreteLogTable}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！CHAPTER10Symmetric-KeyCryptography(SolutiontoPracticeSet)ReviewQuestions1.Symmetric-keycryptographyisbasedonsharingsecrecy;asymmetric-keycryp-khdaw.comtographyisbasedonpersonalsecrecy.2.Inasymmetric-keycryptography,eachentityhasapairofpublic/privatekey.Thepublickeyisuniversal;theprivatekeyispersonal.Insymmetric-keycryptographyasharedsecretkeyisusedforsecretcommunicationbetweentwoentities.课后答案网3.Incryptography,atrapdoorisasecretwithwhichBobcanuseafeasiblealgorithmtodecrypttheciphertext.IfEvedoesnotknowthetrapdoor,sheneedstouseanalgorithmwhichisnormallyinfeasible.www.hackshp.cn4.Intheknapsackcryptosystem,ifwearetoldwhichelements,fromapredefinedsetofnumbers,areinaknapsack,wecaneasilycalculatethesumofthenumbers;ifwearetoldthesum,itisdifficulttosaywhichelementsareintheknapsack.a.Theone-wayfunctionisthemultiplicationoftherowmatrixxbythecolumnmatrixatogets=x×a.Givenxanda,itiseasytocalculates;givensanda,itisdifficulttocalculatex.b.ThetrapdoorinthissystemisthevalueofrandnthatallowBobtocalculatethevalueofs′=r−1×s.Inthematrixmultiplications′=x×b,thematrixbcanbecalculatedifitisasuperincreasingcolumnmatrix(tuple).c.Thepublickeyisthek-tuplea.Theprivatekeyisn,r,andthek-tupleb.d.Thesecurityofthesystemdependsonthesizeofthetwomatricesxanda.Iftheyareverylarge,itisdifficulttofindxgivensanda.However,today,knap-sackcryptosystemisnotconsideredsecure;itisbroken.5.RSAusestwoexponents,eandd,whereeispublicanddisprivate.Alicecalcu-latesC=PemodntocreateciphertextCfromplaintextP;BobusesP=CdmodntoretrievetheplaintextsentbyAlice.a.Theone-wayfunctionistheC=Pemodn.GivenPande,itiseasytocalculateC;givenCande,itdifficulttocalculatePifnisverylarge.khdaw.com1若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！2b.Thetrapdoorinthissystemisthevalueofd,whichenablesBobtouseP=Cdmodn.c.Thepublickeyisthetuple(e,n).Theprivatekeyisd.d.ThesecurityofRSAmainlydependonthefactorizationofn.Ifnisverylarge,andthevalueofeanddarechosenproperly,thesystemissecure.6.TheRabincryptosystemisavariationoftheRSAcryptosystem.RSAisbasedontheexponentiationcongruence;Rabinisbasedonquadraticcongruence.TheRabincryptosystemcanbethoughtofasanRSAcryptosysteminwhiche=2andd=1/2.a.TheonewayfunctionisC=P2modn.GivenP,itiseasytocalculateC;givenC,itdifficulttocalculatePifnisverylarge.b.Thetrapdooristhefactorizationofn=p×q.Bobknowsthevalueofpandq,butEvedoesnot.BobusestheChineseremaindertheoremandthevaluesofpkhdaw.comandq,tofindP.c.Thepublickeyisn.Theprivatekeyisthetuple(pandq).d.SecurityofRabincryptosystemisbasicallydependsonhowitdifficulttofactorn.课后答案网7.ElGamalisbasedondiscretelogarithmproblem.Theplaintextismaskedwithe1rdtocreatetheciphertext.PartofthemaskiscreatedbyBobandbecomepublic;thewww.hackshp.cnotherpartiscreatedbyAlice.a.Theone-wayfunctionisC=mask(P).GivenPandthemask,itiseasytocal-culatetheC;givenCisdifficulttounmaskP.b.ThetrapdooristhevalueofdthatenablesBobtounmaskC.c.Thepublickeyis(e1,e2andn).Theprivatekeyisd.d.ThesecurityofElGamaldependsontwopoints;pshouldbeverylargeandAliceneedstoselectanewrforeachencryption.8.ECCisbasedonellipticcurves.WecandefinedagroupGF(p)orGF(2n)inwhichtheelementsarepointsonanellipticcurve.ECCsimulatestheideaofElGamalusingtheabove-mentionedgroups.a.Theone-wayfunctioninECCistheideaofmultiplyinganintegerbyapointtogetanewpointonthecurve.Iftheoriginalpointisgiven,thenewpointcanbecalculatedwithpolynomialcomplexity.Ifthenewpointisgiven,itisveryhardtocalculatetheoriginalpointwithoutknowingthetrapdoor.b.ThetrapdooristhevalueofdthatenablesBobtocalculatetheoriginalpointonthecurveusinganalgorithmwithpolynomialcomplexity.c.Thepublickeyis(e1,e2,andE)inwhiche1ande2aretwopointsonthecurveE.Theprivatekeyisd.d.ThesecurityofECCisbasedonthedifficultyofsolvingellipticcurveloga-rithms.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！39.Anellipticcurveisanequationintwovariablessimilartotheequationsusedtocalculatethelengthofacurveinthecircumferenceofanellipse.EllipticcurveswithpointsbelongingtothegroupsGF(p)orGF(2n)areusedincryptography.10.Operationsarebasicallyaddingtwopointsonthecurvetogetanewpointonthecurve.Exercises11.Weusethe7-bitrepresentationofcharacter"a"astheplaintext.KeyGeneration:t=[287,451,943,762,564,86,623]→a=[623,86,564,287,451,943,762]Encryption:khdaw.comPlaintext:x=[1,1,0,0,0,0,1]→Ciphertext:s=1471Decryption:s’=(41−1,1471)mod1001=293×1471mod1001=573课后答案网x’=[0,0,0,1,0,1,1]→Plaintextx=[1,1,0,0,0,0,1]12.a.φ(n)=φ(13×17d=e−1modφ(n)=5−1mod192=77)=192→www.hackshp.cnb.φ(n)=φ(31×127)=3780→d=e−1modφ(n)=17−1mod3780=3113c.n=p×q=437→φ(n)=396.Sincegcd(n,e)≠1,wecannotcalculatedforthisproblem.Thisshowsthatweneedtochoosethevalueofecarefully.Inthiscaseφ(n)=396=22×32×1,whichmeansecannotbe2,3,or11.Wecanhavee=5,whichmeansd=5−1mod396=317.13.n=187=17×11→φ(n)=17×11=160→d=e−1modφ(n)=113.ThisprovesthatthevalueofninRSAmustbeverylarge.Wecouldfinddbecausewecouldfactorn.Themodulusmustbelargeenoughtomakethefactorizationinfea-sible.14.Wecancreatetwoequationsoftwounknowns(pandq):p×q=n(p−1)×(q−1)=φ(n)IfweletA=(n−φ(n)+1),thenp2−A×p+n=0.Thismeansp=[A+(A2−4×n)1/2]/2andq=[A−(A2−4×n)1/2]/2Forexample,assumen=209andφ(n)=180.ThenA=209−180+1=30.Wehavep=19andq=11.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！415.Inarealsituation,thevalueofnissolargethatitisimpossibleforAlicetocheckifnandearechosenproperly.Inthistoyproblem,itiseasytoseethatnisnotproperlyselectedbecausen=100cannotbefactoredintotwoprimes(n=p×q).Althoughwecanstillencryptthemessageusinge=13andn=100,theencryptedmessagecannotbedecrypted.TheproblemprovethatBobneedstofirstselectpandqandbesurethattheyareprimesbeforecalculatingn=p×q.Afterthecor-rectselectionofn,theneneedstobeselectedinsuchawaythatφ(n)andebecoprimes.Thisproblemhasnosolution.16.AlthoughinreallifeAlicecannotchecktoseeifnandeareproperlyselectedbyBob,inthistoyproblemshecan.Thevalueofnisproperbecausen=107×113(twoprimes).Thevalueofeisalsoproperbecausee,whichis13andφ(n),whichis11872,arecoprime.a.Theplaintextis:19070818260818261914200607b.Forencryption,wecreate4-digitblockssothatthevalueofeachblockbelesskhdaw.comthann.P13mod12091=106141=1907→C1=1907课后答案网P2=0818→C2=081813mod12091=7787P13mod12091=16183=2608→C3=2608P13mod12091=107174=1826→C4=1826www.hackshp.cnP5=1914→C5=191413mod12091=4084P13mod12091=65586=2006→C6=2006P13mod12091=66517=07→C7=07c.Inthistoyproblem,wecaneasilyfindd=e−1modφ(n)=3653.EachblockcanbedecryptedasC3653mod12091=19071=10614→P1=10614C2=7787→P2=77873653mod12091=0818C3653mod12091=26083=1618→P3=1618C3653mod12091=18264=10717→P4=10717C5=4084→P5=40843653mod12091=1914C3653mod12091=20066=6558→P6=6558C3653mod12091=077=6651→P7=6651Theplaintextis:19070818260818261914200607or“THISISTOUGH”.17.a.Ife=1,thereisnoencryption:C=P.IfEveinterceptstheciphertext,shehastheplaintext.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！5b.Ife=2,thecipherisactuallyRabin,notRSA.18.Evecanuseatypeofplaintextattackcalledshort-messageattackifsheknowsthateachcharacterisencryptedseparately.Evecanwriteasimpleprogramusingeandntofindallplaintext/ciphertextcharacterasshowninthefollowingtable.P=0P=1P=2P=3P=4P=5P=6C=0C=1C=13958C=2459C=6625C=7340C=8320P=7P=8P=9P=10P=11P=12P=13C=8911C=10247C=15310C=16008C=18021C=12029C=2232P=14P=15P=16P=17P=18P=19P=20C=4670C=13504C=11913C=10706C=2968C=8539C=5671P=21P=22P=23P=24P=25C=11831C=15284C=4718C=17863C=1160EveknowsthattheplaintextismadeofP=4,P=0,P=18,andP=24.Theplain-khdaw.comtextis"easy".Evecanbreakthecodebecausethesetofplaintextvaluesissmall.Evecantryallofthemusingaprogram.Thesetshouldbeverylarge.EvenifAlicehasshortpiecesofmessagestosend,sheneedtopadthemtomakethesetlarge(seeOAEPencryption/decryption).19.EvehasinterceptedC=57课后答案网a.EvechoosesX=17(whichisinZ143*).www.hackshp.cnb.EvecalculatesY=C×177mod143=57×177mod143=137c.Evesends137toBobandasktodecryptit.TheresponseisZ=136(Weknowhowtocalculatethisbecausewecaneasilyfindd=103,butweassumethatEvecannot;sheneedstosendtheciphertexttoBobandreceivetheplaintext.d.P=(Z×X−1)mod143=(136×17−1)mod143=8mod143.Whichistheplaintext.ThisshowsthatRSAisveryvulnerabletochosen-ciphertextattack.20.InterceptedciphertextisC=22.Cemodn=223mod35=8.1=CCemodn=83mod35=22.2=C1SinceC2=C=22,P=C1=8.21.Onesolutionistousedifferentpaddingwitheachplaintext.Aswediscussedinthetext,usingOAEPencryption,eachtimewithdifferentrandomr,removestherela-tionshipsbetweendifferentplaintextsthataresentbyAlicetoBob.22.Wefirstfindn=p×q=47×11=517.a.C=P2mod517=172mod517=289.b.a1=+C(p+1)/4modp=+28912mod47=+17anda2=−17.b1=+C(q+1)/4modq=+2893mod11=+5andb2=−5.Wehavethefollowingfoursets,eachoftwoequationstosolve:khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！6P1≡+17(mod47)P1≡+5(mod11)→P1=346P2≡+17(mod47)P2≡−5(mod11)→P2=17P3≡−17(mod47)P3≡+5(mod11)→P3=500P4≡−17(mod47)P4≡−5(mod11)→P4=171TheonlyacceptableanswerisP2=17.23.a.Wechoosee101=3(aprimitiverootofp=31)andd=10.Thenwehavee2=3mod31=25.b.ThecommonfactorforcalculationofC7mod31=257mod31=25.2’sise2P="H"=07C1=37mod31=17C2=07×25mod31=20→C=(17,20)khdaw.comP="E"=04C1=37mod31=17C2=04×25mod31=07→C=(17,07)P="L"=11C=37mod31=17C=11×25mod31=27→C=(17,27)12P="L"=11C=37mod31=17C=11×25mod31=27→C=(17,27)12P="O"=14C=37mod31=17C=14×25mod31=09→C=(17,09)课后答案网12c.www.hackshp.cn10)−1C=(17,20)→P=20×(17mod31=07→"H"10)−1C=(17,07)→P=07×(17mod31=04→"E"10)−1C=(17,27)→P=27×(17mod31=11→"L"10)−1C=(17,27)→P=27×(17mod31=11→"L"10)−1C=(17,09)→P=09×(17mod31=14→"O"24.Ingeneral,thenumericvalueofC1andC2aredifferentinaciphertext.Ifthesetwovaluesareswappedduringtransmission,BobcannotcorrectlydecrypttheciphertexttogettheplaintextbecauseCd)−1≠Cd)−12×(C11×(C225.Althoughthevalueofp(themodulus)anddarenotgiven,wecanassumeamod-uluswhichisgreaterthat17and37anditsprimitiverootis2.Wehavechosenp=53andd=3.Inthiscase,wehavep=53,d=3,e3mod53=8.1=2,ande2=e1a.Aliceusesr=9toencrypttwomessages,17and37.Thevaluesofciphertextsare:C1=35,C2=19,C1′=35andC2′=32.b.EveinterceptsC1=35,C2=19,C1′=35andC2′=32andsheknowP=17.Evecanusetheknown-plaintextattacktofindP′.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！7P’=Cr)−1modp=C−1)−1modp=C−1×Pmodp2′×(e22′×(C2×P2′×C2P’=32×19−1×17mod53=32×14×17mod53=3726.a.E(1,2)meansthata=1andb=2intheequationy2=x3+ax+b.Theequationofthecurveistheny2=x3+x+2.b.FigureS10.26showsthepointsonthecurve.FigureS10.26PartofsolutiontoExercise26yP−P(1,2)(1,9)(2,1)(2,10)109(4,2)(4,9)khdaw.com8(5,0)(5,0)76(6,2)(6,9)5(7,0)(7,0)4课后答案网(8,4)(8,7)32(9,5)(9,6)1(10,0)(10,0)0x012345678910Pointswww.hackshp.cnGraphc.Bobchoosese1=(2,1)andd=3,thene2=3×(2,1)=(4,9).PublickeyisE11(1,2),e1,ande2.Theprivatekeyisd.d.AssumeAlicehastheplaintextP=(4,2)tosendtoBob.e.Alicechooser=6andcalculatethetwopointsoftheciphertextC1=r×e1=6×(2,1)=(8,7)C2=(4,2)+6×(4,9)=(4,2)+(8,4)=(2,10)f.BobreceivesC1andC2.BobcalculatestheplaintextastogettheP.P=C2−(d×C1)=(2,10)−3×(8,7)=(2,10)−(8,4)=(2,10)+(8,7)=(4,2)27.a.E(g4,1)meansthata=g4andb=1.Theequationofthecurveisy2+xy=x3+g4x2+1b.Assumethattheirreduciblepolynomialisx4+x+1(SeeAppendixG).WeusetheprocessinExample10.16inthetextbookPage326tofindthepointsonthecurveasshowninFigureS10.27.khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！8FigureS10.27PartofthesolutiontoExercise27yP−Pg14g13(0,1)(0,1)g12(1,g6)(1,g13)g11g10(g3,g8)(g3,g13)g9(g5,g3)(g5,g11)g8g7(g6,g8)(g6,g14)g6g5(g9,g10)(g9,g13)g4(g10,g)(g10,g8)g3g2(g12,0)(g12,g12)gPoints10x01gg2g3g4g5g6g7g8g9g10g11g12g13g14Graphkhdaw.comc.Bobchoosese1=(g3,g8)andd=2.Thene2=d×e1=(g5,g3).Thepublickeyisthecombinationofe1,e2,andE(g4,1).Theprivatekeyisd.d.AlicechoosesP=(g10,g)andr=3.e.AlicecalculatesC课后答案网9,g10)andC6).1=r×e1=(g2=P+r×e2=(1,gf.BobdecryptthemessageP=C2−(d×C1)=(g10,g)=Pwww.hackshp.cn28.a.Thefollowingshowstheencryptingalgorithm.ItcallstheKnapsackSumalgo-rithmdefinedinthetext(Algorithm10.1).KnapsackEncrypt(P,a){C=KnapSum(P,a)returnC}b.Thefollowingshowsthedecryptingalgorithm.Itcallstheinv_KnapsackSumalgorithmdefinedinthetext(Algorithm10.1).KnapsackDecrypt(C,b,r,n){−1C’=r×CmodnP’=inv_KnapsackSum(C’,b)P=permute(P’)returnC}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！929.a.Thefollowingshowstheencryptingalgorithm.Aliceusestheoriginalmessage(m),arandomnumber(r)andtwofunctions(GandH).RSA_OAEP_Encrypt(m,e,n,r){M←pad(m)P1←M⊕G(r)P2←H(P1)⊕rC←Fast_Exponentiation(P1|P2,e,n)returnC}b.Thefollowingshowsthedecryptingalgorithm.Bobusestheciphertext(C),thekhdaw.comprivatekey(d),modulus(n),andtwofunctionsGandH.RSA_OAEP_Decrypt(C,d,n){课后答案网P←Fast_Exponentiation(C,d,n)P1,P2←Splitm,k(P)r←H(P1)⊕P2M←P1⊕G(r)www.hackshp.cnm←Extract(M)returnm}30.CyclingAttack(C,e,n){T1←CT2←T1emodnwhile(T2≠C){T1←T2eT2←T1modn}returnT1}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 课后答案网：www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！1031.ThefollowingshowstheAddPointalgorithm.P(x)andP(y)arexandycompo-nentsofP.CalculationsaredoneinGF(p).AddPoint(p,a,b,P1,P2){if(P1(x)≠P2(x))λ←((P2(y)−P1(y))/(P2(x)−P1(x)))modpelseλ←((3×(P1(x))2+a)/(2×P1(y)))modpP←(λ2−P−P3(x)1(x)2(x))modpP3(y)←(λ×(P1(x)−P3(x))−P1(y))modpreturnP3}32.ThefollowingshowstheAddPointalgorithm.P(x)andP(y)arexandycompo-khdaw.comnentsofP.CalculationaredoneinGF(2n)withtheselectedirreduciblepolyno-mial.AddPoint(n,a,b,P1,P2){课后答案网if(P1(x)≠P2(x)){λ←(P2(y)+P1(y))/(P2(x)+P1(x))www.hackshp.cnP3(x)←λ2+λ+P1(x)+P2(x)+aP←λ(P+P+P3(y)1(x)3(x))+P3(x)1(y)}else{λ←P1(x)+P1(y)/P1(x)P←λ2+λ+a3(x)P←(P2+(λ+1)P3(y)1(x))3(x)}returnP3}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com'