現(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)計平均值。現(xiàn)的信息的統(tǒng)計平均值。 它表示它表示X中出現(xiàn)一個事件平均給出的信中出現(xiàn)一個事件平均給出的信息量，或事件的平均不確定性。息量，或事件的平均不確定性。0 )(1log)()(iiaixpxpXH8熵的含義熵的含義n 熵反映了集中事件出現(xiàn)的平均不確定性，或為確定集中出現(xiàn)一個事件平均所需的信息量（觀測之前），或集中每出現(xiàn)一個事件平均給出的信息量（

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

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

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

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

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

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