現(xiàn)代密碼學(xué)第3章：密碼學(xué)的信息論基礎(chǔ)

1、1密碼學(xué)的信息論基礎(chǔ)密碼學(xué)的信息論基礎(chǔ)現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué)第第3章章2本章主要內(nèi)容本章主要內(nèi)容n1 1、保密系統(tǒng)的數(shù)學(xué)模型、保密系統(tǒng)的數(shù)學(xué)模型n2 2、信息論與熵、信息論與熵n3 3、完善保密性、完善保密性3 C.E. Shannon （香農(nóng)） 1948, A mathematical theory of communication.確立了現(xiàn)代信息論。 1949, Communication theory of secrecy systems.定義了密碼系統(tǒng)的精確數(shù)學(xué)模型。41. 保密系統(tǒng)的數(shù)學(xué)模型保密系統(tǒng)的數(shù)學(xué)模型n通信系統(tǒng)模型n保密通信系統(tǒng)模型5Shannon的保密通信系統(tǒng)模型的保密通信系

2、統(tǒng)模型nShannon的保密通信系統(tǒng)模型6密碼學(xué)數(shù)學(xué)模型密碼學(xué)數(shù)學(xué)模型樣本空間樣本空間密鑰空間密鑰空間密文空間密文空間72. 信息論與熵信息論與熵 (entropy)n 熵（熵（Entropy）定義為事件集）定義為事件集X中事件出中事件出現(xiàn)的信息的統(tǒng)計(jì)平均值。現(xiàn)的信息的統(tǒng)計(jì)平均值。 它表示它表示X中出現(xiàn)一個(gè)事件平均給出的信中出現(xiàn)一個(gè)事件平均給出的信息量，或事件的平均不確定性。息量，或事件的平均不確定性。0 )(1log)()(iiaixpxpXH8熵的含義熵的含義n 熵反映了集中事件出現(xiàn)的平均不確定性，或?yàn)榇_定集中出現(xiàn)一個(gè)事件平均所需的信息量（觀測之前），或集中每出現(xiàn)一個(gè)事件平均給出的信息量（

3、觀測之后）。如果從編碼的角度來考慮，熵也可以理解成用最優(yōu)的二進(jìn)制編碼形式表示所需的比特?cái)?shù)。 0*log20=09熵的含義熵的含義n 采用以2為底的對數(shù)時(shí)，相應(yīng)的信息單位稱作比特（Bit）。n 如果集X為均勻分布時(shí)，即， 則 。n ，X為確定性的事件時(shí)，即X概率分布為p(X=a)=1，則H(X)=0。10熵的實(shí)例熵的實(shí)例n例1:設(shè)有一個(gè)密碼系統(tǒng),明文空間 的概率分布為 ；密鑰空間 的概率分布為 。密文空間 ，且假定加密函數(shù)為 。可用右邊的密矩陣表示：11熵的實(shí)例熵的實(shí)例n 按公式我們很容易計(jì)算出密文空間的概率分布及關(guān)于明文的條件分布： 1）密文空間的概率分布表如下： 2）明文關(guān)于密文的條件分布P

4、(m/c)表如下： 12熵的實(shí)例熵的實(shí)例 明文空間的熵為： 類似地可計(jì)算13條件概率條件概率n 在給定密文發(fā)生的條件下，某個(gè)明文發(fā)生的條件概率14條件熵條件熵n集X和Y的聯(lián)合熵定義為n集相對于事件的條件熵定義為n集相對于集的條件熵定義為15含糊度、散布度含糊度、散布度n 若將X視作一個(gè)系統(tǒng)的輸入空間，Y視作是系統(tǒng)的輸出空間。在通信中，通常將條件熵H(X|Y)稱作含糊度(Equivocation)，將條件熵H(Y|X)稱為散布度（Divergence）， X和Y之間的平均互信息 表示X熵減少量。16熵的基本特性熵的基本特性n引理1 （Jensen不等式）假定f是區(qū)間I上的一個(gè)連續(xù)的嚴(yán)格凸函數(shù):

5、那么 ，且僅， 時(shí)等號(hào)成立。17熵的基本特性熵的基本特性 定理1 假定X是有概率分布 的隨機(jī)變量，其中 ，則 ， （即樣本點(diǎn)是等概率分布）時(shí)取等號(hào)，即均勻分布下集X的不確定性最大。ni1 ,n1pi18熵的基本特性熵的基本特性n定理2， ,，且僅，X和Y獨(dú)立時(shí)等號(hào)成立。n定理3 。n推論1 ，且僅，X和Y獨(dú)立時(shí)等號(hào)成立。19各類熵之間的關(guān)系各類熵之間的關(guān)系203. 完善保密性完善保密性n定理4 設(shè) 是一個(gè)密碼系統(tǒng)。則n定義3 一個(gè)保密系統(tǒng)稱為是完善的或無條件的保密系統(tǒng)，如果 或 。n定理3.5 。n由定理3.5知，完善保密系統(tǒng)存在的必要條件是 ，即 。21無條件安全無條件安全n 無條件安全的密

