現(xiàn)代密碼學(xué)理論第二講古典密碼學(xué)

1、現(xiàn)代密碼學(xué)理論Modern Cryptography第二講 古典密碼學(xué)代換密碼及其密碼分析單表代換密碼與頻率分析多表代換密碼置換密碼及其密碼分析古典密碼學(xué)的意義現(xiàn)代密碼學(xué)與古典密碼學(xué)的區(qū)別古典密碼（Classical Cipher） 古典密碼是密碼學(xué)的淵源，這些密碼大都比較簡(jiǎn)單，可用手工或機(jī)械操作實(shí)現(xiàn)加解密，現(xiàn)在已很少采用了。然而，研究這些密碼的原理，對(duì)于理解、構(gòu)造和分析現(xiàn)代密碼都是十分有益的。代換密碼和置換密碼代換密碼（Substitution Cipher)是明文中的每一個(gè)字符被替換成密文中的另一個(gè)字符。接收者對(duì)密文做反向替換就可以恢復(fù)出明文。置換密碼(Permutation Cipher

2、)又稱換位密碼（Transposition Cipher)，加密過(guò)程中明文的字母保持相同，但順序被打亂了。代換密碼(Substitution Cipher) 明文字母表A ： Zq=0, 1, , q-1 明文消息是長(zhǎng)為L(zhǎng)個(gè)字母串，稱為明文組，以m表示， m=(m0 m1, mL-1) miZq m也稱作L-報(bào)文(L-gram)，它是定義在ZqL上的隨機(jī)變量，ZqL是Zq上的L維矢量空間。L=1為單字母報(bào)(1-gram)，L=2為雙字母報(bào)(Digrams)，L=3為三字母報(bào)(Trigrams)。明文空間m，mZqL。 密文字母集A ：Zq=(0, 1, q-1)表示。密文組 c=(c0, c1

3、, ., cL-1) cZqc是定義在L維矢量空間ZqL上的隨機(jī)變量。密文空間C=c, cZqL。一般當(dāng)A = A時(shí)有C =c, cZqL，即明文和密文由同一字母表構(gòu)成。代換密碼加密變換：明文空間到密文空間的映射： f：mc mM， c C在11的映射下，存在有逆映射f-1，使 f-1(c)=f-1f(m)=m m M ，c C加密變換通常是在密鑰控制下變化的，即 c=f(m, k)=Ek(m)式中，k K ， K為密鑰空間。一個(gè)密碼系統(tǒng)就是在f和密鑰k作用下，由ZqLZqL的映射，或以ZqL中的元素代換ZqL中的元素，在這意義下，稱這種密碼為代換密碼(Substitution Cipher)

4、。L=1時(shí)，稱作單字母或單碼代換(Monogram Substition)，也稱為流密碼(Stream Cipher)。L1時(shí)稱作多字母或多碼代換(Polygram Substition)，也稱為分組密碼。代換密碼代換網(wǎng)絡(luò) m=(m0, m1,mL-1) c=(c0, c1,cL-1) 明文源 k密鑰源代換密碼 一般選擇q=q，即明文和密文字母表相同。此時(shí)， L=L， f可以構(gòu)造成11的映射，密碼沒(méi)有數(shù)據(jù)擴(kuò)展。 LL，則明文數(shù)據(jù)將被壓縮(Compression)。函數(shù)f不是可逆的，保密通信LL。LL 可用在數(shù)據(jù)認(rèn)證系統(tǒng)中。 單表代換(Monoalphabetic Substitution)：在

5、A = A 、q=q和L=1時(shí)，對(duì)所有明文字母，都用一個(gè)固定的代換進(jìn)行加密。 多表代換(Polyalphabetic Substitution) ：在A = A 、q=q和L=1時(shí)，用一個(gè)以上的代換表進(jìn)行加密。， 這是古典密碼中的兩種重要體制，曾得到過(guò)廣泛的應(yīng)用。單表代換密碼單表代換密碼：明文字母表到密文字母表的固定映射， f：ZqZq令明文m=m0m1.，則相應(yīng)密文為 c=Ek(m)=c0c1.=f(m0)f(m1). 1移位代換密碼 (Shift Substitution Cipher) 加密變換：Ek (i)=(i+k)j mod q 0 i , j q K=k0k1個(gè)字母進(jìn)行代換， 。

