Chap2古典密碼密碼學(xué)的發(fā)展歷史三個(gè)階段：古代加密方法、古典密碼和近代密碼。

1.古代加密方法（手工階段）

從某種意義上說，戰(zhàn)爭(zhēng)是科學(xué)技術(shù)進(jìn)步的催化劑。人類自從有了戰(zhàn)爭(zhēng)，就面臨著通信安全的需求，密碼技術(shù)源遠(yuǎn)流長(zhǎng)。

古代加密方法大約起源于公元前440年出現(xiàn)在古希臘戰(zhàn)爭(zhēng)中的隱寫術(shù)。當(dāng)時(shí)為了安全傳送軍事情報(bào)，奴隸主剃光奴隸的頭發(fā)，將情報(bào)寫在奴隸的光頭上，待頭發(fā)長(zhǎng)長(zhǎng)后將奴隸送到另一個(gè)部落，再次剃光頭發(fā)，原有的信息復(fù)現(xiàn)出來，從而實(shí)現(xiàn)這兩個(gè)部落之間的秘密通信。

公元前400年，斯巴達(dá)人就發(fā)明了“塞塔式密碼”，即把長(zhǎng)條紙螺旋形地斜繞在一個(gè)多棱棒上，將文字沿棒的水平方向從左到右書寫，寫一個(gè)字旋轉(zhuǎn)一下，寫完一行再另起一行從左到右寫，直到寫完。解下來后，紙條上的文字消息雜亂無章、無法理解，這就是密文,但將它繞在另一個(gè)同等尺寸的棒子上后，就能看到原始的消息。這是最早的密碼技術(shù)。

SpartanScytale,c.500B.C.塞塔式密碼

斯巴達(dá)人用于加解密的一種軍事設(shè)備，發(fā)送者把一條羊皮螺旋形地纏在一個(gè)圓柱形棒上思想：置換（permutation)我國(guó)古代也早有以藏頭詩、藏尾詩、漏格詩及繪畫等形式，將要表達(dá)的真正意思或“密語”隱藏在詩文或畫卷中特定位置的記載，一般人只注意詩或畫的表面意境，而不會(huì)去注意或很難發(fā)現(xiàn)隱藏其中的“話外之音”。

比如：我畫藍(lán)江水悠悠，愛晚亭楓葉愁。秋月溶溶照佛寺，香煙裊裊繞輕樓2.古典密碼（機(jī)械階段）

古典密碼的加密方法一般是文字置換，使用手工或機(jī)械變換的方式實(shí)現(xiàn)。古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出近代密碼系統(tǒng)的雛形，它比古代加密方法復(fù)雜，其變化較小。古典密碼的代表密碼體制主要有：?jiǎn)伪泶婷艽a、多表代替密碼及轉(zhuǎn)輪密碼。

3.近代密碼（計(jì)算機(jī)階段）

