《密碼學(xué)-加密演算法》 第4章 信息理論概要課件

返回總目錄第4章

信息理論返回總目錄第4章

信息理論教學(xué)目的回憶概率的基本概念和定理了解什么是完美秘密？了解熵了解自然之熵教學(xué)目的回憶概率的基本概念和定理概率本章內(nèi)容完美秘密熵自然之熵概率本章內(nèi)容完美秘密熵自然之熵概率4.1概率定義令S為一非空的有限集合，稱為樣本空間（SampleSpace），其部分集合稱為事件（Events）。在樣本空間上的概率分布（ProbabilityDistribution）即用一個(gè)函數(shù)p將事件映至某實(shí)數(shù)，（其中表S的冪集合，即）滿足下列各條件：（1）對(duì)所有的事件（2）（3）當(dāng)兩事件與互斥（即）若A為事件，則p(A)為此事件的概率。概率4.1概率定義令S為一非空的有限集合，稱為樣本空概率的性質(zhì)性質(zhì)（1）（2）若則（3）當(dāng)

（4）（5）若均兩兩相斥，則（6）其中概率的性質(zhì)性質(zhì)（1）其中條件概率和獨(dú)立事件定義條件概率，ConditionalProbability令A(yù)與B為事件，且，A在條件B成立下的條件概率定義為定義兩事件A與B稱為獨(dú)立事件（IndependentEvents）此等式也等價(jià)于若等式不成立，則稱A與B為相依事件（DependentEvents）條件概率和獨(dú)立事件定義條件概率，ConditionalBayes定理Bayes定理若A與B為事件，且，，則證明：由條件概率的定義，得：和因此：Bayes定理Bayes定理若A與B為事件，且完美秘密4.2完美秘密定義：一個(gè)密碼系統(tǒng)定義為完美秘密（PerfectSecrecy）所有給定密文出現(xiàn)的事件與所有特定明文出現(xiàn)的事件，皆是獨(dú)立事件。對(duì)所有明文m以及所有密文c皆成立。

Shannon定理令（所有密文的可能數(shù)目等于所有密鑰的可能數(shù)目）且任一明文m出現(xiàn)的概率均為正數(shù)，即。此密碼系統(tǒng)為完美秘密下列條件皆成立：（1）在密鑰空間上的概率分布函數(shù)為pK均勻分布。（2）對(duì)任一明文m以及任一密文c，均恰好僅存在一把密鑰k使得完美秘密4.2完美秘密定義：一個(gè)密碼系統(tǒng)定義為完美秘熵4.3熵定義熵，Entropy令A(yù)為樣本空間，X為定義在樣本空間上的隨機(jī)變量，則隨機(jī)變量X的熵定義為定義連接熵，JointEntropy令X與Y為樣本空間A與B上的隨機(jī)數(shù)，則連接熵H（X，Y）定義為熵4.3熵定義熵，Entropy令A(yù)為樣本空條件熵定義條件熵，ConditionalEntropy令X與Y為樣本空間A與B上的隨機(jī)數(shù)，則在條件X下的Y條件熵定義為條件熵定義條件熵，ConditionalEntrop鏈?zhǔn)揭?guī)則定理鏈?zhǔn)揭?guī)則，ChainRule證明：條件概率定義指數(shù)律鏈?zhǔn)揭?guī)則定理鏈?zhǔn)揭?guī)則，ChainRule證明：條件概熵性質(zhì)（1），“=”成立當(dāng)樣本空間A的各元素出現(xiàn)的概率相同。（2）。（3），“=”成立當(dāng)X與Y為獨(dú)立事件。定理令M為明文空間M的隨機(jī)變量，C為密文空間C的隨機(jī)變量。密碼系統(tǒng)為完美秘密。熵性質(zhì)（1）熵定理證明：鏈?zhǔn)揭?guī)則K與M為獨(dú)立事件鏈?zhǔn)揭?guī)則故由鏈?zhǔn)揭?guī)則熵定理證明：鏈?zhǔn)揭?guī)則K與M為獨(dú)立事件鏈?zhǔn)揭?guī)則故由鏈?zhǔn)揭?guī)自然語(yǔ)言之熵4.4自然語(yǔ)言之熵定義假密鑰，SpuriousKey

令為含n個(gè)字元的某密文。令c，其中m為符合語(yǔ)法，有意義的明文}為產(chǎn)生密文c的假密鑰的集合。定義自然語(yǔ)言熵，EntropyoftheNaturalLanguage令M為某自然語(yǔ)言的字母集合，Mn表長(zhǎng)度為n的各種不同字母排列。該自然語(yǔ)言L之熵值定義為：此處?kù)刂礖L就是該自然語(yǔ)言的熵值；而由此M中字母所產(chǎn)生的隨機(jī)信息熵是log2|M|，該自然語(yǔ)言的“重復(fù)率”（Redundancy）可定義為：自然語(yǔ)言之熵4.4自然語(yǔ)言之熵定義假密鑰，SpuUnicity距離定義Unicity距離n0，就是該密碼系統(tǒng)所產(chǎn)生密文而惟一決定惟一密鑰值的密文長(zhǎng)度。定理Unicity距離n0估計(jì)為：其中|K|表示所有可能的密鑰數(shù)，而|M|表示所有的字母總數(shù)，R即重復(fù)率。Unicity距離定義Unicity距離n0，就是該密Unicity距離示例例：（愷撒挪移）此時(shí)可能的密鑰總數(shù)|K|=26，（含未加密）故Unicity距離為：（仿射密碼）此時(shí)可能密鑰總數(shù)|K|=12×26=312，（含未加密）故：例：若Alice以單次密碼本加密法將長(zhǎng)度為二元字串信息加密，傳訊給Bob。其中可能密鑰總數(shù)（含未加密）為|K|=2n，Eve計(jì)算例：Unicity距離示例例：（愷撒挪移）此時(shí)可能的密鑰總數(shù)|K返回總目錄第4章

