第2講 古典密碼教材

第6章傳統(tǒng)加密技術(shù)2.1對稱密碼模型2.2代換(替代)技術(shù)

2.2.1愷撒密碼

2.2.2單表替代密碼

2.2.3Playfair密碼

2.2.4Hill密碼

2.2.5多表密碼

2.2.6一次一密one-timepad2.3置換技術(shù)2.4轉(zhuǎn)輪機(jī)Rotor2.5隱寫術(shù)Steganography密碼學(xué)簡史在密碼學(xué)的發(fā)展中，有一條原則就是秘而不宣。雖然歷史上早就有密碼學(xué)應(yīng)用的痕跡，但是是一戰(zhàn)刺激了其需求，而在二戰(zhàn)中得到了充分發(fā)展和應(yīng)用，并極大的影響了戰(zhàn)爭進(jìn)程。http:///wiki/珍珠港事件1949年，Shannon關(guān)于保密系統(tǒng)通信理論的發(fā)表，奠定了密碼學(xué)在公開領(lǐng)域研究的基礎(chǔ)。然后是廣泛商業(yè)應(yīng)用的DES標(biāo)準(zhǔn)。1975年，Hellman和Diffie提出了公密算法方向，這是現(xiàn)代密碼學(xué)的里程碑。隨后響應(yīng)這一思路而提出的RSA算法，至今仍是當(dāng)今網(wǎng)絡(luò)安全的基石。此后，隨著互聯(lián)網(wǎng)絡(luò)的發(fā)展，開創(chuàng)了密碼學(xué)應(yīng)用的新領(lǐng)域。大體分三個階段1949年之前

密碼學(xué)是一門藝術(shù)

1949～1975年

密碼學(xué)成為科學(xué)

1976年以后

密碼學(xué)的新方向——公鑰密碼學(xué)一封密碼信在美國人多次表示“不確定拉登是否還活著”之后，拉登決定寫封親筆信給美國總統(tǒng)布什，以表明他還活得好好的，沒有那么早善罷干休。當(dāng)布什打開信封，看到信里似乎寫了一組密碼：

370HSSV0773H布什心頭震動，于是把這組密碼以電子郵件傳給國務(wù)卿科林˙包威爾?？屏指闹窒肓税胩?，也沒辦法解開密碼的含意，于是要求FBI幫忙。但是FBI也沒人能參透其中含意，只好請求CIA，然后NASA，最后連國家安全局也沒輒。

一封密碼信370HSSV0773H370HSSV0773HHELLOASSHOLE在束手無策之下，他們只好轉(zhuǎn)向英國的軍情六處(MI6)請求協(xié)助。Q和007看了之后，便打通熱

線電話到白宮去。

Q說：麻煩轉(zhuǎn)告總統(tǒng)先生，他把信拿反了.......

加密技術(shù)的開拓者經(jīng)典密碼軍事、外交、諜報現(xiàn)代密碼對稱密碼、非對稱密碼、簽名算法、PRNG密碼學(xué)家∈數(shù)學(xué)家標(biāo)準(zhǔn)化和產(chǎn)品NIST、NSA、ISORFC、PGPMS、IBM,RSA、Entrust2.1

對稱密碼模型

5個基本要素明文

plaintext密文

ciphertext密鑰

key加密算法

encryptionalgorithm解密算法

decryptionalgorithm

術(shù)語加密

encipher(encrypt)

解密

decipher(decrypt)

密碼體制

cryptographicsystem(cipher)密碼學(xué)

cryptology密碼編碼學(xué)

cryptography

密碼分析學(xué)

cryptanalysis(codebreaking)簡化的傳統(tǒng)加密模型加密算法必須夠強(qiáng)(什么算強(qiáng)?)必須安全地協(xié)商密鑰(天知地知你知我知?)應(yīng)當(dāng)滿足的要求系統(tǒng)即使達(dá)不到理論上是不可破的，也應(yīng)當(dāng)為實(shí)際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。無條件安全（unconditionalsecurity）

