第5講--Shannon理論2

1、2022-3-301 定理定理3.1 設(shè)設(shè)b1,則有則有 且ij ,都有; 0)(ixp(2) 當(dāng)且僅當(dāng)i;1)(nxpinXHblog)(,都有(1)(0XH;log nbniibixpxp1)(log)(3) 當(dāng)且僅當(dāng)存在nii1:使得1)(ixp0)(XH上節(jié)內(nèi)容上節(jié)內(nèi)容回顧回顧1()( )log( )nibiiH Xp xp x 熵熵:2022-3-302上節(jié)內(nèi)容上節(jié)內(nèi)容回顧回顧 定理定理3.3)|()(),(YXHYHYXH 推論推論3.1)()|(XHYXH且等號(hào)成立且等號(hào)成立X與與Y獨(dú)立獨(dú)立. 定理定理3.2:)()(),(YHXHYXH且等號(hào)成立且等號(hào)成立X與與Y獨(dú)立獨(dú)立.ni

2、mjjijiyxpyxpYXH11),(log),(),(聯(lián)合熵聯(lián)合熵:nimjjijiyxpyxpYXH11)|(log),()|(條件熵條件熵: 結(jié)論結(jié)論:0)|()()|()();(XYHYHYXHXHYXI且等號(hào)成立且等號(hào)成立X與與Y獨(dú)立獨(dú)立. 平均互信息平均互信息:),()()();(YXHYHXHYXI3.3 偽密鑰和唯一解距離偽密鑰和唯一解距離 主要內(nèi)容主要內(nèi)容: 利用利用Shannon信息論信息論,研究密文、明文和密研究密文、明文和密鑰的信息量。鑰的信息量。 分析唯密文攻擊條件下要唯一確定密鑰時(shí)分析唯密文攻擊條件下要唯一確定密鑰時(shí)至少需要的密文長(zhǎng)度。至少需要的密文長(zhǎng)度。 定理定

3、理3.4 設(shè)設(shè)M,K,C分別是明文空間、密鑰空分別是明文空間、密鑰空間和密文空間上的隨機(jī)變量，則有間和密文空間上的隨機(jī)變量，則有 截獲密文后密鑰的未知信息量等于截獲密文后密鑰的未知信息量等于明文與密鑰明文與密鑰總總的未知信息量減去從已知的密文中獲得的信息量。的未知信息量減去從已知的密文中獲得的信息量。)()()()|(CHMHKHCKH直觀含義直觀含義: 定理定理3.4 設(shè)設(shè)M,K,C分別是明文空間、密鑰空分別是明文空間、密鑰空間和密文空間上的隨機(jī)變量，則有間和密文空間上的隨機(jī)變量，則有 根據(jù)條件熵與聯(lián)合熵之間的關(guān)系根據(jù)條件熵與聯(lián)合熵之間的關(guān)系,有有)()()()|(CHMHKHCKH證明證明

4、: 由于知道密文和密鑰由于知道密文和密鑰,自然也知道明文自然也知道明文,因而密鑰因而密鑰和密文都知道時(shí)提供的信息量和密文都知道時(shí)提供的信息量H(K,C)等于密鑰、密等于密鑰、密文和明文都知道時(shí)提供的信息量文和明文都知道時(shí)提供的信息量H(K,M,C),即即下證之下證之.)(),()|(CHCKHCKH),(),(MCKHCKH由由 和和條件熵條件熵與與聯(lián)合熵聯(lián)合熵的關(guān)系知的關(guān)系知(| (,)0H MK C同理同理,有有),(),(MCKHMKH,故由密鑰與明文獨(dú)立知故由密鑰與明文獨(dú)立知(|)(,)( )H K CH K CH C)(),(CHMKH)(),(CHMCKH)()()(CHMHKH)

5、,(CKH),(),(CKHMCKH),( |(CKMH 截獲密文截獲密文C后后,就可將密鑰唯一確定就可將密鑰唯一確定等價(jià)于等價(jià)于 下面根據(jù)這個(gè)條件下面根據(jù)這個(gè)條件,計(jì)算至少需要多少密文才能計(jì)算至少需要多少密文才能將密鑰將密鑰唯一確定唯一確定. 將密鑰將密鑰唯一確定唯一確定所需要的最少的密文的數(shù)量所需要的最少的密文的數(shù)量,就稱為該密碼體制的就稱為該密碼體制的唯一解距離唯一解距離（唯一解碼量）（唯一解碼量）. 要求唯一解距離要求唯一解距離,需要首先計(jì)算出需要首先計(jì)算出n長(zhǎng)明文長(zhǎng)明文M的的熵熵H(M)和和n長(zhǎng)密文的熵長(zhǎng)密文的熵H(C).)()()()|(CHMHKHCKH 定理定理3.4說(shuō)明說(shuō)明:

6、0)()()(CHMHKH 截獲密文截獲密文C后后,就可將密鑰唯一確定就可將密鑰唯一確定等價(jià)于等價(jià)于 0)|(CKH (A) n長(zhǎng)密文熵的計(jì)算長(zhǎng)密文熵的計(jì)算 我們需要做一個(gè)合理的假設(shè)我們需要做一個(gè)合理的假設(shè): 假設(shè)假設(shè): 密文是隨機(jī)的密文是隨機(jī)的! 設(shè)密文字母表為設(shè)密文字母表為Y,則則n長(zhǎng)密文長(zhǎng)密文就是由字母表就是由字母表Y中中n 個(gè)字母?jìng)€(gè)字母 組成的密文字母串組成的密文字母串 .nyyy,21nnyyyY21)(結(jié)論結(jié)論: : 設(shè)設(shè)n長(zhǎng)密文服從長(zhǎng)密文服從均勻分布均勻分布,則則n長(zhǎng)密文的熵為長(zhǎng)密文的熵為 |log)(YnCH證明證明: : 因因n長(zhǎng)密文共有長(zhǎng)密文共有 個(gè)個(gè),從而由從而由n長(zhǎng)密文

7、服從長(zhǎng)密文服從均勻分布和熵的性質(zhì)知均勻分布和熵的性質(zhì)知 nY |log|log)(YnYCHn 如何刻劃明文本身包含的未知信息量呢如何刻劃明文本身包含的未知信息量呢?我們我們 給出如下的定義：給出如下的定義： 設(shè)明文字母表為設(shè)明文字母表為X,則則n長(zhǎng)明文長(zhǎng)明文就是由字母表就是由字母表X中中n 個(gè)字母?jìng)€(gè)字母 組成的明文字母串組成的明文字母串 .nxxx,21nnxxxX21)( (B) n長(zhǎng)明文熵的計(jì)算長(zhǎng)明文熵的計(jì)算 定義定義3.5 3.5 （2 2）設(shè)設(shè)L是一種語(yǔ)言是一種語(yǔ)言,則稱則稱21logLLHRX 為該為該語(yǔ)言語(yǔ)言L的冗余度的冗余度(Redundancy) .其中，其中，X表示語(yǔ)言表示

8、語(yǔ)言L的字母表，的字母表，X(n)是是Xn上的隨上的隨 機(jī)變量機(jī)變量.定義定義3.53.5 (1) 設(shè)設(shè)L是一種語(yǔ)言是一種語(yǔ)言,則稱則稱nXHHnnL)(lim)( 為該為該語(yǔ)言語(yǔ)言L的的(單字母單字母)熵熵.2022-3-3010例例1 如果由如果由64個(gè)二進(jìn)制數(shù)構(gòu)成的某類密鑰個(gè)二進(jìn)制數(shù)構(gòu)成的某類密鑰 的的熵平均是熵平均是56比特比特,則該類密鑰的熵為則該類密鑰的熵為0.875比比特特.例例2 如果由如果由64個(gè)二進(jìn)制數(shù)構(gòu)成的某類密鑰的熵個(gè)二進(jìn)制數(shù)構(gòu)成的某類密鑰的熵平均是平均是56比特比特,則該類密鑰的冗余度是則該類密鑰的冗余度是 1 - 0.875 = 0.125 比特比特即即:平均每個(gè)密

9、鑰比特有平均每個(gè)密鑰比特有0.125個(gè)比特是多余的個(gè)比特是多余的.nH HL L表示自然語(yǔ)言表示自然語(yǔ)言L L中每個(gè)字母的熵，它是中每個(gè)字母的熵，它是“有意義的有意義的”明明文字母串中每個(gè)字母的平均信息量的度量文字母串中每個(gè)字母的平均信息量的度量. .對(duì)于字母表對(duì)于字母表X X上的一個(gè)隨機(jī)語(yǔ)言，因?yàn)樯系囊粋€(gè)隨機(jī)語(yǔ)言，因?yàn)閄 X(n)(n)是是X Xn n上的均勻隨機(jī)變量，所上的均勻隨機(jī)變量，所以，以， 隨機(jī)語(yǔ)言隨機(jī)語(yǔ)言L L的熵為的熵為 nnXxnnXxnXnXXxpxpXH|log|1log|1)(log)()()(且且當(dāng)當(dāng)n n很大時(shí)很大時(shí), ,近似有近似有|log|log)()(XnRX

10、nXHLn|log XHL 截獲密文截獲密文C后后,就可將密鑰唯一確定就可將密鑰唯一確定等價(jià)于等價(jià)于)()()()|(CHMHKHCKH 定理定理3.4說(shuō)明說(shuō)明:0)()()(CHMHKH 截獲密文截獲密文C后后,就可將密鑰唯一確定就可將密鑰唯一確定等價(jià)于等價(jià)于 0)|(CKH 下面轉(zhuǎn)到分析需要截獲多少密文才能將密鑰下面轉(zhuǎn)到分析需要截獲多少密文才能將密鑰唯一確定的問(wèn)題唯一確定的問(wèn)題.0)|()()()()()(CKHYHXHKHnn 當(dāng)截獲當(dāng)截獲n長(zhǎng)明文長(zhǎng)明文X(n)對(duì)應(yīng)的對(duì)應(yīng)的 n長(zhǎng)密文長(zhǎng)密文Y(n)后后,就可將密鑰的信息全部確定就可將密鑰的信息全部確定等價(jià)于等價(jià)于 現(xiàn)設(shè)現(xiàn)設(shè) ,|YX 則有

11、則有從而從而即即)()()()()(KHXHYHnn|log|)|log|(log|log)()()()(XnRXRXnYnXHYHLLnn|log)(XRKHnL 也就是說(shuō)也就是說(shuō),當(dāng)截獲當(dāng)截獲 個(gè)密文字母后個(gè)密文字母后,就就可將密鑰的信息全部確定可將密鑰的信息全部確定.|log)(XRKHnL|log)(XRKHnL 設(shè)已知密文設(shè)已知密文C(n)及對(duì)應(yīng)的明文及對(duì)應(yīng)的明文M(n).由于明文由于明文M(n)是已知的是已知的,因而此時(shí)該明文的熵因而此時(shí)該明文的熵H(M(n)=0,因而因而RL=1.這就是說(shuō)這就是說(shuō),當(dāng)當(dāng)n=H(K)/RL=128時(shí)時(shí),就可將密鑰的信就可將密鑰的信息唯一確定息唯一確

12、定.即此時(shí)唯一解距離為即此時(shí)唯一解距離為128. 結(jié)論結(jié)論: 設(shè)明文的設(shè)明文的(單字母單字母)冗余度為冗余度為,則所有密碼則所有密碼體制的唯一解距離均為體制的唯一解距離均為 LR 例例: : 對(duì)于具有對(duì)于具有128比特密鑰的密碼體制比特密鑰的密碼體制,平均需要平均需要128比特的已知明文比特的已知明文,就能將密鑰唯一確定就能將密鑰唯一確定. 其中已知明文就是已知一個(gè)密文和它對(duì)應(yīng)的明文其中已知明文就是已知一個(gè)密文和它對(duì)應(yīng)的明文.解解:2022-3-3015 幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明: （1）由于唯一解距離是用熵推出來(lái)的，因而它只）由于唯一解距離是用熵推出來(lái)的，因而它只是將密鑰唯一確定所是將密鑰唯一確定所

13、平均平均需要的密文長(zhǎng)度。需要的密文長(zhǎng)度。 由于明文熵是每份明文所包含的信息量關(guān)于所有由于明文熵是每份明文所包含的信息量關(guān)于所有明文的平均值，因而有時(shí)需要的密文數(shù)量少，有時(shí)明文的平均值，因而有時(shí)需要的密文數(shù)量少，有時(shí)需要的數(shù)量多，但其平均值就是唯一解距離。需要的數(shù)量多，但其平均值就是唯一解距離。 （2）明文熵不同，唯一解距離也不同。）明文熵不同，唯一解距離也不同。 明文熵就是你在攻擊過(guò)程中每個(gè)字母所能利用明文熵就是你在攻擊過(guò)程中每個(gè)字母所能利用的信息量。的信息量。 （3）如何確定唯一密鑰？確定過(guò)程實(shí)際上能否實(shí)）如何確定唯一密鑰？確定過(guò)程實(shí)際上能否實(shí)現(xiàn)，這里并不關(guān)心。一般而言，窮舉攻擊所需的平現(xiàn)，

14、這里并不關(guān)心。一般而言，窮舉攻擊所需的平均密文量就是該密碼體制的唯一解距離。均密文量就是該密碼體制的唯一解距離。2022-3-3016 偽密鑰偽密鑰 首先介紹首先介紹候選密鑰候選密鑰、偽密鑰偽密鑰和和等效密鑰等效密鑰的概念。的概念。 候選密鑰：候選密鑰：攻擊者在求解正確密鑰時(shí)，求出的攻擊者在求解正確密鑰時(shí)，求出的可能密鑰都稱為候選密鑰?？赡苊荑€都稱為候選密鑰。 平均來(lái)看平均來(lái)看,當(dāng)?shù)玫降拿芪臄?shù)量小于唯一解距離時(shí)當(dāng)?shù)玫降拿芪臄?shù)量小于唯一解距離時(shí),候選密鑰未必只有一個(gè)候選密鑰未必只有一個(gè),此時(shí)此時(shí),就會(huì)有多個(gè)候選密鑰就會(huì)有多個(gè)候選密鑰. 偽密鑰：偽密鑰：攻擊者得到的候選密鑰中的錯(cuò)誤密鑰攻擊者得到的

