密碼編碼學與網(wǎng)絡安全+答案

SolutionsManual

CRYPTOGRAPHYANDNETWORKSECURITY

PrinciplesandPractice

FourthEdition

WilliamStallings

Copyright2006:WilliamStallings

?2006by

CONTACT_Con-475D4AA31\c\s\l

WilliamStallings

Allrightsreserved.Nopartofthisdocumentmaybereproduced,inanyformorbyanymeans,orpostedontheInternet,withoutpermissioninwritingfromtheauthor.

Notice

ThismanualcontainssolutionstoallofthereviewquestionsandhomeworkproblemsinCryptographyandNetworkSecurity,FourthEdition.Ifyouspotanerrorinasolutionorinthewordingofaproblem,Iwouldgreatlyappreciateitifyouwouldforwardtheinformationviaemailtows@.Anerratasheetforthismanual,ifneeded,isavailableat.

W.S.

TABLEOFCONTENTS

Chapter1: Introduction 5

Chapter2: ClassicalEncryptionTechniques 7

Chapter3: BlockCiphersandtheDateEncryptionStandard 13

Chapter4: FiniteFields 21

Chapter5: AdvancedEncryptionStandard 28

Chapter6: MoreonSymmetricCiphers 33

Chapter7: ConfidentialityUsingSymmetricEncryption 38

Chapter8: IntroductiontoNumberTheory 42

Chapter9: Public-KeyCryptographyandRSA 46

Chapter10: KeyManagement;OtherPublic-KeyCryptosystems 55

Chapter11: MessageAuthenticationandHashFunctions 59

Chapter12: HashandMACAlgorithms 62

Chapter13: DigitalSignaturesandAuthenticationProtocols 66

Chapter14: AuthenticationApplications 71

Chapter15: ElectronicMailSecurity 73

Chapter16: IPSecurity 76

Chapter17: WebSecurity 80

Chapter18: Intruders 83

Chapter19: MaliciousSoftware 87

Chapter20: Firewalls 89

Chapter1

Introduction

AnswerstoQuestions

TheOSISecurityArchitectureisaframeworkthatprovidesasystematicwayofdefiningtherequirementsforsecurityandcharacterizingtheapproachestosatisfyingthoserequirements.Thedocumentdefinessecurityattacks,mechanisms,andservices,andtherelationshipsamongthesecategories.

1.2 Passiveattackshavetodowitheavesdroppingon,ormonitoring,transmissions.Electronicmail,filetransfers,andclient/serverexchangesareexamplesoftransmissionsthatcanbemonitored.Activeattacksincludethemodificationoftransmitteddataandattemptstogainunauthorizedaccesstocomputersystems.

1.3 Passiveattacks:releaseofmessagecontentsandtrafficanalysis.Activeattacks:masquerade,replay,modificationofmessages,anddenialofservice.

1.4 Authentication:Theassurancethatthecommunicatingentityistheonethatitclaimstobe.

Accesscontrol:Thepreventionofunauthorizeduseofaresource(i.e.,thisservicecontrolswhocanhaveaccesstoaresource,underwhatconditionsaccesscanoccur,andwhatthoseaccessingtheresourceareallowedtodo).

Dataconfidentiality:Theprotectionofdatafromunauthorizeddisclosure.

Dataintegrity:Theassurancethatdatareceivedareexactlyassentbyanauthorizedentity(i.e.,containnomodification,insertion,deletion,orreplay).

Nonrepudiation:Providesprotectionagainstdenialbyoneoftheentitiesinvolvedinacommunicationofhavingparticipatedinallorpartofthecommunication.

Availabilityservice:Thepropertyofasystemorasystemresourcebeingaccessibleandusableupondemandbyanauthorizedsystementity,accordingtoperformancespecificationsforthesystem(i.e.,asystemisavailableifitprovidesservicesaccordingtothesystemdesignwheneverusersrequestthem).

1.5 SeeTable1.3.

AnswerstoProblems

Releaseofmessagecontents

Trafficanalysis

Masquerade

Replay

