新編-第2章信息安全與信息論-精品課件

1、信息安全的數(shù)學基礎-信息論及與信息安全的關系北京師范大學應用數(shù)學學院楊進1信息論與密碼學 Shannon在1949年發(fā)表了一重要論文，“保密通信的通信理論”，用信息論觀點系統(tǒng)地闡述了保密通信的問題。他提出了保密系統(tǒng)的模型、完善保密(Perfect secrecy)理論、理論保密性、實際保密性的理論、設計和破譯密碼的基本原則，將密碼學從藝術(art)變?yōu)榭茖W。 Diffie and Hellman在1976年提出了公鑰密碼體制，(1981得Donald G. Fink Prize 論文獎，2019年獲IEEE Information Theory Society Golden Jubilee A

2、wards for Technological Innovation)。Hellman引用Shannon原話， “好的密碼設計本質上是尋求一個困難問題的解，相對于某種其它條件，我們可以構造密碼，使其破譯它(或在過程中的某點上)等價于解某個已知數(shù)學難題。”這是指引Hellman走向發(fā)現(xiàn)公鑰密碼的思想。因此，人們尊稱Shannon為公鑰密碼學之父(Godfather)。 2 一、保密系統(tǒng)(Secrecy System)(M,C,K1,K2,Ek1,Dk2) k1mcmC m圖2-1 保密系統(tǒng)模型密鑰源 K1 密鑰源 K2 k2密鑰信道信 源 M加密器c=Ek1(m) 解密器m=D k2(c) 接

3、收者(主動攻擊)(被動攻擊)非 法接入者密碼分析員 (竊聽者)信道 搭線信道 搭線信道 信息論與密碼學3l信源：是產(chǎn)生消息的源，在離散情況下可以產(chǎn)生字母或符號?？梢杂煤唵胃怕士臻g描述離散無記憶源。設信源字母表為M=ai , i=0, 1, q1，字母ai 出現(xiàn)的概率為pi 0，且 (21)信源產(chǎn)生的任一長為L個符號的消息序列為 m=(m1 , m2 , mL) mi M=Zq (22)l消息空間或明文空間M ：長為L的信源輸出序列的集合 mM=ML=ZqL (23)它含有qL個元素。若信源為有記憶時，我們需要考慮M中各元素的概率分布。當信源為無記憶時有 p(m)=p(m1,m2,mL)= (2

4、4)信源的統(tǒng)計特性對密碼設計和分析起重要作用。 信息論與密碼學4l密鑰源：是產(chǎn)生密鑰序列的源。密鑰通常是離散的，設密鑰字母表為：L=kt , t=0, 1, ., s-1。字母kt的概率p(kt)0，且密鑰源為無記憶均勻分布，所以各密鑰符號為獨立等概。l密鑰空間K：對于長為r的密鑰序列 k=k1, k2, ., kr k1 , krK=ZS (25)的全體，且有 K Kr=Zsr (26) 一般消息空間K與密鑰空間M彼此獨立。合法的接收者知道k和密鑰空間K 。竊聽者不知道k。 雙鑰體制下，有兩個密鑰空間K1和K2、在單鑰體制下K1= K2= K，此時密鑰k需經(jīng)安全的密鑰信道由發(fā)方傳給收方。信息

