深入浅出密码学习题答案(3)

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

奇数题号答案< …… 此处隐藏：4491字，全部文档内容请下载后查看。喜欢就下载吧 ……