密碼形成一門新的學(xué)科是在20世紀(jì)70年代，快速電子計(jì)算機(jī)和現(xiàn)代數(shù)學(xué)方法一方面為加密技術(shù)提供了新的概念和工具，另一方面也給破譯者提供了有力武器。他們可以輕易地?cái)[脫原先用鉛筆和紙進(jìn)行手工設(shè)計(jì)時(shí)易犯的錯(cuò)誤，也不用再面對(duì)用電子機(jī)械方式實(shí)現(xiàn)的密碼機(jī)的高額費(fèi)用?？傊?，利用電子計(jì)算機(jī)可以設(shè)計(jì)出更為復(fù)雜的密碼系統(tǒng)。目錄密碼學(xué)的起源、發(fā)展和現(xiàn)狀密碼學(xué)基本概念典型幾種古典密碼技術(shù)密碼學(xué)發(fā)展階段1949年之前密碼學(xué)是一門藝術(shù)1949～1975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向——公鑰密碼學(xué)第1階段－古典密碼

密碼學(xué)還不是科學(xué),而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段出現(xiàn)，針對(duì)的是字符簡(jiǎn)單的密碼分析手段出現(xiàn)主要特點(diǎn)：數(shù)據(jù)的安全基于算法的保密第1階段－古典密碼Phaistos圓盤，一種直徑約為160mm的Cretan-Mnoan粘土圓盤，始于公元前17世紀(jì)。表面有明顯字間空格的字母，至今還沒有破解。20世紀(jì)早期密碼機(jī)第1階段－古典密碼1883年Kerchoffs第一次明確提出了編碼的原則：加密算法應(yīng)建立在算法的公開不影響明文和密鑰的安全。這一原則已得到普遍承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為古典密碼和近代密碼的分界線。

計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能相關(guān)技術(shù)的發(fā)展1949年Shannon的“TheCommunicationTheoryofSecretSystems”

1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實(shí)驗(yàn)室的HorstFeistel等幾篇技術(shù)報(bào)告主要特點(diǎn)：數(shù)據(jù)的安全基于密鑰而不是算法的保密

第2階段1949~19751976年：Diffie&Hellman的

“NewDirectionsinCryptography”

提出了不對(duì)稱密鑰密1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法主要特點(diǎn)：公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡艿?階段1976~1977年DES正式成為標(biāo)準(zhǔn)80年代出現(xiàn)“過渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代對(duì)稱密鑰密碼進(jìn)一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現(xiàn)2001年Rijndael成為DES的替代者第3階段1976~目錄密碼學(xué)的起源、發(fā)展和現(xiàn)狀密碼學(xué)基本概念典型幾種古典密碼技術(shù)基本概念密碼學(xué)(Cryptology):是研究信息系統(tǒng)安全保密的科學(xué).密碼編碼學(xué)(Cryptography):主要研究對(duì)信息進(jìn)行編碼,實(shí)現(xiàn)對(duì)信息的隱蔽.密碼分析學(xué)(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.明文（Plaintext）：消息的初始形式；密文（CypherText）：加密后的形式記： 明文記為P且P為字符序列，P=[P1,P2,…,Pn]

密文記為C,C=[C1,C2,…,Cn]

明文和密文之間的變換記為C=E(P)及P=D(C)

其中C表示密文，E為加密算法；P為明文，D為解密算法 我們要求密碼系統(tǒng)滿足：P=D(E(P))基本概念

加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的,分別稱為加密密鑰(EncryptionKey)和解密密鑰(DecryptionKey).明文明文密文加密算法解密算法密鑰密鑰

需要密鑰的加密算法，記為：C=E(K,P),即密文消息同時(shí)依賴于初始明文和密鑰的值。實(shí)際上，E是一組加密算法，而密鑰則用于選擇其中特定的一個(gè)算法。加密與解密的密鑰相同，即：P=D(K,E(K,P))

加密與解密的密鑰不同，則：P=D(KD,E(KE,P))基本概念常規(guī)加密簡(jiǎn)化模型

加密算法足夠強(qiáng)大：僅知密文很難破譯出明文基于密鑰的安全性，而不是基于算法的安全性：基于密文和加/解密算法很難破譯出明文算法開放性：開放算法，便于實(shí)現(xiàn)常規(guī)加密的安全性常規(guī)加密系統(tǒng)的模型密碼體系是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）任意k∈K，有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函數(shù)，滿足dk(ek(x))=x

，這里x∈P。密碼體系形式化描述

保密內(nèi)容密鑰數(shù)量明文處理的方式密碼編碼系統(tǒng)分類

受限制的（restricted)算法算法的保密性基于保持算法的秘密（古典）基于密鑰（key-based)的算法算法的保密性基于對(duì)密鑰的保密（近代：對(duì)稱+非對(duì)稱）保密內(nèi)容

對(duì)稱密碼算法（symmetriccipher)

加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個(gè)易于推出另一個(gè)又稱秘密密鑰算法或單密鑰算法非對(duì)稱密鑰算法（asymmetriccipher)

加密密鑰和解密密鑰不相同，從一個(gè)很難推出另一個(gè)又稱公開密鑰算法（public-keycipher)

公開密鑰算法用一個(gè)密鑰進(jìn)行加密,而用另一個(gè)進(jìn)行解密其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡(jiǎn)稱公鑰。解密密鑰必須保密,又稱私人密鑰（privatekey)私鑰，簡(jiǎn)稱私鑰密鑰數(shù)量

分組密碼（blockcipher)

將明文分成固定長(zhǎng)度的組，用同一密鑰和算法對(duì)每一塊加密，輸出也是固定長(zhǎng)度的密文。

流密碼（streamcipher)

又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文。明文處理方式密碼分析試圖破譯單條消息試圖識(shí)別加密的消息格式，以便借助直接的解密算法破譯后續(xù)的消息試圖找到加密算法中的普遍缺陷（無須截取任何消息）密碼分析的條件與工具