5、論與密碼學5l密文空間C：密文c的全體構成的集合。 c=(c1 , c2, . , cV)=EK (m1, m2, . , mL) (27)l加密變換：Ek1E，MC，由加密器完成，即 c=f(m,k1)=Ek1(m) m M ，k1K1 (28)l解密變換：Dk2 D，C M，由加密器完成，即m=Dk2(c) mM ，k2K2 (29)l合法接收者：知道密文c、解密變換和密鑰，信道是無擾條件下，易于從密文得到原來的消息m，即 m=Dk(c)=Dk(Ek(m) (210)l密碼分析者：可以得到密文c，他知道明文的統(tǒng)計特性、加密體制、密鑰空間及其統(tǒng)計特性，但不知道截獲的密文c所用的特定密鑰。信息

6、論與密碼學6 密碼分析者實施被動攻擊 (Passive attack)：對一個保密系統(tǒng)采取截獲密文進行分析的攻擊。用其選定的變換函數(shù)h，對截獲的密文c進行變換，得到 m=h(c) (211) 一般 mm。l 主動攻擊 (Active attack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達到利已害人的目的。l A. Kerckhoff(18351903荷蘭)原則：密碼的安全必須完全寓于秘密鑰之中。信息論與密碼學7 通信系統(tǒng)與保密系統(tǒng) 對消息m的加密變換的作用類似于向消息注入噪聲。密文c就相

7、當于經(jīng)過有擾信道得到的接收消息。密碼分析員就相當于有擾信道下原接收者。所不同的是，這種干擾不是信道中的自然干擾，而是發(fā)送者有意加進的，目的是使竊聽者不能從c恢復出原來的消息。 由此可見，通信問題和保密問題密切相關，有一定的對偶性，用信息論的觀點來闡述保密問題是十分自然的事。信息論自然成為研究密碼學和密碼分析學的一個重要理論基礎，Shannon的工作開創(chuàng)了用信息理論研究密碼學的先河。信息論與密碼學8二、完善保密性 令明文熵為H(M)H(ML )，密鑰熵為H(K)，密文熵為H(C)=H(C)，在已知密文條件下明文的含糊度為H(ML/C )，在已知密文條件下密鑰的含糊度為H(K/C) 惟密文破譯下，

8、密碼分析者的任務是從截獲的密文中提取有關明文的信息 I(ML; C)=H(ML)H(ML/C) (212)或從密文中提取有關密鑰的信息 I(K ; C)=H(K)H(K /C) (213) 由此可知，H(K /C)和H(ML/C)越大，竊聽者從密文能夠提取出的有關明文和密鑰的信息就越小。信息論與密碼學9 合法的接收者已知密鑰和密文知 H(ML/CK)=0 (2514)因而有 I(ML ; C K )=H(ML) (215)定理2-1 對任意保密系統(tǒng) I(ML ; C)H(ML)H(K ) (216) 證明：由式(2-5-34)及式(2-5-22)有 H(K /C)=H(K/C)H(ML/KC)

9、=H(MLK/C) =H(ML/C)H(/MLC)H(ML/C)又 H(K) H(K /C)故由式(2-14)可得 I(ML ; C)H(ML)H(K) 信息論與密碼學10 定理說明，保密系統(tǒng)的密鑰量越小，其密文中含有的關于明文的信息量就越大。完善的(Perfect)或無條件的(Unconditionally)保密系統(tǒng)： I(ML; C)=0 (217)密文與明文之間的互信息為零，竊聽者從密文就得不到任何有關明文的信息,不管竊聽者截獲的密文有多少，他用于破譯的計算資源有多豐富,都是無濟于事的。顯然，這種系統(tǒng)是安全的。 定理2-2：完善保密系統(tǒng)存在的必要條件是 H(K)H(ML) (218) 證

10、明 ：(2-16)和平均互信息的非負性知，當式(2-18)成立時必有式(2-17)。信息論與密碼學11 完善保密系統(tǒng)的密鑰量的對數(shù)(密鑰空間為均勻分布條件下)要大于明文集的熵。當密鑰為二元序列時要滿足 H(ML)H(M)=H(k1, k2, , kr)r bits (219)定理2-3：存在有完善保密系統(tǒng)。 證明 今以構造法證明。不失一般性可假定明文是二元數(shù)字序列 m=(m1, m2, , mL), miGF(2)令密鑰序列 k=(k1 , k2, , kr) 密文序列 c=(c1, c2, , cv) 也都是二元序列。m和k彼此獨立。今選L=r=v，并令k是一理想二元對稱源(BSS)的輸出，

11、即k為隨機數(shù)字序列，因而有 H()=L bits。若采用Vernam體制，則有 c=Ek(m)=mk。式中，加法是逐位按模2進行，即信息論與密碼學12 ci=mi ki。這等價于將m通過一個轉移概率p=1/2的BSC傳送，BSC的容量為零(參看例2-5-3)。因而有 I(ML；CL)LC=0。 但由平均互信息的非負性有I(ML；CL)0，從而證明上述系統(tǒng)有 I(ML；CL)=0，即系統(tǒng)是完善的。 定理2-5-4構造的系統(tǒng)在惟密文破譯下是安全的，但在已知明文攻擊下是不安全的。Shannon最先證明這種體制是完善保密的，并能抗擊已知明文-密文下的攻擊。在不知密鑰條件下，任何人采用任何破譯法都不會比

12、隨機猜測更好些! 在實際應用中，為了安全起見，必須保證密鑰以完全隨機方式產(chǎn)生(如擲硬幣)并派可靠信使通過安全途徑送給對方，每次用過后的密鑰都立即銷毀。信息論與密碼學13三、冗余度 P31-P32r: 語言的信息率R:語言的絕對信息率冗余度=R-r題：2.3密碼分析者借助自然語言的冗余度進行密碼分析，冗余度越大，越容易進行破譯， 所以加密明文前，用一個壓縮程序來降低明文的冗余度是一個非常好的選擇信息論與密碼學14四、壓縮編碼 在二元情況下，為實現(xiàn)完善保密所需的密鑰量僅為N bit。理想壓縮編碼可使密鑰長度減至 r=NH(M1, M2, , ML) （224)收端先由收到的密文c利用已知密鑰k恢復

13、出壓縮后的明文 m=ck，再由明文m恢復原來的明文消息m。可能實現(xiàn)完善保密。而所需的密鑰量由原來的L bits降為H(M1, M2, ML)bit。當然，這并不能從根本上解決一次一密體制中密鑰量過大的問題。但是在下面我們將會看到，加密前的數(shù)據(jù)壓縮是強化保密系統(tǒng)的重要措施，這也是Shannon最先指出的一個重要結果。降低明文中的多余度常常會使密碼分析者處于困境。 信息論與密碼學15 五、理論保密性 長密文序列集C=C1, C2, .,C C， 密鑰的不確定性，即從密鑰含糊度，由條件熵性質知 H(K/C)=(K/C1, , C+1 )H(K/C1, C) (225)顯然，當=0時的密鑰的含糊度就是

14、密鑰的熵H(K)。即隨著的加大，密鑰含糊度是非增的。即隨著截獲密文的增加，得到的有關明文或密鑰的信息量就增加，而保留的不確定性就會越來越小。 若H=(K/C)0，就可惟一地確定密鑰K，而實現(xiàn)破譯。0=minN | H(K/C)0 (226)信息論與密碼學16惟一解距離(Unicity distance) 對于給定的密碼系統(tǒng)，在惟密文攻擊下的 0=minN | H(K/C)0 (227)N是正整數(shù)集。當截獲的密報量大于0時，原則上就可惟一地確定系統(tǒng)所用的密鑰，即原則上可以破譯該密碼。0與明文多余度的關系0H(K)/L (228)圖 2-2給出H(K)l的典型變化特性。信息論與密碼學17H(K)

15、0 1 2 3 H(K)/L l（密文量）圖2-2 H(K)l的典型變化特性信息論與密碼學18證明：令Ml，Cl和K都是二元序列集。K和Cl之間平均互信息為I(K; Cl)=H(Cl)K(Cl /K) (229)對于典型的密碼系統(tǒng)，當l足夠小時，二元密文序列的前l(fā) bit實際上是完全隨機的二元數(shù)字，因而有 H(Cl )l bits (230)由熵的性質有 H(MlCl /K)=H(Ml/K)H(Cl/MlK) =H(Cl /K)H(Ml /ClK) (231)式中：H(Cl /Ml K)=0 (232) H(Ml /Cl K)=0 (233)又由所有密碼系統(tǒng)的明文和密鑰統(tǒng)計獨立，即 信息論與密

16、碼學19 H(Ml /K)=H(Ml) (234)將上述三式代入式(2-5-49) 得 H(Cl /K)=H(Ml) (235)對于多數(shù)密碼系統(tǒng)和相應的明文源，在l不太大時，例如lL，不確定性H(Cl /K)隨l近似于線性關系增加，因而可將上式寫成 H(Cl |K)H(ML) 1 lL (236)將式(2-5-48)和式(2-5-54)代入式(2-5-47)得 (237)由式(2-5-41)知，上式括號中的量是L長二元信源序列的多余度，故有 I(K; CL)=lL 0 L 1 (238)又由于信息論與密碼學20I(K; CL)=H(K)H(K/Cl)因而有 H(K/Cl)H(K)lL (239

17、)由此可見，當l足夠小時，密鑰含糊度將隨截獲的密文長度l線性地降低，直到當H(KCl)變得相當小為止。 由式(2-5-57)及唯一解距離0的定義可得 0H(K)/L (240)討論： 若L=0，即當明文經(jīng)過最佳數(shù)據(jù)壓縮編碼后，其惟一解距離0。雖然這時系統(tǒng)不一定滿足H(K)H(ML)的完善保密條件，但不管截獲的密報量有多大，密鑰的含糊度仍為H(K/Cl)H(K)，即可能的密鑰解有2H(K)個之多! 信息論與密碼學21 實際中不可能實現(xiàn)L =0，但是在消息進行加密之 前，先進行壓縮編碼來減小多余度，對于提高系統(tǒng)安全性是絕對必要的! 多余度的存在，使得任何密碼體制在有限密鑰下(H(K)為有限)，其惟

18、一解距離都將是有限的，因而在理論上都將是可破的。 一些使數(shù)據(jù)擴展的方式對于密碼的安全是不利的。 增大H(K)是提高保密系統(tǒng)安全性的途徑，即采用復雜的密碼體制，直至一次一密鑰體制。信息論與密碼學22 例2-2 英語單表代換密碼的密鑰量|K=26!，其密鑰空間的熵為H(K)=lb(26!)=88.4 bits。由例2-1知，=3.2bits/字母，所以這一密碼體制的唯一解距離=88.4/3.2=27.6字母。 此例說明，只要截獲到28個字母長的密文，原則上就可能破譯英語單表代換密碼。這和著名密碼分析家W. F. Friedman的經(jīng)驗值25個字母相符。例如，當密文量=40字母，若每個字母的多余度以

19、=1.5計算，一個有意義的脫密消息的期望數(shù)僅為1.210-10。因此，當?shù)玫揭粋€有意義的解時顯然是可信賴的。但若以=20個密文字母破譯，有意義的脫密解高達2.2107個之多，如果得到了一個有意義的解，其可信度是很低的。信息論與密碼學23 例2-3 下面給出幾種密碼體制對英語報文加密時的唯一解距離。 (1)周期為d的移位密碼，H(K)=lb(d!)，0=lb(d!)/3.2=0.3dlb(d/e)字母。若選d=27，則d/e10，lb(d/e)3.2，故0=2.7字母。 (2)含q個字母表的單表代換，H(K)=lb(q!)，0=lb(q!)/。例如q=26，=3.2就為例2-5-6的情況。 (3

20、) 周期為d的代換密碼(如Beaufort或Vigenre密碼)。H(K)=lb(qd)=dlbq，0 =(dlbq)/，對英語，01.5d。 這些結果都是在統(tǒng)計意義下得到的，因此，只有當處理的報文數(shù)據(jù)足夠大時才適用。信息論與密碼學24 六、實際保密性 理論保密性：碼分析者有無限的時間、設備和資金條件下，惟密文攻擊時密碼系統(tǒng)的安全性。一個密碼系統(tǒng)，如果對手有無限的資源可利用，而在截獲任意多密報下仍不能被破譯，則它在理論上是保密的。 實際保密性：一個密碼系統(tǒng)的破譯所需要的努力，如果超過了對手的能力(時間、資源等)時，則該系統(tǒng)為實際上安全保密的 。 保密的相對性: 最小保障時間(Minimum c

21、over time)：信息論與密碼學25 計算能力 (時間、費用等)與破譯算法的有效性 破譯平均工作量W(l)：破譯l長截獲密文所需的計算。 破譯工作特性(Work characteristic) ：W(l)隨l的變化曲線 ，其中W(l)可用人-時度量。平均是在所有可能密鑰上進行的。W(l)可用來衡量密碼系統(tǒng)的實際保密性。信息論與密碼學26W(l)H(K /C)W(l) 0 H(K)/ L l(密文量)圖2-3 破譯工作特性信息論與密碼學27 圖中，點線表示可能的解多于一個的區(qū)域，對各可能的解出現(xiàn)的概率需分別確定；實線表示有惟一解的區(qū)域。由圖可知，隨密文量l增加，W(l)會降至一個漸近值。 任

