【正文】 信息論與密碼學(xué) 65 參考文獻(xiàn) Menezes, A. Z., “Hand Book of Applied Cryptography,” CRC Press, 1997. Schineier, B., “Applied Cryptography,” 2nd ed., John Wiley amp。 首先 ， 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)題都是難于處理的 。 (例如 ，由同一密鑰加密的幾個(gè)組密文 。 l 密碼的強(qiáng)度依賴(lài)于構(gòu)造密碼問(wèn)題的計(jì)算復(fù)雜性 。 但是 ， 如果將密碼問(wèn)題限制于 NP類(lèi) ，就使得密碼分析者可以猜測(cè)某個(gè)密鑰 ， 而能在多項(xiàng)式時(shí)間內(nèi)檢驗(yàn)其是否正確 (如以它加密已知明文看密文是否與截獲的一致 )。 信息論與密碼學(xué) 60 密碼與計(jì)算復(fù)雜性關(guān)系 Shannon[1949]指出 “ 設(shè)計(jì)好的密碼問(wèn)題本質(zhì)上是尋求在某些其它條件下的一個(gè)難解問(wèn)題 。概率性檢驗(yàn)證明是當(dāng)今復(fù)雜性理論中最為深刻的結(jié)果。 Kolmogorov復(fù)雜性 ：為計(jì)算一個(gè)問(wèn)題所需的 “ 典型 ” 輸入長(zhǎng)度。rd等證明經(jīng)過(guò) MD強(qiáng)化后，雜湊算法抗自由起始攻擊的強(qiáng)度等價(jià)于迭代函數(shù)的強(qiáng)度。 為了減小碰撞，通常都將輸入消息數(shù)字串長(zhǎng)度作為參數(shù)納入最后一個(gè)分段中，這樣攻擊者在試圖找到偽消息 M’與發(fā)送消息 M的雜湊值一樣時(shí)，必須使 M’的長(zhǎng)度和 M的長(zhǎng)度一致才合法，從而大大增加了攻擊的難度。一般 L?n bit，且當(dāng) L不是 n的整數(shù)倍時(shí)，采用 填充 辦法湊成 ?L/n?倍 (?因而 {K}=1。 由此可以得出一個(gè)重要結(jié)論 ， 即對(duì)于 n bit雜湊值下 ， 選擇密鑰比特?cái)?shù)大于 2n bit是無(wú)意義的 。 模仿偽造成功概率 (2— 55) 此與最佳線性檢錯(cuò)碼的不可檢錯(cuò)概率的上限一致 。而有 pd ? 2n (2— 54) 54 信息論與密碼學(xué) 線性分組檢錯(cuò)碼是一種 MDC雜湊，可作為數(shù)據(jù)完整性檢驗(yàn)，但不能作為身份認(rèn)證。 GF(2)上 L＋ n維線性空間中的 L維子空間就是這類(lèi)線性分組檢錯(cuò)碼的碼空間 。 52 信息論與密碼學(xué) 密碼學(xué)中所用的雜湊函數(shù)必須滿(mǎn)足安全性的要求，要能防偽造，抗擊各種類(lèi)型的攻擊，如生日攻擊、中途相遇攻擊等等。 51 信息論與密碼學(xué) ? 一般雜湊函數(shù) ， 無(wú)密鑰控制 。 分類(lèi) ： ? 密碼雜湊函數(shù) ， 有密鑰控制 ， 以 h(k, M)表示 。 49 信息論與密碼學(xué) 在認(rèn)證系統(tǒng)中 ， 密鑰的作用類(lèi)似于信道的干擾 ， 在它們的控制下變換編碼規(guī)則 ， 使造出的代表消息的碼字盡可能交義地配置 ， 即將消息空間 X最佳地散布于輸出空間 (信道傳送序列集 )Y之中 ， 以使竄擾者在不知道密鑰情況下 ， 偽造成功的概率極小化 。 糾錯(cuò)碼的目的是抗噪聲等干擾 ， 要求將碼中各碼字配置得盡可能地散開(kāi) (如最小漢明距離極大化 )， 以保證在干擾作用下所得到的接收序列與原來(lái)的碼字最接近 。 48 信息論與密碼學(xué) 認(rèn)證碼 上面給出了認(rèn)證系統(tǒng)安全性指標(biāo) pd的下限 ， 本節(jié)將研究如何構(gòu)造認(rèn)證碼使其接近或達(dá)到其性能下限 。 實(shí)際安全性 是根據(jù)破譯認(rèn)證體制所需的計(jì)算量來(lái)評(píng)價(jià)其安全性的 。 Gilbert等曾給出一個(gè)更強(qiáng)的下限 。 定理 611 認(rèn)證信道有 log pI?－ I(Y； K) (2— 49) 44 信息論與密碼學(xué) 等號(hào)成立的充要條件為式 (613)和 (614)成立 ， 且 log pd ?－ I(Y； K) (2— 50) 等號(hào)成立的必要條件為式 (2— 47)和 (2— 48)成立 。 而且可以證明 ， 要求式 (612)等號(hào)成立的充要條件是：對(duì)任一 k?K， 都恰有 {Ak}{X}。 一般認(rèn)證編碼中 {Y} {X}， 且認(rèn)證碼中元素個(gè)數(shù) {Ak}?{X }。 若接收者接受 y*為認(rèn)證碼字 ， 則稱(chēng)竄擾者攻擊成功 。 如果發(fā)生這一事件 ， 則認(rèn)為竄擾者欺詐成功 。 令 x?X為要發(fā)送的消息， k?K是發(fā)方選定的密鑰，y=A(x, k)?Y是表示消息 x的認(rèn)證碼字， Ak={y=A(x, k), x?X}為認(rèn)證碼。 信息論與密碼學(xué) 37 信息論與密碼學(xué) 圖 24 純認(rèn)證系統(tǒng)模型 信道 竄擾者 認(rèn)證編碼器 認(rèn)證譯碼器 信 源 信 宿 密鑰源 安全信道 38 信息論與密碼學(xué) 認(rèn)證編碼 在要發(fā)送的消息中引入多余度，使通過(guò)信道傳送的可能序列集 Y大于消息集 X。 一個(gè)純認(rèn)證系統(tǒng)的模型如圖 24所示 。 l 必要時(shí)可由第三者作出仲裁 。 信息論與密碼學(xué) 35 要求： l 意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性和真實(shí)性 。 l 保密性：保密性是使截獲者在不知密鑰條件下不能解讀密文的內(nèi)容 。因?yàn)? (S1 S2) (S1 S2)=S1 (S2 S1) S2 =(S1 S1) (S2 S2)=S1 S2 (2— 44) 信息論與密碼學(xué) 33 八 、 認(rèn)證系統(tǒng) (Authentication system) 認(rèn)證是 為了 防止主動(dòng)攻擊，如對(duì)消息的內(nèi)容、順序、和時(shí)間的竄改以及重發(fā)等偽裝、竄擾等的重要技術(shù)， 使發(fā)送的消息具有被驗(yàn)證的能力，使接收者或第三者能夠識(shí)別和確認(rèn)消息的真?zhèn)巍?若密碼是冪等的 ， 則不會(huì)采用乘積 S2，即使用另一個(gè)密鑰 ， 也不會(huì)增大安全性 。 乘積密碼系統(tǒng)的密鑰為 k=(k1, k2)， k1? K1 ， k2? K2 加密： (2— 41) ? 信息論與密碼學(xué) E m E E mk k k k( ) ( ) ( ( ))1 2 2 1?31 解 密： mmEDmEEDDmEEDmEDcDkkkkkkkkkkkkkkkk?????))(())))(((()))((())(()(1112211221212121)(,),()(由于 k1和 k2獨(dú)立選取，故有 )()(),( 2121 21 kpkpkkp kkk ??信息論與密碼學(xué) (2— 42) (2— 43) 32 特例：冪等 (Idempotent)密碼系統(tǒng)： S S=S2 =S。 設(shè)計(jì)當(dāng)代密碼有重要指導(dǎo)意義 ， 許多近代分組密碼體制 ， 幾乎無(wú)一例外都采用了這一思想 。 設(shè)計(jì)者要盡可能在一般條件下描述這些分析方法 ， 設(shè)法構(gòu)造一種可以抗擊這類(lèi)一般分析法的密碼系統(tǒng) 。 ? 如何實(shí)現(xiàn)使破譯一個(gè)密碼系統(tǒng)所需的工作量極大化，這是博奕論中“極大化極小”問(wèn)題。由圖可知，隨密文量 l增加， W(l)會(huì)降至一個(gè)漸近值。 破譯工作特性 (Work characteristic) ： W(l)隨 l的變化曲線 ， 其中 W(l)可用人 時(shí)度量 。 信息論與密碼學(xué) 25 六 、 實(shí)際保密性 理論保密性 ：碼分析者有無(wú)限的時(shí)間 、 設(shè)備和資金條件下 ， 惟密文攻擊時(shí)密碼系統(tǒng)的安全性 。 例如 q=26， δ= 256的情況 。 信息論與密碼學(xué) 24 例 23 下面給出幾種密碼體制對(duì)英語(yǔ)報(bào)文加密時(shí)的唯一解距離 。 這和著名密碼分析家 W. F. Friedman的經(jīng)驗(yàn)值 25個(gè)字母相符 。 ? 增大 H(K)是提高保密系統(tǒng)安全性的途徑 ， 即采用復(fù)雜的密碼體制 ， 直至一次一密鑰體制 。 CL)=H(K)－ H(K/Cl) 因而有 H(K/Cl)?H(K)－ l?L (2— 39) 由此可見(jiàn) ， 當(dāng) l足夠小時(shí) ， 密鑰含糊度將隨截獲的密文長(zhǎng)度 l線性地降低 ， 直到當(dāng) H(K?Cl)變得相當(dāng)小為止 。 信息論與密碼學(xué) 18 H(K) 0 1 2 3 ? H(K)/?L l（密文量） 圖 22 H(K)～ l的典型變化特性 信息論與密碼學(xué) 19 證明 ： 令 Ml， Cl和 K都是二元序列集。 若 H=(K/C?)?0， 就可惟一地確定密鑰 K， 而實(shí)現(xiàn)破譯 。 降低明文中的多余度常常會(huì)使密碼分析者處于困境 。 可能實(shí)現(xiàn)完善保密 。 Shannon最先證明這種體制是完善保密的，并能抗擊已知明文 密文下的攻擊。 這等價(jià)于將 m通過(guò)一個(gè)轉(zhuǎn)移概率 p=1/2的 BSC傳送，BSC的容量為零 (參看例 253)。 m和 k彼此獨(dú)立。 信息論與密碼學(xué) 12