Modificationofmessages

Denialofservice

Peerentityauthentication

Y

Dataoriginauthentication

Y

Accesscontrol

Y

Confidentiality

Y

Trafficflowconfidentiality

Y

Dataintegrity

Y

Y

Non-repudiation

Y

Availability

Y

Releaseofmessagecontents

Trafficanalysis

Masquerade

Replay

Modificationofmessages

Denialofservice

Encipherment

Y

Digitalsignature

Y

Y

Y

Accesscontrol

Y

Y

Y

Y

Y

Dataintegrity

Y

Y

Authenticationexchange

Y

Y

Y

Y

Trafficpadding

Y

Routingcontrol

Y

Y

Y

Notarization

Y

Y

Y

Chapter2

ClassicalEncryptionTechniquesr

AnswerstoQuestions

2.1 Plaintext,encryptionalgorithm,secretkey,ciphertext,decryptionalgorithm.

2.2 Permutationandsubstitution.

2.3 Onekeyforsymmetricciphers,twokeysforasymmetricciphers.

2.4 Astreamcipherisonethatencryptsadigitaldatastreamonebitoronebyteatatime.Ablockcipherisoneinwhichablockofplaintextistreatedasawholeandusedtoproduceaciphertextblockofequallength.

2.5 Cryptanalysisandbruteforce.

2.6 Ciphertextonly.Onepossibleattackunderthesecircumstancesisthebrute-forceapproachoftryingallpossiblekeys.Ifthekeyspaceisverylarge,thisbecomesimpractical.Thus,theopponentmustrelyonananalysisoftheciphertextitself,generallyapplyingvariousstatisticalteststoit.Knownplaintext.Theanalystmaybeabletocaptureoneormoreplaintextmessagesaswellastheirencryptions.Withthisknowledge,theanalystmaybeabletodeducethekeyonthebasisofthewayinwhichtheknownplaintextistransformed.Chosenplaintext.Iftheanalystisabletochoosethemessagestoencrypt,theanalystmaydeliberatelypickpatternsthatcanbeexpectedtorevealthestructureofthekey.

2.7 Anencryptionschemeisunconditionallysecureiftheciphertextgeneratedbytheschemedoesnotcontainenoughinformationtodetermineuniquelythecorrespondingplaintext,nomatterhowmuchciphertextisavailable.Anencryptionschemeissaidtobecomputationallysecureif:(1)thecostofbreakingthecipherexceedsthevalueoftheencryptedinformation,and(2)thetimerequiredtobreakthecipherexceedstheusefullifetimeoftheinformation.

2.8 TheCaesarcipherinvolvesreplacingeachletterofthealphabetwiththeletterstandingkplacesfurtherdownthealphabet,forkintherange1through25.

2.9 Amonoalphabeticsubstitutionciphermapsaplaintextalphabettoaciphertextalphabet,sothateachletteroftheplaintextalphabetmapstoasingleuniqueletteroftheciphertextalphabet.

2.10 ThePlayfairalgorithmisbasedontheuseofa55matrixoflettersconstructedusingakeyword.Plaintextisencryptedtwolettersatatimeusingthismatrix.

2.11 Apolyalphabeticsubstitutioncipherusesaseparatemonoalphabeticsubstitutioncipherforeachsuccessiveletterofplaintext,dependingonakey.

2.12 1.Thereisthepracticalproblemofmakinglargequantitiesofrandomkeys.Anyheavilyusedsystemmightrequiremillionsofrandomcharactersonaregularbasis.Supplyingtrulyrandomcharactersinthisvolumeisasignificanttask.

2.Evenmoredauntingistheproblemofkeydistributionandprotection.Foreverymessagetobesent,akeyofequallengthisneededbybothsenderandreceiver.Thus,amammothkeydistributionproblemexists.

2.13 Atranspositioncipherinvolvesapermutationoftheplaintextletters.

2.14 Steganographyinvolvesconcealingtheexistenceofamessage.

AnswerstoProblems

