It計算機課件 密碼學基礎(chǔ)知識

密碼學

基礎(chǔ)知識

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

非學無以廣才，非志無以成

學。

諸葛亮

概述

■密碼學

密碼編碼學

密碼分析學

-作用:

機密性

鑒別

完整性

抗抵賴

密碼學文獻的發(fā)展歷程：

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

碼學中的應用》。

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

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

論》

■1967年，Kahn《破譯者》

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

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

密碼學，《密碼學的新方向》

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

■1978年，MIT的RSA算法。

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

KoblitzMiller提出橢圓曲線密碼學

?1995年，Hoffstein,Pipher,Siverman

發(fā)明NTRU密碼

■密碼學之前，信息安全的保護主要是通

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

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

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

-第一階段：

手工計算

-第二階段：

機械和電動機械

-第三階段：

電子和計算機

內(nèi)容

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

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

■3.密碼體制

■4.密碼分析

■5.加密方式

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

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

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

一個密碼體制由五元組(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è)計準則

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

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

當為實際上是不可破的。

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

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

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

元素。

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

Kerckhoff六項準貝ij

在19世紀對軍事密碼體制提出六項準則：

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

應該是實際上不可破的。

■體制的泄露不應該給通信者帶來麻煩。

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

-明文

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

■惟一解距離UD

Plaintext明文

■Entropy:一條信息的信息量通過嫡來度量。

是對信息或不確定性的數(shù)學度量，通過

概率分布的函數(shù)來計算。

■語言信息率：r=H(M)/NN相當大時，

標準英語的語言信息率在L0-L5/字母之

間。

■語言絕對信息率：假定每一個字符串是

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

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

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

信息率為1.3位/字符。

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

字母。英語語言是75%冗余。Huffman

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

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

位，相當于每位ASCII文本有0.84位冗余

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

一個重要工具。

■它最重要也是最基本的特征：單個字母

出現(xiàn)的頻率。

密碼系統(tǒng)的嫡

■由密鑰空間大小來衡量

H(K)=logK

一般來說，嫡越大，破譯它越困難。

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

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

征完全決定。

■收到的密文越長，分析者找到密鑰或明

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

唯一的密鑰，理論上S至少將要多長。

惟一解距離UD

■在給定足夠的計算時間下，分析者能唯

一計算出密鑰所需密文的平均值。

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

個具有無限計算能力的攻擊者能夠恢復

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

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

鑰曖昧度趨近于零。

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

UD

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

值。

■當密文字符大于UD時，這種密碼就存在

一個解，而當密文字符小于UD時，就會

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

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

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

UD

■Shannon指出：惟一解距離可以保證當

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

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

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

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

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

■惟一解距離與冗余度成反比，當冗余度

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

能是木前破的。

UD

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

越好。無窮大時為理想保密。

密碼分析

■利用自然語言的冗余度來減少可能的明

文數(shù)目。

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

■最重要也是最基本的特征：單個字母出

現(xiàn)的頻率。

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

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

當均勻地分布到在整個消息空間中。

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

-是密碼學研究的一個重要課題

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

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

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

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

蘊含明文的信息作為標準。

基于計算復雜性理論的方法：是考

慮信息是否能有效地被提取出來。

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

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

信息論和計算復雜性理論

信息理論密碼學

計算復雜性理論密碼學

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

（OTP除外）都能被破譯。

.復雜性理論告訴我們，何時能被破譯。

信息理論密碼學

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

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

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

■理論保密：完全保密

理想保密

-實際保密：計算安全

（可證明安全性）

［理論安全

-經(jīng)典方法

-無條件安全性

.基于信息論的密碼學

■信息理論密碼學：用信息論的觀點和方

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

全性及破譯等，它所研究的安全性準則，

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

完全保密

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

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

體制，將每個明文變換成每個密文都恰

好有一個密鑰，所有的密鑰都是等可能

的。

■Shannon從理論上證明：僅當可能的密

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

完全保密才是有可能的。

完全保密

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

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

■One-TimePad在要求無條件安全的軍事

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

完全保密：

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

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

文x的先驗概率

理想保密

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

向于無窮大的密碼體制。

-意味著語言的多余度趨向于零。當然消

除語言中的全部多余度事實上不可能。

■它是不實用的，但它揭示我們設(shè)計密碼

體制（算法）時，應盡量縮小多余度。

