It計(jì)算機(jī)課件 密碼學(xué)基礎(chǔ)知識(shí)

密碼學(xué)

基礎(chǔ)知識(shí)

夫?qū)W須靜也，才須學(xué)也，

非學(xué)無(wú)以廣才，非志無(wú)以成

學(xué)。

諸葛亮

概述

■密碼學(xué)

密碼編碼學(xué)

密碼分析學(xué)

-作用:

機(jī)密性

鑒別

完整性

抗抵賴

密碼學(xué)文獻(xiàn)的發(fā)展歷程：

■1918年，F(xiàn)riedman《重合指數(shù)及其在密

碼學(xué)中的應(yīng)用》。

■1918年，Heberm的轉(zhuǎn)輪機(jī)

■1949年，Shannon《保密系統(tǒng)的通信理

論》

■1967年，Kahn《破譯者》

■1971年，F(xiàn)eistel的Lucifer

■1975年，Diffie&Hellman提出公開密鑰

密碼學(xué)，《密碼學(xué)的新方向》

■1977年，DES成為聯(lián)邦信息處理標(biāo)準(zhǔn)

■1978年，MIT的RSA算法。

■1985年，日Gamal體制（離散對(duì)數(shù)）；

KoblitzMiller提出橢圓曲線密碼學(xué)

?1995年，Hoffstein,Pipher,Siverman

發(fā)明NTRU密碼

■密碼學(xué)之前，信息安全的保護(hù)主要是通

過(guò)物理和行政手段實(shí)現(xiàn)的。

■密碼學(xué)最早多用于外交情報(bào)和軍事領(lǐng)域。

■現(xiàn)代密碼學(xué)家通常是理論數(shù)學(xué)家。

-第一階段：

手工計(jì)算

-第二階段：

機(jī)械和電動(dòng)機(jī)械

-第三階段：

電子和計(jì)算機(jī)

內(nèi)容

■L保密與保密系統(tǒng)

■2.古典密碼技術(shù)

■3.密碼體制

■4.密碼分析

■5.加密方式

［一、保密與保密系統(tǒng)

保密學(xué)：研究信息系統(tǒng)安全保密的科學(xué)。

L保密系統(tǒng)模型圖

一個(gè)密碼體制由五元組(P,C,K,E,D)

構(gòu)成。

SymmetricCipherModel

Secretke<\shared?Secret?"shinedl)?>

wilderundrvvipivntwilderundrvcipicnl

Iiniisniittcd

tiphertext

llaintcUPluintvxt

EncnptionalgorithmDecryptionulgorithm

inputoutput

II.JJ.,I)l>i(reverseofencnption

alguritlim)

BasicTerminology

■plaintext-theoriginalmessage

■ciphertext-thecodedmessage

■cipher-algorithmfortransformingplaintexttociphertext

■key-infousedincipherknownonlytosender/receiver

■encipher(encrypt)-convertingplaintexttociphertext

■decipher(decrypt)-recoveringciphertextfromplaintext

■cryptography-studyofencryptionprinciples/methods

■cryptanalysis(codebreaking)-thestudyofprinciples/

methodsordecipheringciphertextwithoutKnowingkey

■cryptology-thefieldofbothcryptographyandcryptanalysis

2.密碼設(shè)計(jì)準(zhǔn)則

■保密系統(tǒng)抗擊密碼分析，應(yīng)滿足：

1）系統(tǒng)即使達(dá)不到理論上是不可破的，也應(yīng)

當(dāng)為實(shí)際上是不可破的。

2）Kerckhoff原則。系統(tǒng)的保密性不依賴于對(duì)

加密體制或算法的保密，而依賴于密鑰。

3）加密和解密算法適用于所有密鑰空間中的

元素。

4）系統(tǒng)便于實(shí)現(xiàn)和使用方便。

Kerckhoff六項(xiàng)準(zhǔn)貝ij

在19世紀(jì)對(duì)軍事密碼體制提出六項(xiàng)準(zhǔn)則：

■密碼體制即便不是在理論上不可破，也

應(yīng)該是實(shí)際上不可破的。

■體制的泄露不應(yīng)該給通信者帶來(lái)麻煩。

3,保密系統(tǒng)的通信理論

-明文

■密碼系統(tǒng)的嫡

■惟一解距離UD

Plaintext明文

■Entropy:一條信息的信息量通過(guò)嫡來(lái)度量。

是對(duì)信息或不確定性的數(shù)學(xué)度量，通過(guò)

概率分布的函數(shù)來(lái)計(jì)算。

■語(yǔ)言信息率：r=H(M)/NN相當(dāng)大時(shí)，

標(biāo)準(zhǔn)英語(yǔ)的語(yǔ)言信息率在L0-L5/字母之

間。

■語(yǔ)言絕對(duì)信息率：假定每一個(gè)字符串是

等可能的，對(duì)每個(gè)字母編碼的最大位數(shù)。

■英文R=logL=log26=4.7位/字母

■ThomasCover采用隨機(jī)估算技術(shù)得到的

信息率為1.3位/字符。

■自然語(yǔ)言具有高冗余度。D=R-r=3.4位/

字母。英語(yǔ)語(yǔ)言是75%冗余。Huffman