2.1 a. No.Achangeinthevalueofbshiftstherelationshipbetweenplaintextlettersandciphertextletterstotheleftorrightuniformly,sothatifthemappingisone-to-oneitremainsone-to-one.

b. 2,4,6,8,10,12,13,14,16,18,20,22,24.Anyvalueofalargerthan25isequivalenttoamod26.

c. Thevaluesofaand26musthavenocommonpositiveintegerfactorotherthan1.Thisisequivalenttosayingthataand26arerelativelyprime,orthatthegreatestcommondivisorofaand26is1.Toseethis,firstnotethatE(a,p)=E(a,q)(0≤p≤q<26)ifandonlyifa(p–q)isdivisibleby26.1.Supposethataand26arerelativelyprime.Then,a(p–q)isnotdivisibleby26,becausethereisnowaytoreducethefractiona/26and(p–q)islessthan26.2.Supposethataand26haveacommonfactork>1.ThenE(a,p)=E(a,q),ifq=p+m/k≠p.

2.2 Thereare12allowablevaluesofa(1,3,5,7,9,11,15,17,19,21,23,25).Thereare26allowablevaluesofb,from0through25).ThusthetotalnumberofdistinctaffineCaesarciphersis1226=312.

2.3 Assumethatthemostfrequentplaintextletteriseandthesecondmostfrequentletterist.Notethatthenumericalvaluesaree=4;B=1;t=19;U=20.Thenwehavethefollowingequations:

1=(4a+b)mod26

20=(19a+b)mod26

Thus,19=15amod26.Bytrialanderror,wesolve:a=3.

Then1=(12+b)mod26.Byobservation,b=15.

AgoodglassintheBishop'shostelintheDevil'sseat—twenty-onedegreesandthirteenminutes—northeastandbynorth—mainbranchseventhlimbeastside—shootfromthelefteyeofthedeath'shead—abeelinefromthetreethroughtheshotfiftyfeetout.(fromTheGoldBug,byEdgarAllanPoe)

a. ThefirstlettertcorrespondstoA,thesecondletterhcorrespondstoB,eisC,sisD,andsoon.Secondandsubsequentoccurrencesofaletterinthekeysentenceareignored.Theresult

ciphertext:SIDKHKDMAFHCRKIABIESHIMCKDLFEAILA

plaintext:basilisktoleviathanblakeiscontact

b. Itisamonalphabeticcipherandsoeasilybreakable.

c. Thelastsentencemaynotcontainallthelettersofthealphabet.Ifthefirstsentenceisused,thesecondandsubsequentsentencesmayalsobeuseduntilall26lettersareencountered.

Thecipherreferstothewordsinthepageofabook.Thefirstentry,534,referstopage534.Thesecondentry,C2,referstocolumntwo.Theremainingnumbersarewordsinthatcolumn.ThenamesDOUGLASandBIRLSTONEaresimplywordsthatdonotappearonthatpage.Elementary!(fromTheValleyofFear,bySirArthurConanDoyle)

2.7 a.

2

8

10

7

9

6

3

1

4

5

C

R

Y

P

T

O

G

A

H

I

B

E

A

T

T

H

E

T

H

I

R

D

P

I

L

L

A

R

F

R

O

M

T

H

E

L

E

F

T

O

U

T

S

I

D

E

T

H

E

L

Y

C

E

U

M

T

H

E

A

T

R

E

T

O

N

I

G

H

T

A

T

S

E

V

E

N

I

F

Y

O

U

A

R

E

D

I

S

T

R

U

S

T

F

U

L

B

R

I

N

G

T

W

O

F

R

I

E

N

D

S

4

2

8

10

5

6

3

7

1

9

N

E

T

W

O

R

K

S

C

U

T

R

F

H

E

H

F

T

I

N

B

R

O

U

Y

R

T

U

S

T

E

A

E

T

H

G

I

S

R

E

H

F

T

E

A

T

Y

R

N

D

I

R

O

L

T

A

O

U

G

S

H

L

L

E

T

I

N

I

B

I

T

I

H

I

U

O

V

E

U

F

E

D

M

T

C

E

