計(jì)算機(jī)系統(tǒng)與網(wǎng)絡(luò)安全：第2章 信息安全數(shù)學(xué)基礎(chǔ)（概率論）

2022/11/2總結(jié)網(wǎng)絡(luò)與信息安全中的概率論方法概率論中的幾個(gè)定理隨機(jī)變量及其分布第2章信息安全數(shù)學(xué)基礎(chǔ)（概率論）概率論基礎(chǔ)2022/11/2總結(jié)網(wǎng)絡(luò)與信息安全中的概率論方法概率論中的幾個(gè)定理隨機(jī)變量及其分布第2章信息安全數(shù)學(xué)基礎(chǔ)（概率論）概率論基礎(chǔ)2022/11/2概率論基礎(chǔ)子曰：君子不重則不威；學(xué)則不固；主忠信；無友不如己者；過則勿憚改。君子要厚重，不厚重就沒有威嚴(yán)，所學(xué)的東西也不會堅(jiān)固；在與人相處中要以忠信為主；不能與德才不如自己的人做朋友；如果有了過失或錯(cuò)誤不要害怕改正?！敝匮?，重行，重貌，重好（言重則有法，行重則有德，貌重則有威，好重則有觀）學(xué)者言行貌好皆須學(xué)其莊重2022/11/2概率論基礎(chǔ)（續(xù)）進(jìn)行一次試驗(yàn)，如果所得結(jié)果不能完全預(yù)知，但其全體的可能結(jié)果是已知的，則稱此試驗(yàn)為隨機(jī)試驗(yàn)。隨機(jī)試驗(yàn)的每一個(gè)可能的結(jié)果稱為一個(gè)樣本（或樣本點(diǎn)），因而一個(gè)隨機(jī)試驗(yàn)的所有樣本點(diǎn)也是確定的。隨機(jī)試驗(yàn)的全體稱為樣本空間。習(xí)慣上，分別用ω與Ω表示樣本與樣本空間。

2022/11/2概率論基礎(chǔ)（續(xù)）對于隨機(jī)試驗(yàn)，常常關(guān)心樣本空間的某些部分（及一個(gè)或多個(gè)眼本）是否出現(xiàn)，稱這種由部分樣本組成的試驗(yàn)結(jié)果為隨機(jī)事件，簡稱事件，通常用大寫的字母A，B，……表示。

2022/11/2概率論基礎(chǔ)（續(xù)）“事件A與B都發(fā)生”這一事件稱作事件A與B的交，記作A∩B或(AB)“事件A與B至少有一個(gè)發(fā)生”這一事件稱作事件A與B的并，記作A∪B

“事件A發(fā)生而B不發(fā)生”這一事件稱作事件A與B的差,記作

A-B事件A不發(fā)生”這一事件稱作事件A的對立事件，記作2022/11/2概率論基礎(chǔ)（續(xù)）定義（概率的經(jīng)典定義）假設(shè)一個(gè)實(shí)驗(yàn)可以從樣本空間Ω中等概率產(chǎn)生一個(gè)樣本。若隨機(jī)事件A包含了m個(gè)樣本，則量m/n稱為事件A在n次試驗(yàn)中發(fā)生的概率，記作P[A]，即：P[A]=m/n2022/11/2概率論基礎(chǔ)（續(xù)）定義（概率的統(tǒng)計(jì)定義）相同條件下重復(fù)進(jìn)行的n次試驗(yàn)中,事件A發(fā)生的頻率穩(wěn)定地在某一常數(shù)p附近擺動,且隨n越大擺動幅度越小,則稱p為事件A的概率,記作P[A]。即：P[A]=p2022/11/2概率論基礎(chǔ)（續(xù)）設(shè)A、B為兩事件，P[A]>0，把事件A發(fā)生的條件下事件B發(fā)生的概率稱之為條件概率，記為：2022/11/2概率論基礎(chǔ)（續(xù)）定理（全概率公式）如果，且則對Ω中任一事件B，有：2022/11/2概率論基礎(chǔ)（續(xù)）定理（貝葉斯定理）如果，那么：貝葉斯定理說明了在已知x是y的概率的條件下，求已知y是x的概率。