已知加密算法截取到明文、密文中已知或推測(cè)的數(shù)據(jù)項(xiàng)數(shù)學(xué)或統(tǒng)計(jì)工具和技術(shù)語言特性計(jì)算機(jī)技巧與運(yùn)氣密碼分析類型加密方案的安全性無條件安全：無論提供的密文有多少，如果由一個(gè)加密方案產(chǎn)生的密文中包含的信息不足以唯一地決定對(duì)應(yīng)的明文除了一次一密的方案外，沒有無條件安全的算法安全性體現(xiàn)在任意一條：破譯的成本超過加密信息的價(jià)值破譯的時(shí)間超過該信息有用的生命周期密鑰搜索所需平均時(shí)間目錄密碼學(xué)的起源、發(fā)展和現(xiàn)狀密碼學(xué)基本概念典型幾種古典密碼技術(shù)

替代置換轉(zhuǎn)子機(jī)經(jīng)典加密技術(shù)

明文的字母由其它字母或數(shù)字或符號(hào)代替若該明文被視為一個(gè)比特序列，則替代涉及到用密文比特模式代替明文比特模式替代（代替）代替密碼簡(jiǎn)單代替密碼（simplesubstitutioncipher),又稱單字母密碼（monoalphabeticcipher):明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替。愷撒密碼破譯以下密文：wuhdwblpsrvvleohTREATYIMPOSSIBLECi=E(Pi)=Pi+3加密算法：字母表：(密碼本）

ABCDEFGHIJKLMNOPQRSTUVWXYZdefghijklmnopqrstuvwxyzabc愷撒密碼(caesarcipher)破譯以下密文：wuhdwblpsrvvleohTREATYIMPOSSIBLECi=E(Pi)=Pi+3加密算法：字母表：(密碼本）ABCDEFGHIJKLMNOPQRSTUVWXYZ（對(duì)應(yīng)數(shù)字0:a，1….25:z)defghijklmnopqrstuvwxyzabc愷撒密碼的改進(jìn)已知加密與解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25個(gè)可能的密鑰k，適用Brute-ForceCryptanalysis明文的語言是已知的且易于識(shí)別愷撒密碼的特點(diǎn)單字母密碼（簡(jiǎn)單替換技術(shù)）簡(jiǎn)單，便于記憶缺點(diǎn)：結(jié)構(gòu)過于簡(jiǎn)單，密碼分析員只使用很少的信息就可預(yù)言加密的整個(gè)結(jié)構(gòu)其它單字母替換使用密鑰keyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyz泄露給破譯者的信息更少其它單字母替換對(duì)字母進(jìn)行無規(guī)則的重新排列

E(i)=3*imod26 ABCDEFGHIJKLMNOPQRSTUVWXYZ adgjmpsvybehknqtwzcfilorux例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ對(duì)抗頻率分析的辦法多字母密碼（ployalphabeticcipher)：明文中多個(gè)字母一起加密多表以一系列（兩個(gè)以上）代換表依此對(duì)明文消息的字母進(jìn)行代換的方法。

多字母密碼-PlayfairPlayfair:將明文中的雙字母組合作為一個(gè)單元對(duì)待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。5×5變換矩陣:I與J視為同一字符

CIPHE RABDF GKLMN(cipher) OQSTU VWXYZ加密規(guī)則:按成對(duì)字母加密相同對(duì)中的字母加分隔符(如x)balloon

balxloon

同行取右邊:he

EC

同列取下邊:dm

MT

其他取交叉:kt

MQOD

TRPlayfair舉例以前面的5×5變換矩陣(cipher)為例

CIPHE RABDF GKLMN(cipher) OQSTU VWXYZ(1)balloonbalxloondbspgsug(2)bookbookrsqg(3)fillfilxlxaespspPlayfair密碼分析字符出現(xiàn)幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當(dāng)?shù)慕Y(jié)構(gòu)信息多字母密碼：Hill密碼（1929）取m個(gè)連續(xù)的明文字母，并且用m個(gè)密文字母替代，如何替代由m個(gè)線性方程決定，每個(gè)字母對(duì)應(yīng)一個(gè)數(shù)值(a=0,b=1,…,z=25)。Y=KX，K=YX-1K是一個(gè)m*m矩陣,在Z/(26)上可逆,即存在K-1使得:

KK-1=I(在Z/(26))。模為26

例子：當(dāng)m=2時(shí)，明文元素x=(x1,x2),密文元素y=(y1,y2)：

(y1,y2)=(x1,x2)K