■一條ASCII消息，每字節(jié)消息含有與英語(yǔ)

相等的L3位的消息，她的冗余信息為6.7

位，相當(dāng)于每位ASCII文本有0.84位冗余

■自然語(yǔ)言的高冗余度為密碼分析提供了

一個(gè)重要工具。

■它最重要也是最基本的特征：?jiǎn)蝹€(gè)字母

出現(xiàn)的頻率。

密碼系統(tǒng)的嫡

■由密鑰空間大小來(lái)衡量

H(K)=logK

一般來(lái)說(shuō)，嫡越大，破譯它越困難。

密鑰：盡量使密鑰源為無(wú)記憶均勻分布源。

■密文的統(tǒng)計(jì)特征由明文和密鑰的統(tǒng)計(jì)特

征完全決定。

■收到的密文越長(zhǎng)，分析者找到密鑰或明

文的可能性越大，為確信分析者可找到

唯一的密鑰，理論上S至少將要多長(zhǎng)。

惟一解距離UD

■在給定足夠的計(jì)算時(shí)間下，分析者能唯

一計(jì)算出密鑰所需密文的平均值。

■惟一解距離UnicityDistance［碼量］:使一

個(gè)具有無(wú)限計(jì)算能力的攻擊者能夠恢復(fù)

惟一的加密密鑰所需要的最小密文量

(字符數(shù))。在達(dá)到惟一解距離時(shí)，密

鑰曖昧度趨近于零。

■臨界值S=H(K)/［loge-H(m)］稱為UD。

UD

■定義為使得偽密鑰的期望值等于零的n的

值。

■當(dāng)密文字符大于UD時(shí)，這種密碼就存在

一個(gè)解，而當(dāng)密文字符小于UD時(shí)，就會(huì)

出現(xiàn)多個(gè)可能的解。

■它利用信息論描述了被截獲的密文量和

成功攻擊的可能性之間的關(guān)系。

UD

■Shannon指出：惟一解距離可以保證當(dāng)

其太小時(shí)，密碼系統(tǒng)是不安全的，但并

不保證當(dāng)其較大時(shí)，密碼系統(tǒng)就是安全

的。惟一解距離不是對(duì)密碼分析需要多

少密文的度量，而是對(duì)存在唯一合理的

密碼分析所需密文數(shù)量的指標(biāo)。

■惟一解距離與冗余度成反比，當(dāng)冗余度

接近于零時(shí)，一個(gè)普通的密碼系統(tǒng)也可

能是木前破的。

UD

■一般而言，惟一解距離越長(zhǎng)，密碼系統(tǒng)

越好。無(wú)窮大時(shí)為理想保密。

密碼分析

■利用自然語(yǔ)言的冗余度來(lái)減少可能的明

文數(shù)目。

■語(yǔ)言的冗余度越大，它就越容易被攻擊。

■最重要也是最基本的特征：?jiǎn)蝹€(gè)字母出

現(xiàn)的頻率。

■一個(gè)好的加密算法是一種混合變換，它

將有意義的小區(qū)域中的有意義的消息相

當(dāng)均勻地分布到在整個(gè)消息空間中。

4,密碼系統(tǒng)的安全性

-是密碼學(xué)研究的一個(gè)重要課題

-有兩種定義“安全性”的方法：

基于信息論的方法（經(jīng)典方法）

基于計(jì)算復(fù)雜性理論的方法（現(xiàn)代方法）

基于信息論的方法：用密文中是否

蘊(yùn)含明文的信息作為標(biāo)準(zhǔn)。

基于計(jì)算復(fù)雜性理論的方法：是考

慮信息是否能有效地被提取出來(lái)。

I現(xiàn)代密碼學(xué)的基礎(chǔ)

傳統(tǒng)的密碼學(xué)和公鑰密碼學(xué)的基礎(chǔ)是

信息論和計(jì)算復(fù)雜性理論

信息理論密碼學(xué)

計(jì)算復(fù)雜性理論密碼學(xué)

■信息論告訴我們，所有的密碼算法

（OTP除外）都能被破譯。

.復(fù)雜性理論告訴我們，何時(shí)能被破譯。

信息理論密碼學(xué)

■Shannon用不確定性和惟一解距離

度量了密碼系統(tǒng)（體制）的安全性。

密碼系統(tǒng)的安全性:

■理論保密：完全保密

理想保密

-實(shí)際保密：計(jì)算安全

（可證明安全性）

［理論安全

-經(jīng)典方法

-無(wú)條件安全性

.基于信息論的密碼學(xué)

■信息理論密碼學(xué)：用信息論的觀點(diǎn)和方

法研究密碼系統(tǒng)模型的建立、密碼的安

全性及破譯等，它所研究的安全性準(zhǔn)則，

假定密碼分析者的計(jì)算資源，不受限制

完全保密

■理論上不可破譯的密碼體制。必要條件:

明文數(shù)、密鑰數(shù)和密文數(shù)都相等的密碼

體制，將每個(gè)明文變換成每個(gè)密文都恰

好有一個(gè)密鑰，所有的密鑰都是等可能

的。

■Shannon從理論上證明：僅當(dāng)可能的密