2022/11/2總結(jié)網(wǎng)絡(luò)與信息安全中的概率論方法概率論中的幾個(gè)定理隨機(jī)變量及其分布第2章信息安全數(shù)學(xué)基礎(chǔ)（概率論）概率論基礎(chǔ)2022/11/2隨機(jī)變量及其分布一般地，如果為某個(gè)隨機(jī)事件，則對于某次試驗(yàn)，要么發(fā)生，要么不發(fā)生，因此試驗(yàn)結(jié)果總可以用以下示性函數(shù)來表示：這就說明，不管隨機(jī)試驗(yàn)的結(jié)果是否具有數(shù)量的性質(zhì)，都可以建立一個(gè)樣本空間和實(shí)數(shù)空間的對應(yīng)關(guān)系，從而使得隨機(jī)試驗(yàn)與數(shù)值發(fā)生聯(lián)系，以便更好地研究隨機(jī)試驗(yàn)的結(jié)果。為此，引入了隨機(jī)變量的概念。2022/11/2隨機(jī)變量及其分布（續(xù)）定義（隨機(jī)變量）

設(shè)隨機(jī)試驗(yàn)E的樣本空間為，是定義在上的單值函數(shù)，若對于任意實(shí)為隨機(jī)變量（RandomVariable）。

數(shù)集合是隨機(jī)事件，則稱2022/11/2隨機(jī)實(shí)驗(yàn)舉例例：隨機(jī)試驗(yàn)E：從一個(gè)裝有編號為0，1，2，…，9的球的袋中任意摸一球。則其樣本空間:={，，…，}

其中“摸到編號為的球”，=0,1,…,9.定義函數(shù)：，即()=，=0，1，…，9。2022/11/2隨機(jī)變量及其分布定義（分布函數(shù)）

=P{x}為的分布函數(shù)。設(shè)是上的隨機(jī)變量，對xR，稱：2022/11/2隨機(jī)變量及其分布（續(xù)）離散型隨機(jī)變量的分布函數(shù)F(X)定義為：因此ξ的分布列也完全刻畫了離散型隨機(jī)變量取值的規(guī)律。這樣，對于離散型隨機(jī)變量，只要知道它的一切可能取值和取這些值的概率，也就是說知道了它的分布，也就掌握了這個(gè)離散型隨機(jī)變量的統(tǒng)計(jì)規(guī)律。2022/11/2常見的離散型分布退化分布（單點(diǎn)分布）：貝努里分布（兩點(diǎn)分布，0-1分布）：2022/11/2常見的離散型分布（續(xù)）二項(xiàng)分布（貝努里分布）：

泊松（Poisson）分布：

2022/11/2隨機(jī)變量的數(shù)學(xué)期望離散型隨機(jī)變量的分布只能描述其概率特征，無法反映出其變化情況，而隨機(jī)變量的某種平均值卻可以更好地描述隨機(jī)變量的變化。隨機(jī)變量所有取值的平均值稱之為隨機(jī)變量的數(shù)學(xué)期望。2022/11/2隨機(jī)變量的數(shù)學(xué)期望（續(xù)）定義（數(shù)學(xué)期望）設(shè)ξ為離散型隨機(jī)變量，其概率分布為：若

則稱：

2022/11/2隨機(jī)變量的方差隨機(jī)變量的數(shù)學(xué)期望描述了隨機(jī)變量一切可能取值的平均水平，而隨機(jī)變量的方差可以描述隨機(jī)變量取值與其數(shù)學(xué)期望值的偏離程度。設(shè)是隨機(jī)變量，E()是其數(shù)學(xué)期望，

則

表示

與E()之間的偏差大小，但由于絕對值對運(yùn)算帶來得不便，所以常用

