【正文】 H(ML)≤H(M)=H(k1, k2, …, kr)≤r bits (2— 19) 定理 23：存在有完善保密系統(tǒng)。 證明 今以構造法證明。不失一般性可假定明文是二元數(shù)字序列 m=(m1, m2, …, mL), mi∈ GF(2) 令密鑰序列 k=(k1 , k2, …, kr) 密文序列 c=(c1, c2, …, cv) 也都是二元序列。 m和 k彼此獨立。今選 L=r=v，并令 k是一理想二元對稱源 (BSS)的輸出，即 k為隨機數(shù)字序列，因而有 H( )=L bits。若采用 Vernam體制，則有 c=Ek(m)=m?k。 式中，加法是逐位按模 2進行，即 信息論與密碼學 13 ci=mi ?ki。 這等價于將 m通過一個轉移概率 p=1/2的 BSC傳送，BSC的容量為零 (參看例 253)。因而有 I(ML；CL)≤LC=0。 但由平均互信息的非負性有 I(ML； CL)≥0，從而證明上述系統(tǒng)有 I(ML； CL)=0，即系統(tǒng)是完善的。 定理 254構造的系統(tǒng)在惟密文破譯下是安全的，但在已知明文攻擊下是不安全的。 Shannon最先證明這種體制是完善保密的，并能抗擊已知明文 密文下的攻擊。在不知密鑰條件下，任何人采用任何破譯法都不會比隨機猜測更好些 ! 在實際應用中，為了安全起見，必須保證密鑰以完全隨機方式產(chǎn)生 (如擲硬幣 )并派可靠信使通過安全途徑送給對方，每次用過后的密鑰都立即銷毀。 信息論與密碼學 14 三 、 冗余度 P31P32 r: 語言的信息率 R:語言的絕對信息率 冗余度 =Rr 題： 密碼分析者借助自然語言的冗余度進行密碼分析 ， 冗余度越大 ， 越容易進行破譯 ， 所以加密明文前 ， 用一個壓縮程序來降低明文的冗余度是一個非常好的選擇 信息論與密碼學 15 四 、 壓縮編碼 在二元情況下 ， 為實現(xiàn)完善保密所需的密鑰量僅為N bit。 理想壓縮編碼可使密鑰長度減至 r=N?H(M1, M2, …, ML) （ 2— 24) 收端先由收到的密文 c利用已知密鑰 k恢復出壓縮后的明文 m’=c?k， 再由明文 m’恢復原來的明文消息 m。 可能實現(xiàn)完善保密 。 而所需的密鑰量由原來的 L bits降為H(M1, M2,… , ML)bit。 當然 ， 這并不能從根本上解決一次一密體制中密鑰量過大的問題 。 但是在下面我們將會看到 ， 加密前的數(shù)據(jù)壓縮是強化保密系統(tǒng)的重要措施 ， 這也是 Shannon最先指出的一個重要結果 。 降低明文中的多余度常常會使密碼分析者處于困境 。 信息論與密碼學 16 五 、 理論保密性 ?長密文序列集 C=C1, C2, ...,C? ?C?， 密鑰的不確定性 ， 即從密鑰含糊度 ， 由條件熵性質知 H(K/C?)=(K/C1, …, C?+1 )?H(K/C1,…, C?) (2— 25) 顯然 ， 當 ?=0時的密鑰的含糊度就是密鑰的熵 H(K)。 即隨著 ?的加大 ， 密鑰含糊度是非增的 。 即隨著截獲密文的增加 ， 得到的有關明文或密鑰的信息量就增加 ， 而保留的不確定性就會越來越小 。 若 H=(K/C?)?0， 就可惟一地確定密鑰 K， 而實現(xiàn)破譯 。 ?0=min{??N | H(K/C?)?0} (2— 26) 信息論與密碼學 17 惟一解距離 (Unicity distance) 對于給定的密碼系統(tǒng) ， 在惟密文攻擊下的 ?0=min{??N | H(K/C?)?0} (2—27) N是正整數(shù)集 。 當截獲的密報量大于 ?0時 ， 原則上就可惟一地確定系統(tǒng)所用的密鑰 ， 即原則上可以破譯該密碼 。 ?0與明文多余度的關系 ?0?H(K)/?L (2— 28) 圖 22給出 H(K)～ l的典型變化特性。 信息論與密碼學 18 H(K) 0 1 2 3 ? H(K)/?L l（密文量） 圖 22 H(K)～ l的典型變化特性 信息論與密碼學 19 證明 ： 令 Ml， Cl和 K都是二元序列集。 K和 Cl之間平均互信息為 I(K。 Cl)=H(Cl)－ K(Cl /K) (2— 29) 對于典型的密碼系統(tǒng)，當 l足夠小時，二元密文序列的前 l bit實際上是完全隨機的二元數(shù)字，因而有 H(Cl )?l bits (2— 30) 由熵的性質有 H(MlCl /K)=H(Ml/K)＋ H(Cl/MlK) =H(Cl /K)＋ H(Ml /ClK) (2— 31) 式中： H(Cl /Ml K)=0 (2— 32) H(Ml /Cl K)=0 (2— 33) 又由所有密碼系統(tǒng)的明文和密鑰統(tǒng)計獨立 ， 即 信息論與密碼學 20 H(Ml /K)=H(Ml) (2— 34) 將上述三式代入式 (2549) 得 H(Cl /K)=H(Ml) (2— 35) 對于多數(shù)密碼系統(tǒng)和相應的明文源，在 l不太大時，例如 l?L，不確定性 H(Cl /K)隨 l近似于線性關系增加，因而可將上式寫成 H(Cl |K)?H(ML) 1? l?L (2—36) 將式 (2548)和式 (2554)代入式 (2547)得 (2— 37) 由式 (2541)知 ， 上式括號中的量是 L長二元信源序列的多余度 ， 故有 I(K。 CL)=l?L 0? ?L ? 1 (2—38) 又由于 信息論與密碼學 21 I(K。 CL)=H(K)－ H(K/Cl) 因而有 H(K/Cl)?H(K)－ l?L (2— 39) 由此可見 ， 當 l足夠小時 ， 密鑰含糊度將隨截獲的密文長度 l線性地降低 ， 直到當 H(K?Cl)變得相當小為止 。 由式 (2557)及唯一解距離 ?0的定義可得 ?0?H(K)/?L (2— 40) 討論 ： ? 若 ?L=0， 即當明文經(jīng)過最佳數(shù)據(jù)壓縮編碼后 ， 其惟一解距離 ? 0??。 雖然這時系統(tǒng)不一定滿足H(K)?H(ML)的完善保密條件 ， 但不管截獲的密報量有多大 ， 密鑰的含糊度仍為 H(K/Cl)?H(K)， 即可能的密鑰解有 2H(K)個之多 ! 信息論與密碼學 22 ? 實際中不可能實現(xiàn) ?L =0，但是在消息進行加密之 前，先進行壓縮編碼來減小多余度，對于提高系統(tǒng)安全性是絕對必要的 ! 多余度的存在，使得任何密碼體制在有限密鑰下 (H(K)為有限 )，其惟一解距離都將是有限的，因而在理論上都將是可破的。 ? 一些使數(shù)據(jù)擴展的方式對于密碼的安全是不利的。 ? 增大 H(K)是提高保密系統(tǒng)安全性的途徑 ， 即采用復雜的密碼體制 ， 直至一次一密鑰體制 。 信息論與密碼學 23 例 22 英語單表代換密碼的密鑰量 |K?=26!， 其密鑰空間的熵為 H(K)=lb(26!)= bits 。 由例 21 知 ，?? =， 所以這一密碼體制的唯一解距離ν=。 此例說明 ， 只要截獲到 28個字母長的密文 ， 原則上就可能破譯英語單表代換密碼 。 這和著名密碼分析家 W. F. Friedman的經(jīng)驗值 25個字母相符 。 例如 ， 當密文量?=40字母 ， 若每個字母的多余度以 δ= ， 一個有意義的脫密消息的期望數(shù)僅為 1010。 因此 ， 當?shù)玫揭粋€有意義的解時顯然是可信賴的 。 但若以 ν=20個密文字母破譯 ， 有意義的脫密解高達 107個之多 ， 如果得到了一個有意義的解 ， 其可信度是很低的 。 信息論與密碼學 24 例 23 下面給出幾種密碼體制對英語報文加密時的唯一解距離 。 (1) 周 期 為 d 的移位密碼 ， H(K)=lb(d!) ，?0=lb(d!)/=(d/e)字母 。 若選 d=27， 則 d/e≈10， lb(d/e)≈， 故 ν0= 。 (2) 含 q 個字母表的單表代換 ， H(K)=lb(q!) ，?0=lb(q!)/δ。 例如 q=26， δ= 256的情況