鑰數(shù)目至少與可能的消息數(shù)目一樣多時(shí),

完全保密才是有可能的。

完全保密

■僅有一次一密（OTP）亂碼本的密碼系

統(tǒng)可獲得完全保密。

■One-TimePad在要求無(wú)條件安全的軍事

和外交環(huán)境中有著很重要的作用。

完全保密：

（完善的或無(wú)條件的保密系統(tǒng)）

■給定密文y,明文為x的后驗(yàn)概率等于明

文x的先驗(yàn)概率

理想保密

■理論上不可譯的，它的惟一解距離UD趨

向于無(wú)窮大的密碼體制。

-意味著語(yǔ)言的多余度趨向于零。當(dāng)然消

除語(yǔ)言中的全部多余度事實(shí)上不可能。

■它是不實(shí)用的，但它揭示我們?cè)O(shè)計(jì)密碼

體制（算法）時(shí)，應(yīng)盡量縮小多余度。

■明文信息加密前先進(jìn)行信源編碼。

■一個(gè)完全保密的密碼系統(tǒng)必須是一個(gè)理

想保密的密碼系統(tǒng)，但是一個(gè)理想保密

的密碼系統(tǒng)不一定是一個(gè)完全保密的密

碼系統(tǒng)。

實(shí)際安全

■現(xiàn)代方法

■有條件安全性

■基于復(fù)雜性理論的密碼學(xué)

■復(fù)雜性理論密碼學(xué)：用復(fù)雜性理論的觀

點(diǎn)和方法研究密碼系統(tǒng)模型的建立、密

碼的安全性分析及破譯等。假定密碼分

析者的計(jì)算資源是有限的，受到限制

實(shí)際安全

■實(shí)際安全性又稱為計(jì)算上的安全性。

■計(jì)算安全性：涉及攻破密碼體制所做的

計(jì)算上的努力。

■可證明安全性：安全性歸結(jié)為某個(gè)經(jīng)過(guò)

深入研究的數(shù)學(xué)難題。

實(shí)際安全性

主要考慮：

-計(jì)算能力（基本運(yùn)算次數(shù)、存儲(chǔ)量）

-破譯算法的有效性

算法：求解某一問(wèn)題的、一步一步地執(zhí)行

的計(jì)算過(guò)程。

計(jì)算復(fù)雜性

-問(wèn)題的計(jì)算復(fù)雜性

可解問(wèn)題的最有效算法的計(jì)算復(fù)雜性

-算法的計(jì)算復(fù)雜性

運(yùn)行它所需的計(jì)算能力。常常用兩個(gè)變

量來(lái)度量：時(shí)間復(fù)雜性T和空間復(fù)雜性S

（或所需存儲(chǔ)空間）

■“計(jì)算上安全”：指利用已有的最好的

方法破譯該系統(tǒng)所需要的努力超過(guò)了敵

手的破譯能力（時(shí)間、空間、資金等）

或破譯該系統(tǒng)的難度等價(jià)于解數(shù)學(xué)上的

某個(gè)已知難題（計(jì)算復(fù)雜性）。

4計(jì)算復(fù)雜性

-計(jì)算復(fù)雜性理論是密碼系統(tǒng)安全性定義

的理論基礎(chǔ)。

■算法：函數(shù)1（常數(shù)）、對(duì)數(shù)、n（線性

函數(shù)）、二次函數(shù)、三次函數(shù)、多項(xiàng)式

函數(shù)、亞指數(shù)、指數(shù)函數(shù)

■問(wèn)題：P、NP、NPC

&時(shí)間復(fù)雜性

-一個(gè)算法的計(jì)算復(fù)雜性或有效性可以用

執(zhí)行該算法所需的運(yùn)行時(shí)間和內(nèi)存空間

來(lái)度量。

-時(shí)間復(fù)雜性有兩種定義方法：

lo用圖靈機(jī)表示一個(gè)算法

2o該算法的比特運(yùn)算次數(shù)

■計(jì)算上保密：

理論上可破,實(shí)際上難破，而不是不可

破。

密碼體制安全性準(zhǔn)則

-計(jì)算安全性：

■可證明安全性：

-無(wú)條件安全性：

5.密碼編碼系統(tǒng)分類:

-密碼編碼系統(tǒng)分類：

明文轉(zhuǎn)換為密文操作的類型?替代

?置換

密鑰數(shù)量?單鑰

?雙鑰

明文處理方式?分組密碼

?序列密碼

4Cryptography

■cancharacterizeby:

■typeofencryptionoperationsused

■substitution/transposition/product

■numberofkeysused

■single-keyorprivate/two-keyorpublic

■wayinwhichplaintextisprocessed

■block/stream

“Purple”紫碼

-1941.12.7日本偷襲珍珠港

-1942.1美成功破譯JN-25

-1942.4美轟炸日東京、神戶等

■194257-8巴布亞新幾內(nèi)亞的莫爾茲比港

PortMoresby（印尼）

■1942中途島之戰(zhàn)

■4.18“山本五十六”飛機(jī)降落時(shí)被擊落

二、古典密碼技術(shù)

-1.代替密碼：?jiǎn)伪泶婷艽a、

Playfair、HilkVigenere>OTP