代替之。又因?yàn)?/p>

仍是一隨機(jī)變量，則用

來描述ξ與其E(ξ)的偏離程度的大小

2022/11/2隨機(jī)變量的方差（續(xù)）定義（方差）

由定義，顯然D(ξ)≥0；當(dāng)ξ的可能取值集中在E(ξ)附近時(shí)，D(ξ)較??；否則D(ξ)較大?？梢?，方差大小反映了ξ與E(ξ)的偏離程度（或取值的分散程度）。2022/11/2方差的計(jì)算

2022/11/2方差的計(jì)算（續(xù)）

例

設(shè)L表示最長為k比特二進(jìn)制的非負(fù)數(shù)集合{0,1}k?，F(xiàn)隨機(jī)的從L中取出一個(gè)數(shù)，證明所取數(shù)為k比特的概率為1/2。

證明：由于L最長為k比特，因此非負(fù)數(shù)集合L＝{0,1,2,…,2k-1}。該集合可以分為兩個(gè)不相交的子集合：長度不等于k比特的數(shù)的集合L1和長度等于k比特的數(shù)的集合L2：L1＝{0,1,2,…,2k-1-1}L2＝{2k-1,2k-1+1,…2k-1}2022/11/2總結(jié)網(wǎng)絡(luò)與信息安全中的概率論方法概率論中的幾個(gè)定理隨機(jī)變量及其分布第2章信息安全數(shù)學(xué)基礎(chǔ)（概率論）概率論基礎(chǔ)2022/11/2概率論中的幾個(gè)定理馬爾可夫不等式契比雪夫不等式切比雪夫大數(shù)定理貝努里大數(shù)定理辛欽大數(shù)定理兩兩獨(dú)立取樣完全獨(dú)立取樣霍弗丁不等式2022/11/2貝努里試驗(yàn)

定義（貝努里試驗(yàn)）假定一個(gè)試驗(yàn)只有兩個(gè)結(jié)果，記為“成功”和“失敗”。獨(dú)立重復(fù)的進(jìn)行該試驗(yàn)，如果每一次試驗(yàn)有且僅有兩種可能的結(jié)果，并且它們的概率在整個(gè)試驗(yàn)的過程中是不變的，那么這樣的試驗(yàn)被稱為貝努里試驗(yàn)。例如，拋擲一枚硬幣的試驗(yàn)就屬于貝努里試驗(yàn)。假設(shè)在任何一次試驗(yàn)中：P[“成功”]＝p，P[“失敗”]＝1－p那么：P[n次試驗(yàn)中有k次為“成功”]＝其中，表示從n件物體中取出k件物品的不同取法。2022/11/2貝努里試驗(yàn)（續(xù)）如果隨機(jī)變量取值為,并且對每一個(gè)p，

有：那么稱服從貝努里分布。2022/11/2馬爾可夫不等式定理（馬爾可夫不等式）令X為一非負(fù)隨機(jī)變量，為一實(shí)數(shù)，則有；等價(jià)地，有

。證明：馬爾可夫（Markov）不等式常用于不了解隨機(jī)變量的整體分布情況，它只要求了解隨機(jī)變量的期望在它的一個(gè)取值范圍內(nèi)的界。因此，利用馬爾可夫不等式，可以得到一個(gè)隨機(jī)變量偏離其均值“更緊”的界。2022/11/2契比雪夫不等式與大數(shù)定理

2022/11/2契比雪夫不等式與大數(shù)定理（續(xù)）

2022/11/2契比雪夫不等式與大數(shù)定理（續(xù)）

2022/11/2貝努里大數(shù)定理

2022/11/2貝努里大數(shù)定理（續(xù)）

2022/11/2兩兩獨(dú)立取樣

2022/11/2兩兩獨(dú)立取樣2022/11/2完全獨(dú)立取樣

2022/11/2霍弗丁不等式