22、何一個非理想系統(tǒng)，其工作特性的趨勢大致和圖2-5-6一致，但W(l)的絕對取值隨密碼體制不同相差極大。即使當它們的密鑰含糊度H(KCl )隨l變化的曲線大致相同時，它們的W(l)也會有很大差別。例如，密鑰量和簡單代換一樣的維吉尼亞或組合維吉尼亞密碼的工作特性要比簡單代換密碼的好得多。 如何實現(xiàn)使破譯一個密碼系統(tǒng)所需的工作量極大化，這是博奕論中“極大化極小”問題。僅僅從對付現(xiàn)有的標準的密碼分析法是不夠的，還必須確保沒有輕而易舉的破譯方法。 要判定密碼體制的安全性絕非易事！信息論與密碼學28 如何保證破譯它所需的工作量足夠大？ 研究分析者可能采用的有哪些分析法，爾后估計各法破譯該體制時所需的平均工

23、作量W(l)。這需要有豐富的密碼分析經(jīng)驗，這種方法在實際中常會使用。設計者要盡可能在一般條件下描述這些分析方法，設法構造一種可以抗擊這類一般分析法的密碼系統(tǒng)。 估計破譯一個保密系統(tǒng)所需的平均工作量W(l) 的另一種途徑是，將破譯此密碼的難度等價于解數(shù)學上的某個已知難題。Shannon在1949年時雖然沒有計算復雜性這樣的理論工具可用，但他已明確地意識到這一問題，他曾指出“好密碼的設計問題，本質上是尋找針對某些其它條件的一種求解難題的問題”。信息論與密碼學29七、乘積密碼系統(tǒng)(Product cryptosystems) 利用“乘積”對簡單密碼進行組合，可構造復雜而安全的密碼系統(tǒng)。設計當代密碼有