6、優(yōu)點(diǎn)：隱蔽或均勻化字母的自然頻度，利于抗擊統(tǒng)計(jì)分析。 矩陣變換密碼，利用矩陣變換描述的多字母代換密碼， f：ZLqZLq f是線性變換時(shí)可用一個(gè)Zq上的LL階矩陣K表示，K=(kij)為密鑰。若K是滿秩的，則變換為一一映射，且存在有逆變換K-1，使KK-1=K-1 K=I(LL階單位方陣)。 明文矢量： m=(m1, m2, , mL)， 密文矢量： c=(c1, c2, , cL)=mK=c 解密變換： cK-1=m.1，希爾密碼Hill 1929 明文組： m=(m1, m2, , mL) 密文組： cmK+b mod q b=(b1, b2, , bL)是Zq上的L維矢量，K是Zq上的L

7、L階滿秩矩陣。式中，“”為矢量相加。： 解密運(yùn)算： m(c-b)K-1 mod q 當(dāng)K是單位方陣時(shí)，就退化為前面介紹的維吉尼亞密碼。Hill密碼的例子例子：當(dāng)q=26, l=2, b=(0,0)時(shí)，Hill密碼分析完全隱藏了字符(對(duì))的頻率信息惟密文攻擊相對(duì)較難線性變換的安全性很脆弱，易被已知明文攻擊擊破。對(duì)于一個(gè)mxm的hill密碼，假定有m個(gè)明文-密文對(duì)，明文和密文的長(zhǎng)度都是m.可以把明文和密文對(duì)記為：Pj=(p1j,p2j,.pmj)和Cj=(C1j,C2j,Cmj), Cj=PjK,1j m 定義mxm的方陣X=（Pij) Y=(Cij),得到Y(jié)=XK，K=X-1Y例子：2， Pla

8、yfair Playfair在1854年發(fā)明了Playfair密碼。在第一次世界大戰(zhàn)中英國(guó)人就使用這種密碼。（ invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair ） Playfair將明文中的雙字母組合作為一個(gè)單元對(duì)待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。I與J視為同一字符，55變換矩陣為CIPHERABDFGKLM NOQSTUVWXYZ加密規(guī)則是按成對(duì)字母加密，規(guī)則為“相同對(duì)中的字母加分隔符(如x)，同行取右邊，同列取下邊，其他取交叉”，例如下面的分組加密方法。明文：ballo

9、on 單詞中的ll為相同字符，所以分組為：ba lx lo on明文：he，h和e在矩陣中同一行，都取右邊的字符，密文為：EC明文：dm，d和m在矩陣中同一列，都取下面的字符，密文為：MT明文：kt，k和t在矩陣中不同行也不同列，取交叉頂點(diǎn)上的字符，密文為：MQ明文：OD ，O和D在矩陣中不同行也不同列，取交叉頂點(diǎn)上的字符，密文為：TR以這個(gè)55變換矩陣為例，可以對(duì)單詞進(jìn)行加密，加密結(jié)果如下表所示。明文分組密文balloonba lx lo ondb sp gs ugbookbo oksr qgfillfi lx lxae sp sp Playfair密碼算法有2626=676種字母對(duì)組合，字

10、符出現(xiàn)幾率一定程度上被均勻化，基于字母頻率的攻擊比較困難，但依然保留了相當(dāng)?shù)慕Y(jié)構(gòu)信息。古典密碼 置換密碼(Permutation Cipher)。當(dāng)矩陣變換密碼的變換矩陣為一置換陣時(shí)，相應(yīng)密碼就是置換密碼。亦稱換位密碼(Transposition Cipher)。它是對(duì)明文L長(zhǎng)字母組中的字母位置進(jìn)行重新排列，而每個(gè)字母本身并不改變。 明文：m=m1 m2,mL。， 加密變換：c=(c1,c2,cL)=E(m)=m(1) m(2) m(L)。 置換矩陣所決定置換為 解密變換： Because the cipher doesnt change any of the characters, the

11、ciphertext will have exactly the same letter frequencies as the underlying plaintext. This means that the cipher can in many cases be identified as a transposition by the close similarity of its letter statistics with the letter frequencies of the underlying language Breaking the permutation cipher

12、Because the cipher operates on blocks of size e, the plaintext and the ciphertext have to have a length which is some multiple of L. This causes two weaknesses in the system: first, the plaintext may have to be padded (if the padding is identifiable then part of the key is revealed) and second, info

13、rmation relating to the length of the key is revealed by the length of the ciphertext. To see this, note that if the ciphertext is of length i then L must be one of the divisors of i. With the different possible key sizes different possible permutations are tried to find the permutation which results in the highest number of frequent bigrams and trigrams as found in the underlying language of the plaintext. 對(duì)稱密碼體制主要分為分組密碼和流密碼對(duì)稱密碼的兩個(gè)基本運(yùn)算代換和置換(Su