如果算法產(chǎn)生的密文不能給出唯一決定相應(yīng)明文的足夠信息，無論截獲多少密文，花費(fèi)多少時間都不能解密密文。

Shannon指出，僅當(dāng)密鑰至少和明文一樣長時達(dá)到無條件安全（即一次一密）計算安全（computationalsecurity

）破譯密文的代價超過被加密信息的價值破譯密文所花時間超過信息的有效期著名的Kerckhoff原則：系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。傳統(tǒng)加密模型Y=EK(X) 或Y=E(K,

X) DK(Y)

=X

D(K,Y)

=X密碼體制五元組（P，C，K，E，D）明文空間P：可能的明文的有限集密文空間C：可能的密文的有限集密鑰空間K：可能的密鑰的有限集對k∈K，決定一個加密規(guī)則ek∈E：P→C

和解密規(guī)則dk∈D：C

→P，滿足對明文x∈P

dk（ek（x））＝x2.1.1

密碼編碼學(xué)(算法)特征運(yùn)算類型代換substitution

明文元素映射為密文元素置換transposition/permutation

把明文元素重排處理明文的方法分組算法vs流算法（序列密碼算法）密鑰數(shù)：--單鑰體制(One-keysystem)：

/對稱算法(symmetricalgorithm)

加密密鑰和解密密鑰相同。--雙鑰體制(Twokeysystem)：

/公開密鑰算法(public-keyalgorithm)

加密密鑰和解密密鑰不同。2.1.1

密碼編碼學(xué)(算法)特征2.1.2

密碼分析學(xué)目標(biāo)：就是要從密文得到明文或者由已知的條件得到密鑰。前提假定：攻擊者總能獲得密文；攻擊者知道加密算法；攻擊者不知道密鑰；分類：攻擊者可獲取的信息量的不同，將攻擊者對密碼系統(tǒng)的4種攻擊類型。

攻擊類型攻擊類型攻擊者擁有的資源惟密文攻擊(Ciphertextonly)加密算法截獲的部分密文已知明文攻擊(knownplaintext)加密算法，截獲的部分密文和相應(yīng)的明文選擇明文攻擊(chosenplaintext)加密算法加密黑盒子，可加密任意明文得到相應(yīng)的密文選擇密文攻擊(chosenciphertext)加密算法解密黑盒子，可解密任意密文得到相應(yīng)的明文選擇文本攻擊(chosentext)加密算法加密/解密黑盒子2.2代換(替代)技術(shù)古典密碼技術(shù)其技術(shù)、思想以及破譯方法雖然很簡單，但是反映了密碼設(shè)計和破譯的思想，是學(xué)習(xí)密碼學(xué)的基本入口。古典算法中使用26個字母組成的明文(現(xiàn)代計算機(jī)使用二進(jìn)制比特序列)。

為了方便，一般使用小寫字母表書明文，使用大寫表書密文。S

&T替代和置換是古典及現(xiàn)代密碼算法的共同、基本思想。替代substitution 把明文的(比特)模式替換成密文的(比特)式置換transposition打亂明文的順序排列方式，即置亂單表代換密碼多表代換密碼凱撒密碼移位變換仿射變換(MonoalphabeticSubstitution)(PolyalphabeticSubstitution)代換密碼幾種古典密碼－代換密碼Playfair密碼Hill密碼字母abcdefghijklm數(shù)字0123456789101112字母nopqrstuvwxyz數(shù)字13141516171819202122232425英文字母和十進(jìn)制數(shù)字的對應(yīng)關(guān)系明文字母abcdefghijklmnopqrstuvwxyz密文字母defghijklmnopqrstuvwxyzabc幾種古典密碼：單表代換密碼1.凱撒密碼(Caesar):依據(jù)下列代替表（由英文字母表左環(huán)移3位得到）對信息中26個英文字母進(jìn)行替換：明文：informationsecurity密文：lqirupdwlrq

