第2講-古典密碼

1第二章古典密碼鄭洪英重慶大學(xué)計(jì)算機(jī)學(xué)院信息技術(shù)系《現(xiàn)代密碼學(xué)》課程幻燈片E-mail:zhenghongy@2上節(jié)課內(nèi)容復(fù)習(xí)明文、密文、密鑰（概念）加密、解密（概念及函數(shù)的表示方法）密碼體制加、解密密鑰，加、解密函數(shù)破譯攻擊方法（窮舉攻擊中根據(jù)密鑰量來推算攻擊時(shí)間）3上節(jié)課補(bǔ)充內(nèi)容－密碼算法的分類保密內(nèi)容受限制的（restricted)算法算法的保密性基于保持算法的秘密

基于密鑰（key-based)的算法算法的保密性基于對(duì)密鑰的保密4上節(jié)課補(bǔ)充內(nèi)容－密碼算法的分類密鑰對(duì)稱密碼算法（symmetriccipher)

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

非對(duì)稱密鑰算法（asymmetriccipher)

加密密鑰和解密密鑰不相同，從一個(gè)很難推出另一個(gè)又稱公開密鑰算法（public-keycipher)。公開密鑰算法用一個(gè)密鑰進(jìn)行加密,而用另一個(gè)進(jìn)行解密。其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡稱公鑰。解密密鑰必須保密,又稱私人密鑰（privatekey)，簡稱私鑰5上節(jié)課補(bǔ)充內(nèi)容－密碼算法的分類明文處理方式分組密碼（blockcipher)

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

流密碼（streamcipher)

又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文。6第二章古典密碼學(xué)習(xí)本章目的：1.學(xué)習(xí)基本的密碼編制原理;2.了解早期編制密碼的基本方法;3.為進(jìn)一步學(xué)習(xí)現(xiàn)代密碼的編制打下基礎(chǔ)。72.1古典密碼中的基本加密運(yùn)算單表密碼體制：對(duì)于一個(gè)密碼體制，如果明文字母對(duì)應(yīng)的密文字母在密文中保持不變，則稱其為單表密碼體制；多表密碼體制：如果明文中不同位置的同一明文字母在密文中對(duì)應(yīng)的密文字母不同，則稱其為多表密碼體制。8加密運(yùn)算1．簡單加法密碼

c=Ek(m)=(m+k)modq其中的加法都是模q加法．顯然，簡單加法密碼的密鑰量為q.2.乘法密碼

c=Ek(m)=(mk)modq其中的乘法都是模q乘法.9加密運(yùn)算3.簡單仿射密碼

c=Ek(m)=(k1+k2m)modq其中的加法和乘法都是模q加法和乘法.4.簡單置換密碼明文的字母保持相同，但順序被打亂了。102.211

1.Caesar密碼(凱撒密碼)

這是一種對(duì)英文字母的典型逐字母加密的的加法密碼,其密鑰k=3。

英文字母被編碼為該字母的序號(hào)

英文ABCD…XYZ

數(shù)字

0123…232425加密變換為：解密變換為：12例愷撒（Caesar）密碼是k＝3的情況。即通過簡單的向右移動(dòng)源字母表3個(gè)字母則形成如下代換字母表若明文為：pleaseconfirmreceipt則密文為：SOHDVEFRQILUPUHFHLSW明文字母abcdefghijklm密文字母:DEFGHIJKLMNOPnopqrstuvwxyzQRSTUVWXYZABC13安全性分析移位密碼是極不安全的（mod26），因?yàn)樗杀桓F舉密鑰搜索所分析：僅有26個(gè)可能的密鑰，嘗試每一個(gè)可能的加密密鑰，直到一個(gè)有意義的明文串被獲得。平均地說，一個(gè)明文在嘗試26/2＝13解密規(guī)則后將顯現(xiàn)出來。142.標(biāo)準(zhǔn)字頭密碼(又稱密鑰字密碼)

這是一種置換密碼,它利用一個(gè)密鑰字來構(gòu)造置換表。

如:

若選擇cipher作為密鑰字,則對(duì)應(yīng)置換表為:明文ABCDEFGHIJKLMNOP…密文

CIPHERABDFGJKLMN…15例2.2密鑰句子為：themessagewastransmittedanhourago。源字母表為：abcdefghijklmnopqrstuvwxyz