24、重要指導意義，許多近代分組密碼體制，幾乎無一例外都采用了這一思想。 為討論簡單，設C=M，這類密碼稱為自同態(tài)(Endomorphic)密碼。令S1=(M, M ,K1, E1, D1)和S2=(M, M ,K2, E2, D2)是兩個自同態(tài)密碼系統(tǒng)，它們有相同的明文空間和密文空間。S1和S1的乘積S1S2表示為(M, M , K1 K2, E, D)。乘積密碼系統(tǒng)的密鑰為 k=(k1, k2)，k1 K1 ，k2 K2 加密： (241) 信息論與密碼學30解 密：由于k1和k2獨立選取，故有信息論與密碼學(242)(243)31 特例：冪等(Idempotent)密碼系統(tǒng)：SS=S2 =S。

25、可以推廣到n階乘積密碼以Sn表示。 移位、代換、仿射、Hill、Vigenre和置換等密碼都是冪等體制。若密碼是冪等的，則不會采用乘積S2，即使用另一個密鑰，也不會增大安全性。 對于非冪等密碼體制，增加迭代次數(shù)，會增大潛在的安全性。兩個不同的密碼進行乘積常會得到一個非冪等密碼。 易于證明，若S1和S2是冪等，則S1S2也是冪等的。因為 (S1S2)(S1S2)=S1(S2S1)S2 =(S1S1)(S2S2)=S1S2 (244)信息論與密碼學32八、認證系統(tǒng)(Authentication system) 認證是為了防止主動攻擊，如對消息的內容、順序、和時間的竄改以及重發(fā)等偽裝、竄擾等的重要技