■2.置換密碼：

-3.乘積密碼：

?4.轉(zhuǎn)輪機(jī)

■5.隱寫術(shù)

1.SubstitutionCiphers

■wherelettersofplaintextarereplaced

byotherlettersorbynumbersor

symbols

■orifplaintextisviewedasasequence

ofbits,thensubstitutioninvolves

replacingplaintextbitpatternswith

ciphertextbitpatterns

代替密碼

-單表代替密碼

-多名碼代替密碼

-多字母代替密碼

-多表代替密碼

1）單表代替密碼

■單表代替密碼

例如“凱撒”密碼古羅馬軍隊(duì)用

由JuliusCaesar發(fā)明

明文字母ABCDEFGHIKLMNOPQRSTVXYZ

密文字母DEFGHIKLMNOPQRSTVXYZABC

注：拉丁文不用J,U,W

CaesarCipher

■earliestknownsubstitutioncipher

■byJuliusCaesar

■firstattesteduseinmilitaryaffairs

■replaceseachletterby3rdletteron

■example:

meetmeafterthetogaparty

PHHWPHDIWHUWKHWRJDSDUWB

CaesarCipher

■candefinetransformationas:

abcdefghijklmnopqrstuvwxyz

DEFGHIJKLMNOPQRSTUVWXYZABC

■mathematicallygiveeachlettera

number

abcdefghijk1m

0123456789101112

nopqrstuvwxyZ

13141516171819202122232425

■thenhaveCaesarcipheras:

C=E(p)=(p+A)mod(26)

p=D(C)=(C-A)mod(26)

CryptanalysisofCaesarCipher

■onlyhave26possibleciphers

■AmapstoA,B,..Z

■couldsimplytryeachinturn

■abruteforcesearch

■givenciphertext,justtryallshiftsofletters

■doneedtorecognizewhenhaveplaintext

■eg.breakciphertext"GCUAVQDTGCM"

Monoalphabetic單表代替Cipher

■ratherthanjustshiftingthealphabet

■couldshuffleQumble)thelettersarbitrarily

■eachplaintextlettermapstoadifferent

randomciphertextletter

■hencekeyis26letterslong

Plain:abed一fghijklmnopqrstuvwxyz

Ciph一r:DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext:ifwewishtor一plac一工一tt一rs

Ciph一rt一xt:WIRFRWAJUHYFTSDVFSFUUFYA

MonoalphabeticCipher

Security

■nowhaveatotalof26!=4x10人26

keys

■withsomanykeys,mightthinkis

secure

■butwouldbe!!!WRONG!!!

■problemislanguagecharacteristics

■單表代替密碼不能掩蓋明文語(yǔ)言的所有

統(tǒng)計(jì)特性。

LanguageRedundancyand

Cryptanalysis

■humanlanguagesareredundant

■eg"thIrdsmshphrdshllntwnt"

■lettersarenotequallycommonlyused

■inEnglisheisbyfarthemostcommonletter

■thenT,R,N,I,O,A,S

■otherlettersarefairlyrare

■cf.Z,J,K,Q,X

■havetablesofsingle,double&tripleletter

frequencies

Eng-一shLetterFrequences

02

.7

12

)

%

(

cy

en

iu

w

f

ve

ei

ec

R

UseinCryptanalysis

■keyconcept-monoalphabeticsubstitution

ciphersdonotchangerelativeletter

frequencies

■discoveredbyArabianscientistsin9thcentury

■calculateletterfrequenciesforciphertext

■comparecounts/plotsagainstknownvalues

■ifCaesarcipherlookforcommon

peaks/troughs

■peaksat:A-E-Itriple,NOpair,RSTtriple

■troughsat:JK,X-Z

■formonoalphabeticmustidentifyeachletter

《安全性

■取決于密文在多大程度上保留了明文語(yǔ)

言的語(yǔ)法模式和結(jié)構(gòu)。

■理想的字母頻率分布情況：如果頻率分

配的信息完全給加密過(guò)程給隱藏了，那

么密文的頻率曲線應(yīng)該是一條水平的線。

■減少密文中殘留明文語(yǔ)言結(jié)構(gòu)的基本方

法：1）對(duì)明文中的多個(gè)字母一起加密

2）采用多表代替密碼

ExampleCryptanalysis

■givenciphertext:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

■countrelativeletterfrequencies(seetext)

■guessP&Zareeandt

■guessZWisthandhenceZWPisthe

■proceedingwithtrialanderrorfinallyget:

itwasdisclosedyesterdaythatseveralinformalbut

directcontactshavebeenmadewithpolitical

representativesofthevietconginmoscow

-單表代替密碼

移位代替密碼E(i)=i+k=jmodq

乘數(shù)密碼E(i)=ik三jmodqk與q互素

線性同余密碼(仿射密碼AffineCipher)

E(i)=ikl+kO=jmodqkl與q互素

＞多表代替密碼

2)PlayfairCipher

■noteventhelargenumberofkeysina

monoalphabeticcipherprovidessecurity

■oneapproachtoimprovingsecuritywas

toencryptmultipleletters

■thePlayfairCipherisanexample

■inventedbyCharlesWheatstonein

1854,butnamedafterhisfriendBaron

