深入浅出密码学习题答案

奇数题号答案

奇数题号答案

SolutionstoHomeworkProblems(OddNumbered

Problems)

UnderstandingATextbookforStudentsandCryptographyPractitioners

byChristofPaarandJanPelzl

1

奇数题号答案

ProblemsofChapter1

1.1

1.Letterfrequencyanalysisoftheciphertext:

countfreq[%]

A

B

C

D

E

F

G

H

I

J

K

L

Mletter177307841713242247201902.631.084.641.0813.002.632.013.723.417.283.102.940.00

2.BecausethepracticeofthebasicmovementsofkataisthefocusandmasteryofselfistheessenceofMatsubayashiRyukaratedo,Ishall

trytoelucidatethemovementsofthekataaccordingtomyinterpretationbasedonfortyyearsofstudy.

Itisnotaneasytasktoexplaineachmovementanditssignificance,andsomemustremainunexplained.Togiveacompleteexplanation,onewouldhavetobequalifiedandinspiredtosuchanextentthathecouldreachthestateofenlightenedmindcapableofrecognizingsoundlesssoundandshapelessshape.Idonotdeemmyselfthefinalauthority,butmyexperiencewithkatahasleftnodoubtthatthefollowingistheproperapplicationandinterpretation.IoffermytheoriesinthehopethattheessenceofOkinawankaratewillremainintact.

3.ShoshinNagamine,furtherreading:TheEssenceofOkinawanKarate-DobyShoshinNagamine,TuttlePublishing,1998.

1.3

Onesearchenginecosts$100includingoverhead.Thus,1milliondollarsbuyus10,000engines.

1.keytestspersecond:5·108·104=5·1012keys/sec

Onaverage,wehavetocheck(2127keys:

(2127keys)/(5·1012keys/sec)=3.40·1025sec=1.08·1018years

Thatisabout108=100,000,000timeslongerthantheageoftheuniverse.Goodluck.

2.LetibethenumberofMooreiterationsneededtobringthesearchtimedownto24h:

1.08·1018years·365/2i=1day

2i=1,08·1018·365days/1dayi=68.42

Weroundthisnumberupto69assumingthenumberofMooreiterationsisdiscreet.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·3mod13≡6mod132·3mod13≡2·3mod13≡6mod132·3mod13≡2·3mod13≡6mod13

奇数题号答案

15,2and-11(and29and3respectively)arerepresentationsofthesameequivalenceclassmodulo13andcanbeused“synonymously”.

1.7

1.

MultiplicationtableforZ4

×0

0123

2

0321

2.

AdditiontableforZ5

+

12340

2

34012

4304321102413MultiplicationtableforZ50123400000

3.

AdditiontableforZ6

+

123450

2

345012

4

50123440543212030303MultiplicationtableforZ6×0012345

4.ElementswithoutamultiplicativeinverseinZ4are2and0

ElementswithoutamultiplicativeinverseinZ6are2,3,4and0

ForallnonzeroelementsofZ5existsbecause5isaprime.Hence,allnonzeroelementssmallerthan5arerelativelyprimeto5.

1.9

1.

2.

3.

4.

5.x=9mod13x=72=49≡10mod13x=310=95≡812·9≡32·9≡81≡3mod13x=7100=4950≡1050≡( 3)50=(310)5≡35≡32=9mod13bytrial:75≡11mod131.11

1.FIRSTTHESENTENCEANDTHENTHEEVIDENCESAIDTHEQUEEN

2.CharlesLutwidgeDodgson,betterknownbyhispennameLewisCarroll

1.13

a≡(x1 x2) 1(y1 y2)modm

b≡y1 ax1modm

Theinverseof(x1 x2)mustexistmodulom,i.e.,gcd((x1 x2),m)=1.

奇数题号答案

ProblemsofChapter2

2.1

1.yi=xi+Kimod26

xi=yi Kimod26

ThekeystreamisasequenceofrandomintegersfromZ26.

2.x1=y1 K1=”B” ”R”=1 17= 16≡10mod26=”K”etc···

DecryptedText:”KASPARHAUSER”

3.Hewasknifed.

2.3

Weneed128pairsofplaintextandciphertextbits(i.e.,16byte)inordertodeterminethekey.siisbeingcomputedby si=xiyi;i=1,2,···,128.

2.5

1

1

1

0

1

0

0

1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1

0 = Z 0 = Z 1 = Z 2 = Z 3 = Z 4 = Z 5 = Z 6 = Z 7 = Z 0

1.Sequence 1: z 0 = 0 0 1 1 1 0 1 0 0 1 1 1 0 1 ...

0

1

0

0

1

1

1

0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1

1 = Z 0 = Z 1 = Z 2 = Z 3 = Z 4 = Z 5 = Z 6 = Z 7 = Z 0

2.Sequence 2: z 0 = 1 1 0 1 0 0 1 1 1 0 1 0 0 1 ...

奇数题号答案

3.Thetwosequencesareshiftedversionsofoneanother.

2.7

Thefeedbackpolynomialfrom2.3isx8+x4+x3+x+1.

1

1

1

1

1

1

01100001001110010111000010011100111110000100111001111100001001110111111000010011111111110000100111111111100001001= Z0= Z1= Z2= Z14= Z15

So,theresulting rsttwooutputbytesare(1001000011111111)2=(90FF)16.

2.9

1.Theattackerneeds512consecutiveplaintext/ciphertextbitpairsxi,yitolaunchasuccessfulattack.

2.a.First,theattackerhastomonitorthepreviouslymentioned512bitpairs.

b.Theattackercalculatessi=xi+yimod2,i=0,1,...,2m 1

c.Inordertocalculatethe(secret)feedbackcoef cientspi,Oscargenerates256linearlydependentequationsusingtherelationshipbetweentheunknownkeybitspiandthekeystreamoutputde nedbytheequation

m 1

si+m≡j=0∑pj·si+jmod2;si,pj∈{0,1};i=0,1,2,...,255

withm=256.

d.Aftergeneratingthislinearequationsystem,ingGaussianElimination,revealingthe256feedbackcoef cients.

3.Thekeyofthissystemisrepresentedbythe256feedbackcoef cients.SincetheinitialcontentsoftheLFSRareunalteredlyshiftedoutoftheLFSRandXORedwiththe rst256plaintextbits,itwouldbeeasytocalculatethem.

2.11 xiyi=xi(xizi)=zi

W 22=101102

5 31=111112

奇数题号答案

I 8=010002

zi=111111000001000

1.InitializationVector:(Z0=1,1,1,1,1,1)

2.

C0111 C1 111 C2 11 …… 此处隐藏：4419字，全部文档内容请下载后查看。喜欢就下载吧 ……