信息理論返回總目錄第4章

信息理論教學(xué)目的回憶概率的基本概念和定理了解什么是完美秘密？了解熵了解自然之熵教學(xué)目的回憶概率的基本概念和定理概率本章內(nèi)容完美秘密熵自然之熵概率本章內(nèi)容完美秘密熵自然之熵概率4.1概率定義令S為一非空的有限集合，稱為樣本空間（SampleSpace），其部分集合稱為事件（Events）。在樣本空間上的概率分布（ProbabilityDistribution）即用一個(gè)函數(shù)p將事件映至某實(shí)數(shù)，（其中表S的冪集合，即）滿足下列各條件：（1）對(duì)所有的事件（2）（3）當(dāng)兩事件與互斥（即）若A為事件，則p(A)為此事件的概率。概率4.1概率定義令S為一非空的有限集合，稱為樣本空概率的性質(zhì)性質(zhì)（1）（2）若則（3）當(dāng)

（4）（5）若均兩兩相斥，則（6）其中概率的性質(zhì)性質(zhì)（1）其中條件概率和獨(dú)立事件定義條件概率，ConditionalProbability令A(yù)與B為事件，且，A在條件B成立下的條件概率定義為定義兩事件A與B稱為獨(dú)立事件（IndependentEvents）此等式也等價(jià)于若等式不成立，則稱A與B為相依事件（DependentEvents）條件概率和獨(dú)立事件定義條件概率，ConditionalBayes定理Bayes定理若A與B為事件，且，，則證明：由條件概率的定義，得：和因此：Bayes定理Bayes定理若A與B為事件，且完美秘密4.2完美秘密定義：一個(gè)密碼系統(tǒng)定義為完美秘密（PerfectSecrecy）所有給定密文出現(xiàn)的事件與所有特定明文出現(xiàn)的事件，皆是獨(dú)立事件。對(duì)所有明文m以及所有密文c皆成立。

Shannon定理令（所有密文的可能數(shù)目等于所有密鑰的可能數(shù)目）且任一明文m出現(xiàn)的概率均為正數(shù)，即。此密碼系統(tǒng)為完美秘密下列條件皆成立：（1）在密鑰空間上的概率分布函數(shù)為pK均勻分布。（2）對(duì)任一明文m以及任一密文c，均恰好僅存在一把密鑰k使得完美秘密4.2完美秘密定義：一個(gè)密碼系統(tǒng)定義為完美秘熵4.3熵定義熵，Entropy令A(yù)為樣本空間，X為定義在樣本空間上的隨機(jī)變量，則隨機(jī)變量X的熵定義為定義連接熵，JointEntropy令X與Y為樣本空間A與B上的隨機(jī)數(shù)，則連接熵H（X，Y）定義為熵4.3熵定義熵，Entropy令A(yù)為樣本空條件熵定義條件熵，ConditionalEntropy令X與Y為樣本空間A與B上的隨機(jī)數(shù)，則在條件X下的Y條件熵定義為條件熵定義條件熵，ConditionalEntrop鏈?zhǔn)揭?guī)則定理鏈?zhǔn)揭?guī)則，ChainRule證明：條件概率定義指數(shù)律鏈?zhǔn)揭?guī)則定理鏈?zhǔn)揭?guī)則，ChainRule證明：條件概熵性質(zhì)（1），“=”成立當(dāng)樣本空間A的各元素出現(xiàn)的概率相同。（2）。（3），“=”成立當(dāng)X與Y為獨(dú)立事件。定理令M為明文空間M的隨機(jī)變量，C為密文空間C的隨機(jī)變量。密碼系統(tǒng)為完美秘密。熵性質(zhì)（1）熵定理證明：鏈?zhǔn)揭?guī)則K與M為獨(dú)立事件鏈?zhǔn)揭?guī)則故由鏈?zhǔn)揭?guī)則熵定理證明：鏈?zhǔn)揭?guī)則K與M為獨(dú)立事件鏈?zhǔn)揭?guī)則故由鏈?zhǔn)揭?guī)自然語(yǔ)言之熵4.4自然語(yǔ)言之熵定義假密鑰，SpuriousKey

令為含n個(gè)字元的某密文。令c，其中m為符合語(yǔ)法，有意義的明文}為產(chǎn)生密文c的假密鑰的集合。定義自然語(yǔ)言熵，EntropyoftheNaturalLanguage令M為某自然語(yǔ)言的字母集合，Mn表長(zhǎng)度為n的各種不同字母排列。該自然語(yǔ)言L之熵值定義為：此處?kù)刂礖L就是該自然語(yǔ)言的熵值；而由此M中字母所產(chǎn)生的隨機(jī)信息熵是log2|M|，該自然語(yǔ)言的“重復(fù)率”（Redundancy）可定義為：自然語(yǔ)言之熵4.4自然語(yǔ)言之熵定義假密鑰，SpuUnicity距離定義Unicity距離n0，就是該密碼系統(tǒng)所產(chǎn)生密文而惟一決定惟一密鑰值的密文長(zhǎng)度。定理Unicity距離n0估計(jì)為：其中|K|表示所有可能的密鑰數(shù)，而