《深入淺出密碼學(xué)習(xí)題答案》由會員分享，可在線閱讀，更多相關(guān)《深入淺出密碼學(xué)習(xí)題答案（20頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 深入淺出密碼學(xué)習(xí)題答案 奇數(shù)題號答案 奇數(shù)題號答案 SolutionstoHomeworkProblems(OddNumbered Problems) UnderstandingATextbookforStudentsandCryptographyPractitioners byChristofPaarandJanPelzl 1 Onaverage,wehavetocheck(2127keys: (2127keys)/(5·1012keys/sec)=3.40·1025

2、sec=1.08·1018years Thatisabout108=100,000,000timeslongerthantheageoftheuniverse.Goodluck. 2.LetibethenumberofMooreiterationsneededtobringthesearchtimedownto24h: 1.08·1018years·365/2i=1day 2i=1,08·1018·365days/1dayi=68.42 Weroundthisnumberupto69assumingthenumberofMooreit

3、erationsisdiscreet.Thus,wehavetowaitfor: 1.5·69=103.5years NotethatitisextremelyunlikelythatMoore’sLawwillbevalidforsuchatimeperiod!Thus,a128bitkeyseemsimpossibletobrute-force,evenintheforeseeablefuture. 1.5 1. 2. 3. 4.15·29mod13≡2·3mod13≡6mod132·29mod13≡2·3

4、mod13≡6mod132·3mod13≡2·3mod13≡6mod132·3mod13≡2·3mod13≡6mod13 1.13 a≡(x1x2)1(y1y2)modm b≡y1ax1modm Theinverseof(x1x2)mustexistmodulom,i.e.,gcd((x1x2),m)=1. 奇數(shù)題號答案 ProblemsofChapter2 2.1 1.yi=xi+Kimod26 xi=yiKimod26 Thekeystreamisasequenceofr

5、andomintegersfromZ26. 2.x1=y1K1=”B””R”=117=16≡10mod26=”K”etc··· DecryptedText:”KASPARHAUSER” 3.Hewasknifed. 2.3 Weneed128pairsofplaintextandciphertextbits(i.e.,16byte)inordertodeterminethekey.siisbeingcomputedbysi=xiyi;i=1,2,···,128. 2.5 1 1 1

6、 0 1 0 0 1011101000011101 0=Z0=Z1=Z2=Z3=Z4=Z5=Z6=Z7=Z0 1.Sequence1:z0=00111010011101... 0 1 0 0 1 1 1 0101001111101001 1=Z0=Z1=Z2=Z3=Z4=Z5=Z6=Z7=Z0 2.Sequence2:z0=11010011101001... m1 si+m≡

7、j=0∑pj·si+jmod2;si,pj∈{0,1};i=0,1,2,...,255 withm=256. d.Aftergeneratingthislinearequationsystem,ingGaussianElimination,revealingthe256feedbackcoefcients. 3.Thekeyofthissystemisrepresentedbythe256feedbackcoefcients.SincetheinitialcontentsoftheLFSRareunalteredlyshiftedoutoftheLFSRan

8、dXORedwiththerst256plaintextbits,itwouldbeeasytocalculatethem. 2.11xiyi=xi(xizi)=zi W22=101102 531=111112 奇數(shù)題號答案 I8=010002 zi=111111000001000 1.InitializationVector:(Z0=1,1,1,1,1,1) 2. C0111C1111C2111=C3111C4110 C5100110=000 3.yi=0100

9、1 zi=11111 J111100110100·0000000000001111111000050000001000A110100110000010001010E0001101111D0100101000J111001110020000110010B E-Expansionboxmapsbitposition1topositions2and48.InputtoS-Boxes:S1:010000 S2=S3=···=S7:000000 S8:000001 TwoS-Boxesgetadifferentinput.P(S)=

10、D0585B9E (L1,R1)=80000000D0585B9E 1.2S-Boxes,S1andS8 2.Accordingtodesigncriteria,aminimumof2bits/bit. 2·2=4bits3.See(1). 4.6bitshavechanged: 3fromS1 2fromS8 1inthelefthalf 3.7 1.K1+i=K16ifori=0,1,...7. 2.Following(a),twoequationsarees

11、tablished: C1+i=C16i D1+i=D16i Theseequationsyield C0,j=0undD0,j=0or C0,j=0undD0,j=1or C0,j=1undD0,j=0oder C0,j=1undD0,j=1 HencethefourweakkeysafterPC-1aregivenby: w1=1...1]0...0]1...1] 奇數(shù)題號答案 255encryptionsforasuccessfullbrute-forcea

