第2章古典密碼學(xué)-PPT課件

1、第2章 古典密碼學(xué)2.1古典密碼學(xué)體制2.1.1定義和分類一個(gè)密碼系統(tǒng)（Cryptosystem）是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）任意 ,有一個(gè)加密算法 和相應(yīng)的解密算法 ，使得 和 分別為加密、解密函數(shù)，滿足 。 xxAlice加密解密密鑰源安全信道竊聽(tīng)者OscarkyBob實(shí)用密碼體系每個(gè)加密函數(shù)和每個(gè)解密函數(shù)應(yīng)當(dāng)能有效地被計(jì)算。 即使看到密文串y，竊聽(tīng)者Oscar確定所用的密鑰k或明文串x是不可行的。已知密文串y的情況下試圖計(jì)算密鑰k的過(guò)程稱為

2、密碼分析（Cryptanalysis）。古典密碼學(xué)分類代換（Substitution）密碼和置換（Permutation）密碼 2.1.2 代換密碼 將明文字母表抽象地表示為一個(gè)整數(shù)集 。在加密時(shí)通常將明文消息劃分成長(zhǎng)為L(zhǎng)的消息單元，稱為明文組，以m表示，如 。 m也稱作L報(bào)文，它可以看作是定義在 上的隨機(jī)變量 這時(shí)明文空間 。密文字母表抽象表示成整數(shù)集 。密文單元或組為 。c是定義在 上的隨機(jī)變量。密文空間 。一般地，明文和密文由同一字母表構(gòu)成。代換密碼可以看作是從 到 的映射。L1時(shí)，稱作單字母代換，也稱作流密碼（Stream cipher）。L1時(shí)，稱作多字母代換，亦稱分組密碼（Bloc

3、k cipher）。 1. 單表代換密碼 單表代換密碼是對(duì)明文的所有字母都用一個(gè)固定的明文字母表到密文字母表的映射，即 。令明文 ,則相應(yīng)地密文為 。 幾類簡(jiǎn)單的單表代換密碼 移位密碼（Shift Cipher）設(shè) 定義 且 例21 愷撒（Caesar）密碼是k3的情況。即通過(guò)簡(jiǎn)單的向右移動(dòng)源字母表3個(gè)字母則形成如下代換字母表 若明文為： please confirm receipt則密文為：SOHDVE FRQILUP UHFHLSW :abcdefghijklm:DEFGHIJKLMNOPnopqrstuvwxyzQRSTUVWXYZABC安全性分析移位密碼是極不安全的（mod26），因?yàn)?/p>

4、它可被窮舉密鑰搜索所分析：僅有26個(gè)可能的密鑰，嘗試每一個(gè)可能的加密規(guī)則，直到一個(gè)有意義的明文串被獲得。平均地說(shuō)，一個(gè)明文在嘗試26/213解密規(guī)則后將顯現(xiàn)出來(lái)。 替換密碼設(shè) ，密鑰空間K由所有可能的26個(gè)符號(hào)0，1，.，25的置換組成。對(duì)每一個(gè)置換 ，定義 則 ，其中 的逆置換。 例2.2 密鑰句子為：the message was transmitted an hour ago 。源字母表為： a b c d e f g h i j k l m n o p q r s t u v w x y z 代換字母表為：THEMSAGWRNIDOUBCFJKLPQVXYZ明文：please conf

5、irm receipt 密文：CDSTKS EBUARJO JSESRCL安全性分析替換密碼的密鑰是由26個(gè)字母的置換組成。這些置換的數(shù)目是26！，超過(guò)，一個(gè)非常大的數(shù)。這樣即使對(duì)現(xiàn)代計(jì)算機(jī)來(lái)說(shuō)，窮舉密鑰搜索也是不可行的。然而，以后我們會(huì)看到，替換密碼容易被其他的分析方法所破譯。 仿射密碼 設(shè) ，且 對(duì) ，定義 且 例2.3 假定 ， ，加密函數(shù)為 ，則相應(yīng)的解密函數(shù)為 ，其中所有的運(yùn)算都是在 中。容易驗(yàn)證 。 加密明文hot。 首先轉(zhuǎn)化這三個(gè)字母分別為數(shù)字7，14和19。然后加密密文串為AGX。 多表代換密碼 多表代換密碼是以一系列（兩個(gè)以上）代換表依次對(duì)明文消息的字母進(jìn)行代換的加密方法。令

