第三講-古典密碼

網(wǎng)絡(luò)信息安全陳羽中yzchen1979@163.com密碼系統(tǒng)分類密碼系統(tǒng)的幾種分類:按執(zhí)行的操作替換(substitution)與置換(permutation)按密鑰的數(shù)量

單密鑰(對稱密鑰)與雙密鑰(公開密鑰)按明文處理方式

流密碼(streamcipher)與分組密碼(blockcipher)古典密碼基于字符的密碼替換（substitutioncipher)：就是明文中的每一個字符被替換成密文中的另一個字符,接收者對密文做反向替換就可以恢復(fù)出明文置換(permutationcipher):又稱換位密碼（transpositioncipher)：明文的字母保持相同，但順序被打亂了替換密碼單字母替換密碼（simplesubstitutioncipher),又稱單字母密碼(monoalphabeticcipher):明文的一個字符用相應(yīng)的一個密文字符代替。多字母替換密碼（ployalphabeticcipher)：明文中的字符映射到密文空間的字符還依賴于它在上下文中的位置。單字母替換密碼一.愷撒密碼

E(p)=(p+3)mod26

明文:abcdefghijklmnopqrstuvwxyz

密文:defghijklmnopqrstuvwxyzabc

例子:

明文：meetmeaftertheparty

密文：phhwphdiwhowkhsduwb給定加密的消息: phhwphdiwhowkhsduwb由于加解密算法已知可能嘗試的密鑰只有２6個明文的語言已知通過強力攻擊得到明文：meetmeaftertheparty.

移位密碼很容易受到唯密文攻擊單字母替換密碼分析單字母替換密碼(續(xù))二.密鑰短語密碼1.選擇密鑰并刪除重復(fù)字母.2.在明文的字母表下方從左往右寫下處理的后的密鑰,然后再寫剩余的字母即得密文字母表.

如密鑰短語密碼為:hello->helo

明文:abcdefghijklmnopqrstuvwxyz

密文:heloabcdfgijkmnpqrstuvwxyz任意的單表替換密碼:

明文:abcdefghijklmnopqrstuvwxyz

密文:sdvjkltioxcfawqzupyreghbam例子:crypt=>VPNZR密鑰空間為26!>4*1026通過字母的使用頻率破譯對單表替換密碼的統(tǒng)計分析攻擊例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ統(tǒng)計分析攻擊單一字母替換容易被攻破，因為反映了原來字母表的頻率數(shù)據(jù)分配給每個字母的符號數(shù)正比于該字母的相對頻率，則單字母的頻率信息就會完全被淹沒對明文的多個字母加密使用多表替換多表替換密碼多表替換密碼:以一系列（兩個以上）替換表依此對明文消息的字母進行替換的方法非周期多表替換密碼：替換表是非周期的無限序列,密鑰和明文長度相同周期多表替換密碼：替換表個數(shù)有限，重復(fù)使用。維吉尼亞密碼(1858)是一種多表移位替換密碼:設(shè)d為一固定的正整數(shù)，d個移位替換表=（1，2,…d)由密鑰序列K＝（k1,k2,…,kd)給定，第i+td個明文字母由表i決定，即密鑰ki決定

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

dk(yi+td)=(yi+td-ki)modq=x替換表維吉尼亞密碼(1858)例子:q=26,x=polyalphabeticcipher, K=RADIO密鑰字為RADIO,則相應(yīng)密鑰為(17,0,3,8,14)明文x=polyalphabeticcipher密鑰k=RADIORADIORADIORADIO密文y=GOOJOCPKTPNTLKQZPKMFPlayfair:將明文中的雙字母組合作為一個單元對待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。5×5變換矩陣的生成:I與J視為同一字符(取CIPHER作為密鑰) CIPHE RABDF GKLMN OQSTU VWXYZ多字母替換密碼-Playfair多字母替換密碼-Playfair明文的分組balloonballoon分組規(guī)則：1、相同字母在同一分組時：在該分組兩個字母之間插入字母X，對明文重新進行分組2、分組只有一個字母時：若發(fā)現(xiàn)情況1并進行調(diào)整后，最后一個分組仍然只有一個字母，在最后加入字母X。balloonbalxloon多字母替換密碼-Playfair加密規(guī)則:按成對字母加密1)若明文對在矩陣中是同行關(guān)系：將這對字母均向右移一格,如有字母在右邊界，則移動到同行左邊首字母。