12、ttackonDES,255/(4.8·1010)≈750600secondsarerequired(whichapproximatelyis8.7days).˙≈18machinesarerequired.2.Forasuccessfullaverageattackinonehour,8.724 3.Themachineperformsabrute–forceattack.However,theremightbemorepowerfulanalyticalat-tackswhichexploreweaknessesofthecipher.Hence,thekey–searchma

13、chineprovidesonlyalowersecuritythreshold. 3.13 1.ThestateofPRESENTaftertheexecutionofoneroundisF00000000000000F.Belowyoucanndallintermediatevalues. Plaintext Roundkey StateafterKeyAdd StateafterS-Layer StateafterP-Layer BBBB55555555EEEEFFFF Keyst

14、ateafterrotation KeystateafterS-box KeystateafterCounterAdd RoundkeyforRound2 1 x+1 x2+1 x2+x+10010xx2x2+xx0x2x+1x2+x+1x+10x2+xx2+x+11x20x+1x2+xx2+1x2+101xx+1x2+x0x2+x+1x2+1xx2+x+10x2+11x2 奇數(shù)題號答案 1.A(x)B(x)=(x2+1)(x3+x2+1)=x5+x4+x2+x3+x2+1

15、A(x)B(x)=x5+x4+x3+1 x+1 4543x+x+1x+x+x+152x+x+x x4+x3+x2+x+1 x4+x+1 x3+x2 C=x3+x2≡A(x)B(x)modP(x).2.A(x)B(x)=(x2+1)(x+1)=x3+x+x2+1 C=x3+x2+x+1≡A(x)B(x)modP(x) ThereductionpolynomialisusedtoreduceC(x)inordertoreducetheresulttoGF(24).Otherwise,a’simple’m

16、ultiplicationwithoutreductionwouldyieldaresultofahigherdegree(e.g.,withx5)whichwouldnotbelongtoGF(24)anymore. 4.7 1.BytheExtendedEuclideanalgorithm: x+x+1=(x)+t2(x)=t0q1t1=q1=x3=x3 x=(x+1)+1t3(x)=t1q2t2=11x3=1x3=x3+1 x+1=(1)+04 So,A1=x3+1. Check:x(x3+1)=x4+x

17、≡(x+1)+xmodP(x)=1modP(x). 2.BytheExtendedEuclideanalgorithm:4x+x+1=(x2+x)+t2=t0q1t1=q1=x2+x+1 x2+x=1+ So,A1=x2+x+1. Check:(x2+x)(x2+x+1)=x4+2x3+2x2+x=x4+x≡(x+1)+xmodP(x)=1modP(x). 4.9 1616161616161616B=ByteSub(A)=1616161616161616 TheShiftRowsoperationdoesnot

18、changeanythingsinceallbytesofBequaleachother.TheMixComumnoperationisequalforeveryresultigbyteCiandisdescribedby (01+01+02+03)hex·(16)hex.Wehavetoremind,thatallcalculationshavetobedoneinGF(28),sothat(01+01+02+03)hex=(01)hexandhence,allresultingbytesofCremain(16)hex1616161616161616C=MixColumn(B)

19、=1616161616161616 Therstroundkeyequalskey.So,theoutputoftherstistheunmodiedAESE9E9E9E9FFFFFFFF1616161616161616FFFFFFFFE9E9E9E9C⊕K=16161616⊕FFFFFFFF=E9E9E9E9E9E9E9E9FFFFFFFF16161616 4.11 4.15 1.RC=x7=(10000000)2 2.RC=x8=x4+x3+x+1=(00011011)2 3.RC=x9=x8·x=x5+x4+x2+x

20、=(00110110)2 128×16=2048byte=2kbyte. Afterthis,thestreamcipheroutputmustrepeat(andoddsarethatthecyclelenghtismuchshorter).Thus,ifanattackerhastoknowatmost2kBofplaintextinordertorecovertheentirestreamcipheroutputwithwhichhecandecryptallotherciphertext. 3.No,westillonlygenerateamaxim

21、umof256keystreamwordsoflength16byte. Remark:Inthechapteronhashfunctionswewilllearnaboutthebirthdayparadox.This√isapplicableheretooandtellsusthattheexpectedlengthofthesequenceisinfactapproximately n·n1 2=7140 keypairs.Remarkthateachofthesekeypairshavetobeexchangedinasecureway(

22、overasecurechannel)! 6.5 1.gcd(7469,2464)=77 2.gcd(4001,2689)=1 6.7 1.gcd(26,7)=1 q1=3,q2=1,q3=2 t2=3,t3=4,t4=11 a1≡t4modm≡11mod26=15 2.gcd(999,19)=1 q1=52,q2=1,q3=1,q4=2,q5=1 t2=52,t3=53,t4=105,t5=263,t6=368 a1≡t6modm≡368mod999