代換字母表為：THEMSAGWRNIDOUBCFJKLPQVXYZ明文：pleaseconfirmreceipt密文：CDSTKSEBUARJOJSESRCL16安全性分析置換密碼的密鑰是由26個(gè)字母的置換組成。這些置換的數(shù)目是26！，一個(gè)非常大的數(shù)。這樣即使對(duì)現(xiàn)代計(jì)算機(jī)來說，窮舉密鑰搜索也是不可行的。然而，以后我們會(huì)看到，置換密碼容易被其他的分析方法所破譯。172.2.2幾種典型的多表古典密碼體制1.playfair密碼英國陸軍在第一次世界大戰(zhàn)，美國陸軍在第二次世界大戰(zhàn)期間大量使用的一種二字母組代替密碼。密鑰由26個(gè)英文字母組成五階方陣。加密時(shí)，首先在明文字母串的適當(dāng)位置插入一些特定的字母，譬如字母q，使得明文字母串的長度為偶數(shù)，將明文串按兩個(gè)字母一組進(jìn)行分組。m1,m2同行：c1,c2在它們右邊；

m1,m2同列：c1,c2在它們下邊；

m1,m2不同行列：c1,c2是m1,m2

組成的長方形的另兩個(gè)頂點(diǎn)；

明文由奇數(shù)個(gè)字母組成，則在明文后加一無效字母18cipherabdfgklmnoqstuvwxyz設(shè)密鑰矩陣：P=明文為:playfaircipherwasactuallyinventedbywheatstone密文為Bsdwrbcaiphecfikqbhoqfksmxekzcmuhfdxyiifutuquf19若明文序列為:密鑰序列為：則密文序列為:其中：這也是序列密碼的一般加密形式將英文字母編碼為它的序號(hào)(0起算)維幾尼亞密碼（Vigenere密碼體制）當(dāng)密鑰的長度比明文短時(shí)，密鑰可以周期性地重復(fù)使用，直至完成明文中每個(gè)字母的加密。20維幾利亞密碼的代替表為明文字母密鑰字母密鑰字母為d,明文字母為b時(shí)查表得密文字母為e21例設(shè)m＝6，且密鑰字是CIPHER,這相應(yīng)于密鑰。假定明文串是thiscryptosystemisnotsecure

首先將明文串轉(zhuǎn)化為數(shù)字串，按6個(gè)一組分段，然后模26“加”上密鑰字得：相應(yīng)的密文串將是: VPXZGIAXIVWPUBTTMJPWIZITWZT解密過程與加密過程類似,不同的只是進(jìn)行模26減,而不是模26加。

22將對(duì)英文字母的加密變換改為：

當(dāng)將明、密文空間均設(shè)為若明文序列為:密鑰序列為：則密文序列為:其中：該密碼稱為維福特密碼（Beaufort密碼體制）此時(shí)解密變換與加密變換完全相同，也是：26mod)()(mk+25mEck-==23

如果將明、密文空間均改為將加密變換改為：若明文序列為：密鑰序列為：則密文序列為：其中：這是眾所周知的完全保密的密碼體制這個(gè)密碼就是著名的Vernam密碼體制24Hill密碼基本思想：將n個(gè)明文字母通過線性變換將它們轉(zhuǎn)換為n個(gè)密文字母，解密時(shí)只需做一次逆變換，密鑰就是變換矩陣25例假定密鑰是現(xiàn)在我們加密明文july分為兩個(gè)明文組（9，20）（相應(yīng)于ju）和（11，24）（相應(yīng)于ly）。計(jì)算如下：因此，july的加密是DELW。

26Hill密碼271.單表代替的優(yōu)缺點(diǎn)

優(yōu)點(diǎn):

明文字符的形態(tài)一般將面目全非

缺點(diǎn):

明文字符相同,則密文字符也相同;

從而導(dǎo)致:(I)若明文字符e被加密成密文字符a,則明文中e的出現(xiàn)次數(shù)就是密文中字符a的出現(xiàn)次數(shù);(II)明文的跟隨關(guān)系反映在密文之中.

因此,明文字符的統(tǒng)計(jì)規(guī)律就完全暴露在密文字符的統(tǒng)計(jì)規(guī)律之中.形態(tài)變但位置不變282.多表代替的優(yōu)缺點(diǎn)

優(yōu)點(diǎn):

只要

(1)多表設(shè)計(jì)合理,即每行中元素互不相同,每列中元素互不相同.(這樣的表稱為拉丁方表)(2)密鑰序列是隨機(jī)序列，即具有等概性和獨(dú)立性。這個(gè)多表代替就是完全保密的。

等概性:各位置的字符取可能字符的概率相同；

獨(dú)立性：在其它所有字符都知道時(shí)，也判斷不出未知的字符取哪個(gè)的概率更大。292.多表代替的優(yōu)缺點(diǎn)密鑰序列是隨機(jī)序列意味著：（1）密鑰