2022/11/2總結(jié)網(wǎng)絡(luò)與信息安全中的概率論方法概率論中的幾個(gè)定理隨機(jī)變量及其分布第2章信息安全數(shù)學(xué)基礎(chǔ)（概率論）概率論基礎(chǔ)2022/11/2密碼體制定義（密碼體制）其中，P表示明文空間，C表示密文空間，K表示密鑰空間，E和D分別表示加密算法和解密算法。從概率論的角度來看，明文取值代表了隨機(jī)變量X，密文的取值代表了隨機(jī)變量Y，密鑰取值代表隨機(jī)變量K，而P[X=x]，P[Y=y]，P[K=k]分別表明文空間、密文空間和密鑰空間所發(fā)生的概率。2022/11/2密碼體制2022/11/2密碼體制（續(xù)）2022/11/2密碼體制（續(xù)）2022/11/2密碼體制（續(xù)）2022/11/2密碼體制的完善保密性（密碼體制的完善保密性）對于密碼體制，如果對于，有：，則稱該密碼體制具有完善保密性。依據(jù)上述定義，如果一個(gè)密碼體制具有完善保密性，則對于給定密文y，明文為x的后驗(yàn)概率等于明文x的先驗(yàn)概率。2022/11/2密碼體制的完善保密性（續(xù)）2022/11/2密碼體制的完善保密性（續(xù)）2022/11/2密碼體制的完善保密性（續(xù)）2022/11/2密碼體制的完善保密性（續(xù)）所以移位密碼具有完善保密性。

2022/11/2生日悖論問題（續(xù)）2022/11/2生日悖論問題（續(xù)）2022/11/2生日悖論問題（續(xù)）2022/11/2生日悖論問題（續(xù)）2022/11/2生日悖論問題（續(xù)）2022/11/2生日悖論問題（續(xù)）從計(jì)算復(fù)雜性來看，發(fā)生碰撞的計(jì)算次數(shù)的復(fù)雜度為O()，即對于一個(gè)輸出空間大小為n的隨機(jī)函數(shù)，只需計(jì)算大約個(gè)函數(shù)值，就可以以一個(gè)不可忽略的概率發(fā)現(xiàn)一個(gè)碰撞：對于兩個(gè)不同的隨機(jī)函數(shù)輸入，其輸出相同。這個(gè)結(jié)論對于密碼系統(tǒng)與密碼協(xié)議的設(shè)計(jì)有著深刻影響。例如：當(dāng)用隨機(jī)函數(shù)來隱藏一組秘密信息，如果這個(gè)隨機(jī)函數(shù)的輸出空間不夠大，就可以通過隨機(jī)的計(jì)算這個(gè)隨機(jī)函數(shù)的函數(shù)值來找出這組秘密信息中的一部分。這種攻擊被稱為平方根攻擊或者生日攻擊。輸出空間的大小n在密碼學(xué)中是非常重要的安全因素，通常稱之為安全參數(shù)。2022/11/2總結(jié)網(wǎng)絡(luò)與信息安全中的概率論方法概率論中的幾個(gè)定理隨機(jī)變量及其分布第2章信息安全數(shù)學(xué)基礎(chǔ)（概率論）概率論基礎(chǔ)2022/11/2教材與參考書教材：李毅超曹躍，網(wǎng)絡(luò)與系統(tǒng)攻擊技術(shù)電子科大出版社2007周世杰陳偉鐘婷，網(wǎng)絡(luò)與系統(tǒng)防御技術(shù)電子科大出版社2007

參考書闕喜戎等編著，信息安全原理及應(yīng)用，清華大學(xué)出版社ChristopherM.King,CuritisE.Dalton,T.ErtemOsmanoglu（常曉波等譯）.安全體系結(jié)構(gòu)的設(shè)計(jì)、部署與操作，清華大學(xué)出版社，2003(ChristopherM.King,etal,SecurityArchitecture,design,deployment&Operations)WilliamStallings，密碼編碼學(xué)與網(wǎng)絡(luò)