網(wǎng)絡(luò)安全導(dǎo)論 課件 第六章 密碼學(xué)與網(wǎng)絡(luò)安全

第6章

密碼學(xué)與網(wǎng)絡(luò)安全6主要內(nèi)容1.密碼學(xué)與安全服務(wù)2.密碼體制的安全性3.古典密碼的基本思想4.對稱密碼與公鑰密碼體制5.信息隱藏與數(shù)字水印1.密碼學(xué)的基本概念及其在信息安全中的作用openchannelShannon‘sModelofaSecrecySystem

SymmetricorSecret-KeyCryptosystemsSamekeyusedforencryptionanddecryptionKeymustbekeptabsolutelysecretSamekeycanbeusedforseveralmessages,butshouldbechangedperiodically

securekeydistributionproblem!

EncryptionEK(P)=CplaintextP

DecryptionDK(C)=PciphertextplaintextPCkey

Kkey

Kdistributionofsecret-keyoversecurechannel明文：發(fā)送方將要發(fā)送的消息。密文：明文被變換成看似無意義的隨機(jī)消息加密：上述變換過程；解密：上述變換過程逆過程，即由密文恢復(fù)出原明文的過程稱為。加密算法：密碼員對明文進(jìn)行加密時所采用的一組規(guī)則。概念解密算法：接收者對密文解密時所采用的一組規(guī)則。密鑰：加解密算法的操作通常都是在一組密鑰控制下進(jìn)行的，分別稱為加密密鑰和解密密鑰。單鑰或?qū)ΨQ密碼體制：傳統(tǒng)密碼體制所用的加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個易于得出另一個。雙鑰或非對稱密碼體制：若加密密鑰和解密密鑰不相同，從一個難于推出另一個。密鑰是密碼體制安全保密的關(guān)鍵，它的產(chǎn)生和管理是密碼學(xué)中的重要研究課題。ClaudeShannon1916-2001

TheFatherofInformationTheoryInformationTheoryWorkedatMIT/BellLabs?TheMathematicalTheoryofCommunication“(1948)MaximumcapacityofanoisytransmissionchannelDefinitionofthe?binarydigit“(bit)asaunitofinformationDefinitionof?entropy“asameasureofinformationCryptographyModelofasecrecysystemDefinitionofperfectsecrecyBasicprinciplesof?confusion“and?diffusion“Cryptography

Cryptography

?Artandscienceof

keepingmessagessecure“

Cryptology

Cryptanalysis

?Artandscienceof

breakingciphertext“cryptographyCryptographyisthestudyofmathematicaltechniquesrelatedtoaspectsofinformationsecurityCryptographicgoalsConfidentialityDataintegrityAuthenticationNon-repudiation密碼學(xué)的一般研究內(nèi)容ArbitrarylengthhashfunctionsOne-waypermutationsRandomsequencesSymmetric-keyciphersArbitrarylengthhashfunctions(MACs)SignaturesPseudorandomsequencesIdentificationprimitivesPublic-keyciphersSignaturesIdentificationprimitivesUnkeyedPrimitivesSymmetric-keyPrimitivesPublic-keyPrimitivesSecurityPrimitivesBlockciphersStreamciphersCryptographicalBuildingBlocksBlock

CiphersStream

CiphersSymmetricKey

CryptographyAuthenticationPrivacyEncryptionHash

FunctionsChallenge

ResponseIVsMACs

MICsMessage

DigestsNoncesPseudo

RandomRandom

SourcesSecretKeysSmart

CardsDH

RSAPublicKey

CryptographyElliptic

CurvesDigitalSignaturesData

IntegritySecureNetworkProtocolsNon-RepudiationSecureNetworkProtocolsfortheOSIStackApplicationlayerssh,S/MIME,PGP,KerberosTransportlayerSSL,TLS,WTLSNetworklayerIPsecDataLinklayerCHAP,PPTP,L2TP,WEP(WLAN)PhysicallayerFrequencyHopping,

QuantumCryptographyCommunicationlayersSecurityprotocols2密碼體制的安全性HowtoconstructaSecureCipher?WorldWarIIGermanEnigmaMachineThomasJefferson‘sCipherWheel1010011101...Cryptanalysis-FundamentalAssumptionsAttackerknowseverydetailofthecryptographicalalgorithmAttackerisinpossessionofencryption/decryptionequipmentAttackerhasaccesstoanarbitrarynumberofplaintext/ciphertextpairsgeneratedwiththesame(unknown)key.Strongcipher:Bestattackshouldbebruteforcekeysearch!Thesecurityofaciphershouldrelyonthesecrecyofthekeyonly!AugusteKerckhoffs,?LaCryptographiemilitaire“,1883Cryptanalysis-TypesofAttacksCiphertext-OnlyAttackAttackerknowsciphertextofseveralmessagesencryptedwiththesamekeyand/orseveralkeysRecovertheplaintextofasmanymessagesaspossibleorevenbetterdeducethekey(orkeys)Known-PlaintextAttackKnownciphertext/plaintextpairofseveralmessagesDeducethekeyoranalgorithmtodecryptfurthermessagesChosen-PlaintextAttackAttackercanchoosetheplaintextthatgetsencryptedtherebypotentiallygettingmoreinformationaboutthekeyAdaptiveChosen-PlaintextAttackAttackercanchooseaseriesofplaintexts,basingthechoiceontheresultofpreviousencryption