vhfxulub明文：Substitutioncryptosystem密文：VXEVWLWXWLRQFUBSWRVBVWHP明文字母abcdefghijklmnopqrstuvwxyz密文字母defghijklmnopqrstuvwxyzabc幾種古典密碼：單表代換密碼1.凱撒密碼(Caesar):依據(jù)下列代換表（由英文字母表左環(huán)移3位得到）對信息中26個英文字母進(jìn)行代換：明文：Caesarcipherisashiftsubstitution

密文：FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQ幾種古典密碼：單表代換密碼2.移位變換明文m：informationsecurity

Key:k=6密文c：otluxtsgzotykixoze明文字母abcdefghijklmnopqrstuvwxyz密文字母

ghijklmnopqrstuvwxyzabcdef幾種古典密碼：單表代換密碼3.仿射變換分析Caesar/Shift及Affine分析：

Caesar/Shift，

Affine2.2.2

單表替代密碼

MonoalphabeticCipher（Substitution）查對照表abcdefghijklmnopqrstuvwxyzRFAPCBZDQVJHKMWGSYUIXELNTO明文/密文meetmeafterclassKCCIKCRBUCYAHRUU密鑰空間26！>10^25單表例子加密Plain:abcdefghijklmnopqrstuvwxyz

Cipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA解密Ciphertext:WIRFRWAJUHYFTSDVFSFUUFYAPlaintext:ifwewishtoreplacelettersCipher:ABCDEFGHIJKLMNOPQRSTUVWXYZPlain:sgmakexofhbvqzujdwlptcinry分析Monoalphabetic

Caesar,Shift,Affine是Monoalphabetic的特例Monoalphabetic

替代沒有去除統(tǒng)計規(guī)律普通英文中各個字母出現(xiàn)的統(tǒng)計概率

英語字母中常見的組合古典密碼的統(tǒng)計分析攻擊法單詞出現(xiàn)概率組合：

密碼攻擊：統(tǒng)計分析攻擊所謂統(tǒng)計分析攻擊就是指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。

統(tǒng)計分析攻擊在歷史上為破譯密碼作出過極大的貢獻(xiàn)。許多古典密碼都可以通過統(tǒng)計分析而破譯。

跳舞的小人

Dancingmen福爾摩斯探案-歸來記

跳舞的小人

Dancingmen福爾摩斯接到一位莊園主人希爾頓·丘比特先生的信，信上說他家最近到處出現(xiàn)神秘的跳舞的小人的圖畫，他還以為是小孩子畫的，可是妻子每次見到都幾乎嚇出魂來。福爾摩斯讓莊園主人把那些圖案，臨摹在紙上帶給他。這幾個晚上，福爾摩斯未曾合眼，他仔細(xì)地分析這些跳舞的小人，原來這些跳舞的小人圖畫背后，竟然隱藏了一個神秘的陰謀……跳舞的小人AMHEREABESLANEYE來源于《密碼學(xué)概論》單表攻擊步驟（已經(jīng)知道算法）先得有足夠多的密文幾十個明文得有明確的意義(古典算法時通常是這樣的)統(tǒng)計密文中各個字母的出現(xiàn)概率結(jié)合明文的統(tǒng)計猜測出現(xiàn)得最多密文字母對應(yīng)明文字母e(或t、a)，最少的是z(或j)猜測出現(xiàn)得最多密文字母雙組是th觀察所謂的明文，并重試攻擊單表示例密文頻率統(tǒng)計（基于P25密文）

P－13.33，Z－11.67 S,U－8.33，O－7.50 M－6.67，H－5.83猜測

P,Z可能是e,t S,U,O,M,H大約是r,n,i,o,a,s*明文在P262.2.3Playfair密碼每兩個明文字母替換為另外兩個密文字母

aa

abacadae

af……az

siiduiweiiop……kl

babbbc

bdbebf……bz

yu

qw

sa

po

ee

