【正文】 )/?L l（密文量） 圖 22 H(K)～ l的典型變化特性 信息論與密碼學(xué) 19 證明 ： 令 Ml， Cl和 K都是二元序列集。 信息論與密碼學(xué) 24 例 23 下面給出幾種密碼體制對英語報文加密時的唯一解距離 。由圖可知，隨密文量 l增加， W(l)會降至一個漸近值。 乘積密碼系統(tǒng)的密鑰為 k=(k1, k2)， k1? K1 ， k2? K2 加密： (2— 41) ? 信息論與密碼學(xué) E m E E mk k k k( ) ( ) ( ( ))1 2 2 1?31 解 密： mmEDmEEDDmEEDmEDcDkkkkkkkkkkkkkkkk?????))(())))(((()))((())(()(1112211221212121)(,),()(由于 k1和 k2獨(dú)立選取，故有 )()(),( 2121 21 kpkpkkp kkk ??信息論與密碼學(xué) (2— 42) (2— 43) 32 特例：冪等 (Idempotent)密碼系統(tǒng)： S S=S2 =S。 信息論與密碼學(xué) 35 要求： l 意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性和真實(shí)性 。 令 x?X為要發(fā)送的消息， k?K是發(fā)方選定的密鑰，y=A(x, k)?Y是表示消息 x的認(rèn)證碼字， Ak={y=A(x, k), x?X}為認(rèn)證碼。 而且可以證明 ， 要求式 (612)等號成立的充要條件是：對任一 k?K， 都恰有 {Ak}{X}。 48 信息論與密碼學(xué) 認(rèn)證碼 上面給出了認(rèn)證系統(tǒng)安全性指標(biāo) pd的下限 ， 本節(jié)將研究如何構(gòu)造認(rèn)證碼使其接近或達(dá)到其性能下限 。 51 信息論與密碼學(xué) ? 一般雜湊函數(shù) ， 無密鑰控制 。 模仿偽造成功概率 (2— 55) 此與最佳線性檢錯碼的不可檢錯概率的上限一致 。 為了減小碰撞，通常都將輸入消息數(shù)字串長度作為參數(shù)納入最后一個分段中，這樣攻擊者在試圖找到偽消息 M’與發(fā)送消息 M的雜湊值一樣時，必須使 M’的長度和 M的長度一致才合法，從而大大增加了攻擊的難度。 信息論與密碼學(xué) 60 密碼與計算復(fù)雜性關(guān)系 Shannon[1949]指出 “ 設(shè)計好的密碼問題本質(zhì)上是尋求在某些其它條件下的一個難解問題 。 首先 ， Brassard[1979]指出除非 NP=CoNP， 否則密碼分析者面臨的問題將不會是 NP難問題； 其次 ， 復(fù)雜性理論主要關(guān)心的是問題的漸近復(fù)雜性； 信息論與密碼學(xué) 64 第三 ， NPC是問題復(fù)雜性最壞情況下的量度 ， 而密碼的安全性應(yīng)當(dāng)依賴于問題的復(fù)雜度平均情況 ， 最好是在所有情況下問題都是難于處理的 。 (例如 ，由同一密鑰加密的幾個組密文 。概率性檢驗(yàn)證明是當(dāng)今復(fù)雜性理論中最為深刻的結(jié)果。一般 L?n bit，且當(dāng) L不是 n的整數(shù)倍時，采用 填充 辦法湊成 ?L/n?倍 (?而有 pd ? 2n (2— 54) 54 信息論與密碼學(xué) 線性分組檢錯碼是一種 MDC雜湊，可作為數(shù)據(jù)完整性檢驗(yàn)，但不能作為身份認(rèn)證。 分類 ： ? 密碼雜湊函數(shù) ， 有密鑰控制 ， 以 h(k, M)表示 。 實(shí)際安全性 是根據(jù)破譯認(rèn)證體制所需的計算量來評價其安全性的 。 一般認(rèn)證編碼中 {Y} {X}， 且認(rèn)證碼中元素個數(shù) {Ak}?{X }。 信息論與密碼學(xué) 37 信息論與密碼學(xué) 圖 24 純認(rèn)證系統(tǒng)模型 信道 竄擾者 認(rèn)證編碼器 認(rèn)證譯碼器 信 源 信 宿 密鑰源 安全信道 38 信息論與密碼學(xué) 認(rèn)證編碼 在要發(fā)送的消息中引入多余度，使通過信道傳送的可能序列集 Y大于消息集 X。 l 保密性：保密性是使截獲者在不知密鑰條件下不能解讀密文的內(nèi)容 。 設(shè)計當(dāng)代密碼有重要指導(dǎo)意義 ， 許多近代分組密碼體制 ， 幾乎無一例外都采用了這一思想 。 破譯工作特性 (Work characteristic) ： W(l)隨 l的變化曲線 ， 其中 W(l)可用人 時度量 。 這和著名密碼分析家 W. F. Friedman的經(jīng)驗(yàn)值 25個字母相符 。 若 H=(K/C?)?0， 就可惟一地確定密鑰 K， 而實(shí)現(xiàn)破譯 。 這等價于將 m通過一個轉(zhuǎn)移概率 p=1/2的 BSC傳送，BSC的容量為零 (參看例 253)。 信息論與密碼學(xué) 10 合法的接收者已知密鑰和密文知 H(ML/C?K)=0 (25— 14) 因而有 I(ML 。 雙鑰體制下 ， 有兩個 密鑰空間 K1和 K 在單鑰體制下 K1= K2= K， 此時密鑰 k需經(jīng)安全的密鑰信道由發(fā)方傳給收方 。他提出了保密系統(tǒng)的模型、完善保密 (Perfect secrecy)理論、理論保密性、實(shí)際保密性的理論、設(shè)計和破譯密碼的基本原則，將密碼學(xué)從藝術(shù) (art)變?yōu)榭茖W(xué)。 l密鑰空間 K： 對于長為 r的密鑰序列 k=k1, k2, ..., kr k1 ,…, kr?K=ZS (2— 5) 的全體 ， 且有 K ＝ Kr=Zsr (2— 6) 一般消息空間 K與密鑰空間 M彼此獨(dú)立 。 信息論與密碼學(xué) 9 二、完善保密性 令明文熵為 H(M)＝ H(ML )，密鑰熵為 H(K)，密文熵為 H(C)=H(C?)，在已知密文條件下明文的含糊度為H(ML/C? )，在已知密文條件下密鑰的含糊度為 H(K/C?) 惟密文破譯下，密碼分析者的任務(wù)是從截獲的密文中提取有關(guān)明文的信息 I(ML。今選 L=r=v，并令 k是一理想二元對稱源 (BSS)的輸出，即 k為隨機(jī)數(shù)字序列，因而有 H( )=L bits。 信息論與密碼學(xué) 16 五 、 理論保密性 ?長密文序列集 C=C1, C2, ...,C? ?C?， 密鑰的不確定性 ， 即從密鑰含糊度 ， 由條件熵性質(zhì)知 H(K/C?)=(K/C1, …, C?+1 )?H(K/C1,…, C?) (2— 25) 顯然 ， 當(dāng) ?=0時的密鑰的含糊度就是密鑰的熵 H(K)。 信息論與密碼學(xué) 23 例 22 英語單表代換密碼的密鑰量 |K?=26!， 其密鑰空間的熵為 H(K)=lb(26!)= bits 。 一個密碼系統(tǒng) ，如果對手有無限的資源可利用 ， 而在截獲任意多密報下仍不能被破譯 ， 則它在理論上是保密的 。 ? 估計破譯一個保密系統(tǒng)所需的平均工作量 W(l) 的另一種途徑是 ， 將破譯此密碼的難度等價于解數(shù)學(xué)上的某個已知難題 。實(shí)現(xiàn)這類功能的密碼系統(tǒng)稱作認(rèn)證系統(tǒng)。 在這個系統(tǒng)中的發(fā)送者通過一個公開信道將消息送給接收者 ， 接收者不僅想收到消息本身 ，而且還要驗(yàn)證消息是否來自合法的發(fā)送者及消息是否經(jīng)過竄改 。 竄擾者可以自由地選擇最有利的攻擊方式 。 定理 613 對具有保密的認(rèn)證 (竄擾者不知信源狀態(tài) )有 log pd ?－ 1/2H(K) (2— 50) 而對無保密的認(rèn)證 (竄擾者知道信源狀態(tài) )有 log pd ?－ 1/2{H(K)－ H(XY)＋ H(Y)} =－ 1/2{H(K)－ H(X|Y) (2— 51) 系 (2— 52) ? ?p Kd ?146 信息論與密碼學(xué) 類似于保密系統(tǒng)的安全性 ， 認(rèn)證系統(tǒng)的安全性也劃分為兩大類 ， 即 理論安全性 和 實(shí)際安全性 。 50 信息論與密碼學(xué) 九 、 雜湊函數(shù) (Hash Function) 將任意長數(shù)字串 M映射成一個較短的定長輸出數(shù)字串 H的函數(shù) ， 以 h表示 ， h(M)易于計算 ， 稱 H= h(M)為 M的 雜湊值 ， 也稱 雜湊碼 、 雜湊結(jié)果等或簡稱雜湊 。 當(dāng)碼字在傳輸過程中被竄擾 ， 若結(jié)果不屬于碼空間 ， 收端通過對 n個一致檢驗(yàn)關(guān)系的檢驗(yàn)可以實(shí)現(xiàn)檢錯 。 雖然其不可檢錯誤的概率上界為 2n， 但 Pd的下界為 1。 信息論與密碼學(xué) 58 通信復(fù)雜性 ：兩個代理人各有一半輸入 bit，通過通信交換盡可能少的信息完成一個布爾函數(shù)的計算。但計算上困難的問題并非一定就意味一個強(qiáng)的密碼 。 如何確定問題在實(shí)際上為一個難題