6、明文字母表為 ， 為代換序列，明文字母序列 ，則相應(yīng)的密文字母序列為 。若f是非周期的無(wú)限序列，則相應(yīng)的密碼稱為非周期多表代換密碼。這類密碼，對(duì)每個(gè)明文字母都采用不同的代換表（或密鑰）進(jìn)行加密，稱作一次一密密碼（One-time pad cipher）,這是一種理論上唯一不可破的密碼 。有名的多表代換密碼有Vigenre、Beaufort、Running-Key、Vernam和轉(zhuǎn)輪機(jī)（Rotor machine）等密碼。 Vigenre密碼設(shè)m是某固定的正整數(shù)，定義 ，對(duì)一個(gè)密鑰 ，我們定義 且 所有的運(yùn)算都在 中。 例 2.4 設(shè)m6，且密鑰字是CIPHER,這相應(yīng)于密鑰。假定明文串是 th

7、is cryptosystem is not secure 首先將明文串轉(zhuǎn)化為數(shù)字串，按6個(gè)一組分段，然后模26“加”上密鑰字得：相應(yīng)的密文串將是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密過(guò)程與加密過(guò)程類似,不同的只是進(jìn)行模26減,而不是模26加。 多字母代換密碼（Polygram substitution cipher）Hill 密碼 設(shè)m是某個(gè)固定的正整數(shù)， ，又設(shè) ；對(duì)任意 ，定義 ， 則 。其中所有的運(yùn)算都是在 中進(jìn)行。 例 2.5 假定密鑰是，則。現(xiàn)在我們加密明文july分為兩個(gè)明文組（9，20）（相應(yīng)于ju）和（11，24）（相應(yīng)于ly）。計(jì)算如下： 因此，jul

8、y的加密是DELW。 2.1.3置換密碼（Permutation Cipher） 設(shè)m是某個(gè)固定的整數(shù)。 ，且由所有 的置換組成。對(duì)一個(gè)密鑰 （即一個(gè)置換），定義 ， 其中， 。 例 2.6 假定m6，密鑰是以下置換 ： ； 則逆置換 為： 。 給出明文 shesellsseashellsbytheseashore. 首先把明文分為6個(gè)字母一組： shesel lsseas hellsb ythese ashore . 每六個(gè)字母按重排，得密文： EESLSHSALSESLSHBLEHSYEETHRAEOS 用 類似地解密。 安全性分析Hill密碼解密等價(jià)于用逆置換 的置換密碼解密。 22 古

9、典密碼體制分析 Kerckhoff假設(shè)：攻擊方知道所用的密碼系統(tǒng)。簡(jiǎn)單的單表代換密碼，如移位密碼，僅統(tǒng)計(jì)標(biāo)出最高頻度字母再與明文字母表字母對(duì)應(yīng)決定出移位量，就差不多得到正確解了。也很容易用窮舉密鑰搜索來(lái)破譯。 一般的仿射密碼，多考慮幾個(gè)密文字母統(tǒng)計(jì)表與明文字母統(tǒng)計(jì)表的匹配關(guān)系也不難解出。結(jié)論：一個(gè)密碼系統(tǒng)是安全的一個(gè)必要條件是密鑰空間必須足夠大，使得窮舉密鑰搜索破譯是不可行的。唯密文攻擊法分析單表和多表代換密碼是可行的。但用唯密文攻擊法分析多字母代換密碼如Hill密碼是比較困難的。分析多字母代換多用已知明文攻擊法。 2.2.1 單表代換密碼分析 例 2.7 假設(shè)從仿射密碼獲得的密文為：FMXV

10、EDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH 僅有57個(gè)密文字母，但足夠分析仿射密碼。最高頻的密文字母是：R(8次)，D（6次），E，H，K（各五次），F(xiàn)，S，V（各四次）。開(kāi)始，我們可以假定R是e的加密且D是t的加密，因?yàn)閑和t分別是兩個(gè)最常見(jiàn)的字母。數(shù)值化后，我們有 。回憶加密函數(shù) 。所以得到兩個(gè)含兩個(gè)未知量的線性方程組： 表2.3 26個(gè)英文字母的概率分布字母概率字母概率A0.082N0.067B0.015O0.075C0.028P0.019D0.043Q0.001E0.127R0.060F0.022S0.063G0.020T