S

A

T

W

T

L

E

D

M

N

E

D

L

R

A

P

T

S

E

T

E

R

F

O

ISRNGBUTLFRRAFRLIDLPFTIYONVSEETBEHIHTETA

EYHATTUCMEHRGTAIOENTTUSRUIEADRFOETOLHMET

NTEDSIFWROHUTELEITDS

b. Thetwomatricesareusedinreverseorder.First,theciphertextislaidoutincolumnsinthesecondmatrix,takingintoaccounttheorderdictatedbythesecondmemoryword.Then,thecontentsofthesecondmatrixarereadlefttoright,toptobottomandlaidoutincolumnsinthefirstmatrix,takingintoaccounttheorderdictatedbythefirstmemoryword.Theplaintextisthenreadlefttoright,toptobottom.

c. Althoughthisisaweakmethod,itmayhaveusewithtime-sensitiveinformationandanadversarywithoutimmediateaccesstogoodcryptanalysis(e.g.,tacticaluse).Plusitdoesn'trequireanythingmorethanpaperandpencil,andcanbeeasilyremembered.

2.8 SPUTNIK

2.9 PTBOATONEOWENINELOSTINACTIONINBLACKETTSTRAITTWOMILESSWMERESUCOVEXCREWOFTWELVEXREQUESTANYINFORMATION

2.10 a.

L

A

R

G

E

S

T

B

C

D

F

H

I/J

K

M

N

O

P

Q

U

V

W

X

Y

Z

b.

O

C

U

R

E

N

A

B

D

F

G

H

I/J

K

L

M

P

Q

S

T

V

W

X

Y

Z

2.11 a. UZTBDLGZPNNWLGTGTUEROVLDBDUHFPERHWQSRZ

b. UZTBDLGZPNNWLGTGTUEROVLDBDUHFPERHWQSRZ

c. Acyclicrotationofrowsand/orcolumnsleadstoequivalentsubstitutions.Inthiscase,thematrixforpartaofthisproblemisobtainedfromthematrixofProblem,byrotatingthecolumnsbyonestepandtherowsbythreesteps.

2.12 a. 25!284

b. Givenany5x5configuration,anyofthefourrowrotationsisequivalent,foratotaloffiveequivalentconfigurations.Foreachofthesefiveconfigurations,anyofthefourcolumnrotationsisequivalent.Soeachconfigurationinfactrepresents25equivalentconfigurations.Thus,thetotalnumberofuniquekeysis25!/25=24!

2.13 AmixedCaesarcipher.Theamountofshiftisdeterminedbythekeyword,whichdeterminestheplacementoflettersinthematrix.

2.14 a. Difficultiesarethingsthatshowwhatmenare.

b. Irrationallyheldtruthsmaybemoreharmfulthanreasonederrors.

2.15 a. Weneedanevennumberofletters,soappenda"q"totheendofthemessage.Thenconvertthelettersintothecorrespondingalphabeticpositions:

M

e

e

t

m

e

a

t

t

h

e

u

s

u

a

l

13

5

5

20

13

5

1

20

20

8

5

21

19

21

1

12

P

l

a

c

e

a

t

t

e

n

r

a

t

h

e

r

16

12

1

3

5

1

20

20

5

14

18

1

20

8

5

18

T

h

a

n

e

i

g

h

t

o

c

l

o

c

k

q

20

8

1

14

5

9

7

8

20

15

3

12

15

3

11

17

Thecalculationsproceedtwolettersatatime.Thefirstpair:

Thefirsttwociphertextcharactersarealphabeticpositions7and22,whichcorrespondtoGV.Thecompleteciphertext:

GVUIGVKODZYPUHEKJHUZWFZFWSJSDZMUDZMYCJQMFWWUQRKR

b. Wefirstperformamatrixinversion.Notethatthedeterminateoftheencryptionmatrixis(97)–(45)=43.Usingthematrixinversionformulafromthebook:

Hereweusedthefactthat(43)–1=23inZ26.Oncetheinversematrixhasbeendetermined,decryptioncanproceed.Source:[LEWA00].

