深入浅出密码学习题答案

SolutionstoHomeworkProblems(OddNumberedProblems)UnderstandingCryptographyATextbookforStudentsandPractitionersbyChristofPaarandJanPelzl12SolutionstoHomeworkProblems(OddNumberedProblems)ProblemsofChapter11.11.Letterfrequencyanalysisoftheciphertext:lettercountfreq[%]lettercountfreq[%]A50.77N172.63B6810.53O71.08C50.77P304.64D233.56Q71.08E50.77R8413.00F10.15S172.63G10.15T132.01H233.56U243.72I416.35V223.41J487.43W477.28K497.59X203.10L81.24Y192.94M629.60Z00.002.BecausethepracticeofthebasicmovementsofkataisthefocusandmasteryofselfistheessenceofMatsubayashiRyukaratedo,Ishalltrytoelucidatethemovementsofthekataaccordingtomyinterpretationbasedonfortyyearsofstudy.Itisnotaneasytasktoexplaineachmovementanditssignificance,andsomemustremainunexplained.Togiveacompleteexplanation,onewouldhavetobequalifiedandinspiredtosuchanextentthathecouldreachthestateofenlightenedmindcapableofrecognizingsoundlesssoundandshapelessshape.Idonotdeemmyselfthefinalauthority,butmyexperiencewithkatahasleftnodoubtthatthefollowingistheproperapplicationandinterpretation.IoffermytheoriesinthehopethattheessenceofOkinawankaratewillremainintact.3.ShoshinNagamine,furtherreading:TheEssenceofOkinawanKarate-DobyShoshinNagamine,TuttlePublishing,1998.1.3Onesearchenginecosts$100includingoverhead.Thus,1milliondollarsbuyus10,000engines.1.keytestspersecond:5·108·104=5·1012keys/secOnaverage,wehavetocheck(2127keys:(2127keys)/(5·1012keys/sec)=3.40·1025sec=1.08·1018yearsThatisabout108=100,000,000timeslongerthantheageoftheuniverse.Goodluck.2.LetibethenumberofMooreiterationsneededtobringthesearchtimedownto24h:1.08·1018years·365/2i=1day2i=1,08·1018·365days/1dayi=68.42Weroundthisnumberupto69assumingthenumberofMooreiterationsisdiscreet.Thus,wehavetowaitfor:1.5·69=103.5yearsNotethatitisextremelyunlikelythatMoore’sLawwillbevalidforsuchatimeperiod!Thus,a128bitkeyseemsimpossibletobrute-force,evenintheforeseeablefuture.1.51.15·29mod13≡2·3mod13≡6mod132.2·29mod13≡2·3mod13≡6mod133.2·3mod13≡2·3mod13≡6mod134.2·3mod13≡2·3mod13≡6mod13SolutionstoHomeworkProblems(OddNumberedProblems)315,2and-11(and29and3respectively)arerepresentationsofthesameequivalenceclassmodulo13andcanbeused“synonymously”.1.71.MultiplicationtableforZ4×0123000001012320202303212.AdditiontableforZ5MultiplicationtableforZ5+01234001234112340223401334012440123×012340000001012342024133031424043213.AdditiontableforZ6MultiplicationtableforZ6+012345001234511234502234501334501244501235501234×0123450000000101234520240243030303404204250543214.ElementswithoutamultiplicativeinverseinZ4are2and0ElementswithoutamultiplicativeinverseinZ6are2,3,4and0ForallnonzeroelementsofZ5existsbecause5isaprime.Hence,allnonzeroelementssmallerthan5arerelativelyprimeto5.1.91.x=9mod132.x=72=49≡10mod133.x=310=95≡812·9≡32·9≡81≡3mod134.x=7100=4950≡1050≡(−3)50=(310)5≡35≡32=9mod135.bytrial:75≡11mod131.111.FIRSTTHESENTENCEANDTHENTHEEVIDENCESAIDTHEQUEEN2.CharlesLutwidgeDodgson,betterknownbyhispennameLewisCarroll1.13a≡(x1−x2)−1(y1−y2)modmb≡y1−ax1modmTheinverseof(x1−x2)mustexistmodulom,i.e.,gcd((x1−x2),m)=1.4SolutionstoHomeworkProblems(OddNumberedProblems)ProblemsofChapter22.11.yi=xi+Kimod26xi=yi−Kimod26ThekeystreamisasequenceofrandomintegersfromZ26.2.x1=y1−K1=”B”−”R”=1−17=−16≡10mod26=”K”etc···DecryptedText:”KASPARHAUSER”3.Hewasknifed.2.3Weneed128pairsofplaintextandciphertextbits(i.e.,16byte)inordertodeterminethekey.siisbeingcomputedbysi=xiLyi;i=1,2,···,128.2.51.Zi111010010111010000111010=Z0=Z1=Z2=Z3=Z4=Z5=Z6=Z7=Z0Sequence1:z0=00111010011101...2.010011101010011111010011=Z0=Z1=Z2=Z3=Z4=Z5=Z6=Z7=Z0Sequence2:z0=11010011101001...SolutionstoHomeworkProblems(OddNumberedProblems)53.Thetwosequencesareshiftedversionsofoneanother.2.7Thefeedbackpolynomialfrom2.3isx8+x4+x3+x+1.00111001100111000100111000100111=Z=Z=Z=Z=Z0121415111111110111111100111111001111100001111100001110100001100100001100100001100100011100100011100100s7s6s5s4s3s2s1CLK0sSo,theresultingfirsttwooutputbytesare(1001000011111111)2=(90FF)16.2.91.Theattackerneeds512consecutiveplaintext/ciphertextbitpairsxi,yitolaunchasuccessfulattack.2.a.First,theattackerhastomonitorthepreviouslymentioned512bitpairs.b.Theattackercalculatessi=xi+yimod2,i=0,1,...,2m−1c.Inordertocalculatethe(secret)feedbackcoefficientspi,Oscargenerates256linearlydependentequationsusingtherelationshipbetweentheunknownkeybitspiandthekeystreamoutputdefinedbytheequationsi+m≡m−1∑j=0pj·si+jmod2;si,pj∈{0,1};i=0,1,2,...,255withm=256.d.Aftergeneratingthislinearequationsystem,itcanbesolvede.g.usingGaussianElimination,revealingthe256feedbackcoefficients.3.Thekeyofthissystemisrepresentedbythe256feedbackcoefficients.SincetheinitialcontentsoftheLFSRareunalteredlyshiftedoutoftheLFSRandXORedwiththefirst256plaintextbits,itwouldbeeasytocalculatethem.2.11xiLyi=xiL(xiLzi)=ziW⇐⇒22=101102J⇔9=010012P⇐⇒15=0111125⇐⇒31=1111126SolutionstoHomeworkProblems(OddNumberedProblems)I⇔8=010002A⇔0=000002xi=101100111101000yi=010011111100000zi=1111110000010001.InitializationVector:(Z0=1,1,1,1,1,1)2.