11、0.091H0.061U0.028I0.070V0.010J0.002W0.023K0.008X0.001L0.040Y0.020M0.024Z0.001 這個(gè)系統(tǒng)有唯一的解 。但這是一個(gè)非法的密鑰，因?yàn)?。所以我們假設(shè)有誤。 我們下一個(gè)猜想可能是R是e的加密，E是t的加密。得 ，又是不可能的。繼續(xù)假定R是e的加密且K是t的加密。這產(chǎn)生了 ，至少是一個(gè)合法的密鑰。剩下的事是計(jì)算相應(yīng)于k（3，5）的解密函數(shù)，然后解密密文看是否得到了有意義的英文串。容易證明這是一個(gè)有效的密鑰。 最后的密文是： algorithms are quite general definitions of arithmet

12、ic processes 2.2.2 多表代換密碼分析 分析Vigenre密碼的方法:Kasiski測(cè)試法 若用給定的m個(gè)密鑰表周期地對(duì)明文字母加密，則當(dāng)明文中有兩個(gè)相同字母組在明文序列中間隔的字母數(shù)為m的倍數(shù)時(shí)，這兩個(gè)明文字母組對(duì)應(yīng)的密文字母組必相同。但反過(guò)來(lái)，若密文中出現(xiàn)兩個(gè)相同的字母組，它們所對(duì)應(yīng)的明文字母組未必相同，但相同的可能性很大。如果我們將密文中相同的字母組找出來(lái)，并對(duì)其相同字母數(shù)綜合研究，找出它們的相同字母數(shù)的最大公因子，就有可能提取出有關(guān)密鑰字的長(zhǎng)度m的信息。 例子： 明文：REQUESTS ADDITIONAL TEST 密鑰：TELEXTEL EXTELEXTEL EXT

13、E密鑰：CAVKTBLT EUQWSWJGEA LTBL一個(gè)給定密文包含下列重復(fù)的序列，且有距離：因?yàn)?是出現(xiàn)最頻繁的因子，所以密文的周期最有可能是3。 字母序列距離PQA150=252 3RET42=723FRT10=25ROPY81=34DER57=193RUN117=1332重合指數(shù)法（Coincidence Index）設(shè)一門語(yǔ)言由n個(gè)字母構(gòu)成，每個(gè)字母發(fā)生的概率為 ，則重合指數(shù)是指其中兩個(gè)隨機(jī)元素相同的概率，記為 。 判斷文本是用單表還是用多表代換加密。提供對(duì)兩個(gè)不同密文的洞察力 。 Chi 測(cè)試 比較兩個(gè)頻率分布 ，決定是否同樣或不同的代換被采用 簡(jiǎn)化多表代換為單表代換 例：明文：

14、EXECUTE THESE COMMANDS密鑰：RADIORA DIORA DIORADIO密文：VXHKIKE WPSJE FWADAQLG VOVTLKVKYVJVTFDDREUJRADIO09121723RADIOVXHKIKEWPSJEFWADAQLG 例2.8 在相距很短的時(shí)間間隔內(nèi)我們收到了兩段密文： 密文1：k o o m m a c o m o q e g l x x m q c c k u e y f c u ry l y l i g z s x c z v b c k m y o p n p o g d g i a zt x d d i a k n v o m x h i

15、 e m r d e z v x b m z r n lz a y q i q x g k k k p n e v h o v v b k k t c s s e pk g d h x y v j m r d k b c j u e f m a k n t d r x b ie m r d p r r j b x f q n e m x d r l b c j h p z t v vi x y e t n i i a w d r g n o m r z r r e i k i o x r us x c r e t v密文 2：z a o z y g y u k n d w p i o u o r i y r h h b z x r ce a y v x u v r x k c m a x s t x s e p b r x c s 1 r uk v b x t g z u g g d w h x m x c s x b i k t n s l r jz h b x m s p u n g z r g k u d x n a u f c m r z x j ry w y m i （1） 假定兩段文本的確是用同樣方式加密的。 （2）采用Kasiski測(cè)試 確認(rèn)是用多表代換加密（3）轉(zhuǎn)化多表代換的密文為某個(gè)單個(gè)的單表代換加密的密文 （4）用一