Playfair

■應(yīng)用：

第一次世界大戰(zhàn)中英軍就使用它作

為陸軍的標(biāo)準(zhǔn)加密體制，在第二次世界

大戰(zhàn)中，美軍極其他一些盟軍用它來(lái)進(jìn)

行加密。

PlayfairKeyMatrix

■a5X5matrixoflettersbasedonakeyword

■fillinlettersofkeyword(sansduplicates)

■fillrestofmatrixwithotherletters

■eg.usingthekeywordMONARCHY

MONAR

CHYBD

EFGIK

LPQST

UVWXZ

EncryptingandDecrypting

■plaintextencryptedtwolettersatatime:

i.ifapairisarepeatedletter,insertafillerlikeX,eg.

"balloon"encryptsas"balxIoon"

2.ifbothlettersfallinthesamerow,replaceeachwithletter

toright(wrappingbacktostartfromend),eg.uar"

encryptsas"RM"

3.ifbothlettersfallinthesamecolumn,replaceeachwiththe

letterbelowit(againwrappingtotopfrombottom),eg.

“mu”encryptsto"CM"

4.otherwiseeachletterisreplacedbytheoneinitsrowinthe

columnoftheotherletterofthepair,eg.uhs"encryptsto

"BP",anduea"to"IM"or"JM"(asdesired)

SecurityofthePlayfairCipher

■securitymuchimprovedovermonoalphabetic

■sincehave26x26=676digrams

■wouldneeda676entryfrequencytableto

analyse(verses26foramonoalphabetic)

■andcorrespondinglymoreciphertext

■waswidelyusedformanyyears(eg.LIS&

BritishmilitaryinWW1)

■itcanbebroken,givenafewhundredletters

■sincestillhasmuchofplaintextstructure

PolyalphabeticCiphers

■anotherapproachtoimprovingsecurityisto

usemultiplecipheralphabets

■calledpolyalphabeticsubstitution

ciphers多表代替密碼

■makescryptanalysisharderwithmore

alphabetstoguessandflatterfrequency

distribution

■useakeytoselectwhichalphabetisusedfor

eachletterofthemessage

■useeachalphabetinturn

■repeatfromstartafterendofkeyisreached

3.Hill代數(shù)法

■利用線性變換的方法，但在Z26上進(jìn)行。

-代數(shù)法（Hill密碼）

ABCDEFGHIJKLM

4825292016517302213

N0PQRSTUVWXYZ

24621152319127111811410

A-Z取值0-25o

力口密：y1=8x1+6x2+9x3+5x4

y2=6x1+9x2+5x3+10x4

y3=5xl+8x2+4x3+9x4

y4=10x1+6x2+11x3+4x4

e.g.HELPxl=H=5x2=E=9x3=L=22

x4=P=21力口密后yl=397mod26=7

y2=15y3=10y4=14密文為UQZY

解密：xl=23yl+20y2+5y3+ly4

x2=2yl+lly2+18y3+ly4

x3=2yl+20y2+6y3+25y4

x4=25yl+2y2+22y3+25y4

■Hill的優(yōu)點(diǎn)：完全隱蔽了單字母頻率特性。

Hill的矩陣越大，所隱蔽的頻率信息越多。

■Hill密碼既不是一種純換位密碼，也不是

一種純代替密碼。大多數(shù)“現(xiàn)代”密碼

算法都是將換位密碼和代替密碼算法有

機(jī)的結(jié)合。

■Hill密碼算法具有線性的缺點(diǎn)。

應(yīng)用

■Hill密碼由數(shù)學(xué)家LesterSHill1929年研

制。

■在第二次世界大戰(zhàn)中，該密碼被用來(lái)對(duì)

無(wú)線電呼叫信號(hào)進(jìn)行加密，加密和解密

均通過(guò)機(jī)械設(shè)備（而非電子設(shè)備）來(lái)完

成。

■較易被已知明文破解。

4)VigenereCipher

■simplestpolyalphabeticsubstitutioncipheris

theVigen6reCipher最簡(jiǎn)單、最著名

■effectivelymultiplecaesarciphers

■keyismultipleletterslongK=klk2…Kd

■ithletterspecifiesithalphabettouse

■useeachalphabetinturn

■repeatfromstartafterdlettersinmessage

■decryptionsimplyworksinreverse

■代換規(guī)則集由26個(gè)類似Caesar密碼的代

換表組成。

■依賴于密鑰詞的長(zhǎng)度

Example

■writetheplaintextout

■writethekeywordrepeatedaboveit

■useeachkeyletterasacaesarcipherkey

■encryptthecorrespondingplaintextletter

■egusingkeyworddeceptive

k一y:d一c一ptiv一d一。一ptiv一d一。一ptiv一

plaint一xt:w一ar一discov一r一dsav一yours一If

ciph一rt一xt:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Aids

■simpleaidscanassistwithen/decryption

■aSaint-CyrSlideisasimplemanualaid

■aslidewithrepeatedalphabet

■lineupplaintext'A'withkeyletter,eg'C

■thenreadoffanymappingforkeyletter

■canbendroundintoacipherdisk

■orexpandintoaVigenereTableau(see

textTable2.3)

