深入浅出密码学习题答案

奇数题号答案

奇数题号答案

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,http://www.77cn.com.cningGaussianElimination,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 111 = C3 111 C4 110

C5100 1 1 0 = 0 0 0

3.yi=01001

zi=11111

J 1 1110 0 110 100 · 0 0 000 0 000 0001 1111110000 5 0000001000 A 1101001100 0 0010001010 E 0001101111 D 0100101000 J 1110011100 2 0000110010 B

奇数题号答案

P(S)=D8D8DBBC

(L1,R1)=00000000D8D8DBBC(1)

3.5

IP(x)mapsbit57toposition33,whichisposition1inR0.

E-Expansionboxmapsbitposition1topositions2and48. InputtoS-Boxes:S1:010000

S2=S3=···=S7:000000

S8:000001

TwoS-Boxesgetadifferentinput.P(S)=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=K16 ifori=0,1,...7.

2.Following(a),twoequationsareestablished:

C1+i=C16 i

D1+i=D16 i

Theseequationsyield

C0,j=0undD0,j=0or

C0,j=0undD0,j=1or

C0,j=1undD0,j=0oder

C0,j=1undD0,j=1

HencethefourweakkeysafterPC-1aregivenby:

w1=[0...0K

w2=[0...0K

w3=[1...1K

w4=[1...1K

3.P(randomlychoseaweakkey)=22fri=0,1,...,7.frj=1,2,...,28.0...0]1...1]0...0]1...1]

奇数题号答案

255encryptionsforasuccessfullbrute-forceattackonDES,255/(4.8·1010)≈750600secondsarerequired(whichapproximatelyis8.7days).˙≈18machinesarerequired.2.Forasuccessfullaverageattackinonehour,8.724

3.Themachineperformsabrute–forceattack.However,theremightbemorepowerfulanalyticalat-tackswhichexploreweaknessesofthecipher.Hence,thekey–searchmachineprovidesonlyalowersecuritythreshold.

3.13

1.ThestateofPRESENTaftertheexecutionofoneroundisF00000000000000F.Belowyoucan ndallintermediatevalues.

Plaintext

Roundkey

StateafterKeyAdd

StateafterS-Layer

StateafterP-Layer

BBBB55555555EEEEFFFF

Keystateafterrotation

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

奇数题号答案

1.A(x) B(x)=(x2+1)(x3+x2+1)=x5+x4+x2+x3+x2+1

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’multiplicationwithoutreductionwouldyieldaresultofahigherdegree(e.g.,withx5)whichwouldnotbelongtoGF(24)anymore.

4.7

1.BytheExtendedEuclideanalgorithm:

x+x+1=[x3](x)+[x+1]t2(x)=t0 q1t1= q1= x3=x3

x=[1](x+1)+1t3(x)=t1 q2t2=1 1 x3=1 x3=x3+1

x+1=[x+1](1)+04

So,A 1=x3+1.

Check:x (x3+1)=x4+x≡(x+1)+xmodP(x)=1modP(x).

2.BytheExtendedEuclideanalgorithm:4x+x+1=[x2+x+1](x2+x)+[1]t2=t0 q1t1= q1=x2+x+1

x2+x=[x2+x]1+[0]

So,A 1=x2+x+1.

Check:(x2+x)(x2+x+1)=x4+2x3+2x2+x=x4+x≡(x+1)+xmodP(x)=1modP(x).

4.9

16161616 16161616 B=ByteSub(A)= 16161616 16161616

TheShiftRowsoperationdoesnotchangeanythingsinceallbytesofBequaleachother.TheMixComumnoperationisequalforeveryresultigbyteCiandisdescribedby

(01+01+02+03)hex·(16)hex.Wehavetoremind,thatallcalculationshavetobedoneinGF(28),sothat(01+01+02+03)hex=(01)hexandhence,allresultingbytesofCremain(16)hex 16161616 16161616 C=MixColumn(B)= 16161616 16161616

The rstroundkeyequalskey. So,theoutputof the rstis the unmodi edAES E9E9E9E9FFFFFFFF16161616 16161616 FFFFFFFF E9E9E9E9 C⊕K= 16161616 ⊕ FFFFFFFF = E9E9E9E9 E9E9E9E9FFFFFFFF16161616

4.11

奇数题号答案

1.d=01,b=1 (b7x7+...+b0)=b.

d0=b0,d1=b1,...,d7=b7.

2.d=02 b=x(b7x7+...+b0)=b7x8+b6x7+...+b0x