26、術，使發(fā)送的消息具有被驗證的能力，使接收者或第三者能夠識別和確認消息的真?zhèn)巍崿F(xiàn)這類功能的密碼系統(tǒng)稱作認證系統(tǒng)。 認證目的： （1）驗證信息的發(fā)送者是真的、而不是冒充的，此為實體認證，包括信源、信宿等的認證和識別； （2）驗證信息的完整性，此為消息認證，驗證數(shù)據(jù)在傳送或存儲過程中未被竄改、重放或延遲等。 信息論與密碼學33 認證的理論與技術：是保密學研究的一個重要領域，包括認證系統(tǒng)、雜湊(Hash)函數(shù)、數(shù)字簽名、身份證明、認證協(xié)議等。 保密性：保密性是使截獲者在不知密鑰條件下不能解讀密文的內容。 認證性：使任何不知密鑰的人不能構造一個密報，使意定的接收者脫密成一個可理解的消息(合法的消息)。

27、 完整性(integrity)：在有自然和人為干擾條件下，系統(tǒng)保持檢測錯誤和恢復消息和原來發(fā)送消息一致性的能力。實際中常常借助于糾、檢錯技術和雜湊技術來保證消息的完整性。 信息論與密碼學34要求： 意定的接收者能夠檢驗和證實消息的合法性和真實性。 消息的發(fā)送者對所發(fā)送的消息不能抵賴。 除了合法消息發(fā)送者外，其它人不能偽造合法的消息。而且在已知合法密文c和相應消息m下，要確定加密密鑰或系統(tǒng)地偽造合法密文在計算上是不可行的。 必要時可由第三者作出仲裁。信息論與密碼學35 認證的信息理論：類似于保密系統(tǒng)的信息理論，可將信息論用于研究認證系統(tǒng)的理論安全性和實際安全性，指出認證系統(tǒng)的性能極限以及設計認證

28、碼必須遵循的原則。保密和認證同是信息系統(tǒng)安全的兩個重要方面，但它們是兩個不同屬性的問題。認證不能自動地提供保密性，而保密也不能自然地提供認證功能。一個純認證系統(tǒng)的模型如圖2-4所示。在這個系統(tǒng)中的發(fā)送者通過一個公開信道將消息送給接收者，接收者不僅想收到消息本身，而且還要驗證消息是否來自合法的發(fā)送者及消息是否經(jīng)過竄改。系統(tǒng)中的密碼分析者不僅要截收和分析信道中傳送的密報，而且可偽造密文送給接收者進行欺詐，稱其為系統(tǒng)的竄擾者(Tamper)更加貼切。實際認證系統(tǒng)可能還要防止收、發(fā)之間的相互欺詐。信息論與密碼學36信息論與密碼學圖2-4 純認證系統(tǒng)模型信道竄擾者認證編碼器認證譯碼器信 源信 宿密鑰源安

29、全信道37信息論與密碼學 認證編碼 在要發(fā)送的消息中引入多余度，使通過信道傳送的可能序列集Y大于消息集X。對于任何選定的編碼規(guī)則(相應于某一特定密鑰)：發(fā)方可從Y中選出用來代表消息的許用序列，即碼字；收方可根據(jù)編碼規(guī)則唯一地確定出發(fā)方按此規(guī)則向他傳來的消息。竄擾者由于不知道密鑰，因而所偽造的假碼字多是Y中的禁用序列，收方將以很高的概率將其檢測出來而被拒絕。認證系統(tǒng)設計者的任務是構造好的認證碼(Authentication Code)，使接收者受騙概率極小化。 令xX為要發(fā)送的消息，kK是發(fā)方選定的密鑰，y=A(x, k)Y是表示消息x的認證碼字，Ak=y=A(x, k), xX為認證碼。Ak是