differentialcryptanalysis!信息論計算復(fù)雜性理論現(xiàn)代密碼體制中對安全的定義一般基于兩種方法Information-theoreticsecurity:

absoluteuncomputability:ciphertextandplaintextarecompletelyindependent

fewmethodshavethisproperty

essence:keyandmessagehavethesamelength信息論方法Shannon‘sDefinitionofPerfectSecrecy

TheOne-TimePadmbitsofplaintextPwithentropyH(P)CompressionAlgorithmC(P)=Z

H(P)

k

mbitsof

compressedplaintextZkbitsofciphertextCOne-TimePadkbitsofrandomkeyK100110101001110110111101000111userandomkeysequenceonlyonceandthendiscardit!計算復(fù)雜性方法Complexity-theoreticsecurity(ourfocus):

conditionalintractabilityduetoourlimitation:cypher-textandplaintextarerelated

extensivelyresearchedandwidelyapplied

essence:two“grandassumptions"Duetolimitationsinourcomputationalability,intractabilitiesformoderncryptographyarebasedontwo“grandassumptions"

Computational:Thereareone-wayfunctionswhichcannotbeinvertedusingourcomputers

Decisional:Therearefunctionstogeneratepseudo-randomnumberswhichareindistinguishablefromtruerandomnumbersusingourcomputersTwo“GrandAssumptions"forComplexity-theoreticbasedSecurity單向函數(shù)單向函數(shù)對于x

X,函數(shù)值f(x)容易計算已知f(x)=y，求相應(yīng)的x

X在計算上不可行陷門單向函數(shù)給出陷門信息，可以求得滿足f(x)=y的x

X例：離散對數(shù)可認(rèn)為離散對數(shù)的計算是單項的y=gxmodp給定

g,x,p,計算

y容易給定

g,y,p,計算

x(離散對數(shù))困難與分解大整數(shù)類似(RSA)時間復(fù)雜度:O(e((lnp)1/3ln(lnp))2/3)3古典密碼的基本思想Shannon‘sPrincipleConfusionDiffusion

ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABCSubstitutionTable-Caesar‘sCipherShannon‘sPrincipleofConfusion

CaesarMonoalphabeticSubstitutionCipherMESSAGEFROMMARYSTUARTKILLTHEQUEENPHVVDJHIURPPDUBVWXDUWNLOOWKHTXHHQPHVVDJPHVVDPHVVPHPkey=3cyclicshiftsABCDEFGHIJKLMNOPQRSTUVWXYZEYUOBMDXVTHIJPRCNAKQLSGZFWGeneralSubstitutionTable26!possiblekeysJBKKEDBMARJJEAFKQLEAQHVIIQXBNLBBPA

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

ZplaintextalphabetA

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

BD

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

CE

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

DF

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

EG

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

FH

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

GI

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

HJ

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

IK

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

JL

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

KM

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

LN

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

NP

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

OQ

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

PR

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

QS

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

RT

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

SU

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

TV

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

UW

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

VX

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

WY

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

XZ

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

YHITWShannon‘sPrincipleofConfusion

VigenèrePolyalphabeticSubstitutionCipherEMESSAGEFROM...Keyword:WHITEMESSAGEFROM...WHITEWHITEWILALECLNKSIMESSAGEFROM...WHITEWHITEWMESSAGEFROM...WHITEWHITEWIMESSAGEFROM...WHITEWHITEWILMESSAGEFROM...WHITEWHITEWILAMESSAGEFROM...WHITEWHITEWILALMESSAGEFROM...WHITEWHITEWILALEMESSAGEFROM...WHITEWHITEWILALECMESSAGEFROM...WHITEWHITEWILALECLMESSAGEFROM...WHITEWHITEWILALECLNMESSAGEFROM...WHITEWHITEWILALECLNKMESSAGEFROM...WHITEWHITEWILALECLNKSVigenèresquare491753286Extendedkey:

orderofcolumns9!=362‘880keysShannon‘sPrincipleofDiffusion

TranspositionCipherMESSAGEFROMMARYSTUARTKILLTHEQUEENMESSAGE

FROM

MARY

STUART

THE

KILL

QUEENPlaintextinCiphertextoutMOAEEMRQMOAEMOAEEMRQSMTUMOAEEMRQSMTUSAKEMOAEEMRQSMTUSAKEARIE

RUHMOAEEMRQSMTUSAKEARIEGYLNMOAEEMRQSMTUSAKEARIEGYLNESL

FTTDiffusionmeanspermutationofbitorbytepositions!123456789Key=9columnsSMTUESLGYLNMOAEARIERUHSAKEFTTEMRQMostCryptoanalyticAttacksbaseonthe

RedundancyofNaturalLanguageTextsE26T18A16O16N14I13R13S12H12highfrequencygroupD8L7U6C6M6mediumfrequencygroupP4F4Y4W3G3B3V2lowfrequencygroupJ1K1X1?QZ?raregroupFrequencytableof200EnglishlettersGeorgesPerec,?Ladisparition“,1969