ConsiderthematrixKwithelementskijtoconsistofthesetofcolumnvectorsKj,where:

and

Theciphertextofthefollowingchosenplaintextn-gramsrevealsthecolumnsofK:

(B,A,A,…,A,A)K1

(A,B,A,…,A,A)K2

(A,A,A,…,A,B)Kn

2.17 a. 7134

b. 7134

c. 134

d. 10134

e. 24132

f. 24 (132–1)13

g. 37648

h. 23530

i. 157248

2.18 key: legleglegle

plaintext: explanation

ciphertext: PBVWETLXOZR

2.19 a.

s

e

n

d

m

o

r

e

m

o

n

e

y

18

4

13

3

12

14

17

4

12

14

13

4

24

9

0

1

7

23

15

21

14

11

11

2

8

9

1

4

14

10

9

3

12

18

23

25

15

12

7

B

E

C

K

J

D

M

S

X

Z

P

M

H

b.

c

a

s

h

n

o

t

n

e

e

d

e

d

2

0

18

7

13

14

19

13

4

4

3

4

3

25

4

22

3

22

15

19

5

19

21

12

8

4

1

4

14

10

9

3

12

18

23

25

15

12

7

B

E

C

K

J

D

M

S

X

Z

P

M

H

yourpackagereadyFriday21stroomthreePleasedestroythisimmediately.

2.21 a. Laythemessageoutinamatrix8lettersacross.Eachintegerinthekeytellsyouwhichlettertochooseinthecorrespondingrow.Result:

Hesittethbetweenthecherubims.Theislesmaybegladthereof.Astheriversinthesouth.

b. Quitesecure.Ineachrowthereisoneofeightpossibilities.Soiftheciphertextis8nlettersinlength,thenthenumberofpossibleplaintextsis8n.

c. Notverysecure.LordPeterfigureditout.(fromTheNineTailors)

Chapter3

BlockCiphersandtheDataEncryptionStandard

AnswerstoQuestions

3.1 MostsymmetricblockencryptionalgorithmsincurrentusearebasedontheFeistelblockcipherstructure.Therefore,astudyoftheFeistelstructurerevealstheprinciplesbehindthesemorerecentciphers.

3.2 Astreamcipherisonethatencryptsadigitaldatastreamonebitoronebyteatatime.Ablockcipherisoneinwhichablockofplaintextistreatedasawholeandusedtoproduceaciphertextblockofequallength.

3.3 Ifasmallblocksize,suchasn=4,isused,thenthesystemisequivalenttoaclassicalsubstitutioncipher.Forsmalln,suchsystemsarevulnerabletoastatisticalanalysisoftheplaintext.Foralargeblocksize,thesizeofthekey,whichisontheorderofn2n,makesthesystemimpractical.

3.4 Inaproductcipher,twoormorebasicciphersareperformedinsequenceinsuchawaythatthefinalresultorproductiscryptographicallystrongerthananyofthecomponentciphers.

3.5 Indiffusion,thestatisticalstructureoftheplaintextisdissipatedintolong-rangestatisticsoftheciphertext.Thisisachievedbyhavingeachplaintextdigitaffectthevalueofmanyciphertextdigits,whichisequivalenttosayingthateachciphertextdigitisaffectedbymanyplaintextdigits.Confusionseekstomaketherelationshipbetweenthestatisticsoftheciphertextandthevalueoftheencryptionkeyascomplexaspossible,againtothwartattemptstodiscoverthekey.Thus,eveniftheattackercangetsomehandleonthestatisticsoftheciphertext,thewayinwhichthekeywasusedtoproducethatciphertextissocomplexastomakeitdifficulttodeducethekey.Thisisachievedbytheuseofacomplexsubstitutionalgorithm.