若K=,可得K-1=若對(duì)明文july加密，它分成2個(gè)元素（j,u),(l,y),分別對(duì)應(yīng)于（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是對(duì)july加密的結(jié)果為DELW。為了解密，Bob計(jì)算

且因此，得到了正確的明文“july”Hill密碼特點(diǎn)完全隱藏了字符(對(duì))的頻率信息線性變換的安全性很脆弱，易被已知明文攻擊擊破。對(duì)于一個(gè)mxm的hill密碼，假定有m個(gè)明文-密文對(duì)，明文和密文的長(zhǎng)度都是m.可以把明文和密文對(duì)記為：模q算術(shù)-i同余：給定任意整數(shù)a和q，以q除a，余數(shù)是r，則可以表示為a=sq+r,0r<q，其中s=[a/q],表示小于a/q的最大整數(shù)。定義r為amodq的剩余，記為ramodq.

若整數(shù)a和b有(amodq)=(bmodq)，則稱a與b在modq下同余。對(duì)于滿足{r}={a|a=sq+r,sZ}的整數(shù)集稱為同余類。模運(yùn)算有下述性質(zhì)：（1）若q|(a-b)，則abmodq（2）(amodq)=(bmodq)意味abmodq（3）abmodq等價(jià)于bamodq（4）若abmodq且bcmodq

，則acmodq模q算術(shù)-ii模算術(shù)（ModularArithmatic)

在modq的q個(gè)剩余類集{0，1，2，…,q-1}上可以定義加法和乘法運(yùn)算如下:

加法:(amodq)+(bmodq)=(a+b)modq

乘法:(amodq)(bmodq)=(ab)modq多表加密--Vigenérecipher是一種多表移位代替密碼設(shè)d為一固定的正整數(shù)，d個(gè)移位代換表

=（1，2,…d)由密鑰序列K＝（k1,k2,…,kd)給定，第i+td個(gè)明文字母由表

i決定，即密鑰ki決定

ek(xi+td)=(xi+td+ki,)modq=y

dk(yi+td)=(xi+td-ki)modq=x例子：q=26,x=polyalphabeticcipher,K=RADIO明文x=POLYALPHABETICCIPHER密鑰k=RADIORADIORADIORADIO密文y=GOOGOCPKTPNTLKQZPKMFVigenérecipher-破譯依然保留了字符頻率某些統(tǒng)計(jì)信息重碼分析法：間距是密鑰長(zhǎng)度整數(shù)倍的相同子串有相同密文，反過來，密文中兩個(gè)相同的子串對(duì)應(yīng)的密文相同的可能性很大。

abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425密鑰:cryptographycryptographycr明文:yourpackagereadyroomathree密文:AFSGIOIPGPGVernam密碼1918年，GillbertVernam建議密鑰與明文一樣長(zhǎng)并且沒有統(tǒng)計(jì)關(guān)系的密鑰內(nèi)容，他采用的是二進(jìn)制數(shù)據(jù): 加密：Ci=Pi

Ki

解密Pi=Ci

Ki

核心：構(gòu)造和消息一樣長(zhǎng)的隨機(jī)密鑰

總結(jié)替換是密碼學(xué)中有效的加密方法。本世紀(jì)上半葉用于外交通信破譯威脅來自頻率分布重合指數(shù)考慮最可能的字母及可能出現(xiàn)的單詞重復(fù)結(jié)構(gòu)分析及克思斯基方法持久性、組織性、創(chuàng)造性和運(yùn)氣

通過執(zhí)行對(duì)明文字母的置換，取得一種類型完全不同的映射，即置換密碼。若該明文被視為一個(gè)比特序列，則置換涉及到用密文比特模式代替明文比特模式置換換位密碼把明文按列寫入,按行讀出密鑰包含3方面信息:行寬,列高,讀出順序key:4312567(先讀第一列)plaintext:attackpostponeduntiltwoamxyzciphertext:TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的統(tǒng)計(jì)信息使用多輪加密可提高安全性K是一個(gè)m*m矩陣,在Z/(26)上可逆,即存在K-1使得:

KK-1=I(在Z/(26))對(duì)每一個(gè)k∈K,定義ek(x)=xK(mod26)

和dk(y)=yK-1(mod26)注：明文與密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)為同余類環(huán)在這個(gè)環(huán)上的可逆矩陣Amxm,是指行列式detAmxm的值∈Z*/(26),它為Z/(26)中全體可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}這里的加密與解密僅僅用了置換，無代數(shù)運(yùn)算例子：設(shè)m=6，取加密密鑰