网络安全导论 课件 第六章 密码学与网络安全

第6章

密码学与网络安全6主要内容1.密码学与安全服务2.密码体制的安全性3.古典密码的基本思想4.对称密码与公钥密码体制5.信息隐藏与数字水印1.密码学的基本概念及其在信息安全中的作用openchannelShannon‘sModelofaSecrecySystem

SymmetricorSecret-KeyCryptosystemsSamekeyusedforencryptionanddecryptionKeymustbekeptabsolutelysecretSamekeycanbeusedforseveralmessages,butshouldbechangedperiodically

securekeydistributionproblem!

EncryptionEK(P)=CplaintextP

DecryptionDK(C)=PciphertextplaintextPCkey

Kkey

Kdistributionofsecret-keyoversecurechannel明文：发送方将要发送的消息。密文：明文被变换成看似无意义的随机消息加密：上述变换过程；解密：上述变换过程逆过程，即由密文恢复出原明文的过程称为。加密算法：密码员对明文进行加密时所采用的一组规则。概念解密算法：接收者对密文解密时所采用的一组规则。密钥：加解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。单钥或对称密码体制：传统密码体制所用的加密密钥和解密密钥相同，或实质上等同，即从一个易于得出另一个。双钥或非对称密码体制：若加密密钥和解密密钥不相同，从一个难于推出另一个。密钥是密码体制安全保密的关键，它的产生和管理是密码学中的重要研究课题。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!信息论计算复杂性理论现代密码体制中对安全的定义一般基于两种方法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单向函数单向函数对于x

X,函数值f(x)容易计算已知f(x)=y，求相应的x

X在计算上不可行陷门单向函数给出陷门信息，可以求得满足f(x)=y的x

X例：离散对数可认为离散对数的计算是单项的y=gxmodp给定

g,x,p,计算

y容易给定

g,y,p,计算

x(离散对数)困难与分解大整数类似(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对称密钥密码体制优点加密速度快密钥相对短（64、128或156比特）易于硬件或其他机械装置实现缺点初始化困难需要用户双方保守秘密n个用户需要管理O(n2)密钥更新周期短对称密码体制Sharingsecretkeys初始化比较困难：在加密消息之前需要通过安全信道或直接联系A与B通信完成后，要与C通信，需要重新生成对称密钥彼此双方需要绝对信任，A与B通信那么A要相信B不会把密钥脚给C。DESTripleDES、RC5、RC6、AES在通信之前需要双方协商共享密钥Fig.公钥加密技术加密明文密文明文解密公钥私钥公钥密码学的历史（一）76年Diffie和Hellman发表了“密码学的新方向”，奠定了公钥密码学的基础公钥技术是二十世纪最伟大的思想之一改变了密钥分发的方式可以广泛用于数字签名和身份认证服务78年，RSA算法公钥密码学的历史（二）McEliece,1978,基于代数编码Rabin,1979,等价于大整数分解ElGamal,1985,基于离散对数Ellipticcurves,1985,基于椭圆曲线点的离散对数NTRU,1996,基于格问题LUC