【正文】 4 認(rèn)證的理論與技術(shù) ： 是保密學(xué)研究的一個(gè)重要領(lǐng)域 ， 包括認(rèn)證系統(tǒng) 、 雜湊 (Hash)函數(shù) 、 數(shù)字簽名 、 身份證明 、認(rèn)證協(xié)議等 。 而且在已知合法密文 c和相應(yīng)消息 m下 ， 要確定加密密鑰或系統(tǒng)地偽造合法密文在計(jì)算上是不可行的 。 實(shí)際認(rèn)證系統(tǒng)可能還要防止收 、 發(fā)之間的相互欺詐 。 竄擾者雖然知道 X、 Y、 y、 A(?，?)， 但不知道具體密鑰 k， 他的目標(biāo)是想偽造出一個(gè)假碼字 y*， 使 y*?Ak， 使接收者收到 y*后可以密鑰 k解密得到一個(gè)合法的 、 可能由發(fā)端送出的消息 x*， 使接收者上當(dāng)受騙 。 41 信息論與密碼學(xué) 完善認(rèn)證性 (Perfect Authentication)：令 {Y}、 {X}、{K}分別表示密文空間 、 消息空間 、 密鑰空間中概率為非零的元素的個(gè)數(shù) 。 43 信息論與密碼學(xué) 若在最佳模仿策略下竄擾者只能隨機(jī)地選取一個(gè)y?Y， 則有 H(Y)=log{Y} (2— 47) 而若在任一給定密鑰下 ， 任一認(rèn)證碼字在認(rèn)證碼 A中等概出現(xiàn) ， 則有 H(Y|K)=log{X} (2— 48) 對(duì)式 (612)兩邊取對(duì)數(shù)可得 log pI?log{X}－ log{Y}=－ {H(Y)－ H(Y|K)}=－ I(Y； K) 上述結(jié)果可歸結(jié)為定理 611。 它與竄擾者的計(jì)算能力或時(shí)間無(wú)關(guān) ， 也就是說(shuō)竄擾者破譯體制所做的任何努力都不會(huì)優(yōu)于隨機(jī)試湊方式 。 這是認(rèn)證和糾錯(cuò)賴以實(shí)現(xiàn)的基本條件 。 h是 多對(duì)一映射 ， 因此我們不能從 H求出原來(lái)的 M， 但可以驗(yàn)證任一給定序列 M’是否與M有相同的雜湊值 。 別名 ：壓縮 (Compression)函數(shù) 、 緊縮 (Contraction)函數(shù) 、 數(shù)據(jù)認(rèn)證碼 (Data Authentication Code)、 消息摘要 (Message Digest)、 數(shù)字指紋 、 數(shù)據(jù)完整性校驗(yàn) (Data Integity Check)、 密碼檢驗(yàn)和 (Cryptographic Check Sum)、 消息認(rèn)證碼 MAC(Message Authentication Code)、竄改檢測(cè)碼 MDC(Manipulation Detection Code)等 。 在抗主動(dòng)攻擊下 ， 可認(rèn)為 p=1/2。 這種非線性碼可能數(shù)極大 ， 即相應(yīng)的密鑰空間 K可以很大 ， 但從式 (255)和式 (256)式可以看出 {K}22n是無(wú)作用的 。 56 信息論與密碼學(xué) 雜湊函數(shù)壓縮輸入數(shù)字串與認(rèn)證編碼之間的差別在于，后者是對(duì)固定長(zhǎng) L bits進(jìn)行編碼成 L＋ n bits碼字，而前者對(duì)輸入字串長(zhǎng)度未加限制。 Damg229。 公鑰密碼學(xué)中的加密、簽字、智力樸克、零知識(shí)證明、概率性檢驗(yàn)證明 (Probabilistically Checkable Proofs)、證實(shí)和近似問(wèn)題的難度等問(wèn)題都和計(jì)算復(fù)雜性理論有密切關(guān)系。 比 NP更難的問(wèn)題 ， 由于加密 、 解密時(shí)間需足夠高 (如可用多項(xiàng)式時(shí)間完成 )而不適用于密碼 。 信息論與密碼學(xué) 62 Shamir[1979]曾給出下述三點(diǎn)理由： l 復(fù)雜性理論通常是處理一類(lèi)問(wèn)題中的單個(gè)孤立例子 ，而密碼分析者常有一大堆與解統(tǒng)計(jì)有關(guān)的問(wèn)題 。 如何確定問(wèn)題在實(shí)際上為一個(gè)難題的準(zhǔn)則不容易 ，Shamir的 “ 中值復(fù)雜度 ” 可以考慮 。 而密碼分析者常常從最易解的問(wèn)題下手 ， 密碼設(shè)計(jì)者希望問(wèn)題中所有情況都是困難的 ， 但常常又難免會(huì)有少數(shù)容易的例子含于其中 。但計(jì)算上困難的問(wèn)題并非一定就意味一個(gè)強(qiáng)的密碼 。 ” 1976年 ， Diffie和 Hellman的文章則具體提出 ， 應(yīng)用計(jì)算復(fù)雜性來(lái)設(shè)計(jì)加密算法 。 信息論與密碼學(xué) 58 通信復(fù)雜性 ：兩個(gè)代理人各有一半輸入 bit，通過(guò)通信交換盡可能少的信息完成一個(gè)布爾函數(shù)的計(jì)算。這種技術(shù)由 Merkle和 Damg229。 雖然其不可檢錯(cuò)誤的概率上界為 2n， 但 Pd的下界為 1。 竄擾成功的概率限由 (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。 當(dāng)碼字在傳輸過(guò)程中被竄擾 ， 若結(jié)果不屬于碼空間 ， 收端通過(guò)對(duì) n個(gè)一致檢驗(yàn)關(guān)系的檢驗(yàn)可以實(shí)現(xiàn)檢錯(cuò) 。 無(wú)密鑰控制的單向雜湊函數(shù) ， 其雜湊值只是輸入字串的函數(shù) ， 任何人都可以計(jì)算 ， 因而 不具有身份認(rèn)證功能 ， 只用于檢測(cè)接收數(shù)據(jù)的完整性 ， 如竄改檢測(cè)碼 MDC， 用于非密碼計(jì)算機(jī)應(yīng)用中 。 50 信息論與密碼學(xué) 九 、 雜湊函數(shù) (Hash Function) 將任意長(zhǎng)數(shù)字串 M映射成一個(gè)較短的定長(zhǎng)輸出數(shù)字串 H的函數(shù) ， 以 h表示 ， h(M)易于計(jì)算 ， 稱(chēng) H= h(M)為 M的 雜湊值 ， 也稱(chēng) 雜湊碼 、 雜湊結(jié)果等或簡(jiǎn)稱(chēng)雜湊 。 無(wú)條件安全認(rèn)證碼和糾錯(cuò)碼理論互為 對(duì)偶 。 定理 613 對(duì)具有保密的認(rèn)證 (竄擾者不知信源狀態(tài) )有 log pd ?－ 1/2H(K) (2— 50) 而對(duì)無(wú)保密的認(rèn)證 (竄擾者知道信源狀態(tài) )有 log pd ?－ 1/2{H(K)－ H(XY)＋ H(Y)} =－ 1/2{H(K)－ H(X|Y) (2— 51) 系 (2— 52) ? ?p Kd ?146 信息論與密碼學(xué) 類(lèi)似于保密系統(tǒng)的安全性 ， 認(rèn)證系統(tǒng)的安全性也劃分為兩大類(lèi) ， 即 理論安全性 和 實(shí)際安全性 。 這表明采用隨機(jī)密碼不能使上式等號(hào)成立 。 竄擾者可以自由地選擇最有利的攻擊方式 。 Ak是 Y中的許用 (合法 )序列集，而其補(bǔ)集 A?k則為禁用序列集，且 Ak∪ A?k=Y。 在這個(gè)系統(tǒng)中的發(fā)送者通過(guò)一個(gè)公開(kāi)信道將消息送給接收者 ， 接收者不僅想收到消息本身 ，而且還要驗(yàn)證消息是否來(lái)自合法的發(fā)送者及消息是否經(jīng)過(guò)竄改 。 l 消息的發(fā)送者對(duì)所發(fā)送的消息不能抵賴 。實(shí)現(xiàn)這類(lèi)功能的密碼系統(tǒng)稱(chēng)作認(rèn)證系統(tǒng)。 可以推廣到 n階乘積密碼以 Sn表示 。 ? 估計(jì)破譯一個(gè)保密系統(tǒng)所需的平均工作量 W(l) 的另一種途徑是 ， 將破譯此密碼的難度等價(jià)于解數(shù)學(xué)上的某個(gè)已知難題 。 ? 任何一個(gè)非理想系統(tǒng)，其工作特性的趨勢(shì)大致和圖 256一致，但 W(l)的絕對(duì)取值隨密碼體制不同相差極大。 一個(gè)密碼系統(tǒng) ，如果對(duì)手有無(wú)限的資源可利用 ， 而在截獲任意多密報(bào)下仍不能被破譯 ， 則它在理論上是保密的 。 (1) 周 期 為 d 的移位密碼 ， H(K)=lb(d!) ，?0=lb(d!)/=(d/e)字母 。 信息論與密碼學(xué) 23 例 22 英語(yǔ)單表代換密碼的密鑰量 |K?=26!， 其密鑰空間的熵為 H(K)=lb(26!)= bits 。 K和 Cl之間平均互信息為 I(K。 信息論與密碼學(xué) 16 五 、 理論保密性 ?長(zhǎng)密文序列集 C=C1, C2, ...,C? ?C?， 密鑰的不確定性 ， 即從密鑰含糊度 ， 由條件熵性質(zhì)知 H(K/C?)=(K/C1, …, C?+1 )?H(K/C1,…, C?) (2— 25) 顯然 ， 當(dāng) ?=0時(shí)的密鑰的含糊度就是密鑰的熵 H(K)。在不知密鑰條件下，任何人采用任何破譯法都不會(huì)比隨機(jī)猜測(cè)更好些 ! 在實(shí)際應(yīng)用中，為了安全起見(jiàn)，必須保證密鑰以完全隨機(jī)方式產(chǎn)生 (如擲硬幣 )并派可靠信使通過(guò)安全途徑送給對(duì)方，每次用過(guò)后的密鑰都立即銷(xiāo)毀。今選 L=r=v，并令 k是一理想二元對(duì)稱(chēng)源 (BSS)的輸出，即 k為隨機(jī)數(shù)字序列，因而有 H( )=L bits。 C?)=0 (2—17) 密文與明文之間的互信息為零，竊聽(tīng)者從密文就得不到任何有關(guān)明文的信息 ,不管竊聽(tīng)者截獲的密文有多少，他用于破譯的計(jì)算資源有多豐富 ,都是無(wú)濟(jì)于事的。 信息論與密碼學(xué) 9 二、完善保密性 令明文熵為 H(M)＝ H(ML )，密鑰熵為 H(K)，密文熵為 H(C)=H(C?)，在已知密文條件下明文的含糊度為H(ML/C? )，在已知密文條件下密鑰的含糊度為 H(K/C?) 惟密文破譯下，密碼分析者的任務(wù)是從截獲的密文中提取有關(guān)明文的信息 I(ML。 l 主動(dòng)攻擊 (Active attack)： 非法入侵者 (Tamper)、攻擊者 (Attcker)或 黑客 (Hacker)主動(dòng)向系統(tǒng)竄擾 ， 采用刪除 、 增添 、 重放 、 偽造等竄改手段向系統(tǒng)注入假消息， 達(dá)到利已害人的目的 。 l密鑰空間 K： 對(duì)于長(zhǎng)為 r的密鑰序列 k=k1, k2, ..., kr k1 ,…, kr?K