■明文信息加密前先進行信源編碼。

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

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

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

碼系統(tǒng)。

實際安全

■現(xiàn)代方法

■有條件安全性

■基于復雜性理論的密碼學

■復雜性理論密碼學：用復雜性理論的觀

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

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

析者的計算資源是有限的，受到限制

實際安全

■實際安全性又稱為計算上的安全性。

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

計算上的努力。

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

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

實際安全性

主要考慮：

-計算能力（基本運算次數(shù)、存儲量）

-破譯算法的有效性

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

的計算過程。

計算復雜性

-問題的計算復雜性

可解問題的最有效算法的計算復雜性

-算法的計算復雜性

運行它所需的計算能力。常常用兩個變

量來度量：時間復雜性T和空間復雜性S

（或所需存儲空間）

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

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

手的破譯能力（時間、空間、資金等）

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

某個已知難題（計算復雜性）。

4計算復雜性

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

的理論基礎(chǔ)。

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

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

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

■問題：P、NP、NPC

&時間復雜性

-一個算法的計算復雜性或有效性可以用

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

來度量。

-時間復雜性有兩種定義方法：

lo用圖靈機表示一個算法

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

■計算上保密：

理論上可破,實際上難破，而不是不可

破。

密碼體制安全性準則

-計算安全性：

■可證明安全性：

-無條件安全性：

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“山本五十六”飛機降落時被擊落

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

-1.代替密碼：單表代替密碼、

Playfair、HilkVigenere>OTP

■2.置換密碼：

-3.乘積密碼：

?4.轉(zhuǎn)輪機

■5.隱寫術(shù)

1.SubstitutionCiphers

■wherelettersofplaintextarereplaced

byotherlettersorbynumbersor

symbols

■orifplaintextisviewedasasequence

ofbits,thensubstitutioninvolves

replacingplaintextbitpatternswith

ciphertextbitpatterns

代替密碼

-單表代替密碼

-多名碼代替密碼

-多字母代替密碼

-多表代替密碼

1）單表代替密碼

■單表代替密碼

例如“凱撒”密碼古羅馬軍隊用

由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

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

統(tǒng)計特性。

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

《安全性

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

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

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

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

么密文的頻率曲線應該是一條水平的線。

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

法：1）對明文中的多個字母一起加密

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

■應用：

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

為陸軍的標準加密體制，在第二次世界

大戰(zhà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上進行。

-代數(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)點：完全隱蔽了單字母頻率特性。

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

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

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

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

機的結(jié)合。

■Hill密碼算法具有線性的缺點。

應用

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

制。

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

無線電呼叫信號進行加密，加密和解密

均通過機械設(shè)備（而非電子設(shè)備）來完

成。

■較易被已知明文破解。

4)VigenereCipher

■simplestpolyalphabeticsubstitutioncipheris

theVigen6reCipher最簡單、最著名

■effectivelymultiplecaesarciphers

■keyismultipleletterslongK=klk2…Kd

■ithletterspecifiesithalphabettouse

■useeachalphabetinturn

■repeatfromstartafterdlettersinmessage

■decryptionsimplyworksinreverse

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

換表組成。

■依賴于密鑰詞的長度

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

一次一密

■陸軍情報官Mauborgne建議使用與消息

一樣長且無重復的隨機密鑰來加密消息

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

機性

■存在兩個難點：

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

■密鑰的分配和保護

主要應用于安全性要求很高的低帶寬信道。

2.TranspositionCiphers

-置換密碼

■nowconsiderclassicaltranspositionor

permutationciphers

■thesehidethemessagebyrearrangingthe

letterorder

■withoutalteringtheactuallettersused

■canrecognisethesesincehavethesame

frequencydistributionastheoriginaltext

■移位密碼

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

臘人采用。斯巴達克人塞塔發(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中間報文：

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)輪機

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

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

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

■轉(zhuǎn)輪機由一系列獨立轉(zhuǎn)動的圓柱體組成,

每個圓柱體具有26個輸入引腳和26個輸

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

替代。

■1.天書6.One-TimePad

■2.caesar7.置換密碼

-3.仿射8.乘積密碼

■4.Playfair9.Hill密碼

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

-封閉性

■唯一性

-可逆性

5.信息隱藏InformationHiding

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

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

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

-信息隱藏主要分為：

隱寫術(shù)

數(shù)字水印