30、Y中的許用(合法)序列集，而其補集Ak則為禁用序列集，且AkAk=Y。38信息論與密碼學 接收者知道認證編碼A(，)和密鑰k，故從收到的y可惟一地確定出消息x。竄擾者雖然知道X、Y、y、A(，)，但不知道具體密鑰k，他的目標是想偽造出一個假碼字y*，使y*Ak，使接收者收到y(tǒng)*后可以密鑰k解密得到一個合法的、可能由發(fā)端送出的消息x*，使接收者上當受騙。如果發(fā)生這一事件，則認為竄擾者欺詐成功。 竄擾者攻擊的基本方式： 模仿偽造(Impersonative Fraudulent)，竄擾者在未觀測到認證信道中傳送的合法消息(或認證碼字)條件下偽造假碼字y*，稱其為無密文偽造更合適些。若接收者接受y*

31、作為認證碼字，則說竄擾者攻擊成功。39信息論與密碼學 代換偽造(Substitution Fraudulent)，竄擾者截收到認證系統(tǒng)中的認證碼字y后，進行分析并偽造假認證碼字y*，故可稱為已知密文偽造。若接收者接受y*為認證碼字，則稱竄擾者攻擊成功。竄擾者可以自由地選擇最有利的攻擊方式。 竄擾者成功概率(接收者受騙概率)： pd=maxpI，pS (245) pI：竄擾者采用模仿攻擊時最大可能的成功概率 ps：在代換攻擊時最大可能的成功概率。 40信息論與密碼學 完善認證性(Perfect Authentication)：令#Y、#X、#K分別表示密文空間、消息空間、密鑰空間中概率為非零的元

32、素的個數(shù)。一般認證編碼中#Y #X，且認證碼中元素個數(shù)#Ak#X 。 對每個kK，至少有#X個不同的密文使p(Y=y|K=k)0。若對手采用模仿偽造策略，完全隨機地以非零概率從Y中選出一個作為偽造密文(認證碼字)送給接收者，則其成功的概率有 (246) 41信息論與密碼學 要安全性高，即要pI小，需有#Y#X。由于#X0，要求完全保護，即要pI=0是不可能實現(xiàn)的。而且可以證明，要求式(6-1-2)等號成立的充要條件是：對任一kK，都恰有#Ak#X。這表明采用隨機密碼不能使上式等號成立。由于認證系統(tǒng)不能實現(xiàn)完全保護，故將完善認證定義為對給定認證碼空間，能使受騙率pd最小的認證系統(tǒng)(在此意義下，即

33、使對#Y=#X時的平凡情況，此時pd =1，也有完善認證可言)。42信息論與密碼學 若在最佳模仿策略下竄擾者只能隨機地選取一個yY，則有 H(Y)=log#Y (247) 而若在任一給定密鑰下，任一認證碼字在認證碼A中等概出現(xiàn)，則有 H(Y|K)=log#X (248)對式(6-1-2)兩邊取對數(shù)可得 log pIlog#Xlog#Y=H(Y)H(Y|K)=I(Y；K) 上述結果可歸結為定理6-1-1。 定理6-1-1 認證信道有 log pII(Y；K) (249) 43信息論與密碼學等號成立的充要條件為式(6-1-3)和(6-1-4)成立，且 log pd I(Y；K) (250)等號成立

34、的必要條件為式(247)和(248)成立。 Simmons稱式(250)為認證信道的容量。定義 完善認證是使式(2-50)等號成立的認證系統(tǒng)。 由式(2-50)可知，即使系統(tǒng)是完善的，要使pd小就必須使I(Y；K)大，也就是說使竄擾者從密文Y中可提取更多的密鑰信息！而由式I (Y；K)=H(K|Y)H(K)知，在極端情況下，當 H(K|Y)=0 即竄擾者可從Y獲取有關密鑰的全部信息時有 log pd H(K) (251) 44信息論與密碼學 即有 pd #K (250) 這是一個平凡的下限。Gilbert等曾給出一個更強的下限。定理6-1-3 對具有保密的認證(竄擾者不知信源狀態(tài))有 log