23、=631 6.9 1.φ(p)=(p1p0)=p1 2.φ(p·q)=(p1)·(q1) φ(15)=φ(3·5)=2·4=8 φ(26)=φ(2·13)=1·12=12 6.11 1.m=6;φ(6)=(31)·(21)=2; Euler’sTheorem:a2≡1mod6,ifgcd(a,6)=102≡0mod6;12≡1mod6;22≡4mod6; 2.Kpub=(n,e)=(697,49) Calculationofd=e1modφ(n)=491mod640using

24、EEA: 640=13·49+3 49=16·3+1 1=4916·3 491mod640≡209.=4916(64013·49)=209·4916·640 7.3 1.e=3;y=26 2.d=27;y=14So,theprivatekeyisdenedbyKpr=(p,q,d)=(41,17,209). ?Test:yi=jemodn;j=32,33,...,126 2.SIMPSONS Anexactdescriptionofthealgorithm,whichisof

25、tenreferredtoask-aryexponentiation,isgivenin .Notethatthebitlengthoftheexponentinthisdescriptionistkbit.Anexampleforthecasek=3isgivenbelow. Thecomplexityofthealgorithmforanl+1bitexponentis2k3multiplicationsintheprecompu-tationphase,andaboutl1squaringsandl(2k1)/2kmultiplicationsinthemainl

26、oop. Example13.2.Thegoalistocomputegemodnwithk-arywheren=163,g=12,k=3,e=14510=2218=23=100100012 Precomputation: g0:=1 g1:=12 g2:=g1·12=144g3:=g2·12=1728mod163=98g4:=g3·12=1176mod163=35g5:=g4·12=420mod163=94g6:=g5·12=1128mod163=150g7:=g6·12=1800mod163=7Exponentiation:

27、 Iteration 10000 1b 10010000 2bA:=A·g1=1680mod163=50A:=A·g2=6768mod163=853SQCalculationA:=g2=1443SQ 奇數(shù)題號答案 a ord(a) 123456 136362 3.Z13: a ord(a) ProblemsofChapter9 9.1a=2,b=2 4·23+27·22=4·8+27·4=32+108=140≡

28、4=0mod17√17≈26,25q.e.d.9.317+12 9.5 1.ThepointsofEare {(0,3),(0,4),(2,3),(2,4),(4,1),(4,6),(5,3),(5,4)} 2.Thegrouporderisgivenby #G=#{O,(0,3),(0,4),(2,3),(2,4),(4,1),(4,6),(5,3),(5,4)}=9 ProblemsofChapter10 10.1 10.9 1.sigKpr(x)=xdmodn=y ve

29、rKpub(x,y):x≡yemodn Assumethatdhaslbits. Usingthesquare&multiplyalgorithm,theaveragesigningwilltake: #≈lsquarings+12·l? TunitTunitT(sig) 100ns25.6μs435.2μs 100ns102.4μs1.741ms 128)· 2·l·Tunit 奇數(shù)題號答案 Tunit 8 F≥ ii)50.33MHz1

30、2·Tunit s2≡(x1dr)(kE1+1) s1(x2dr) rmodp1 10.15SimilarlytotheattackonElgamal,anattackercanusefollowingsystemofequations 1s1≡(SHA(x1)+dr)kEmodq 1s2≡(SHA(x2)+dr)kEmodq forknowns1,s2,x1,andx2torstcomputetheephemeralkeykEandthentheprivatekeyd: 1s1s2≡kE(SHA(

31、x1)SHA(x2))modq SHA(x1)SHA(x2)kE≡ rmodq ProblemsofChapter11 11.1 1.A1=E0+f1(B0,C0,D0)+(A)<<<5+Wj+Kt=5A827999hexB1=A0=00000000hexC1=(B0)<<<30=00000000hexD1=C0=00000000hexE1=D0=00000000hex 2.A1=E0+f1(B0,C0,D0)+(A)<<<5+Wj+Kt=6A827999hexB1=A0=00000000hexC1=(B0)<<<30=0

32、0000000hexD1=C0=00000000hexE1=D0=00000000hex 奇數(shù)題號答案 11.3 xixixi Hi1Hi1Hi1Hi (a)e(Hi1,xi)⊕xi Hi(b)e(Hi1,xi⊕Hi1)⊕xi⊕H i1Hi(c)e(Hi1,xi)⊕xi⊕Hi1 Hi1 xiHi1 Hi1xixiHi (d)e(Hi1,xi⊕H i1)⊕xiHi(e)e(xi,Hi1)⊕Hi1 Hi(f)e(xi,xi⊕Hi1)⊕xi⊕Hi