x8≡x4+x3+x+1modP(x).

d=b6x7+b5x6+b4x5+[b3+b7]x4+[b2+b7]x3+b1x2+[b0+b7]x+b7

d7=b6d6=b5

d5=b4d4=b3+b7

d3=b2+b7d2=b1

d1=b0+b7d0=b7

3.d=03 b=(x+1)b=xb+b

Usingsolutionsfroma)andb):

d=(b6+b7)x7+(b5+b6)x6+(b4+b5)x5+(b3+b4+b7)x4+(b2+b3+b7)x3+(b1+b2)x2+(b0+b1+b7)x+(b0+b7)

d7=b6+b7d6=b5+b6

d5=b4+b5d4=b3+b4+b7

d3=b2+b3+b7d2=b1+b2

d1=b0+b1+b7d0=b0+b7

4.13

1.A=01h,A(x)=1

A 1(x)=1=01h

A 1(x)isnowtheinputtotheaf netransformationofRijndaelasdescribedinSubsection4.2.1oftheRijndaelSpeci cations:

M·A 1+V

whereMandVarea xedmatrixandvector,respectively.

11110 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 M·A+V=M· 0 + 0 = 1 + 0 = 1 0 1 0 1 1 0 1 0 1 1 00000

ByteSub(01h)=7Ch

2.A=12h,A(x)=x4+x

ApplyextendedEuclideanalgorithm:A 1(x)=x7+x5+x3+x=AAh.

01011 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 M·A+V=M· 0 + 0 = 0 + 0 = 0 1 1 1 1 0 0 1 0 1 1 10101

Remark:Itis(big)coincidencethatM·A 1=A 1.Thisonlyholdsforthisspeci cvalueofA 1.ByteSub(12h)=C9h

4.15

1.RC[8]=x7=(10000000)2

2.RC[9]=x8=x4+x3+x+1=(00011011)2

3.RC[10]=x9=x8·x=x5+x4+x2+x=(00110110)2

奇数题号答案

ProblemsofChapter5

5.1

Sincetherecordsarenotrelated,wetypicallywanttoaccessonlyasinglerecordandnotitsadjacentones.TheuseofCBCmodeisthusnotwellsuited.ECBmostseemstobethebestchoice.

5.3

Thedecryptionofan”CBC-encrypted” leisde nedbyxi=dK(yi)⊕yi 1.SinceyouknowthekeyKandthepair(x0,y0)(fromthe rst le),theunknownIVcaneasilybeobtainedbyconvertingtheequation:

IV=y 1=dk(y0)⊕x0

Afterthat,thesecond(unidenti ed) lecaneasilybedecryptedbyusingthedecryptionequationmen-tionedabove(withy 1=IV).

5.5

IfthesameIVisusedfortheOFBencryption,thecon dentialitymaybecompromized.Ifaplaintextblockxjofsuchamessagemisknown,theoutputcanbecomputedeasilyfromtheciphertextblockyjofthemessagem.Thisinformationthenallowsthecomputationoftheplaintextblockx′jofanyothermessagem′thatisencryptedusingthesameIV.

5.7

1.

2.Theproblemwiththeschemeisthatthereareonly256differentinputsFBitotheAESalgorithm.Thatmeansthereareonly256differentoutputvectorsoflength128bitthatformthekeystream.Tomakethingsworse,thecipheroutputwillrunintoacyclequickly.Let’sdenotethesequenceoffeedbackbytesbyFB1,FB2,...AssoonasafeedbackbyteFBjisgeneratedthatisequaltoanearlieroneFBi,i.e.,i<j,thesequence

FBi,FBi+1,...,FBj=FBi,FBi+1,...,FBj=FBi,FBi+1,...

repeatsperiodically.Sincethereareonly256differentvaluesforFB,themaximumsequencelengthis256.Sinceeachvalueisassociatedwitha128(16byte)AESoutput,thekeystreamsequencesihasamaximumcyclelengthof:

128×16=2048byte=2kbyte.

Afterthis,thestreamcipheroutputmustrepeat(andoddsarethatthecyclelenghtismuchshorter).Thus,ifanattackerhastoknowatmost2kBofplaintextinordertorecovertheentirestreamcipheroutputwithwhichhecandecryptallotherciphertext.

3.No,westillonlygenerateamaximumof256keystreamwordsoflength16byte.

Remark:Inthechapteronhashfunctionswewilllearnaboutthebirthdayparadox.This√isapplicableheretooandtellsusthattheexpectedlengthofthesequenceisinfactapproximately

