【正文】 Sons, . Simmons, G. J., (Ed), “Contemporary Cryptology: The Science of Information Integrity,” IEEE Press, 1992. Stinson, D., “Cryptography: Theory and Practice,” CRC Press, 1995. 王育民 、 劉建偉 ， “ 通信網(wǎng)的安全 —— 理論與技術(shù) ” ， 西安電子科技大學(xué)出版社 ， 1999. 1。 如何確定問題在實(shí)際上為一個(gè)難題的準(zhǔn)則不容易 ，Shamir的 “ 中值復(fù)雜度 ” 可以考慮 。 而密碼分析者常常從最易解的問題下手 ， 密碼設(shè)計(jì)者希望問題中所有情況都是困難的 ， 但常常又難免會(huì)有少數(shù)容易的例子含于其中 。 這樣才能保證以此信息 、 且只能以它才能容易地實(shí)現(xiàn)解密 信息論與密碼學(xué) 63 計(jì)算復(fù)雜性無疑為設(shè)計(jì)密碼提供了一種理論依據(jù)和可能的途徑 ， 但這種理論像其它密碼安全度量理論一樣 ， 不可能提供一個(gè)密碼安全的充分條件 ， 而是提供了又一個(gè)新的必要條件 ！ 采用 NPC問題設(shè)計(jì)的 MerkleHellman背包體制被破譯說明了用 NPC問題設(shè)計(jì)雙鑰體制的局限性 。 ) l 問題的復(fù)雜性典型的作法是以其最壞 (最困難 )的情況或平均性質(zhì)作為度量標(biāo)準(zhǔn) ， 而對密碼有用的是在幾乎所有情況下都應(yīng)是難解的問題 。 信息論與密碼學(xué) 62 Shamir[1979]曾給出下述三點(diǎn)理由： l 復(fù)雜性理論通常是處理一類問題中的單個(gè)孤立例子 ，而密碼分析者常有一大堆與解統(tǒng)計(jì)有關(guān)的問題 。但計(jì)算上困難的問題并非一定就意味一個(gè)強(qiáng)的密碼 。 l 陷門單向函數(shù)是將一個(gè)陷門信息鑲嵌入一個(gè)計(jì)算難題之中 ， 以實(shí)現(xiàn)了對密碼分析者破譯它為一個(gè)難題 ， 而對自己人解密則容易實(shí)現(xiàn) 。 因此 ， 破譯者分析工作量若為多項(xiàng)式時(shí)間的任何加密算法都將歸為 NP類問題 。 比 NP更難的問題 ， 由于加密 、 解密時(shí)間需足夠高 (如可用多項(xiàng)式時(shí)間完成 )而不適用于密碼 。 ” 1976年 ， Diffie和 Hellman的文章則具體提出 ， 應(yīng)用計(jì)算復(fù)雜性來設(shè)計(jì)加密算法 。當(dāng)今，任何密碼算法、協(xié)議的設(shè)計(jì)和相應(yīng)標(biāo)準(zhǔn)的制定，都不能回避可證明安全性，都必須通過這一理論的嚴(yán)格檢驗(yàn)。 信息論與密碼學(xué) 59 現(xiàn)代密碼學(xué)的一些新理論，特別是安全性的形式證明理論，也是建立在計(jì)算復(fù)雜性理論之上的。 公鑰密碼學(xué)中的加密、簽字、智力樸克、零知識(shí)證明、概率性檢驗(yàn)證明 (Probabilistically Checkable Proofs)、證實(shí)和近似問題的難度等問題都和計(jì)算復(fù)雜性理論有密切關(guān)系。 信息論與密碼學(xué) 58 通信復(fù)雜性 ：兩個(gè)代理人各有一半輸入 bit，通過通信交換盡可能少的信息完成一個(gè)布爾函數(shù)的計(jì)算。 Shannon在 1949年曾指出幾乎所有有 n個(gè)輸入的布爾函數(shù)，其計(jì)算所要求的門的個(gè)數(shù)都隨 n指數(shù)增長。 57 十、密碼學(xué)與計(jì)算復(fù)雜性 計(jì)算復(fù)雜性理論始于 60年代，研究為什么某些計(jì)算不能有效地完成，其內(nèi)在原因是什么，它與信息論有廣泛而深刻的聯(lián)系。 Damg229。這種技術(shù)由 Merkle和 Damg229。但對雜湊函數(shù)來說，輸入空間的選擇遠(yuǎn)大于認(rèn)證碼的情況。?表示取不小于括號內(nèi)數(shù)的最小整數(shù) )。 56 信息論與密碼學(xué) 雜湊函數(shù)壓縮輸入數(shù)字串與認(rèn)證編碼之間的差別在于，后者是對固定長 L bits進(jìn)行編碼成 L＋ n bits碼字，而前者對輸入字串長度未加限制。 雖然其不可檢錯(cuò)誤的概率上界為 2n， 但 Pd的下界為 1。 對于線性分組檢測碼來說 ， 其編碼規(guī)則是固定的 。 這對于設(shè)計(jì)雜湊算法有重要意義 。 這種非線性碼可能數(shù)極大 ， 即相應(yīng)的密鑰空間 K可以很大 ， 但從式 (255)和式 (256)式可以看出 {K}22n是無作用的 。 竄擾成功的概率限由 (613)有 (2— 56) p xyI n? ? ?{ }{ } 2p p pkd I s? ?m a x { , }{ }155 信息論與密碼學(xué) l 雜湊函數(shù)可以看作是一種非線性認(rèn)證碼，將 L bit輸入消息 M變成碼字 M||H，其中 H是 M的雜湊值，一般為 n bit。 為了實(shí)現(xiàn)無條件安全認(rèn)證 ， 希望在密鑰控制下能將消息所對應(yīng)的碼字在盡可能交叉地配置 ， 使不知密鑰的竄擾者成功的概率極小化 。 l 二元認(rèn)證碼是將長為 L 的 消息 bit序列映射為 L＋ n bit序列的編碼 。 在抗主動(dòng)攻擊下 ， 可認(rèn)為 p=1/2。 當(dāng)碼字在傳輸過程中被竄擾 ， 若結(jié)果不屬于碼空間 ， 收端通過對 n個(gè)一致檢驗(yàn)關(guān)系的檢驗(yàn)可以實(shí)現(xiàn)檢錯(cuò) 。 l 線性分組檢錯(cuò)碼 是在長為 L的消息數(shù)字上增加 n比特校驗(yàn)位 ， 構(gòu)成一個(gè)長為 L＋ n (bit)線性碼 。為此，必須深入研究雜湊函數(shù)的性質(zhì)，從中找出能滿足密碼學(xué)需要的雜湊函數(shù)。 別名 ：壓縮 (Compression)函數(shù) 、 緊縮 (Contraction)函數(shù) 、 數(shù)據(jù)認(rèn)證碼 (Data Authentication Code)、 消息摘要 (Message Digest)、 數(shù)字指紋 、 數(shù)據(jù)完整性校驗(yàn) (Data Integity Check)、 密碼檢驗(yàn)和 (Cryptographic Check Sum)、 消息認(rèn)證碼 MAC(Message Authentication Code)、竄改檢測碼 MDC(Manipulation Detection Code)等 。 無密鑰控制的單向雜湊函數(shù) ， 其雜湊值只是輸入字串的函數(shù) ， 任何人都可以計(jì)算 ， 因而 不具有身份認(rèn)證功能 ， 只用于檢測接收數(shù)據(jù)的完整性 ， 如竄改檢測碼 MDC， 用于非密碼計(jì)算機(jī)應(yīng)用中 。 它要滿足各種安全性要求 ， 密碼雜湊函數(shù)在現(xiàn)在密碼學(xué)中有重要作用 。 其雜湊值不僅與輸入有關(guān) ， 而且與密鑰有關(guān) ， 只有持此密鑰的人才能計(jì)算出相應(yīng)的雜湊值 ， 因而具有 身份驗(yàn)證功能 ， 如消息認(rèn)證碼 MAC[ANSI X ]。 h是 多對一映射 ， 因此我們不能從 H求出原來的 M， 但可以驗(yàn)證任一給定序列 M’是否與M有相同的雜湊值 。 50 信息論與密碼學(xué) 九 、 雜湊函數(shù) (Hash Function) 將任意長數(shù)字串 M映射成一個(gè)較短的定長輸出數(shù)字串 H的函數(shù) ， 以 h表示 ， h(M)易于計(jì)算 ， 稱 H= h(M)為 M的 雜湊值 ， 也稱 雜湊碼 、 雜湊結(jié)果等或簡稱雜湊 。 對于發(fā)送的任何消息序列 (或碼字 )， 竄擾者采用最佳策略所引入的代換或模擬偽造序列應(yīng)盡可能地散布于信道可傳送的序列集中 。在最大似然譯碼時(shí)可以使平均譯碼錯(cuò)誤概率極小化 。 這是認(rèn)證和糾錯(cuò)賴以實(shí)現(xiàn)的基本條件 。 無條件安全認(rèn)證碼和糾錯(cuò)碼理論互為 對偶 。 47 信息論與密碼學(xué) 這兩種安全性雖都是從計(jì)算量來考慮 ， 但不盡相同 ，計(jì)算安全要算出或估計(jì)出破譯它的計(jì)算量下限 ， 而可證明安全則要從理論上證明破譯它的計(jì)算量不低于解已知難題的計(jì)算量 。 如果破譯一個(gè)系統(tǒng)在原理上是可能的 ，但以所有已知的算法和現(xiàn)有的計(jì)算工具不可能完成所要求的計(jì)算量 ， 就稱其為計(jì)算上安全的 。 它與竄擾者的計(jì)算能力或時(shí)間無關(guān) ， 也就是說竄擾者破譯體制所做的任何努力都不會(huì)優(yōu)于隨機(jī)試湊方式 。 定理 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í)際安全性 。 由式 (250)可知 ， 即使系統(tǒng)是完善的 ， 要使 pd小就必須使 I(Y； K)大 ， 也就是說使竄擾者從密文 Y中可提取更多的密鑰信息 ！ 而由式－ I (Y； K)=H(K|Y)－ H(K)知 ，在極端情況下 ， 當(dāng) H(K|Y)=0 即竄擾者可從 Y獲取有關(guān)密鑰的全部信息時(shí)有 log pd ?－ H(K) (2— 51) 45 信息論與密碼學(xué) 即有 pd ?{K} (2— 50) 這是一個(gè)平凡的下限 。 Simmons稱式 (2— 50)為 認(rèn)證信道的容量 。 43 信息論與密碼學(xué) 若在最佳模仿策略下竄擾者只能隨機(jī)地選取一個(gè)y?Y， 則有 H(Y)=log{Y} (2— 47) 而若在任一給定密鑰下 ， 任一認(rèn)證碼字在認(rèn)證碼 A中等概出現(xiàn) ， 則有 H(Y|K)=log{X} (2—