33、1 奇數(shù)題號答案 Hi1Hi1 xi xixiHi1Hi (g)e(xi,Hi1)⊕xi⊕Hi1 Hi(h)e(xi,xi⊕Hi1)⊕Hi1 Hi(i)e(xi⊕Hi1,xi)⊕xi Hi1xiHi1 xiHi1xiHi (j)e(xi⊕Hi1,Hi1)⊕Hi1 Hi(k)e(xi⊕Hi1,xi)⊕Hi1 Hi(l)e(xi⊕Hi1,Hi1)⊕xi 11.5 Birthdayattack:k≈1ε n 2

34、64 1.5·10196.0·1018 2160 奇數(shù)題號答案 passwordsbyincrementingxi.Thisway,youwillgeneratepseudo-randomoutputsy.EventhoughthereisachanceyouwillnotgenerateyUattheoutput,thelikelihoodissmall.Notethatyoucanalsotryvaluesxiwhichhavemorethan64bitbyiteratingthehashfunction. 3.Asecond-p

35、reimageattack 4.Whenc=0bothhalfsoftheoutputwillalmostneverbethesame.So,theentropyoftheoutputgrowsto(roundabout)128bitwhichmakesasecond-preimageattackcomputationalinfeasible.ProblemsofChapter12 12.1 1. 2. 1Calculatex||h=ek1(y).Calculateh′=H(k2||x).Ifh=h′,themessageisauth

36、entic.Ifh=h′,eitherthemessageortheMAC(orboth)hasbeenalteredduringtransfer.1Calculatex||s=ek1(y).Calculateh′=H(x).Verifythesignature:verkpub(s,H(x)) 12.3 1.ci=zi{x1x2...xnH1(x)H2(x)...Hm(x)};i=1,2,...,n+m 1)Assumexhasnbits.Oscarrstcomputes zi=xi⊕ci;i=1,2,...,n 2)Oscarrec

37、omputesH(x)sinceheknowsx. 3)AssumeH(x)hasmoutputbits.Oscarcomputes zj+n=Hj(x)⊕cj+nj=1,2,...,m′4)OscarcomputesH(x) 5)Oscarcomputes′c′i=1,2,...,ni=zi⊕xi′′cj+n=zj+n⊕Hj(x)j=1,2,...,m 2.No.AlthoughOscarcanstillrecoverz1,z2,...,zn,hecannotrecoverthebit-streamportionzn+1,zn+2,...,zn

38、+mwhichwasusedforencryptingMACk2(x).Evenifhewouldknowthewholebit-stream,hewouldnotbeabletocomputeavalidMACk2(x′)sincehedoesnotknowk2. 12.5 1.ThisattackassumesthatOscarcantrickBobintosigningthemessagex1.Thisis,ofcourse,notpossibleineverysituation,butonecanimaginescenarioswhereOscarcanpose

39、asaninnocentpartyandx1isthemessagebeinggeneratedbyOscar. AliceOscar → ←(x2,m)x1Bobm=MACk(x1) m′=MACk(x2) verk(m′,m)=truereplace!← √(x1,m)2.Forconstructingcollisions,Oscarmustbeabletocomputeabout ithesessionkeysKsesareencryptedwithKU,KDC.Hewillalsobeabletodec

40、ryptthefollowingkeys KU,KDCuntiltheattackisdetected(ty)andnewkeysareexchangedusingasecurechannel.Hence,all icommunicationbetweentxandtymaybecompromised.Though,heis,evenwithknowledgeofKU,KDC, i1notabletorecoverKU,KDC.Hence,hecannotdecryptmessagesbeforethepointoftimetx.Inconclusion,

41、 thisvariantprovidesPerfectForwardSecrecy. 13.7 1.OnceAlice’sKEKkAisbeingcompromised,Oscarcancomputethesessionkeyksesand,thus,decryptallmessages. 2.ThesameappliestoacompromisedKEKkBofBob. 13.9 1.t=106bits/sec storage=t·r=2h·106bits/sec=2·3600·106bits/sec=7.2Gbits=0.9GByte Storageoflessthan1GBytecanbedoneatmoderatecosts,e.g.,onharddisksorCDs. pute#keysthatanattackercanrecoverin30days: =4320#Keys=30days 10Keyderivationperiod: TKder=2hi+j - 20 -