奇数题号答案

ForachievingthesameprobabilitywithAES-256,2127plaintextsandciphertextsarerequired(whichisveryveryunlikely)!

5.15y′=eK3(eK2(eK1(x′)))

1.Pre–computeeKi(x′)=zi;i=1,2,...,256andstoreallpairs(zi,Ki)

(2)1 1′56562.Decryptza,b=e Kb(eKa(y));a=1,2,...,2;b=1,2,...,2

Ifamatchisfound,ifthereisaza,b=zitestfurtherkeypairs(x′′,y′′),(x′′′,y′′′),...,withthethreekeysinvolvedinthematch:

Ifthethreekeysgenerateavalidencryptionforallpairs,thesearemostlikelythecorrectkeys.OtherwisecontinuewiththenextpairKa,Kb.

l=3;t=3pairs

23·56 3·64=2 3·8=2 24 t=3pairs(x,y)aresuf cient(2)(1)(1)(1)

ProblemsofChapter6

6.1Fromatheoreticalpointofview,publickeycryptographycanbeusedasareplacementforsymmet-riccryptography.However,inpracticalapplications,symmetriccipherstendtobeapproximately1000timesfasterthanpublickeyschemes.Hence,symmetricciphersareusedwhenitcomestobulkdataencryption.

6.3Ifeverypairoutofn=120employeesrequiresadistinctkey,weneedinsum

n·n 1

2=7140