eq……kk …… …… …… ……該表共有26×26＝676項(xiàng)密鑰空間達(dá)676!Playfair分析比單字母代換安全性好 需要更多的密文（幾百個字母） 雙字母的統(tǒng)計規(guī)律仍沒有被打破*幾種密文的 相對頻率對比2.2.4Hill密碼C＝KP： {0,1,2,…25}=Z26 c1 k11k12k13 p1 c2 ＝ k21k22k32 p2 c3 k31k32k33 p3即：

c1=k11*p1+k12*p2+k13*p3 c2=k21*p1+k32*p2+k23*p3 c3=k31*p1+k32*p2+k33*p3*矩陣K得有逆KK-1=K-1K=I，即K的行列式得非零Hill分析不能抵抗已知明文攻擊

c1

c1

c1

k11k12k13p1

p1

p1

c2

c2

c2

＝ k21k22k32p2

p2

p2

c3

c3

c3

k31k32k33p3

p3

p3 *已知三個(明文、密文)對，求K作業(yè)2.5ciphertext:SIDKHKDMAFHCRKIABIESHIMCKDLFEAILAplaintext:

basilisktoleviathanblakeiscontactb. Itisamonalphabeticcipherandsoeasilybreakable.c. Thelastsentencemaynotcontainallthelettersofthealphabet.Ifthefirstsentenceisused,thesecondandsubsequentsentencesmayalsobeuseduntilall26lettersareencountered.維吉尼亞(Vigenere)密碼發(fā)明了多字母替換密碼（使用多個單字母替換表因此一個字母可以被多個字母替換。而密文字母也可以表示為多個明文字母。方法：密鑰寫在明文的上面，并不斷重復(fù)書寫，這樣每個明文字母都與一個密鑰中的字母關(guān)聯(lián)。然后將明文字母和密文字母的配對,按照密鑰字母作為行，明文字母作為列來查Vigenere表得到密文。例如：密鑰key=hold明文m=thisistheplaintextholdholdholdholdhothisistheplaintext2.2.5多表密碼PolyalphabeticCipher維幾尼亞密碼的代替表明文字母密鑰字母密鑰字母為h,明文字母為t時查表得密文字母為a

abcdefghijklmnopqrstuvwxyzaabcdefghijklmnopqrstuvwxyzbbcdefghijklmnopqrstuvwxyzaccdefghijklmnopqrstuvwxyzabddefghijklmnopqrstuvwxyzabceefghijklmnopqrstuvwxyzabcdffghijklmnopqrstuvwxyzabcdeg

ghijklmnopqrstuvwxyzabcdefhhijklmnopqrstuvwxyzabcdefgiijklmnopqrstuvwxyzabcdefghjjklmnopqrstuvwxyzabcdefghikklmnopqrstuvwxyzabcdefghijllmnopqrstuvwxyzabcdefghijkmmnopqrstuvwxyzabcdefghijklnnopqrstuvwxyzabcdefghijklmoopqrstuvwxyzabcdefghijklmnppqrstuvwxyzabcdefghijklmnoqqrstuvwxyzabcdefghijklmnoprrstuvwxyzabcdefghijklmnopqsstuvwxyzabcdefghijklmnopqrttuvwxyzabcdefghijklmnopqrsuuvwxyzabcdefghijklmnopqrstvvwxyzabcdefghijklmnopqrstuwwxyzabcdefghijklmnopqrstuvxxyzabcdefghijklmnopqrstuvwy

yzabcdefghijklmnopqrstuvwxzzabcdefghijklmnopqrstuvwxy維幾尼亞密碼的代替表明文字母密鑰字母密鑰字母為o,明文字母為t時查表得密文字母為h

abcdefghijklmnopqrstuvwxyzaabcdefghijklmnopqrstuvwxyzbbcdefghijklmnopqrstuvwxyzaccdefghijklmnopqrstuvwxyzabddefghijklmnopqrstuvwxyzabceefghijklmnopqrstuvwxyzabcdffghijklmnopqrstuvwxyzabcdeg

