【正文】 消息和原來發(fā)送消息一致性的能力 。 信息論與密碼學 35 要求： l 意定的接收者能夠檢驗和證實消息的合法性和真實性 。 l 除了合法消息發(fā)送者外 ， 其它人不能偽造合法的消息 。 l 必要時可由第三者作出仲裁 。保密和認證同是信息系統(tǒng)安全的兩個重要方面 ， 但它們是兩個不同屬性的問題 。 一個純認證系統(tǒng)的模型如圖 24所示 。 系統(tǒng)中的密碼分析者不僅要截收和分析信道中傳送的密報 ， 而且可偽造密文送給接收者進行欺詐 ， 稱其為系統(tǒng)的竄擾者 (Tamper)更加貼切 。 信息論與密碼學 37 信息論與密碼學 圖 24 純認證系統(tǒng)模型 信道 竄擾者 認證編碼器 認證譯碼器 信 源 信 宿 密鑰源 安全信道 38 信息論與密碼學 認證編碼 在要發(fā)送的消息中引入多余度，使通過信道傳送的可能序列集 Y大于消息集 X。竄擾者由于不知道密鑰，因而所偽造的假碼字多是 Y中的禁用序列，收方將以很高的概率將其檢測出來而被拒絕。 令 x?X為要發(fā)送的消息， k?K是發(fā)方選定的密鑰，y=A(x, k)?Y是表示消息 x的認證碼字， Ak={y=A(x, k), x?X}為認證碼。 39 信息論與密碼學 接收者知道認證編碼 A(?， ?)和密鑰 k， 故從收到的 y可惟一地確定出消息 x。 如果發(fā)生這一事件 ， 則認為竄擾者欺詐成功 。 若接收者接受 y*作為認證碼字 ， 則說竄擾者攻擊成功 。 若接收者接受 y*為認證碼字 ， 則稱竄擾者攻擊成功 。 竄擾者成功概率 (接收者受騙概率 )： pd=max{pI， pS} (2— 45) pI： 竄擾者采用模仿攻擊時最大可能的成功概率 ps： 在代換攻擊時最大可能的成功概率。 一般認證編碼中 {Y} {X}， 且認證碼中元素個數(shù) {Ak}?{X }。 若對手采用模仿偽造策略 ， 完全隨機地以非零概率從 Y中選出一個作為偽造密文 (認證碼字 )送給接收者 ， 則其成功的概率有 (2— 46) ? ?? ?? ?? ?YXYApI km i n??42 信息論與密碼學 要安全性高 ， 即要 pI小 ， 需有 {Y}{X}。 而且可以證明 ， 要求式 (612)等號成立的充要條件是：對任一 k?K， 都恰有 {Ak}{X}。 由于認證系統(tǒng)不能實現(xiàn)完全保護 ，故將完善認證定義為對給定認證碼空間 ， 能使受騙率 pd最小的認證系統(tǒng) (在此意義下 ， 即使對 {Y}={X}時的平凡情況 ， 此時 pd =1， 也有完善認證可言 )。 定理 611 認證信道有 log pI?－ I(Y； K) (2— 49) 44 信息論與密碼學 等號成立的充要條件為式 (613)和 (614)成立 ， 且 log pd ?－ I(Y； K) (2— 50) 等號成立的必要條件為式 (2— 47)和 (2— 48)成立 。 定義 完善認證 是使式 (250)等號成立的認證系統(tǒng) 。 Gilbert等曾給出一個更強的下限 。 理論安全性 又稱作無條件安全性 ， 就是我們上面所討論的 。 實際安全性 是根據(jù)破譯認證體制所需的計算量來評價其安全性的 。 如果能夠證明破譯某體制的困難性等價于解決某個數(shù)學難題 ， 就稱其為可證明安全的 ， 如 RSA體制 。 48 信息論與密碼學 認證碼 上面給出了認證系統(tǒng)安全性指標 pd的下限 ， 本節(jié)將研究如何構(gòu)造認證碼使其接近或達到其性能下限 。 這兩者都需要引入多余數(shù)字 ， 在信道中可傳送的序列集中只有一小部分用于傳信 。 糾錯碼的目的是抗噪聲等干擾 ， 要求將碼中各碼字配置得盡可能地散開 (如最小漢明距離極大化 )， 以保證在干擾作用下所得到的接收序列與原來的碼字最接近 。 認證碼的目的是防止偽造和受騙 。 49 信息論與密碼學 在認證系統(tǒng)中 ， 密鑰的作用類似于信道的干擾 ， 在它們的控制下變換編碼規(guī)則 ， 使造出的代表消息的碼字盡可能交義地配置 ， 即將消息空間 X最佳地散布于輸出空間 (信道傳送序列集 )Y之中 ， 以使竄擾者在不知道密鑰情況下 ， 偽造成功的概率極小化 。 特點 ： H打上了輸入數(shù)字串的烙印 ， 為數(shù)字指紋(Digital Finger Print)。 分類 ： ? 密碼雜湊函數(shù) ， 有密鑰控制 ， 以 h(k, M)表示 。 雜湊值 也是一種認證符 或 認證碼 。 51 信息論與密碼學 ? 一般雜湊函數(shù) ， 無密鑰控制 。 應(yīng)用 ：在密碼學和數(shù)據(jù)安全技術(shù)中 ， 它是實現(xiàn)有效 、安全可靠數(shù)字簽字和認證的重要工具 ， 是安全認證協(xié)議中的重要模塊 。 52 信息論與密碼學 密碼學中所用的雜湊函數(shù)必須滿足安全性的要求，要能防偽造，抗擊各種類型的攻擊，如生日攻擊、中途相遇攻擊等等。 53 信息論與密碼學 雜湊函數(shù)、認證碼與檢錯碼的關(guān)系 雜湊函數(shù) 、 認證碼與檢錯碼都是利用冗余度 。 GF(2)上 L＋ n維線性空間中的 L維子空間就是這類線性分組檢錯碼的碼空間 。 一個好的檢錯線性碼在于使不可檢錯概率極小化 ，其最佳碼的不可檢錯上限為 pd ? 2n[1－ (1－ p)n] (2— 53) 式中 p是信道誤碼率 。而有 pd ? 2n (2— 54) 54 信息論與密碼學 線性分組檢錯碼是一種 MDC雜湊，可作為數(shù)據(jù)完整性檢驗，但不能作為身份認證。 在不同密鑰下 ， 同一消息序列被映射為不同的碼序列 。 模仿偽造成功概率 (2— 55) 此與最佳線性檢錯碼的不可檢錯概率的上限一致 。故碼長為 L＋ n (bit)。 由此可以得出一個重要結(jié)論 ， 即對于 n bit雜湊值下 ， 選擇密鑰比特數(shù)大于 2n bit是無意義的 。 這是將雜湊函數(shù)看作是一種認證編碼給我們的啟示 。因而 {K}=1。 可見它不能抗擊竄擾者的攻擊 。一般 L?n bit，且當 L不是 n的整數(shù)倍時，采用 填充 辦法湊成 ?L/n?倍 (?雖然式 (255)給出的對任意 L取值模仿攻擊成功概率下限都是 2n。 為了減小碰撞，通常都將輸入消息數(shù)字串長度作為參數(shù)納入最后一個分段中，這樣攻擊者在試圖找到偽消息 M’與發(fā)送消息 M的雜湊值一樣時，必須使 M’的長度和 M的長度一致才合法，從而大大增加了攻擊的難度。rd等提出，稱作 MD強化技術(shù) 。rd等證明經(jīng)過 MD強化后，雜湊算法抗自由起始攻擊的強度等價于迭代函數(shù)的強度。兩者在研究史、理論、技術(shù)和方法論上都存在著密切關(guān)系。 Kolmogorov復(fù)雜性 ：為計算一個問題所需的 “ 典型 ” 輸入長度?？山鉀Q并行復(fù)雜性的下限以及在芯片上計算函數(shù)所需的面積和時間等問題。概率性檢驗證明是當今復(fù)雜性理論中最為深刻的結(jié)果。這一極為重要而又很前沿的問題。 信息論與密碼學 60 密碼與計算復(fù)雜性關(guān)系 Shannon[1949]指出 “ 設(shè)計好的密碼問題本質(zhì)上是尋求在某些其它條件下的一個難解問題 。 他們注意到一些 NPC問題可能作為密碼的備選方案 。 但是 ， 如果將密碼問題限制于 NP類 ，就使得密碼分析者可以猜測某個密鑰 ， 而能在多項式時間內(nèi)檢驗其是否正確 (如以它加密已知明文看密文是否與截獲的一致 )。 信息論與密碼學 61 通過對 NP復(fù)雜性理論的檢驗 ， Diffie和 Hellman推想密碼學可以利用其中的 NPC類問題來加密數(shù)據(jù) ，使得破譯者在用一般方法破譯它時需解 NPC問題 。 l 密碼的強度依賴于構(gòu)造密碼問題的計算復(fù)雜性 。即計算復(fù)雜性大只是密碼安全的一個必要條件 。 (例如 ，由同一密鑰加密的幾個組密文 。 l 一種任意困難的問題不一定可能變成為一種密碼體制 ， 只有在問題中以某種方法可嵌入陷門信息的才能用于密碼 。 首先 ， Brassard[1979]指出除非 NP=CoNP， 否則密碼分析者面臨的問題將不會是 NP難問題； 其次 ， 復(fù)雜性理論主要關(guān)心的是問題的漸近復(fù)雜性； 信息論與密碼學 64 第三 ， NPC是問題復(fù)雜性最壞情況下的量度 ， 而密碼的安全性應(yīng)當依賴于問題的復(fù)雜度平均情況 ， 最好是在所有情況下問題都是難于處理的 。 只要： 敵人不能輕易認出容易的問題； 采用隨機密鑰 ， 能夠輕易解出問題的概率極小 ， 以至于不值得去試 。 信息論與密碼學 65 參考文獻 Menezes, A. Z., “Hand Book of Applied Cryptography,” CRC Press, 1997. Schineier, B., “Applied Cryptography,” 2nd ed., John Wiley amp。 信息論與密碼學