3.6 Blocksize:Largerblocksizesmeangreatersecurity(allotherthingsbeingequal)butreducedencryption/decryptionspeed.Keysize:Largerkeysizemeansgreatersecuritybutmaydecreaseencryption/decryptionspeed.Numberofrounds:TheessenceoftheFeistelcipheristhatasingleroundoffersinadequatesecuritybutthatmultipleroundsofferincreasingsecurity.Subkeygenerationalgorithm:Greatercomplexityinthisalgorithmshouldleadtogreaterdifficultyofcryptanalysis.Roundfunction:Again,greatercomplexitygenerallymeansgreaterresistancetocryptanalysis.Fastsoftwareencryption/decryption:Inmanycases,encryptionisembeddedinapplicationsorutilityfunctionsinsuchawayastoprecludeahardwareimplementation.Accordingly,thespeedofexecutionofthealgorithmbecomesaconcern.Easeofanalysis:Althoughwewouldliketomakeouralgorithmasdifficultaspossibletocryptanalyze,thereisgreatbenefitinmakingthealgorithmeasytoanalyze.Thatis,ifthealgorithmcanbeconciselyandclearlyexplained,itiseasiertoanalyzethatalgorithmforcryptanalyticvulnerabilitiesandthereforedevelopahigherlevelofassuranceastoitsstrength.

3.7 TheS-boxisasubstitutionfunctionthatintroducesnonlinearityandaddstothecomplexityofthetransformation.

3.8 Theavalancheeffectisapropertyofanyencryptionalgorithmsuchthatasmallchangeineithertheplaintextorthekeyproducesasignificantchangeintheciphertext.

3.9 DifferentialcryptanalysisisatechniqueinwhichchosenplaintextswithparticularXORdifferencepatternsareencrypted.Thedifferencepatternsoftheresultingciphertextprovideinformationthatcanbeusedtodeterminetheencryptionkey.Linearcryptanalysisisbasedonfindinglinearapproximationstodescribethetransformationsperformedinablockcipher.

AnswerstoProblems

3.1 a. Forann-bitblocksizeare2npossibledifferentplaintextblocksand2npossibledifferentciphertextblocks.Forboththeplaintextandciphertext,ifwetreattheblockasanunsignedinteger,thevaluesareintherange0through2n–1.Foramappingtobereversible,eachplaintextblockmustmapintoauniqueciphertextblock.Thus,toenumerateallpossiblereversiblemappings,theblockwithvalue0canmapintoanyoneof2npossibleciphertextblocks.Foranygivenmappingoftheblockwithvalue0,theblockwithvalue1canmapintoanyoneof2n–1possibleciphertextblocks,andsoon.Thus,thetotalnumberofreversiblemappingsis(2n)!.

b. Intheory,thekeylengthcouldbelog2(2n)!bits.Forexample,assigneachmappinganumber,from1through(2n)!andmaintainatablethatshowsthemappingforeachsuchnumber.Then,thekeywouldonlyrequirelog2(2n)!bits,butwewouldalsorequirethishugetable.Amorestraightforwardwaytodefinethekeyistohavethekeyconsistoftheciphertextvalueforeachplaintextblock,listedinsequenceforplaintextblocks0through2n–1.ThisiswhatissuggestedbyTable3.1.Inthiscasethekeysizeisn2nandthehugetableisnotrequired.

3.2 Becauseofthekeyschedule,theroundfunctionsusedinrounds9through16aremirrorimagesoftheroundfunctionsusedinrounds1through8.Fromthisfactweseethatencryptionanddecryptionareidentical.Wearegivenaciphertextc.Letm'=c.Asktheencryptionoracletoencryptm'.Theciphertextreturnedbytheoraclewillbethedecryptionofc.

a. WeneedonlydeterminetheprobabilitythatfortheremainingN–tplaintextsPi,wehaveE[K,Pi]≠E[K',Pi].ButE[K,Pi]=E[K',Pi]foralltheremainingPiwithprobability1–1/(N–t)!.

