網(wǎng)絡安全導論 課件 第六章 密碼學與網(wǎng)絡安全

第6章

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

SymmetricorSecret-KeyCryptosystemsSamekeyusedforencryptionanddecryptionKeymustbekeptabsolutelysecretSamekeycanbeusedforseveralmessages,butshouldbechangedperiodically

securekeydistributionproblem!

EncryptionEK(P)=CplaintextP

DecryptionDK(C)=PciphertextplaintextPCkey

Kkey

Kdistributionofsecret-keyoversecurechannel明文：發(fā)送方將要發(fā)送的消息。密文：明文被變換成看似無意義的隨機消息加密：上述變換過程；解密：上述變換過程逆過程，即由密文恢復出原明文的過程稱為。加密算法：密碼員對明文進行加密時所采用的一組規(guī)則。概念解密算法：接收者對密文解密時所采用的一組規(guī)則。密鑰：加解密算法的操作通常都是在一組密鑰控制下進行的，分別稱為加密密鑰和解密密鑰。單鑰或對稱密碼體制：傳統(tǒng)密碼體制所用的加密密鑰和解密密鑰相同，或實質上等同，即從一個易于得出另一個。雙鑰或非對稱密碼體制：若加密密鑰和解密密鑰不相同，從一個難于推出另一個。密鑰是密碼體制安全保密的關鍵，它的產生和管理是密碼學中的重要研究課題。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密碼學的一般研究內容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!信息論計算復雜性理論現(xiàn)代密碼體制中對安全的定義一般基于兩種方法Information-theoreticsecurity:

absoluteuncomputability:ciphertextandplaintextarecompletelyindependent

fewmethodshavethisproperty

essence:keyandmessagehavethesamelength信息論方法Shannon‘sDefinitionofPerfectSecrecy

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

H(P)

k

mbitsof

compressedplaintextZkbitsofciphertextCOne-TimePadkbitsofrandomkeyK100110101001110110111101000111userandomkeysequenceonlyonceandthendiscardit!計算復雜性方法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，求相應的x

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

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

g,x,p,計算

y容易給定

g,y,p,計算

x(離散對數(shù))困難與分解大整數(shù)類似(RSA)時間復雜度: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.對稱密碼與公鑰密碼體制

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