35、pd 1/2H(K) (250)而對無保密的認證(竄擾者知道信源狀態(tài))有l(wèi)og pd 1/2H(K)H(XY)H(Y)=1/2H(K)H(X|Y) (251)系 (252)45信息論與密碼學 類似于保密系統(tǒng)的安全性，認證系統(tǒng)的安全性也劃分為兩大類，即理論安全性和實際安全性。 理論安全性又稱作無條件安全性，就是我們上面所討論的。它與竄擾者的計算能力或時間無關，也就是說竄擾者破譯體制所做的任何努力都不會優(yōu)于隨機試湊方式。 實際安全性是根據(jù)破譯認證體制所需的計算量來評價其安全性的。如果破譯一個系統(tǒng)在原理上是可能的，但以所有已知的算法和現(xiàn)有的計算工具不可能完成所要求的計算量，就稱其為計算上安全的。如果

36、能夠證明破譯某體制的困難性等價于解決某個數(shù)學難題，就稱其為可證明安全的，如RSA體制。46信息論與密碼學 這兩種安全性雖都是從計算量來考慮，但不盡相同，計算安全要算出或估計出破譯它的計算量下限，而可證明安全則要從理論上證明破譯它的計算量不低于解已知難題的計算量。 47信息論與密碼學 認證碼 上面給出了認證系統(tǒng)安全性指標pd的下限，本節(jié)將研究如何構造認證碼使其接近或達到其性能下限。 無條件安全認證碼和糾錯碼理論互為對偶。這兩者都需要引入多余數(shù)字，在信道中可傳送的序列集中只有一小部分用于傳信。這是認證和糾錯賴以實現(xiàn)的基本條件。糾錯碼的目的是抗噪聲等干擾，要求將碼中各碼字配置得盡可能地散開(如最小漢

37、明距離極大化)，以保證在干擾作用下所得到的接收序列與原來的碼字最接近。在最大似然譯碼時可以使平均譯碼錯誤概率極小化。認證碼的目的是防止偽造和受騙。對于發(fā)送的任何消息序列(或碼字)，竄擾者采用最佳策略所引入的代換或模擬偽造序列應盡可能地散布于信道可傳送的序列集中。48信息論與密碼學 在認證系統(tǒng)中，密鑰的作用類似于信道的干擾，在它們的控制下變換編碼規(guī)則，使造出的代表消息的碼字盡可能交義地配置，即將消息空間X最佳地散布于輸出空間(信道傳送序列集)Y之中，以使竄擾者在不知道密鑰情況下，偽造成功的概率極小化。 49信息論與密碼學九、雜湊函數(shù)(Hash Function) 將任意長數(shù)字串M映射成一個較短的

38、定長輸出數(shù)字串H的函數(shù)，以h表示，h(M)易于計算，稱H= h(M)為M的雜湊值，也稱雜湊碼、雜湊結果等或簡稱雜湊。 特點：H打上了輸入數(shù)字串的烙印，為數(shù)字指紋(Digital Finger Print)。h是多對一映射，因此我們不能從H求出原來的M，但可以驗證任一給定序列M是否與M有相同的雜湊值。 分類： 密碼雜湊函數(shù)，有密鑰控制，以h(k, M)表示。其雜湊值不僅與輸入有關，而且與密鑰有關，只有持此密鑰的人才能計算出相應的雜湊值，因而具有身份驗證功能，如消息認證碼MACANSI X 9.9。雜湊值也是一種認證符或認證碼。它要滿足各種安全性要求，密碼雜湊函數(shù)在現(xiàn)在密碼學中有重要作用。50信息

39、論與密碼學 一般雜湊函數(shù)，無密鑰控制。無密鑰控制的單向雜湊函數(shù)，其雜湊值只是輸入字串的函數(shù)，任何人都可以計算，因而不具有身份認證功能，只用于檢測接收數(shù)據(jù)的完整性，如竄改檢測碼MDC，用于非密碼計算機應用中。 應用：在密碼學和數(shù)據(jù)安全技術中，它是實現(xiàn)有效、安全可靠數(shù)字簽字和認證的重要工具，是安全認證協(xié)議中的重要模塊。 別名：壓縮(Compression)函數(shù)、緊縮(Contraction)函數(shù)、數(shù)據(jù)認證碼(Data Authentication Code)、消息摘要(Message Digest)、數(shù)字指紋、數(shù)據(jù)完整性校驗(Data Integity Check)、密碼檢驗和(Cryptogra

40、phic Check Sum)、消息認證碼MAC(Message Authentication Code)、竄改檢測碼MDC(Manipulation Detection Code)等。51信息論與密碼學 密碼學中所用的雜湊函數(shù)必須滿足安全性的要求，要能防偽造，抗擊各種類型的攻擊，如生日攻擊、中途相遇攻擊等等。為此，必須深入研究雜湊函數(shù)的性質，從中找出能滿足密碼學需要的雜湊函數(shù)。52信息論與密碼學 雜湊函數(shù)、認證碼與檢錯碼的關系 雜湊函數(shù)、認證碼與檢錯碼都是利用冗余度。 線性分組檢錯碼是在長為L的消息數(shù)字上增加n比特校驗位，構成一個長為Ln (bit)線性碼。GF(2)上Ln維線性空間中的L維