Bookof280pageswithoutasinglelettere

...AntonVoyln'arrivaitpasàdormir.Ilalluma.SonJazmarquaitminuitvingt.Ilpoussaunprofondsoupir,s'assitdanssonlit,s'appuyantsursonpolochon.

Ilpritunroman,ill'ouvrit,illut;maisiln'ysaisitqu'unimbroglioconfus,

ilbutaitàtoutinstantsurunmotdontilignoraitlasignification.Ilabandonnasonromansursonlit.Ilallaàsonlavabo;ilmouillaungantqu'ilpassasursonfront,sursoncou.Sonpoulsbattaittropfort.Ilavaitchaud...Excerptfrom?Ladisparition“?EditionsDen?el2024/5/31EntropyoftheEnglishLanguageSinglecharacterstatisticsEntropyH=4bits/characterWrittenEnglishtakingintoaccountthefullcontextShannon(1950): EntropyH=0.6...1.3bits/characterSimulations(1999): EntropyH=1.1bits/characterWhatabouttheentropyofCsourcecode?

for(c=0;c<256;c++){

i2=(key_data_ptr[i1]+state[c]+i2)%256;

swap_byte(&state[c],&state[i2]);

i1=(i1+1)%key_data_len;

}CompressionbeforeencryptionincreasessecurityGooddatacompressionalgorithms(e.g.Lempel-Ziv)

removeallredundancyandcomeveryclosetotheentropyoftheplaintext.

4.對稱密碼與公鑰密碼體制

對稱加密技術(shù)加密明文密文明文解密對稱密鑰SymmetricKeyCryptosystems

StreamCiphersPseudo-RandomSequenceGeneratorPlaintextBitstreamCiphertextBitstreamKey11111111000000…10011010110100…01100101110100…PlaintextStreamPseudo-RandomStreamCiphertextStreamStreamCiphers

LinearFeedbackShiftRegisters(LFSRs)Maximumpossiblesequencelengthis2n-1withnregistersLFSRsareoftenusedasbuildingblocksforstreamciphersGSMA5isacipherwith3LFSRsoflengths19,22,and23Key11010LoadKeyR0R1R2Rn-2Rn-1SymmetricKeyCryptosystems

BlockCiphersciphertextblocksnbitsnbitsplaintextblocksnbitsnbitsCommonBlockSizes:

n=64,128,256bitsCommonKeySizes:

k=40,56,

64,80,128,

168,192,256bitskbitsKeyBlockCiphernbitsBlockCipherModes

ElectronicCodeBookMode(ECB)P1P2P3C1EDP1C1EC3C3DP3SenderReceiverEC2DP2C2SomePopularBlockCiphersBlockSizeNameofAlgorithmKeySizeDES(DataEncryptionStandard,IBM)64563DES(TripleDES)64168IDEA(Lai/Massey,ETHZürich)64128RC2(RonRivest,RSA)6440...1024CAST(Canada)64128Blowfish(BruceSchneier)64128...448Skipjack(NSA,clipperchip,wasclassified)6480RC5(RonRivest,RSA)64...25664...256DataEncryptionStandard(DES)

RoundsofConfusionandDiffusionInitialPermutationStripParity(56bits)Key(64bits)Round1Round2Round16ReversePermutationPlaintextBlock(64bits)CiphertextBlock(64bits)OneRoundofDESExpansionPermutation48P-BoxPermutationS-BoxSubstitution32ShiftShift48Compression

PermutationFeistelNetwork563232Keyi-1Ri-1Li-1KeyiRiLi323256對稱密鑰密碼體制優(yōu)點加密速度快密鑰相對短（64、128或156比特）易于硬件或其他機(jī)械裝置實現(xiàn)缺點初始化困難需要用戶雙方保守秘密n個用戶需要管理O(n2)密鑰更新周期短對稱密碼體制Sharingsecretkeys初始化比較困難：在加密消息之前需要通過安全信道或直接聯(lián)系A(chǔ)與B通信完成后，要與C通信，需要重新生成對稱密鑰彼此雙方需要絕對信任，A與B通信那么A要相信B不會把密鑰腳給C。DESTripleDES、RC5、RC6、AES在通信之前需要雙方協(xié)商共享密鑰Fig.公鑰加密技術(shù)加密明文密文明文解密公鑰私鑰公鑰密碼學(xué)的歷史（一）76年Diffie和Hellman發(fā)表了“密碼學(xué)的新方向”，奠定了公鑰密碼學(xué)的基礎(chǔ)公鑰技術(shù)是二十世紀(jì)最偉大的思想之一改變了密鑰分發(fā)的方式可以廣泛用于數(shù)字簽名和身份認(rèn)證服務(wù)78年，RSA算法公鑰密碼學(xué)的歷史（二）McEliece,1978,基于代數(shù)編碼Rabin,1979,等價于大整數(shù)分解ElGamal,1985,基于離散對數(shù)Ellipticcurves,1985,基于橢圓曲線點的離散對數(shù)NTRU,1996,基于格問題LUC