SecurityofVigenereCiphers

■havemultipleciphertextlettersforeach

plaintextletter

■henceletterfrequenciesareobscured

■butnottotallylost

■startwithletterfrequencies

■seeiflookmonoalphabeticornot

■ifnot,thenneedtodeterminenumberof

alphabets,sincethencanattacheach

KasiskiMethod

■methoddevelopedbyBabbage/Kasiski

■repetitionsinciphertextgivecluestoperiod

■sofindsameplaintextanexactperiodapart

■whichresultsinthesameciphertext

■ofcourse,couldalsoberandomfluke

■egrepeated"VTW”inpreviousexample

■suggestssizeof3or9

■thenattackeachmonoalphabeticcipher

individuallyusingsametechniquesasbefore

AutokeyCipher

■ideallywantakeyaslongasthemessage

■Vigenereproposedtheautokeycipher

■withkeywordisprefixedtomessageaskey

■knowingkeywordcanrecoverthefirstfew

letters

■usetheseinturnontherestofthemessage

■butstillhavefrequencycharacteristicsto

attack

■eg,givenkeydeceptive

key:d一。一ptiv一w一ar一discov一r一dsav

plaintext:w一ar一discov一r一dsav一yours一If

5）One-TimePad（一次一密）

■ifatrulyrandomkeyaslongasthemessage

isused,thecipherwillbesecure

■calledaOne-Timepad

■isunbreakablesinceciphertextbearsno

statisticalrelationshiptotheplaintext

■sinceforanyplaintext&anyciphertext

thereexistsakeymappingonetoother

■canonlyusethekeyoncethough

■haveproblemofsafedistributionofkey

一次一密

■陸軍情報(bào)官M(fèi)auborgne建議使用與消息

一樣長(zhǎng)且無(wú)重復(fù)的隨機(jī)密鑰來(lái)加密消息

■一次一密的安全性完全取決于密鑰的隨

機(jī)性

■存在兩個(gè)難點(diǎn)：

?產(chǎn)生大規(guī)模隨機(jī)密鑰

■密鑰的分配和保護(hù)

主要應(yīng)用于安全性要求很高的低帶寬信道。

2.TranspositionCiphers

-置換密碼

■nowconsiderclassicaltranspositionor

permutationciphers

■thesehidethemessagebyrearrangingthe

letterorder

■withoutalteringtheactuallettersused

■canrecognisethesesincehavethesame

frequencydistributionastheoriginaltext

■移位密碼

古希臘的“天書”器械，公元前400年希

臘人采用。斯巴達(dá)克人塞塔發(fā)明的。

加密方法

密鑰

RowTranspositionCiphers

■amorecomplexscheme柵欄技術(shù)

■writelettersofmessageoutinrows

overaspecifiednumberofcolumns

■thenreorderthecolumnsaccordingto

somekeybeforereadingofftherows

Kay:4312567

Plaintext:attackp

ostpon一

dunti1t

woamxyz

Ciph一rt一xt:TTNAAPTMTSUOAODWCOIXKNLYPETZ

■代替密碼Substitution：明文字母被不同

的密文字母所代替。

■置換密碼Transposition：Permutation保

持明文的所有字母不變，只是利用置換

打亂了明文字母的位置和次序。

3.ProductCiphers

ciphersusingsubstitutionsortranspositionsare

notsecurebecauseoflanguage

characteristics

■henceconsiderusingseveralciphersin

successiontomakeharder,but:

■twosubstitutionsmakeamorecomplex

substitution

■twotranspositionsmakemorecomplex

transposition

■butasubstitutionfollowedbyatransposition

makesanewmuchhardercipher

■thisisbridgefromclassicaltomodernciphers

■乘積密碼：

以德軍第一次世界大戰(zhàn)中所使用的密碼

為例：ADFGVX乘積密碼

ADFGVX明文：PRODUCT

AKZWR1FCIPHERS

D9B6CL5中間報(bào)文：

FQ7JPGXFGAGVDVFXADGXV

GEVY3ANDGXFFGVGGAAGXG

V80DH02

XU4ISTM

DEUTSCH密鑰

2376514排列順序

FGAGVDV密文：

FXADGXVDXGXFFDGGXGG

DGXFFGVVWGVGFGGDFA

GGAAGXGAAXA

4.RotorMachines

■beforemodernciphers,rotormachineswere

mostcommonproductcipher

■werewidelyusedinWW2

■GermanEnigma,AlliedHagelin,JapanesePurple

■implementedaverycomplex,varying

substitutioncipher

■usedaseriesofcylinders,eachgivingone

substitution,whichrotatedandchangedafter

eachletterwasencrypted

■with3cylindershave263=17576alphabets

《轉(zhuǎn)輪機(jī)

■轉(zhuǎn)輪機(jī)密碼系統(tǒng)（多層加密原理）

■多筒系統(tǒng)中，操作員每按一次輸入鍵，

最后一個(gè)轉(zhuǎn)輪就旋轉(zhuǎn)一個(gè)引腳的位置。

■轉(zhuǎn)輪機(jī)由一系列獨(dú)立轉(zhuǎn)動(dòng)的圓柱體組成,

每個(gè)圓柱體具有26個(gè)輸入引腳和26個(gè)輸

