【正文】 48) 對(duì)式 (612)兩邊取對(duì)數(shù)可得 log pI?log{X}－ log{Y}=－ {H(Y)－ H(Y|K)}=－ I(Y； K) 上述結(jié)果可歸結(jié)為定理 611。 這表明采用隨機(jī)密碼不能使上式等號(hào)成立 。 由于{X}0， 要求完全保護(hù) ， 即要 pI=0是不可能實(shí)現(xiàn)的 。 對(duì)每個(gè) k?K ， 至少有 {X} 個(gè) 不 同 的 密 文 使p(Y=y|K=k)≠0。 41 信息論與密碼學(xué) 完善認(rèn)證性 (Perfect Authentication)：令 {Y}、 {X}、{K}分別表示密文空間 、 消息空間 、 密鑰空間中概率為非零的元素的個(gè)數(shù) 。 竄擾者可以自由地選擇最有利的攻擊方式 。 40 信息論與密碼學(xué) ? 代換偽造 (Substitution Fraudulent)， 竄擾者截收到認(rèn)證系統(tǒng)中的認(rèn)證碼字 y后 ， 進(jìn)行分析并偽造假認(rèn)證碼字 y*， 故可稱為已知密文偽造 。 竄擾者攻擊的基本方式 ： ? 模仿偽造 (Impersonative Fraudulent)， 竄擾者在未觀測(cè)到認(rèn)證信道中傳送的合法消息 (或認(rèn)證碼字 )條件下偽造假碼字 y*， 稱其為無密文偽造更合適些 。 竄擾者雖然知道 X、 Y、 y、 A(?，?)， 但不知道具體密鑰 k， 他的目標(biāo)是想偽造出一個(gè)假碼字 y*， 使 y*?Ak， 使接收者收到 y*后可以密鑰 k解密得到一個(gè)合法的 、 可能由發(fā)端送出的消息 x*， 使接收者上當(dāng)受騙 。 Ak是 Y中的許用 (合法 )序列集，而其補(bǔ)集 A?k則為禁用序列集，且 Ak∪ A?k=Y。認(rèn)證系統(tǒng)設(shè)計(jì)者的任務(wù)是構(gòu)造好的認(rèn)證碼 (Authentication Code)，使接收者受騙概率極小化。對(duì)于任何選定的編碼規(guī)則 (相應(yīng)于某一特定密鑰 )：發(fā)方可從 Y中選出用來代表消息的許用序列，即碼字；收方可根據(jù)編碼規(guī)則唯一地確定出發(fā)方按此規(guī)則向他傳來的消息。 實(shí)際認(rèn)證系統(tǒng)可能還要防止收 、 發(fā)之間的相互欺詐 。 在這個(gè)系統(tǒng)中的發(fā)送者通過一個(gè)公開信道將消息送給接收者 ， 接收者不僅想收到消息本身 ，而且還要驗(yàn)證消息是否來自合法的發(fā)送者及消息是否經(jīng)過竄改 。 認(rèn)證不能自動(dòng)地提供保密性 ，而保密也不能自然地提供認(rèn)證功能 。 信息論與密碼學(xué) 36 認(rèn)證的信息理論 ：類似于保密系統(tǒng)的信息理論 ， 可將信息論用于研究認(rèn)證系統(tǒng)的理論安全性和實(shí)際安全性 ， 指出認(rèn)證系統(tǒng)的性能極限以及設(shè)計(jì)認(rèn)證碼必須遵循的原則 。 而且在已知合法密文 c和相應(yīng)消息 m下 ， 要確定加密密鑰或系統(tǒng)地偽造合法密文在計(jì)算上是不可行的 。 l 消息的發(fā)送者對(duì)所發(fā)送的消息不能抵賴 。 實(shí)際中常常借助于糾 、 檢錯(cuò)技術(shù)和雜湊技術(shù)來保證消息的完整性 。 l 認(rèn)證性：使任何不知密鑰的人不能構(gòu)造一個(gè)密報(bào) ，使意定的接收者脫密成一個(gè)可理解的消息 (合法的消息 )。 信息論與密碼學(xué) 34 認(rèn)證的理論與技術(shù) ： 是保密學(xué)研究的一個(gè)重要領(lǐng)域 ， 包括認(rèn)證系統(tǒng) 、 雜湊 (Hash)函數(shù) 、 數(shù)字簽名 、 身份證明 、認(rèn)證協(xié)議等 。實(shí)現(xiàn)這類功能的密碼系統(tǒng)稱作認(rèn)證系統(tǒng)。 易于證明 ， 若 S1和 S2是冪等 ， 則 S1 S2也是冪等的 。 對(duì)于非冪等密碼體制 ， 增加迭代次數(shù) ， 會(huì)增大潛在的安全性 。re和置換等密碼都是冪等體制 。 可以推廣到 n階乘積密碼以 Sn表示 。 S1和 S1的乘積 S1 S2表示為(M, M , K1 K2, E, D)。 為討論簡單 ， 設(shè) C=M， 這類密碼稱為自同態(tài)(Endomorphic) 密碼 。 信息論與密碼學(xué) 30 七 、 乘積密碼系統(tǒng) (Product cryptosystems) 利用 “ 乘積 ” 對(duì)簡單密碼進(jìn)行組合 ， 可構(gòu)造復(fù)雜而安全的密碼系統(tǒng) 。 ? 估計(jì)破譯一個(gè)保密系統(tǒng)所需的平均工作量 W(l) 的另一種途徑是 ， 將破譯此密碼的難度等價(jià)于解數(shù)學(xué)上的某個(gè)已知難題 。 這需要有豐富的密碼分析經(jīng)驗(yàn) ， 這種方法在實(shí)際中常會(huì)使用 。僅僅從對(duì)付現(xiàn)有的標(biāo)準(zhǔn)的密碼分析法是不夠的，還必須確保沒有輕而易舉的破譯方法。例如，密鑰量和簡單代換一樣的維吉尼亞或組合維吉尼亞密碼的工作特性要比簡單代換密碼的好得多。 ? 任何一個(gè)非理想系統(tǒng)，其工作特性的趨勢(shì)大致和圖 256一致，但 W(l)的絕對(duì)取值隨密碼體制不同相差極大。 信息論與密碼學(xué) 27 W(l) H(K /C’) W(l) 0 H(K)/ ?L l(密文量 ) 圖 23 破譯工作特性 信息論與密碼學(xué) 28 ? 圖中，點(diǎn)線表示可能的解多于一個(gè)的區(qū)域，對(duì)各可能的解出現(xiàn)的概率需分別確定；實(shí)線表示有惟一解的區(qū)域。 平均是在所有可能密鑰上進(jìn)行的 。 保密的相對(duì)性 : 最小保障時(shí)間 (Minimum cover time)： 信息論與密碼學(xué) 26 計(jì)算能力 (時(shí)間 、 費(fèi)用等 )與破譯算法的有效性 破譯平均工作量 W(l)：破譯 l長截獲密文所需的計(jì)算 。 一個(gè)密碼系統(tǒng) ，如果對(duì)手有無限的資源可利用 ， 而在截獲任意多密報(bào)下仍不能被破譯 ， 則它在理論上是保密的 。 這些結(jié)果都是在統(tǒng)計(jì)意義下得到的 ， 因此 ， 只有當(dāng)處理的報(bào)文數(shù)據(jù)足夠大時(shí)才適用 。 (3) 周期為 d的代換密碼 (如 Beaufort或 Vigen re密碼) 。 (2) 含 q 個(gè)字母表的單表代換 ， H(K)=lb(q!) ，?0=lb(q!)/δ。 (1) 周 期 為 d 的移位密碼 ， H(K)=lb(d!) ，?0=lb(d!)/=(d/e)字母 。 但若以 ν=20個(gè)密文字母破譯 ， 有意義的脫密解高達(dá) 107個(gè)之多 ， 如果得到了一個(gè)有意義的解 ， 其可信度是很低的 。 例如 ， 當(dāng)密文量?=40字母 ， 若每個(gè)字母的多余度以 δ= ， 一個(gè)有意義的脫密消息的期望數(shù)僅為 1010。 此例說明 ， 只要截獲到 28個(gè)字母長的密文 ， 原則上就可能破譯英語單表代換密碼 。 信息論與密碼學(xué) 23 例 22 英語單表代換密碼的密鑰量 |K?=26!， 其密鑰空間的熵為 H(K)=lb(26!)= bits 。 ? 一些使數(shù)據(jù)擴(kuò)展的方式對(duì)于密碼的安全是不利的。 由式 (2557)及唯一解距離 ?0的定義可得 ?0?H(K)/?L (2— 40) 討論 ： ? 若 ?L=0， 即當(dāng)明文經(jīng)過最佳數(shù)據(jù)壓縮編碼后 ， 其惟一解距離 ? 0??。 CL)=l?L 0? ?L ? 1 (2—38) 又由于 信息論與密碼學(xué) 21 I(K。 K和 Cl之間平均互信息為 I(K。 ?0與明文多余度的關(guān)系 ?0?H(K)/?L (2— 28) 圖 22給出 H(K)～ l的典型變化特性。 ?0=min{??N | H(K/C?)?0} (2— 26) 信息論與密碼學(xué) 17 惟一解距離 (Unicity distance) 對(duì)于給定的密碼系統(tǒng) ， 在惟密文攻擊下的 ?0=min{??N | H(K/C?)?0} (2—27) N是正整數(shù)集 。 即隨著截獲密文的增加 ， 得到的有關(guān)明文或密鑰的信息量就增加 ， 而保留的不確定性就會(huì)越來越小 。 信息論與密碼學(xué) 16 五 、 理論保密性 ?長密文序列集 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ì)看到 ， 加密前的數(shù)據(jù)壓縮是強(qiáng)化保密系統(tǒng)的重要措施 ， 這也是 Shannon最先指出的一個(gè)重要結(jié)果 。 而所需的密鑰量由原來的 L bits降為H(M1, M2,… , ML)bit。 理想壓縮編碼可使密鑰長度減至 r=N?H(M1, M2, …, ML) （ 2— 24) 收端先由收到的密文 c利用已知密鑰 k恢復(fù)出壓縮后的明文 m’=c?k， 再由明文 m’恢復(fù)原來的明文消息 m。在不知密鑰條件下，任何人采用任何破譯法都不會(huì)比隨機(jī)猜測(cè)更好些 ! 在實(shí)際應(yīng)用中，為了安全起見，必須保證密鑰以完全隨機(jī)方式產(chǎn)生 (如擲硬幣 )并派可靠信使通過安全途徑送給對(duì)方，每次用過后的密鑰都立即銷毀。 定理 254構(gòu)造的系統(tǒng)在惟密文破譯下是安全的，但在已知明文攻擊下是不安全的。因而有 I(ML；CL)≤LC=0。 式中，加法是逐位按模 2進(jìn)行，即 信息論與密碼學(xué) 13 ci=mi ?ki。今選 L=r=v，并令 k是一理想二元對(duì)稱源 (BSS)的輸出，即 k為隨機(jī)數(shù)字序列，因而有 H( )=L bits。不失一般性可假定明文是二元數(shù)字序列 m=(m1, m2, …, mL), mi∈ GF(2) 令密鑰序列