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