出弓I腳，單個(gè)圓柱體定義了一個(gè)單字母

替代。

■1.天書6.One-TimePad

■2.caesar7.置換密碼

-3.仿射8.乘積密碼

■4.Playfair9.Hill密碼

■5.Vigenere10.轉(zhuǎn)輪機(jī)

-封閉性

■唯一性

-可逆性

5.信息隱藏InformationHiding

-最大的優(yōu)點(diǎn)也就是它最大的缺點(diǎn)。

-信息隱藏又稱信息偽裝。

-信息隱藏是一門古老的技術(shù)。

-信息隱藏主要分為：

隱寫術(shù)

數(shù)字水印

信息隱藏的特點(diǎn)：

1.不破壞載體的正常使用。

2.載體具有某種冗余性

3.隱形性：

4.穩(wěn)健性：信號(hào)處理變換

5.通用性：圖象、視頻、音頻

6.確定性：唯一的鑒別確定

Steganography（隱寫術(shù)）

■analternativetoencryption

■hidesexistenceofmessage

■usingonlyasubsetofletters/wordsinalonger

messagemarkedinsomeway

■usinginvisibleink

■hidinginLSBingraphicimageorsoundfile

■hasdrawbacks

■highoverheadtohiderelativelyfewinfobits

■藏頭詩(shī)

■不可見墨水

■優(yōu)點(diǎn)：可以應(yīng)用于通信雙方寧愿他們的

秘密信息被發(fā)現(xiàn)而不愿其中的重要內(nèi)容

丟失的情況。

■缺點(diǎn)：它需要大量額外的開銷來(lái)隱藏相

對(duì)較少的信息。

j數(shù)字水印

數(shù)字水印的三要素：

■水銀本身的結(jié)構(gòu)

■加載水印的地方或加載水印的策略

-水印的檢測(cè)

J言息隱藏的方法

-主要分為兩類：

-空間域算法：

最低有效位LSB方法

-變換域算法：

離散傅立葉變換DFT方法

離散余弦變換DCT方法

離散小波變換DWT方法

數(shù)字水印的應(yīng)用：

-版權(quán)保護(hù)

■隱藏標(biāo)識(shí)和標(biāo)簽

■認(rèn)證

■數(shù)據(jù)隱藏技術(shù)或隱寫術(shù)

為將而不通天文，不識(shí)地理，

不知奇門，不曉陰陽(yáng)，不看陣圖,

不明兵勢(shì)，（不懂信息安全，）

是庸才也。

諸葛亮

三、密碼體制

■單鑰體制（密碼保險(xiǎn)柜）

■雙鑰體制（郵箱）

SymmetricEncryption

■orconventional/private-key/single-

key

■senderandrecipientshareacommon

key

■allclassicalencryptionalgorithmsare

private-key

■wasonlytypepriortoinventionof

public-keyin19705s

1,單鑰體制

-加密密鑰和解秘密鑰相同。

-系統(tǒng)的安全性取決于密鑰的安全性

-密鑰管理是該體制設(shè)計(jì)和實(shí)現(xiàn)的主要課

題。

■對(duì)明文加密有兩種方式：

序列密碼（流密碼）：按字符逐位加密。

分組密碼：將明文消息分組，逐組加密。

序列密碼

序列密碼示意圖

StreamCiphers

■processthemessagebitbybit(asastream)

■typicallyhavea(pseudo)randomstream

key

■combined(XOR)withplaintextbitbybit

■randomnessofstreamkeycompletely

destroysanystatisticallypropertiesinthe

message

■蠢=XORStr一amK一yi

■whatcouldbesimpler!!!!

■butmustneverreusestreamkey

■otherwisecanremoveeffectandrecover

StreamCipherProperties

■somedesignconsiderationsare:

■longperiodwithnorepetitions

■statisticallyrandom

■dependsonlargeenoughkey

■largelinearcomplexity

■correlationimmunity

■confusion

■diffusion

■useofhighlynon-linearbooleanfunctions

■序列（流）密碼一直是作為軍事和外交

場(chǎng)合使用的主要密碼技術(shù)之一。

序列密碼

-體制的保密性完全取決于密鑰的隨機(jī)性。

-密碼強(qiáng)度完全依賴于密鑰序列產(chǎn)生器所

形成序列的隨機(jī)性和不可預(yù)測(cè)性。

-核心問(wèn)題：密鑰序列生成器的設(shè)計(jì)。

-分類：

1）同步流密碼

2）自同步流密碼

■同步流密碼ssc：

加密變換是無(wú)記憶的，它是時(shí)變的。

密鑰流獨(dú)立于明文。

優(yōu)點(diǎn)：對(duì)主動(dòng)攻擊異常敏感，利于檢測(cè)

無(wú)錯(cuò)誤傳播。

缺點(diǎn)：一旦失步，同步后才恢復(fù)工作。

重要技術(shù)課題：失步后如何重新同步。

■自同步序列密碼sssc：

密文不僅與當(dāng)前明文有關(guān)，而且與以

前的輸入有關(guān)。

優(yōu)點(diǎn)：自恢復(fù)同步性

強(qiáng)化其抗統(tǒng)計(jì)分析的能力。

