前往總目錄第4章

信息實(shí)際教學(xué)目的回想概率的根本概念和定理了解什么是完美？了解熵了解自然之熵概率本章內(nèi)容完美熵自然之熵概率4.1概率定義令S為一非空的有限集合，稱為樣本空間〔SampleSpace〕，其部分集合稱為事件〔Events〕。在樣本空間上的概率分布〔ProbabilityDistribution〕即用一個(gè)函數(shù)p將事件映至某實(shí)數(shù)，〔其中表S的冪集合，即〕滿足以下各條件：〔1〕對(duì)一切的事件〔2〕〔3〕當(dāng)兩事件與互斥〔即〕假設(shè)A為事件，那么p(A)為此事件的概率。概率的性質(zhì)性質(zhì)〔1〕〔2〕假設(shè)那么〔3〕當(dāng)〔4〕〔5〕假設(shè)均兩兩相斥，那么〔6〕其中條件概率和獨(dú)立事件定義條件概率，ConditionalProbability令A(yù)與B為事件，且，A在條件B成立下的條件概率定義為定義兩事件A與B稱為獨(dú)立事件〔IndependentEvents〕此等式也等價(jià)于假設(shè)等式不成立，那么稱A與B為相依事件〔DependentEvents〕Bayes定理Bayes定理假設(shè)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均勻分布?！?〕對(duì)任一明文m以及任一密文c，均恰好僅存在一把密鑰k使得熵4.3熵定義熵，Entropy令A(yù)為樣本空間，X為定義在樣本空間上的隨機(jī)變量，那么隨機(jī)變量X的熵定義為定義銜接熵，JointEntropy令X與Y為樣本空間A與B上的隨機(jī)數(shù)，那么銜接熵H〔X，Y〕定義為條件熵定義條件熵，ConditionalEntropy令X與Y為樣本空間A與B上的隨機(jī)數(shù)，那么在條件X下的Y條件熵定義為鏈?zhǔn)揭?guī)那么定理鏈?zhǔn)揭?guī)那么，ChainRule證明：條件概率定義指數(shù)律熵性質(zhì)〔1〕，“=〞成立當(dāng)樣本空間A的各元素出現(xiàn)的概率一樣?！?〕?！?〕，“=〞成立當(dāng)X與Y為獨(dú)立事件。定理令M為明文空間M的隨機(jī)變量，C為密文空間C的隨機(jī)變量。密碼系統(tǒng)為完美。熵定理證明：鏈?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〕可定義為：Unicity間隔定義Unicity間隔n0，就是該密碼系統(tǒng)所產(chǎn)生密文而獨(dú)一決議獨(dú)一密鑰值的密文長(zhǎng)度。定理Unicity間隔n0估計(jì)為：其中|K|表示一切能夠的密鑰數(shù)，而|M|表示一切的字母總數(shù)，R即反復(fù)率。Unicity間隔例如例：〔愷撒挪移〕此時(shí)能夠的密鑰總數(shù)|K|=26，〔含未加密〕故Unicity間隔為：〔仿射密碼〕此時(shí)