第三講-古典密碼

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

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

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

E(p)=(p+3)mod26

明文:abcdefghijklmnopqrstuvwxyz

密文:defghijklmnopqrstuvwxyzabc

例子:

明文：meetmeaftertheparty

密文：phhwphdiwhowkhsduwb給定加密的消息: phhwphdiwhowkhsduwb由于加解密算法已知可能嘗試的密鑰只有２6個(gè)明文的語(yǔ)言已知通過(guò)強(qiáng)力攻擊得到明文：meetmeaftertheparty.

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

如密鑰短語(yǔ)密碼為:hello->helo

明文:abcdefghijklmnopqrstuvwxyz

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

明文:abcdefghijklmnopqrstuvwxyz

密文:sdvjkltioxcfawqzupyreghbam例子:crypt=>VPNZR密鑰空間為26!>4*1026通過(guò)字母的使用頻率破譯對(duì)單表替換密碼的統(tǒng)計(jì)分析攻擊例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ統(tǒng)計(jì)分析攻擊單一字母替換容易被攻破，因?yàn)榉从沉嗽瓉?lái)字母表的頻率數(shù)據(jù)分配給每個(gè)字母的符號(hào)數(shù)正比于該字母的相對(duì)頻率，則單字母的頻率信息就會(huì)完全被淹沒對(duì)明文的多個(gè)字母加密使用多表替換多表替換密碼多表替換密碼:以一系列（兩個(gè)以上）替換表依此對(duì)明文消息的字母進(jìn)行替換的方法非周期多表替換密碼：替換表是非周期的無(wú)限序列,密鑰和明文長(zhǎng)度相同周期多表替換密碼：替換表個(gè)數(shù)有限，重復(fù)使用。維吉尼亞密碼(1858)是一種多表移位替換密碼:設(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)=(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:將明文中的雙字母組合作為一個(gè)單元對(duì)待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。5×5變換矩陣的生成:I與J視為同一字符(取CIPHER作為密鑰) CIPHE RABDF GKLMN OQSTU VWXYZ多字母替換密碼-Playfair多字母替換密碼-Playfair明文的分組balloonballoon分組規(guī)則：1、相同字母在同一分組時(shí)：在該分組兩個(gè)字母之間插入字母X，對(duì)明文重新進(jìn)行分組2、分組只有一個(gè)字母時(shí)：若發(fā)現(xiàn)情況1并進(jìn)行調(diào)整后，最后一個(gè)分組仍然只有一個(gè)字母，在最后加入字母X。balloonbalxloon多字母替換密碼-Playfair加密規(guī)則:按成對(duì)字母加密1)若明文對(duì)在矩陣中是同行關(guān)系：將這對(duì)字母均向右移一格,如有字母在右邊界，則移動(dòng)到同行左邊首字母。

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

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

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

ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

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

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

可能嘗試的密鑰只有1１個(gè)例子，設(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是一個(gè)m*m矩陣,在Z26上可逆,即存在K-1使得:KK-1=I(在Z26)對(duì)每一個(gè)k∈K,定義ek(x)=xK(mod26)dk(y)=yK-1(mod26)明文與密文都是m元的向量(x1,x2…,xm);(y1,y2,…,ym)Hill密碼例子：當(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）,（11,24）,有（9,20）＝（99＋60,72＋140）＝（3,4）

且(11,24)

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

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

Ki解密：Pi=Ci

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

一次一密方案絕對(duì)安全但不實(shí)用，需要以某種安全的方法將與消息長(zhǎng)度相等的密鑰傳送給接收方，以允許解密。而且，密鑰只使用一次，然后就被丟棄，增加了密鑰管理問題媒體訪問接入?yún)f(xié)議中使用了一次一密古典密碼安全性分析單表替換：字母頻度、重復(fù)字母模式、字母結(jié)合方式的統(tǒng)計(jì)特性不變多表替換：明文統(tǒng)計(jì)特性通過(guò)多表替換被隱藏古典密碼安全性分析假設(shè)從仿射密碼獲得的密文為FMXVEDKAPIIFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH.試破解該密文。統(tǒng)計(jì)各字母頻率，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