缺點(diǎn)：不敏感、有限的錯(cuò)誤傳播

-密鑰序列生成器輸出序列應(yīng)滿足:

1）周期要足夠大，＞10人50

2）偽隨機(jī)性好

3）易于高速生成

4）不可預(yù)測(cè)性

一般要進(jìn)行統(tǒng)計(jì)檢驗(yàn)。

實(shí)現(xiàn)：硬件、軟件or二者結(jié)合。

■例子：

A5：歐洲數(shù)字蜂窩移動(dòng)電話系統(tǒng)GSM

用于從用戶手機(jī)到基站的連接加密0

RC-4：SSL/TLS

W印正EE802.il無(wú)線LAN

4分組密碼

■將明文劃分為固定的數(shù)據(jù)組，以組為單

位。

-優(yōu)點(diǎn)：不需要同步

■例：DES

IDEA

AES

RSA

-通常：m=n若n>m有數(shù)據(jù)擴(kuò)展

n<m有數(shù)據(jù)壓縮

算法應(yīng)滿足：

1）分組長(zhǎng)度、密鑰量要足夠大

2）由密鑰確定置換的方法要足夠復(fù)雜

3）加解密運(yùn)算簡(jiǎn)單，易于軟硬件高速實(shí)

現(xiàn)。止匕外，一般無(wú)數(shù)據(jù)擴(kuò)展。

2.雙鑰密碼體制

■1975年Stanford大學(xué)的W.Diffie

Hellman在《密碼學(xué)的新方向》一文提

出了公開密鑰編碼學(xué)，他們懂得一種間

接貢獻(xiàn)是引入了一個(gè)看來(lái)不易解決的問(wèn)

題。他們提出：使用不同的加密密鑰和

解密密鑰，由已知加密密鑰推導(dǎo)出解密

密鑰在計(jì)算上是不可行的密碼體制。

■公鑰加密算法是基于數(shù)學(xué)函數(shù)（數(shù)論）

的，而不是基于簡(jiǎn)單的比特位操作。

■公鑰加密是幾千年來(lái)在加密領(lǐng)域中第一

次出現(xiàn)的真正的革命性進(jìn)展。

■對(duì)保密、密鑰分配、鑒別等諸多領(lǐng)域有

深遠(yuǎn)的影響。

Public-KeyCryptography

■probablymostsignificantadvanceinthe3000

yearhistoryofcryptography

■usestwokeys-apublic&aprivatekey

■asymmetricsincepartiesarenotequal

■usescleverapplicationofnumbertheoretic

conceptstofunction

■complementsratherthanreplacesprivate

keycrypto

SourceADestinationB

Figure9.4Public-KeyCptosystcin:SecrecyandAutlivntication

■公開密鑰密碼體制產(chǎn)生原因：

1）常規(guī)密鑰密碼體制的密鑰分配問(wèn)題

2）數(shù)字簽名的需求

-使用情況

1）保密通信

2）數(shù)字簽名

3）密鑰交換

■公開密鑰密碼體制：

1）基于NP完全理論的背包體制。

2）基于編碼理論的McEliece體制

3）基于數(shù)論中大數(shù)分解問(wèn)題的RSA體制

離散對(duì)數(shù)D-H、日Gamal、Rabin、

ECT。

四、密碼分析

■“知彼知己者，百戰(zhàn)不殆”。

■目的：通過(guò)分析改變關(guān)于每個(gè)可能

明文的可能性，最后，一個(gè)明文當(dāng)

然（至少非?？赡埽?huì)從所有可能

的明文集合中暴露出來(lái)。

■不會(huì)攻擊者設(shè)計(jì)不出好密碼

■密碼分析：試圖從截獲的密文中推

斷出密鑰或明文的過(guò)程。

-分析法：

1.確定性分析

1）差分攻擊

2）線性攻擊

2.統(tǒng)計(jì)分析

-窮舉分析：（野蠻、強(qiáng)行攻擊）

-非技術(shù)方法：

■密碼分析學(xué)：

攻擊依賴于算法的性質(zhì)和明文的一般

特征或某些明文-密文對(duì)。它企圖利用算

法的特征來(lái)推導(dǎo)出特別的明文或使用的

密鑰來(lái)。

確定性分析法

-確定性分析法：利用一個(gè)或幾個(gè)已知量

用數(shù)學(xué)關(guān)系式表示出所求未知量。

-關(guān)鍵：尋求已知量和未知量之間的關(guān)系。

1）差分分析：

2）線性分析：y=kx

■對(duì)稱體制：明文中結(jié)構(gòu)的痕跡或模式可

能經(jīng)加密后在密文中仍然是可辨認(rèn)的。

■公鑰體制:密鑰對(duì)的數(shù)學(xué)性質(zhì)使得從一個(gè)

密鑰推出另一個(gè)密鑰成為可能.

統(tǒng)計(jì)分析法

-利用明文的已知統(tǒng)計(jì)規(guī)律進(jìn)行破譯的方

法。

■對(duì)密文統(tǒng)計(jì)分析總結(jié)規(guī)律，并與明文規(guī)

律進(jìn)行對(duì)照比較。

■密碼分析成功的根本原因是明文中