15、候選密鑰中的錯(cuò)誤密鑰稱為偽密鑰稱為偽密鑰. 等效密鑰：等效密鑰：如果兩個(gè)密鑰對(duì)所有明文的加密結(jié)如果兩個(gè)密鑰對(duì)所有明文的加密結(jié)果都相同果都相同,則稱這兩個(gè)密鑰為等效密鑰則稱這兩個(gè)密鑰為等效密鑰.)(1mEk)(2mEk 兩個(gè)等效密鑰兩個(gè)等效密鑰k1和和k2對(duì)應(yīng)的加密函數(shù)對(duì)應(yīng)的加密函數(shù) 和和 就是一個(gè)函數(shù)就是一個(gè)函數(shù),因而它們的加密效果完全相同因而它們的加密效果完全相同.2022-3-30173.4 密碼體制的完善保密性密碼體制的完善保密性 定義定義3.73.7( (完善保密性完善保密性) ) 對(duì)一個(gè)密碼體制而言，對(duì)一個(gè)密碼體制而言，如果明文與密文獨(dú)立，即對(duì)所有明文空間中的任一如果明文與密文獨(dú)立，

16、即對(duì)所有明文空間中的任一點(diǎn)點(diǎn) x 和密文空間中的任一點(diǎn)和密文空間中的任一點(diǎn) y ,都有都有)()|(xmpycxmpm則稱該密碼體制具有完善保密性則稱該密碼體制具有完善保密性(Perfect secrecy).或或稱該密碼體制是完全保密的。稱該密碼體制是完全保密的。 等價(jià)刻劃等價(jià)刻劃: :一個(gè)密碼體制具有完善保密性一個(gè)密碼體制具有完善保密性當(dāng)且僅當(dāng)且僅當(dāng)當(dāng)對(duì)所有明文空間中的任一點(diǎn)對(duì)所有明文空間中的任一點(diǎn) x 和密文空間中的任和密文空間中的任一點(diǎn)一點(diǎn) y ,都有都有)()|(ycpxmycpc2022-3-3018 定理定理3.63.6 設(shè)設(shè)S=(M,C,K,E,D)是一個(gè)密碼體制，并且是一個(gè)密

17、碼體制，并且|M|=|C|=|K|，則密碼體制，則密碼體制S具有完善的保密性的充要具有完善的保密性的充要條件是：密鑰的選取滿足均勻分布，并且對(duì)任意的條件是：密鑰的選取滿足均勻分布，并且對(duì)任意的 和和 ，都存在唯一的密鑰，都存在唯一的密鑰 ，使得，使得證明證明：（必要性）假設(shè)：（必要性）假設(shè)S具有完善的保密性，所以對(duì)任意具有完善的保密性，所以對(duì)任意的的 ，一定至少存在一個(gè)密鑰，一定至少存在一個(gè)密鑰 使得使得因此，因此，由已知條件由已知條件|C|=|K|,所以一定有所以一定有 即，不存在兩個(gè)不同的密鑰即，不存在兩個(gè)不同的密鑰 ，使得，使得因此，對(duì)任意的因此，對(duì)任意的 和任意和任意 ，存在唯一的密鑰

18、，存在唯一的密鑰 使得使得 MxyCkK( )kExyyCkK( )kExy| | )( |KKkxECk|( )| |kExkKKKkk21,12( )( )kkExExMxyCkK( )kExy2022-3-3019 下證密鑰的選取滿足均勻分布：下證密鑰的選取滿足均勻分布：令令 ，固定一個(gè)，固定一個(gè) ，令，令 是滿足是滿足 的密鑰。由貝葉斯公式，得的密鑰。由貝葉斯公式，得 因?yàn)橐驗(yàn)镾具有完善的保密性，所以具有完善的保密性，所以由上式可得由上式可得這說(shuō)明密鑰的選取是等概率的，所以這說(shuō)明密鑰的選取是等概率的，所以()ikiExy11( )|iP kKn( |) ()( ) ()(| )( )( )iiiiiP y x P xP k P xP xyP yP yyC,|,|21nxxxMKnik)()|(iixPyxP( )( )iP kP y2022-3-3020 充分性的證明：充分性的證明：因?yàn)槊魑呐c密鑰相互獨(dú)立，所以對(duì)任意因?yàn)槊魑呐c密鑰相互獨(dú)立，所以對(duì)任意 ，因?yàn)橐驗(yàn)?是是 的一個(gè)重的一個(gè)重新排列，所以有新排列，所以有因此，對(duì)任意因此，對(duì)任意另外，對(duì)任意另外，對(duì)任意 和和 ，令，令 是滿足是滿足 的唯一密鑰，則的唯一密鑰，則由上式可知，由上式可知，對(duì)任意對(duì)任意 和和 ， 因此，該密碼體