【正文】 k=(k1 , k2, …, kr) 密文序列 c=(c1, c2, …, cv) 也都是二元序列。當密鑰為二元序列時要滿足 H(ML)≤H(M)=H(k1, k2, …, kr)≤r bits (2— 19) 定理 23：存在有完善保密系統(tǒng)。 定理 22：完善保密系統(tǒng)存在的必要條件是 H(K)?H(ML) (2— 18) 證明 ： (216)和平均互信息的非負性知，當式 (218)成立時必有式 (217)。 C?)=0 (2—17) 密文與明文之間的互信息為零，竊聽者從密文就得不到任何有關明文的信息 ,不管竊聽者截獲的密文有多少，他用于破譯的計算資源有多豐富 ,都是無濟于事的。 C?)?H(ML)－ H(K) 信息論與密碼學 11 定理說明，保密系統(tǒng)的密鑰量越小，其密文中含有的關于明文的信息量就越大。 C? K )=H(ML) (2— 15) 定理 21 對任意保密系統(tǒng) I(ML 。 C?)=H(K)－ H(K /C?) (2— 13) 由此可知， H(K /C?)和 H(ML/C?)越大，竊聽者從密文能夠提取出的有關明文和密鑰的信息就越小。 信息論與密碼學 9 二、完善保密性 令明文熵為 H(M)＝ H(ML )，密鑰熵為 H(K)，密文熵為 H(C)=H(C?)，在已知密文條件下明文的含糊度為H(ML/C? )，在已知密文條件下密鑰的含糊度為 H(K/C?) 惟密文破譯下，密碼分析者的任務是從截獲的密文中提取有關明文的信息 I(ML。 由此可見，通信問題和保密問題密切相關，有一定的 對偶性 ，用信息論的觀點來闡述保密問題是十分自然的事。密碼分析員就相當于有擾信道下原接收者。 信息論與密碼學 8 通信系統(tǒng)與保密系統(tǒng) 對消息 m的加密變換的作用類似于向消息注入噪聲。 l 主動攻擊 (Active attack)： 非法入侵者 (Tamper)、攻擊者 (Attcker)或 黑客 (Hacker)主動向系統(tǒng)竄擾 ， 采用刪除 、 增添 、 重放 、 偽造等竄改手段向系統(tǒng)注入假消息， 達到利已害人的目的 。 信息論與密碼學 7 密碼分析者實施 被動攻擊 (Passive attack)：對一個保密系統(tǒng)采取截獲密文進行分析的攻擊 。 信息論與密碼學 6 l密文空間 C： 密文 c的全體構成的集合 。 竊聽者不知道 k。 l密鑰空間 K： 對于長為 r的密鑰序列 k=k1, k2, ..., kr k1 ,…, kr?K=ZS (2— 5) 的全體 ， 且有 K ＝ Kr=Zsr (2— 6) 一般消息空間 K與密鑰空間 M彼此獨立 。 密鑰通常是離散的 ， 設密鑰字母表為： L={kt , t=0, 1, ..., s1}。 當信源為無記憶時有 p(m)=p(m1,m2,…, mL)= (2— 4) 信源的統(tǒng)計特性對密碼設計和分析起重要作用 。 設信源字母表為 M={ai , i=0, 1,… , q－ 1}， 字母 ai 出現(xiàn)的概率為 pi ?0， 且 (2— 1) 信源產(chǎn)生的任一長為 L個符號的消息序列為 m=(m1 , m2 ,…, mL) mi ?M=Zq (2—2) l消息空間或明文空間 M ：長為 L的信源輸出序列的集合 m?M=ML=ZqL (2— 3) 它含有 qL個元素 。 3 一、保密系統(tǒng) (Secrecy System)(M,C,K1,K2,Ek1,Dk2) k1 m c m C’ m’ 圖 21 保密系統(tǒng)模型 密鑰源 K1 密鑰源 K2 k2 密鑰信道 信 源 M 加密器 c=Ek1(m) 解密器 m=D k2(c) 接 收者 (主動攻擊 ) (被動攻擊 ) 非 法 接入者 密碼分析員 (竊聽者 ) 信道 搭線信道 搭線信道 信息論與密碼學 4 l信源 ：是產(chǎn)生消息的源 ， 在離散情況下可以產(chǎn)生字母或符號 ?！边@是指引 Hellman走向發(fā)現(xiàn)公鑰密碼的思想。 Diffie and Hellman在 1976年提出了公鑰密碼體制，(1981得 Donald G. Fink Prize 論文獎， 1998年獲 IEEE Information Theory Society Golden Jubilee Awards for Technological Innovation)。1 信息安全的數(shù)學基礎 信息論及與信息安全的關系 北京師范大學應用數(shù)學學院 楊進 2 信息論與密碼學 Shannon在 1949年發(fā)表了一重要論文，“保密通信的通信理論”，用信息論觀點系統(tǒng)地闡述了保密通信的問題。他提出了保密系統(tǒng)的模型、完善保密 (Perfect secrecy)理論、理論保密性、實際保密性的理論、設計和破譯密碼的基本原則，將密碼學從藝術 (art)變?yōu)榭茖W。 Hellman引用 Shannon原話， “ 好的密碼設計本質(zhì)上是尋求一個困難問題的解，相對于某種其它條件，我們可以構造密碼，使其破譯它 (或在過程中的某點上 )等價于解某個已知數(shù)學難題。因此，人們尊稱 Shannon為公鑰密碼學之父 (Godfather)。 可以用簡單概率空間描述離散無記憶源 。 若信源為有記憶時 ， 我們需要考慮 M中各元素的概率分布 。 ????101qiip信息論與密碼學 ??iLip m1 ( )5 l密鑰源 ：是產(chǎn)生密鑰序列的源 。 字母 kt的概率p(kt)?0， 且 密鑰源為無記憶均勻分布 ， 所以各密鑰符號為獨立等概 。 合法的接收者知道 k和密鑰空間 K 。 雙鑰體制下 ， 有兩個 密鑰空間 K1和 K 在單鑰體制下 K1= K2= K， 此時密鑰 k需經(jīng)安全的密鑰信道由發(fā)方傳給收方 。 c=(c1 , c2, ... , cV)=EK (m1, m2, ... , mL) (2— 7) l加密變換 ： Ek1?E， M?C，由加密器完成，即 c=f(m,k1)=Ek1(m) m? M ， k1?K1 (2— 8) l解密變換 ： Dk2 ?D， C ?M，由加密器完成，即 m=Dk2(c) m?M ， k2?K2 (2— 9) l合法接收者 ：知道密文 c、 解密變換和密鑰，信道是無擾條件下，易于從密文得到原來的消息 m，即 m=Dk(c)=Dk(Ek(m)) (2—10) l密碼分析者 ：可以得到密文 c， 他知道明文的統(tǒng)計特性 、 加密體制 、 密鑰空間及其統(tǒng)計特性 ， 但不知道截獲的密文 c所用的特定密鑰 。 用其選定的變換函數(shù) h， 對截獲的密文 c進行變換 ， 得到 m’=h(c) (2— 11) 一般 m’?m。 l A. Kerckhoff(1835— 1903荷蘭 )原則 ：密碼的安全必須完全寓于秘密鑰之中 。密文 c就相當于經(jīng)過有擾信道得到的接收消息。所不同的是，這種干擾不是信道中的自然干擾，而是發(fā)送者有意加進的，目的是使竊聽者不能從 c恢復出原來的消息。信息論自然成為研究密碼學和密碼分析學的一個重要理論基礎， Shannon的工作開創(chuàng)了用信息理論研究密碼學的先河。 C?)=H(ML)－ H(ML/C?) (2— 12) 或從密文中提取有關密鑰的信息 I(K 。 信息論與密碼學 10 合法的接收者已知密鑰和密文知 H(ML/C?K)=0 (25— 14) 因而有 I(ML 。 C?)?H(ML)－ H(K ) (2— 16) 證明：由式 (2534)及式 (2522)有 H(K /C?)=H(K/C?)＋ H(ML/KC?)=H(MLK/C?) =H(ML/C?)＋ H( /MLC?)?H(ML/C?) 又 H(K) ? H(K /C?) 故由式 (214)可得 I(ML 。 完善的 (Perfect)或無條件的 (Unconditionally)保密系統(tǒng)