41、子空間就是這類線性分組檢錯碼的碼空間。當碼字在傳輸過程中被竄擾，若結果不屬于碼空間，收端通過對n個一致檢驗關系的檢驗可以實現(xiàn)檢錯。一個好的檢錯線性碼在于使不可檢錯概率極小化，其最佳碼的不可檢錯上限為 pd 2-n1(1p)n (253) 式中p是信道誤碼率。在抗主動攻擊下，可認為p=1/2。而有 pd 2-n (254) 53信息論與密碼學 線性分組檢錯碼是一種MDC雜湊，可作為數(shù)據(jù)完整性檢驗，但不能作為身份認證。 二元認證碼是將長為L 的消息bit序列映射為Ln bit序列的編碼。在不同密鑰下，同一消息序列被映射為不同的碼序列。為了實現(xiàn)無條件安全認證，希望在密鑰控制下能將消息所對應的碼字在盡

42、可能交叉地配置，使不知密鑰的竄擾者成功的概率極小化。模仿偽造成功概率 (255) 此與最佳線性檢錯碼的不可檢錯概率的上限一致。 竄擾成功的概率限由(6-1-3)有 (256) 54信息論與密碼學 雜湊函數(shù)可以看作是一種非線性認證碼，將L bit輸入消息M變成碼字M|H，其中H是M的雜湊值，一般為n bit。故碼長為Ln (bit)。 這種非線性碼可能數(shù)極大，即相應的密鑰空間K可以很大，但從式(2-55)和式(2-56)式可以看出#K22n是無作用的。由此可以得出一個重要結論，即對于n bit雜湊值下，選擇密鑰比特數(shù)大于2n bit是無意義的。這對于設計雜湊算法有重要意義。這是將雜湊函數(shù)看作是一

43、種認證編碼給我們的啟示。 對于線性分組檢測碼來說，其編碼規(guī)則是固定的。因而#K=1。雖然其不可檢錯誤的概率上界為2-n，但Pd的下界為1。可見它不能抗擊竄擾者的攻擊。 55信息論與密碼學 雜湊函數(shù)壓縮輸入數(shù)字串與認證編碼之間的差別在于，后者是對固定長L bits進行編碼成Ln bits碼字，而前者對輸入字串長度未加限制。一般Ln bit，且當L不是n的整數(shù)倍時，采用填充辦法湊成L/n倍(表示取不小于括號內數(shù)的最小整數(shù))。雖然式(2-55)給出的對任意L取值模仿攻擊成功概率下限都是2-n。但對雜湊函數(shù)來說，輸入空間的選擇遠大于認證碼的情況。 為了減小碰撞，通常都將輸入消息數(shù)字串長度作為參數(shù)納入最

44、后一個分段中，這樣攻擊者在試圖找到偽消息M與發(fā)送消息M的雜湊值一樣時，必須使M的長度和M的長度一致才合法，從而大大增加了攻擊的難度。這種技術由Merkle和Damgrd等提出，稱作MD強化技術。Damgrd等證明經(jīng)過MD強化后，雜湊算法抗自由起始攻擊的強度等價于迭代函數(shù)的強度。56十、密碼學與計算復雜性 計算復雜性理論始于60年代，研究為什么某些計算不能有效地完成，其內在原因是什么，它與信息論有廣泛而深刻的聯(lián)系。兩者在研究史、理論、技術和方法論上都存在著密切關系。 Shannon在1949年曾指出幾乎所有有n個輸入的布爾函數(shù)，其計算所要求的門的個數(shù)都隨n指數(shù)增長。 Kolmogorov復雜性：

45、為計算一個問題所需的“典型”輸入長度。信息論與密碼學57 通信復雜性：兩個代理人各有一半輸入bit，通過通信交換盡可能少的信息完成一個布爾函數(shù)的計算?？山鉀Q并行復雜性的下限以及在芯片上計算函數(shù)所需的面積和時間等問題。 公鑰密碼學中的加密、簽字、智力樸克、零知識證明、概率性檢驗證明(Probabilistically Checkable Proofs)、證實和近似問題的難度等問題都和計算復雜性理論有密切關系。概率性檢驗證明是當今復雜性理論中最為深刻的結果。信息論與密碼學58 現(xiàn)代密碼學的一些新理論，特別是安全性的形式證明理論，也是建立在計算復雜性理論之上的。這一極為重要而又很前沿的問題。當今，任何密碼算法、協(xié)議的設計和相應標準的制定，都不能回避可證明安全性，都必須通過這一理論的嚴格檢驗。信息論與密碼學59密碼與計算復雜性關系 Shannon1949指出 “設計好的密碼問