keypairs.Remarkthateachofthesekeypairshavetobeexchangedinasecureway(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

a 1≡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

a 1≡t6modm≡ 368mod999=631

6.9

1.φ(p)=(p1 p0)=p 1

2.φ(p·q)=(p 1)·(q 1)

φ(15)=φ(3·5)=2·4=8

φ(26)=φ(2·13)=1·12=12

6.11

1.m=6;φ(6)=(3 1)·(2 1)=2;

Euler’sTheorem:a2≡1mod6,ifgcd(a,6)=102≡0mod6;12≡1mod6;22≡4mod6;

奇数题号答案

32≡9≡3mod6;42≡16≡4mod6;52≡25≡1mod62.m=9;φ(9)=32 31=9 3=6;

Euler’sTheorem:a6≡1mod9,ifgcd(a,9)=106≡0mod9;16≡1mod9;26≡64≡1mod9;36≡(33)2≡02≡0mod9;46≡(26)2≡12≡1mod9;56≡1mod9;66≡26·36≡1·0≡0mod9;76≡1mod9;86≡1mod96.13

Euclid’sAlgorithm:

Iteration2:r0=q1r1+r2

Iteration3:r1=q2r2+r3r2=r0 q1r1=s2r0+t2r1r3=[ q2]·r0+[1+q1q2]·r1=s3r0+t3r1(1)(2)

from(1),(2):s2=1;s3= q2(3)

t2= q1;t3=1+q1q2(4)

TheiterationformulafortheEuclideanAlgorithmgives:

(5)

(6)

(7)

(8)s2=s0 q1s1=1EA(3)EA(3)(3)s3=s1 q2s2=s1 q2= q2 s1=0EAEA(6)t2=t0 q1t1= q1(4) s0=1(4)(5)t3=t1 q2t2=t1+q1q2=1+q1q2

t1=1(8)(4) t0=0(7)

ProblemsofChapter7

7.1

1.Onlye=31isavalidpublickey,becauseΦ(n)=(p 1)(q 1)=40·16=640=27·5.Furthermoregcd(ei,φ(n))=1hastobeful lled.Hence,onlye2=49maybeusedaspublicexponent.

2.Kpub=(n,e)=(697,49)

Calculationofd=e 1modφ(n)=49 1mod640usingEEA:

640=13·49+3

49=16·3+1

1=49 16·3

49 1mod640≡209.=49 16(640 13·49)=209·49 16·640

7.3

1.e=3;y=26

2.d=27;y=14So,theprivatekeyisde nedbyKpr=(p,q,d)=(41,17,209).

奇数题号答案

7.5

1.Inthiscase,abrute-forceattackonallpossibleexponentswouldbeeasilyfeasible.

2.Asanabsoluteminimum,abitlengthof128bitisrecommendedinordertoprecludebrute-forceattacksontheprivateexponent.However,theexponentmustevenbelargersincethereexistanalyticalattackswhicharemorepowerful.Inpractice,alengthfordofleast0.3timesthebitlengthofnisrecommended,i.e.forRSA-2048theexponentshouldatleast615bit.

7.7

p=31,q=37,e=17,y=2

n=31·37=1147d=17 1=953mod1080dp=953≡23mod30dq=953≡17mod36xp=ydp=223≡8mod31xq=ydq=217≡18mod37cp=q 1=37 1≡6 1≡26mod31cq=p 1=31 1≡6mod37x=[qcp]xp+[pcq]xq=

[37·26]8+[31·6]18=

8440=721mod1147

AliceBob

setup:kpr=d;kpub=e

publishe,n

y7.9chooserandomsessionkeyksesemodny=ekpub(kses)=kses

→kses=dkpr(y)=ydmodn

Alicecompletelydeterminesthechoiceofthesessionkeykses.

Notethatinpracticeksesmightbemuchlongerthanneededforasymmmetric-keyalgorithm.Forinstance,ksesmayhave1024bitsbutonly128actualkeybitsareneeded.Inthiscasejustusethe128MSB(orLSB)bitareusedandtheremainingbitarediscarded.Often,itissafepracticetoapplyacryptographichashfunction rsttoksesandthentaketheMSBorLSBbits.

7.11

1.Encryptionequation:y≡xemodn.Wecannotsolvetheequationanalytical,becausetheexponenti-ationtakesplaceina nitering,wherenoef cientalgorithmsforcomputingrootsisknown.

2.

Φ(n)=p·q

No!ThecalculationofΦ(n)presumestheknowledgeofpandq,whichwedonothave.

3.Factorizationyields:p=43andq=61

Φ(n)=42·60=2520

d≡e 1mod2520≡191

x=1088

7.13

1.Amessageconsistsof,let’ssay,mpiecesofciphertexty0,y1,...,ym 1.However,theplaintextspaceisrestrictedto95possiblevaluesandtheciphertextspacetoo.Thatmeansweonlyhavetotest95possibleplaintextcharacterstobuildupatablecontainingallpossibleciphertextcharacters:

?Test:yi=jemodn;j=32,33,...,126

2.SIMPSONS

奇数题号答案

3.WithOAEPpaddingarandomstringseedisusedwitheveryencryption.Sinceseedhasinpracticealengthof128–160bit,thereexistmany,manydifferentciphertextsforagivenplaintext.

7.15

Thebasicideaistorepresenttheexponentinaradix2krepresentation.Thatmeanswegroupkbitsoftheexponenttogether.The rststepofthealgorithmistopre-computealook-uptablewiththevalueskA0=1,A1=A,A2,...,A2 1.Notethattheexponentsofthelook-uptablevaluesrepresentallpossiblebitpatternsoflengthk.Thetablecomputationrequires2k 2multiplications(notethatcomputingA0andA1isforfree).Afterthelook-uptablehasbeencomputed,thetwoelementaryoperationsinthealgorithmarenow:

Shiftintermediateexponentbykpositionstotheleftbyperformingksubsequentsquarings(Recall:Thestandards-a-malgorithmshiftstheexponentonlybyonepositionbyperformingonesquaringperiteration.)Theexponenthasnowktrailingzerosattherightmostbitpositions.Fillintherequiredbitpatternfortheexponentbymultiplyingthecorrespondingvaluefromthelook-uptablewiththeintermediateresult.

Thisiterationisonlyperformedl/ktimes,wherel+1isthebitlengthoftheexponent.Hence,thereareonlyl/kmultiplicationsbeingperformedinthispartofthealgorithm.

Anexactdescriptionofthealgorithm,whichisoftenreferredtoask-aryexponentiation,isgivenin

[120].Notethatthebitlengthoftheexponentinthisdescriptionistkbit.Anexampleforthecasek=3isgivenbelow.

Thecomplexityofthealgorithmforanl+1bitexponentis2k 3multiplicationsintheprecompu-tationphase,andaboutl 1squaringsandl(2k 1)/2kmultiplicationsinthemainloop.

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:

Iteration

10000

1b

10010000

2bA:=A·g1=1680mod163=50A:=A·g2=6768mod163=853SQCalculationA:=g2=1443SQ

奇数题号答案

a

ord(a)

123456

136362

3.Z 13:

a

ord(a)

奇数题号答案

OscarsharesnowasecretkeywithAliceandBob.AliceandBobbothdon’tknowaboutitandthinktheyshareakeywitheachother.Oscarcannowdecrypt,read,andencryptanymessagesbetweenAliceandBobwithoutthemlearningaboutitifhecontinuestointerceptallencryptedmessages.

Thisistheinfamousman-in-the-middleattack.Thisattackis,inessence,responsibleforthingssuchascerti cates,public-keyinfrastructures,etc.

8.13

Computeβ:β=αdmodp.

Encrypt:(kE,y)=(αimodp,x·βimodp).d) 1modp.Decrypt:x=y(kE

1.

2.

3.

4.(kE,y)=(29,296),x=33(kE,y)=(125,301),x=33(kE,y)=(80,174),x=248

(kE,y)=(320,139),x=248

CausedbythepreviouslymentionedPRNG,beginningwithkM,n 1,kM,j 1caneasilycalculatedrecur-sivleythrough

kM,j 1=βij 1=βij f(j)=βij·β f(j)=kM,j 1·β f(j)modp8.15Oscarknowsxn,ynandn(byjustcountingthenumberofciphertexts).The rststepofapossibleattackistocalculate1kM,n=yn·x (13.3)nmodp.(13.4)

wherethevaluesofallvariablesareknown.WiththeknowledgeofkM,jforallj,Oscarisnowabletodecryptthewholeciphertextbysolvingtheusualdecryptionequation

1xj=yj·kM,jmodp(13.5)

8.17

1.Bychoosingadifferentsecretexponenti,theciphertextyofthesameplaintextxisdifferentevery-time.Evenifapairofplaintext/ciphertextiscompromised,suchapairwillmostlikelynotrepeatasecondtimeinanon-deterministicencryptionscheme!

2.Ingeneral,thereare#{2,3,···,p 2}=p 3differentvalidciphertextsforasingleplaintext.I.e.,wehave464differentpossibilitiesforp=467.

3.TheplainRSAcryptosystemisdeterministic.Aspeci cplaintextalwaysyieldsthesameciphertextassumingthesamepublicparameters.

ProblemsofChapter9

9.1a=2,b=2

4·23+27·22=4·8+27·4=32+108=140≡4=0mod17√17≈26,25q.e.d.9.317+1 2

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

奇数题号答案

http://www.77cn.com.cnputeallmultiplesofα:

0·α=O

1·α=(0,3)

2·α=(2,3)

3·α=(5,4)

4·α=(4,6)

5·α=(4,1)

6·α=(5,3)

7·α=(2,4)

8·α=(0,4)

9·α=O=0·α

ord(α)=9=#G

9.7

1.9·P=(1001|2)P=(2·(2·(2·P)))+P=(4,10)

2.20·P=(10100|2)P=(2·(2·(2·(2·P)+P)))=(19,13)

9.9

K=aB=6·B=2(2B+B)

2B=(x3,y3):x1=x2=5;y1=y2=9 1 1=76·18 1mod11s=(3x21+a)·y1=(3·25+1)(2·9)

s≡10·8=80≡3mod11

x3=s2 x1 x2=32 10= 1≡10mod11y3=s(x1 x3) y1=3(5 10) 9= 15 9= 24≡9mod11

2B=(10,9)

′3B=2B+B=(x′3,y3):x1=10,x2=5,y1=9,y2=9

s=(y2 y1)(x2 x1) 1=0mod11

x′3=0 x1 x2= 15≡7mod11

y′3=s(x1 x3) y1= y1= 9≡2mod11

3B=(7,2)

′′6B=2·3B=(x′′3,y3):x1=x2=7,y1=y2=2

1 1≡5·4 1≡5·3=15≡4mod11s=(3x21+a)·y1=(3·49+1)·422x′′3=s x1 x2=4 14=16 14=2mod11y′′3=s(x1 x3) y1=4(7 2) 2=20 2=18≡7mod11

6B=(2,7) KAB=2 αisprimitivesinceitgeneratesthegroup!

9.11

Abrute-forceattackona128bitkeycurrentlyiscomputitionalinfeasible!

Inthiscontext,amuchmoreef cientattackistomakeuseofthecorrelationbetweenthex andy coordinateofapoint.SinceitisknownthatthereisaninverseforeverypointP=(x,y)with P=(x, y),itwouldbetheeasiestapproachtotestall264possiblex coordinatesbysolvingthecurveequation.Theeffectivekeylengthisthenreducedto65bit,whichmaybeinsuf cientinafewyears(ifthisproblemhasnotalreadybeenbrokenbywell-fundedintelligenceservices).

ProblemsofChapter10

10.1

本文来源：https://www.bwwdw.com/article/xo1i.html