b. WithoutlossofgeneralitywemayassumetheE[K,Pi]=PisinceEK(?)istakenoverallpermutations.ItthenfollowsthatweseektheprobabilitythatapermutationonN–tobjectshasexactlyt'fixedpoints,whichwouldbetheadditionalt'pointsofagreementbetweenE(K,?)andE(K',?).ButapermutationonN–tobjectswitht'fixedpointsisequaltothenumberofwayst'outofN–tobjectscanbefixed,whiletheremainingN–t–t'arenotfixed.ThenusingProblem3.4wehavethat

Pr(t'additionalfixedpoints) = Pr(nofixedpointsinN–t–t'objects)

=

Weseethatthisreducestothesolutiontopart(a)whent'=N–t.

Letbethesetofpermutationson[0,1,...,2n–1],whichisreferredtoasthesymmetricgroupon2nobjects,andletN=2n.For0≤i≤N,letAibeallmappingsforwhichπ(i)=i.Itfollowsthat|Ai|=(N–1)!and=(N–k)!.Theinclusion-exclusionprinciplestatesthat

Pr(nofixedpointsinπ) =

=

= 1–1+1/2!–1/3!+...+(–1)N1/N!

= e–1+

Thensincee–10.368,wefindthatforevensmallvaluesofN,approximately37%ofpermutationscontainnofixedpoints.

3.6 MainkeyK=111…111(56bits)

RoundkeysK1=K2=…=K16=1111..111(48bits)

CiphertextC=1111…111(64bits)

Inputtothefirstroundofdecryption=

LD0RD0=RE16LE16=IP(C)=1111...111(64bits)

LD0=RD0=1111...111(32bits)

Outputofthefirstroundofdecryption=LD1RD1

LD1=RD0=1111…111(32bits)

Thus,thebitsno.1and16oftheoutputareequalto‘1’.

RD1=LD0F(RD0,K16)

Wearelookingforbitsno.1and16ofRD1(33and48oftheentireoutput).

BasedontheanalysisofthepermutationP,bit1ofF(RD0,K16)comesfromthefourthoutputoftheS-boxS4,andbit16ofF(RD0,K16)comesfromthesecondoutputoftheS-boxS3.ThesebitsareXOR-edwith1’sfromthecorrespondingpositionsofLD0.

InsideofthefunctionF,

E(RD0)≈K16=0000…000(48bits),

andthusinputstoalleightS-boxesareequalto“000000”.

OutputfromtheS-boxS4=“0111”,andthusthefourthoutputisequalto‘1’,

OutputfromtheS-boxS3=“1010”,andthusthesecondoutputisequalto‘0’.

Fromhere,aftertheXOR,thebitno.33ofthefirstroundoutputisequalto‘0’,andthebitno.48isequalto‘1’.

3.7 InthesolutiongivenbelowthefollowinggeneralpropertiesoftheXORfunctionareused:

A1=A'

(AB)'=A'B=AB'

A'B'=AB

WhereA'=thebitwisecomplementofA.

a. F(Rn,Kn+1)=1

Wehave

Ln+1=Rn;Rn+1=LnF(Rn,Kn+1)=Ln1=Ln'

Thus

Ln+2=Rn+1=Ln';Rn+2=Ln+1=Rn'

i.e.,aftereachtworoundsweobtainthebitcomplementoftheoriginalinput,andeveryfourroundsweobtainbacktheoriginalinput:

Ln+4=Ln+2'=Ln;Rn+2=Rn+2'=Rn

Therefore,

L16=L0;R16=R0

AninputtotheinverseinitialpermutationisR16L16.

Therefore,thetransformationcomputedbythemodifiedDEScanberepresentedasfollows:

C=IP–1(SWAP(IP(M))),whereSWAPisapermutationexchangingthepositionoftwohalvesoftheinput:SWAP(A,B)=(B,A).

Thisfunctionislinear(andthusalsoaffine).Actually,thisisapermutation,theproductofthreepermutationsIP,SWAP,andIP–1.Thispermutationishoweverdifferentfromtheidentitypermutation.

b. F(Rn,Kn+1)=Rn'

Wehave

Ln+1=Rn;Rn+1=LnF(Rn,Kn+1)=LnRn'

Ln+2=Rn+1=LnRn'

Rn+2=Ln+1F(Rn+1,Kn+2)=Rn≈(LnRn')'=RnLnRn''=Ln

Ln+3=Rn+2=Ln

Rn+3=Ln+2F(Rn+2,Kn+3)=(Ln≈Rn')Ln'=Rn'1=Rn

i.e.,aftereachthreeroundswecomebacktotheoriginalinput.

L15=L0;R15=R0

and

L16=R0(1)

R16=L0R0'(2)

AninputtotheinverseinitialpermutationisR16L16.

Afunctiondescribedby(1)and(2)isaffine,asbitwisecomplementisaffine,andtheothertransformationsarelinear.

ThetransformationcomputedbythemodifiedDEScanberepresentedasfollows:

C=IP–1(FUN2(IP(M))),whereFUN2(A,B)=(AB',B).

Thisfunctionisaffineasaproductofthreeaffinefunctions.

Inallcasesdecryptionlooksexactlythesameasencryption.

3.8 a. First,passthe64-bitinputthroughPC-1(Table)toproducea56-bitresult.Thenperformaleftcircularshiftseparatelyonthetwo28-bithalves.Finally,passthe56-bitresultthroughPC-2(Table3.4b)toproducethe48-bitK1.:

inbinarynotation: 000010110000001001100111

100110110100100110100101

inhexadecimalnotation: 0B02679B49A5

b. L0,R0arederivedbypassingthe64-plaintextthroughIP(Table):

L0=11001100000000001100110011111111

R0=11110000101010101111000010101010

c. TheEtable(Table)expandsR0to48bits:

E(R0)=01110100001010101010101011110100001010101010101

d. A=011100010001011100110010111000010101110011110000

e. (1110)=(14)= 0(base10) = 0000(base2)

(1000)=(8)= 12(base10) = 1100(base2)

(1110)=(14)= 2(base10) = 0010(base2)

(1001)=(9)= 1(base10) = 0001(base2)

(1100)=(12)= 6(base10) = 0110(base2)

(1010)=(10)= 13(base10) = 1101(base2)

(1001)=(9)= 5(base10) = 0101(base2)

(1000)=(8)= 0(base10) = 0000(base2)

f. B=00001100001000010110110101010000

g. UsingTable3.2d,P(B)=10010010000111000010000010011100

h. R1=01011110000111001110110001100011

i. L1=R0.TheciphertextistheconcatenationofL1andR1.Source:[MEYE82]

ThereasoningfortheFeistelcipher,asshowninFigure3.6appliesinthecaseofDES.WeonlyhavetoshowtheeffectoftheIPandIP–1functions.Forencryption,theinputtothefinalIP–1isRE16||LE16.Theoutputofthatstageistheciphertext.Ondecryption,thefirststepistotaketheciphertextandpassitthroughIP.BecauseIPistheinverseofIP–1,theresultofthisoperationisjustRE16||LE16,whichisequivalenttoLD0||RD0.Then,wefollowthesamereasoningaswiththeFeistelciphertoreachapointwhereLE0=RD16andRE0=LD16.DecryptioniscompletedbypassingLD0||RD0throughIP–1.Again,becauseIPistheinverseofIP–1,passingtheplaintextthroughIPasthefirststepofencryptionyieldsLD0||RD0,thusshowingthatdecryptionistheinverseofencryption.

a. Letusworkthisfromtheinsideout.

T16(L15||R15)=L16||R16

T17(L16||R16)=R16||L16

IP[IP–1(R16||L16)]=R16||L16

TD1(R16||L16)=R15||L15

b. T16(L15||R15)=L16||R16

IP[IP–1(L16||R16)]=L16||R16

TD1(R16||L16)=R16||L16f(R16,K16)

≠L15||R15

PC-1isessentiallythesameasIPwitheveryeighthbiteliminated.Thiswouldenableasimilartypeofimplementation.Beyondthat,theredoesnotappeartobeanyparticularcryptographicsignificance.

3.12

Roundnumber

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Bitsrotated

0

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1

a. Theequalityinthehintcanbeshownbylistingall1-bitpossibilities:

A

B

AB