ghijklmnopqrstuvwxyzabcdefhhijklmnopqrstuvwxyzabcdefgiijklmnopqrstuvwxyzabcdefghjjklmnopqrstuvwxyzabcdefghikklmnopqrstuvwxyzabcdefghijllmnopqrstuvwxyzabcdefghijkmmnopqrstuvwxyzabcdefghijklnnopqrstuvwxyzabcdefghijklmoopqrstuvwxyzabcdefghijklmnppqrstuvwxyzabcdefghijklmnoqqrstuvwxyzabcdefghijklmnoprrstuvwxyzabcdefghijklmnopqsstuvwxyzabcdefghijklmnopqrttuvwxyzabcdefghijklmnopqrsuuvwxyzabcdefghijklmnopqrstvvwxyzabcdefghijklmnopqrstuwwxyzabcdefghijklmnopqrstuvxxyzabcdefghijklmnopqrstuvwy

yzabcdefghijklmnopqrstuvwxzzabcdefghijklmnopqrstuvwxyVigenère分析分析列寬N（步長）洞察：如果猜中步長，則其統(tǒng)計分布符合單表的對應(yīng)情況分析N個單表密碼結(jié)合列間關(guān)系*建議N要大

one-timepad

1、D＝E＝XOR 2、K是真隨機(jī)的，且和P等長 這個算法也是理論上安全的唯一的算法2.2.6一次一密one-timepad2.2.6一次一密one-timepad思路：密鑰和明文一樣長（而不是和Vigenère

那樣重復(fù)使用某個單詞）哪一個是真正的明文？ 事實(shí)上，你可以產(chǎn)生任何你想要的明文。ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTSpxlmvmsydofuyrvzwc

tnlebnecvgdupahfzzlmnyihmrmustardwiththecandlestickinthehallANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTSmfugpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwtmissscarletwiththeknifeinthelibraryOne-timePad再例舉例：哪一個明文/密鑰是正確的呢？密文IPKLPSFHGQ密鑰UCGSHGBSGN（猜）明文onetimepad “onetimepad”密文IPKLPSFHGQ密鑰DBQUBQUTEG（再猜）

明文fouroclock “fouro’clock”一次一密的安全性是唯一具有理論安全性的算法也可以直接用于二進(jìn)制（XOR）流算法就是使用密鑰為種子產(chǎn)生偽隨機(jī)序列并和明文XOR太不方便使用，密鑰太長（和明文等長），難于產(chǎn)生、傳輸、保存等。在極端場合仍在使用（外交?）2.3置換技術(shù)Substitution

Transposition

不是替代，而是重排明文（“洗牌”）。比如加密 “meetmeafterthetogaparty”密文：

“MEMATRHTGPRYETEFETEOAAT”明文：transpositioncryptosystem密鑰：

=(352614)密文：上述將明文加密成密文的過程是：①將明文每６個字母分成一組（最后不夠一組時用字母x補(bǔ)足）；②作為密鑰的置換=(352614)③依據(jù)置換

,按列讀出就是密文。SIPTXAIRYXTDNOMPOTEXRSCSXNTYSX2.4轉(zhuǎn)輪機(jī)Rotor多表算法動態(tài)演化中的表請閱讀資料Three-RotorMachineWithWiringRepresentedbyNumberedContacts

ENIGMA

ENIGMA

示圖

破譯實(shí)例二戰(zhàn)EnigmaRSAchallengeRSA、DEShttp:///

超級計算TOP500 NSA 2.5隱寫術(shù)Steganography藏匿

暗語、暗喻、暗號

藏頭詩

特殊墨水

－施耐庵/吳用蘆花灘上有扁舟俊杰黃昏獨(dú)自游義到盡頭原是命反躬逃難必?zé)o憂這是一個信息隱藏（不引起注意）的例子數(shù)字水印DigitalWatermarkApatternofbitsinsertedintoadigitalimage,audioorvideofilethatidentifiesthefile'scopyrightinformation(author,ri