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

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

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

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

4、它可被窮舉密鑰搜索所分析：僅有26個可能的密鑰，嘗試每一個可能的加密規(guī)則，直到一個有意義的明文串被獲得。平均地說，一個明文在嘗試26/213解密規(guī)則后將顯現(xiàn)出來。 替換密碼設(shè) ，密鑰空間K由所有可能的26個符號0，1，.，25的置換組成。對每一個置換 ，定義 則 ，其中 的逆置換。 例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個字母的置換組成。這些置換的數(shù)目是26！，超過，一個非常大的數(shù)。這樣即使對現(xiàn)代計(jì)算機(jī)來說，窮舉密鑰搜索也是不可行的。然而，以后我們會看到，替換密碼容易被其他的分析方法所破譯。 仿射密碼 設(shè) ，且 對 ，定義 且 例2.3 假定 ， ，加密函數(shù)為 ，則相應(yīng)的解密函數(shù)為 ，其中所有的運(yùn)算都是在 中。容易驗(yàn)證 。 加密明文hot。 首先轉(zhuǎn)化這三個字母分別為數(shù)字7，14和19。然后加密密文串為AGX。 多表代換密碼 多表代換密碼是以一系列（兩個以上）代換表依次對明文消息的字母進(jìn)行代換的加密方法。令

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

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

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

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

10、EDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH 僅有57個密文字母，但足夠分析仿射密碼。最高頻的密文字母是：R(8次)，D（6次），E，H，K（各五次），F(xiàn)，S，V（各四次）。開始，我們可以假定R是e的加密且D是t的加密，因?yàn)閑和t分別是兩個最常見的字母。數(shù)值化后，我們有 ?；貞浖用芎瘮?shù) 。所以得到兩個含兩個未知量的線性方程組： 表2.3 26個英文字母的概率分布字母概率字母概率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 這個系統(tǒng)有唯一的解 。但這是一個非法的密鑰，因?yàn)?。所以我們假設(shè)有誤。 我們下一個猜想可能是R是e的加密，E是t的加密。得 ，又是不可能的。繼續(xù)假定R是e的加密且K是t的加密。這產(chǎn)生了 ，至少是一個合法的密鑰。剩下的事是計(jì)算相應(yīng)于k（3，5）的解密函數(shù)，然后解密密文看是否得到了有意義的英文串。容易證明這是一個有效的密鑰。 最后的密文是： algorithms are quite general definitions of arithmet

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

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

14、EXECUTE THESE COMMANDS密鑰：RADIORA DIORA DIORADIO密文：VXHKIKE WPSJE FWADAQLG VOVTLKVKYVJVTFDDREUJRADIO09121723RADIOVXHKIKEWPSJEFWADAQLG 例2.8 在相距很短的時間間隔內(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測試 確認(rèn)是用多表代換加密（3）轉(zhuǎn)化多表代換的密文為某個單個的單表代換加密的密文 （4）用一