6、碼系統(tǒng)安全性依賴于每個(gè)密鑰僅僅用在一次加密中，在每個(gè)消息被傳送之前，一個(gè)新的密鑰必須被產(chǎn)生。另外，每個(gè)消息必須與同樣長度的密鑰相伴，這是極其不利的，因?yàn)槊荑€應(yīng)，在消息之前被安全傳送。這些都給密鑰管理帶來了嚴(yán)重的問題。再加上一次一密系統(tǒng)對已知明文攻擊非常脆弱。因此無條件安全的保密系統(tǒng)是很不實(shí)用的，也具有很大的局限性，但在軍事和外交上很早就使用了這種體制。n 密碼學(xué)的歷史發(fā)展一直在試圖設(shè)計(jì)一個(gè)用一個(gè)密鑰就可以加密一個(gè)相，長的明文串（即一個(gè)密鑰可用來加密許多消息）的密碼系統(tǒng)，且仍能保持至少計(jì)算上安全。22理論安全性和實(shí)際安全性n圖 密鑰，消息和密鑰顯現(xiàn)含糊度作為S的函數(shù)23語言的多余度語言的多余度n

7、定義4 假如L是一種自然語言，語言L的熵為n語言的多余度定義為 其中A表示語言L的字母集，表示A中字母的個(gè)數(shù)， 表示所有明文n字母報(bào)構(gòu)成的全體。24密鑰含糊度密鑰含糊度n定理6 密鑰含糊度有下列下界 其中，S表示接受到的密文序列長度， 表示明文語言的冗余度， 表示密文空間中符號(hào)或字母的數(shù)目。 定理7 ，明文由一個(gè)離散獨(dú)立信源產(chǎn)生，如果 ，其中 是字母表的大小。密鑰的含糊度能變?yōu)榱恪?5估計(jì)一個(gè)系統(tǒng)的實(shí)際保密性估計(jì)一個(gè)系統(tǒng)的實(shí)際保密性n 理論上，截獲的密報(bào)量大于唯一解距離時(shí)，原則上就可破譯。n 由于自然語言的復(fù)雜性，沒有任何一種分析方法能夠假定分析者能利用明文語言的全部統(tǒng)計(jì)知識(shí)，所以，一般破譯所

8、需的密文量都遠(yuǎn)大于理論值。n 沒有涉及為了得到唯一解需完成多少計(jì)算量。從實(shí)際破譯來看，有時(shí)雖然截獲的密文量遠(yuǎn)大于唯一解距離，但由于所需的工作量還太大而難以實(shí)現(xiàn)破譯。26估計(jì)一個(gè)系統(tǒng)的實(shí)際保密性估計(jì)一個(gè)系統(tǒng)的實(shí)際保密性n 理論保密性是假定密碼分析者有無限的時(shí)間、設(shè)備和資金的條件下，研究唯密文攻擊時(shí)密碼系統(tǒng)的安全性。比如一次一密體制。n 實(shí)際安全性又稱為計(jì)算上的安全性，這個(gè)方法關(guān)心的是破譯一個(gè)具體的密碼系統(tǒng)所需的計(jì)算量。n 在實(shí)際中，人們說一個(gè)密碼系統(tǒng)是“計(jì)算上安全的”，意指利用已有的最好的方法破譯該系統(tǒng)所需要的努力超過了敵手的破譯能力（諸如時(shí)間、空間、和資金等資源）或破譯該系統(tǒng)的難度等價(jià)于解數(shù)學(xué)上的某個(gè)已知難題27估計(jì)一個(gè)系統(tǒng)的實(shí)際保密性估計(jì)一個(gè)系統(tǒng)的實(shí)際保密性n密碼分析者的計(jì)算能力；n所采用的破譯算法的有有性。28Shannon關(guān)于設(shè)計(jì)密碼的一些基本觀點(diǎn)關(guān)于設(shè)計(jì)密碼的一些基本觀點(diǎn)n 通過合并簡單密碼系統(tǒng)而形成它們的“積”挫敗統(tǒng)計(jì)分析的觀點(diǎn)：n 在加密之前將語言的一些多余度除去。n 采用所謂的“擴(kuò)散（Diffus