信息隱藏的特點：

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

2.載體具有某種冗余性

3.隱形性：

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

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

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

Steganography（隱寫術(shù)）

■analternativetoencryption

■hidesexistenceofmessage

■usingonlyasubsetofletters/wordsinalonger

messagemarkedinsomeway

■usinginvisibleink

■hidinginLSBingraphicimageorsoundfile

■hasdrawbacks

■highoverheadtohiderelativelyfewinfobits

■藏頭詩

■不可見墨水

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

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

丟失的情況。

■缺點：它需要大量額外的開銷來隱藏相

對較少的信息。

j數(shù)字水印

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

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

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

-水印的檢測

J言息隱藏的方法

-主要分為兩類：

-空間域算法：

最低有效位LSB方法

-變換域算法：

離散傅立葉變換DFT方法

離散余弦變換DCT方法

離散小波變換DWT方法

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

-版權(quán)保護

■隱藏標識和標簽

■認證

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

為將而不通天文，不識地理，

不知奇門，不曉陰陽，不看陣圖,

不明兵勢，（不懂信息安全，）

是庸才也。

諸葛亮

三、密碼體制

■單鑰體制（密碼保險柜）

■雙鑰體制（郵箱）

SymmetricEncryption

■orconventional/private-key/single-

key

■senderandrecipientshareacommon

key

■allclassicalencryptionalgorithmsare

private-key

■wasonlytypepriortoinventionof

public-keyin19705s

1,單鑰體制

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

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

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

題。

■對明文加密有兩種方式：

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

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

序列密碼

序列密碼示意圖

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

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

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

序列密碼

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

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

形成序列的隨機性和不可預測性。

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

-分類：

1）同步流密碼

2）自同步流密碼

■同步流密碼ssc：

加密變換是無記憶的，它是時變的。

密鑰流獨立于明文。

優(yōu)點：對主動攻擊異常敏感，利于檢測

無錯誤傳播。

缺點：一旦失步，同步后才恢復工作。

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

■自同步序列密碼sssc：

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

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

優(yōu)點：自恢復同步性

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

缺點：不敏感、有限的錯誤傳播

-密鑰序列生成器輸出序列應滿足:

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

2）偽隨機性好

3）易于高速生成

4）不可預測性

一般要進行統(tǒng)計檢驗。

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

■例子：

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

用于從用戶手機到基站的連接加密0

RC-4：SSL/TLS

W印正EE802.il無線LAN

4分組密碼

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

位。

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

■例：DES

IDEA

AES

RSA

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

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

算法應滿足：

1）分組長度、密鑰量要足夠大

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

3）加解密運算簡單，易于軟硬件高速實

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

2.雙鑰密碼體制

■1975年Stanford大學的W.Diffie

Hellman在《密碼學的新方向》一文提

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

接貢獻是引入了一個看來不易解決的問

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

解密密鑰，由已知加密密鑰推導出解密

密鑰在計算上是不可行的密碼體制。

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

的，而不是基于簡單的比特位操作。

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

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

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

深遠的影響。

Public-KeyCryptography

■probablymostsignificantadvanceinthe3000

yearhistoryofcryptography

■usestwokeys-apublic&aprivatekey

■asymmetricsincepartiesarenotequal

■usescleverapplicationofnumbertheoretic

conceptstofunction

■complementsratherthanreplacesprivate

keycrypto

SourceADestinationB

Figure9.4Public-KeyCptosystcin:SecrecyandAutlivntication

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

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

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

-使用情況

1）保密通信

2）數(shù)字簽名

3）密鑰交換

■公開密鑰密碼體制：

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

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

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

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

ECT。

四、密碼分析

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

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

明文的可能性，最后，一個明文當

然（至少非?？赡埽乃锌赡?/p>

的明文集合中暴露出來。

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

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

斷出密鑰或明文的過程。

-分析法：

1.確定性分析

1）差分攻擊

2）線性攻擊

2.統(tǒng)計分析

-窮舉分析：（野蠻、強行攻擊）

-非技術(shù)方法：

■密碼分析學：

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

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

法的特征來推導出特別的明文或使用的

密鑰來。

確定性分析法

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

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

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

1）差分分析：

2）線性分析：y=kx

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

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

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

密鑰推出另一個密鑰成為可能.

統(tǒng)計分析法

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

法。

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

律進行對照比較。

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