【正文】 改檢測碼 MDC(Manipulation Detection Code)等 。 52 信息論與密碼學(xué) 密碼學(xué)中所用的雜湊函數(shù)必須滿足安全性的要求，要能防偽造，抗擊各種類型的攻擊，如生日攻擊、中途相遇攻擊等等。為此，必須深入研究雜湊函數(shù)的性質(zhì)，從中找出能滿足密碼學(xué)需要的雜湊函數(shù)。 53 信息論與密碼學(xué) 雜湊函數(shù)、認(rèn)證碼與檢錯碼的關(guān)系 雜湊函數(shù) 、 認(rèn)證碼與檢錯碼都是利用冗余度 。 l 線性分組檢錯碼 是在長為 L的消息數(shù)字上增加 n比特校驗位 ， 構(gòu)成一個長為 L＋ n (bit)線性碼 。 GF(2)上 L＋ n維線性空間中的 L維子空間就是這類線性分組檢錯碼的碼空間 。 當(dāng)碼字在傳輸過程中被竄擾 ， 若結(jié)果不屬于碼空間 ， 收端通過對 n個一致檢驗關(guān)系的檢驗可以實現(xiàn)檢錯 。 一個好的檢錯線性碼在于使不可檢錯概率極小化 ，其最佳碼的不可檢錯上限為 pd ? 2n[1－ (1－ p)n] (2— 53) 式中 p是信道誤碼率 。 在抗主動攻擊下 ， 可認(rèn)為 p=1/2。而有 pd ? 2n (2— 54) 54 信息論與密碼學(xué) 線性分組檢錯碼是一種 MDC雜湊，可作為數(shù)據(jù)完整性檢驗，但不能作為身份認(rèn)證。 l 二元認(rèn)證碼是將長為 L 的 消息 bit序列映射為 L＋ n bit序列的編碼 。 在不同密鑰下 ， 同一消息序列被映射為不同的碼序列 。 為了實現(xiàn)無條件安全認(rèn)證 ， 希望在密鑰控制下能將消息所對應(yīng)的碼字在盡可能交叉地配置 ， 使不知密鑰的竄擾者成功的概率極小化 。 模仿偽造成功概率 (2— 55) 此與最佳線性檢錯碼的不可檢錯概率的上限一致 。 竄擾成功的概率限由 (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。故碼長為 L＋ n (bit)。 這種非線性碼可能數(shù)極大 ， 即相應(yīng)的密鑰空間 K可以很大 ， 但從式 (255)和式 (256)式可以看出 {K}22n是無作用的 。 由此可以得出一個重要結(jié)論 ， 即對于 n bit雜湊值下 ， 選擇密鑰比特數(shù)大于 2n bit是無意義的 。 這對于設(shè)計雜湊算法有重要意義 。 這是將雜湊函數(shù)看作是一種認(rèn)證編碼給我們的啟示 。 對于線性分組檢測碼來說 ， 其編碼規(guī)則是固定的 。因而 {K}=1。 雖然其不可檢錯誤的概率上界為 2n， 但 Pd的下界為 1。 可見它不能抗擊竄擾者的攻擊 。 56 信息論與密碼學(xué) 雜湊函數(shù)壓縮輸入數(shù)字串與認(rèn)證編碼之間的差別在于，后者是對固定長 L bits進(jìn)行編碼成 L＋ n bits碼字，而前者對輸入字串長度未加限制。一般 L?n bit，且當(dāng) L不是 n的整數(shù)倍時，采用 填充 辦法湊成 ?L/n?倍 (??表示取不小于括號內(nèi)數(shù)的最小整數(shù) )。雖然式 (255)給出的對任意 L取值模仿攻擊成功概率下限都是 2n。但對雜湊函數(shù)來說，輸入空間的選擇遠(yuǎn)大于認(rèn)證碼的情況。 為了減小碰撞，通常都將輸入消息數(shù)字串長度作為參數(shù)納入最后一個分段中，這樣攻擊者在試圖找到偽消息 M’與發(fā)送消息 M的雜湊值一樣時，必須使 M’的長度和 M的長度一致才合法，從而大大增加了攻擊的難度。這種技術(shù)由 Merkle和 Damg229。rd等提出，稱作 MD強(qiáng)化技術(shù) 。 Damg229。rd等證明經(jīng)過 MD強(qiáng)化后，雜湊算法抗自由起始攻擊的強(qiáng)度等價于迭代函數(shù)的強(qiáng)度。 57 十、密碼學(xué)與計算復(fù)雜性 計算復(fù)雜性理論始于 60年代，研究為什么某些計算不能有效地完成，其內(nèi)在原因是什么，它與信息論有廣泛而深刻的聯(lián)系。兩者在研究史、理論、技術(shù)和方法論上都存在著密切關(guān)系。 Shannon在 1949年曾指出幾乎所有有 n個輸入的布爾函數(shù)，其計算所要求的門的個數(shù)都隨 n指數(shù)增長。 Kolmogorov復(fù)雜性 ：為計算一個問題所需的 “ 典型 ” 輸入長度。 信息論與密碼學(xué) 58 通信復(fù)雜性 ：兩個代理人各有一半輸入 bit，通過通信交換盡可能少的信息完成一個布爾函數(shù)的計算。可解決并行復(fù)雜性的下限以及在芯片上計算函數(shù)所需的面積和時間等問題。 公鑰密碼學(xué)中的加密、簽字、智力樸克、零知識證明、概率性檢驗證明 (Probabilistically Checkable Proofs)、證實和近似問題的難度等問題都和計算復(fù)雜性理論有密切關(guān)系。概率性檢驗證明是當(dāng)今復(fù)雜性理論中最為深刻的結(jié)果。 信息論與密碼學(xué) 59 現(xiàn)代密碼學(xué)的一些新理論，特別是安全性的形式證明理論，也是建立在計算復(fù)雜性理論之上的。這一極為重要而又很前沿的問題。當(dāng)今，任何密碼算法、協(xié)議的設(shè)計和相應(yīng)標(biāo)準(zhǔn)的制定，都不能回避可證明安全性，都必須通過這一理論的嚴(yán)格檢驗。 信息論與密碼學(xué) 60 密碼與計算復(fù)雜性關(guān)系 Shannon[1949]指出 “ 設(shè)計好的密碼問題本質(zhì)上是尋求在某些其它條件下的一個難解問題 。 ” 1976年 ， Diffie和 Hellman的文章則具體提出 ， 應(yīng)用計算復(fù)雜性來設(shè)計加密算法 。 他們注意到一些 NPC問題可能作為密碼的備選方案 。 比 NP更難的問題 ， 由于加密 、 解密時間需足夠高 (如可用多項式時間完成 )而不適用于密碼 。 但是 ， 如果將密碼問題限制于 NP類 ，就使得密碼分析者可以猜測某個密鑰 ， 而能在多項式時間內(nèi)檢驗其是否正確 (如以它加密已知明文看密文是否與截獲的一致 )。 因此 ， 破譯者分析工作量若為多項式時間的任何加密算法都將歸為 NP類問題 。 信息論與密碼學(xué) 61 通過對 NP復(fù)雜性理論的檢驗 ， Diffie和 Hellman推想密碼學(xué)可以利用其中的 NPC類問題來加密數(shù)據(jù) ，使得破譯者在用一般方法破譯它時需解 NPC問題 。 l 陷門單向函數(shù)是將一個陷門信息鑲嵌入一個計算難題之中 ， 以實現(xiàn)了對密碼分析者破譯它為一個難題 ， 而對自己人解密則容易實現(xiàn) 。 l 密碼的強(qiáng)度依賴于構(gòu)造密碼問題的計算復(fù)雜性 。但計算上困難的問題并非一定就意味一個強(qiáng)的密碼 。即計算復(fù)雜性大只是密碼安全的一個必要條件 。 信息論與密碼學(xué) 62 Shamir[1979]曾給出下述三點理由： l 復(fù)雜性理論通常是處理一類問題中的單個孤立例子 ，而密碼分析者常有一大堆與解統(tǒng)計有關(guān)的問題 。 (例如 ，由同一密鑰加密的幾個組密文 。 ) l 問題的復(fù)雜性典型的作法是以其最壞 (最困難 )的情況或平均性質(zhì)作為度量標(biāo)準(zhǔn) ， 而對密碼有用的是在幾乎所有情況下都應(yīng)是難解的問題 。 l 一種任意困難的問題不一定可能變成為一種密碼體制 ， 只有在問題中以某種方法可嵌入陷門信息的才能用于密碼 。 這樣才能保證以此信息 、 且只能以它才能容易地實現(xiàn)解密 信息論與密碼學(xué) 63 計算復(fù)雜性無疑為設(shè)計密碼提供了一種理論依據(jù)和可能的途徑 ， 但這種理論像其它密碼安全度量理論一樣 ， 不可能提供一個密碼安全的充分條件 ， 而是提供了又一個新的必要條件 ！ 采用 NPC問題設(shè)計的 MerkleHellman背包體制被破譯說明了用 NPC問題設(shè)計雙鑰體制的局限性 。 首先 ， Brassard[1979]指出除非 NP=CoNP， 否則密碼分析者面臨的問題將不會是 NP難問題； 其次 ， 復(fù)雜性理論主要關(guān)心的是問題的漸近復(fù)雜性； 信息論與密碼學(xué) 64 第三 ， NPC是問題復(fù)雜性最壞情況下的量度 ， 而密碼的安全性應(yīng)當(dāng)依賴于問題的復(fù)雜度平均情況 ， 最好是在所有情況下問題都是難于處理的 。 而密碼分析者常常從最易解的問題下手 ， 密碼設(shè)計者希望問題中所有情況都是困難的 ， 但常常又難免會有少數(shù)容易的例子含于其中 。 只要： 敵人不能輕易認(rèn)出容易的問題； 采用隨機(jī)密鑰 ， 能夠輕易解出問題的概率極小 ， 以至于不值得去試 。 如何確定問題在實際上為一個難題的準(zhǔn)則不容易 ，Shamir的 “ 中值復(fù)雜度 ” 可以考慮 。 信息論與密碼學(xué) 65 參考文獻(xiàn) Menezes, A. Z., “Hand Book of Applied Cryptography,” CRC Press, 1997. Schineier, B., “Applied Cryptography,” 2nd ed., John Wiley amp。 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。 信息論與密碼學(xué)