heEC2)若明文對在矩陣中是同列關(guān)系：將這對字母均向下移一格。若有字母在下邊界，則移動到同列首字母。

dmMT3)其他情況取交叉:ktMQODTRPlayfair密碼以前面的5×5變換矩陣(cipher)為例

CIPHE RABDF GKLMN OQSTU VWXYZ (1)balloonbalxloondbspgsug (2)bookbookrsqg (3)fillfilxlxaespspPlayfair有26X26=676種字母對組合字符出現(xiàn)幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當?shù)慕Y(jié)構(gòu)信息Playfair密碼分析仿射密碼用形如e(x)=ax+b(mod26),a∈Z26,b∈Z26的加密函數(shù)的加密算法稱為仿射密碼，這類加密函數(shù)稱為仿射函數(shù)。(a=1時為移位密碼)(1)：要求解唯一的充要條件是gcd(a,26)=1(2)：從(1)可知,當且僅當a與26互素時，加密變換才是一一映射的，因此a的選擇有11種：

a=3,5,7,9,11,15,17,19,21,23,25密鑰空間大小12x26=312種！仿射密碼算法定義設(shè)P=C=Z26,K={(a,b)∈Z26*Z26|gcd(a,26)=1},對k=(a,b)∈K,定義:ek(x)=ax+b(mod26)dk(y)=a-1(y-b)(mod26)x,y∈Z26加密函數(shù)取形式為e(x)=ax(mod26),a∈Z26要求唯一解的充要條件是gcd(a,26)=1該算法描述為：設(shè)P=C=Z26，K={a∈Z26|gcd(a,26)=1},對k=a∈K,定義:ek(x)=ax(mod26)dk(y)=a-1(y)(mod26)x,y∈Z26仿射密碼-乘數(shù)密碼算法乘數(shù)密碼算法例子例子:a=9,

ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

cipher=>SUFLKX乘數(shù)密碼分析:對于乘數(shù)密碼，當且僅當a與２６互素時，加密變換才是一一映射的，因此a的選擇有１１種：

a=3,5,7,9,11,15,17,19,21,23,25

可能嘗試的密鑰只有1１個例子，設(shè)k＝（7，3），注意到7-1(mod26)=15,加密函數(shù)是ek(x)=7x+3,相應(yīng)的解密函數(shù)是dk(y)=15(y-3)=15y-19,易見

dk(ek(x)）=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)若加密明文：hot，首先轉(zhuǎn)換字母h,o,t成為數(shù)字7,14,19,然后加密：解密：（二)Hill密碼（1929）基于矩陣的線性變換:K是一個m*m矩陣,在Z26上可逆,即存在K-1使得:KK-1=I(在Z26)對每一個k∈K,定義ek(x)=xK(mod26)dk(y)=yK-1(mod26)明文與密文都是m元的向量(x1,x2…,xm);(y1,y2,…,ym)Hill密碼例子：當m=2時，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

K

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

且(11,24)

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

且因此，得到了正確的明文“july”一次一密方案-Vernam密碼1918年，GillbertVernam建議密鑰采用與明文一樣長并且沒有統(tǒng)計關(guān)系的密鑰內(nèi)容(隨機生成)，他采用的是二進制數(shù)據(jù):加密：Ci=Pi

Ki解密：Pi=Ci

Ki核心：構(gòu)造和消息一樣長的隨機密鑰

一次一密方案絕對安全但不實用，需要以某種安全的方法將與消息長度相等的密鑰傳送給接收方，以允許解密。而且，密鑰只使用一次，然后就被丟棄，增加了密鑰管理問題媒體訪問接入?yún)f(xié)議中使用了一次一密古典密碼安全性分析單表替換：字母頻度、重復(fù)字母模式、字母結(jié)合方式的統(tǒng)計特性不變多表替換：明文統(tǒng)計特性通過多表替換被隱藏古典密碼安全性分析假設(shè)從仿射密碼獲得的密文為FMXVEDKAPIIFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH.試破解該密文。統(tǒng)計各字母頻率，R出現(xiàn)8次，D出現(xiàn)6次，E,H,K各出現(xiàn)5次，F(xiàn),S,V各出現(xiàn)4次假定R(17)是e(4)的加密，D(3)是t(19)的加密，得a=6,b=19假定R是e的加密，E是t的加密,得a=8,b=11假定R是e的加密，K是t的加密，得a=3,b=5