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