1、2020/9/1,電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,計(jì)算系統(tǒng)與網(wǎng)絡(luò)安全Computer System and Network Security,2020/9/1,概率論基礎(chǔ),子曰：君子不重則不威；學(xué)則不固；主忠信；無(wú)友不如己者；過則勿憚改。 君子要厚重，不厚重就沒有威嚴(yán)，所學(xué)的東西也不會(huì)堅(jiān)固；在與人相處中要以忠信為主；不能與德才不如自己的人做朋友；如果有了過失或錯(cuò)誤不要害怕改正。” 重言，重行，重貌，重好 （言重則有法，行重則有德，貌重則有威，好重則有觀 ） 學(xué)者言行貌好皆須學(xué)其莊重,2020/9/1,總結(jié),網(wǎng)絡(luò)與信息安全中的概率論方法,概率論中的幾個(gè)定理,隨機(jī)變量及其分布,第2章 信息安全

2、數(shù)學(xué)基礎(chǔ)（概率論）,概率論基礎(chǔ),2020/9/1,總結(jié),網(wǎng)絡(luò)與信息安全中的概率論方法,概率論中的幾個(gè)定理,隨機(jī)變量及其分布,第2章 信息安全數(shù)學(xué)基礎(chǔ)（概率論）,概率論基礎(chǔ),2020/9/1,概率論基礎(chǔ),進(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í)慣上，分別用與表示樣本與樣本空間。,2020/9/1,概率論基礎(chǔ)（續(xù)）,定義（概率的經(jīng)典定義）假設(shè)一個(gè)實(shí)驗(yàn)可以從樣本空間中等概率產(chǎn)生一個(gè)樣本。若隨機(jī)事件A包含了m個(gè)樣本，則量m/n稱

3、為事件A在n次試驗(yàn)中發(fā)生的概率，記作P A，即： PA=m/n,2020/9/1,概率論基礎(chǔ)（續(xù)）,定義（概率的統(tǒng)計(jì)定義）相同條件下重復(fù)進(jìn)行的n次試驗(yàn)中, 事件A發(fā)生的頻率穩(wěn)定地在某一常數(shù)p附近擺動(dòng), 且隨n越大擺動(dòng)幅度越小, 則稱p為事件A的概率, 記作PA。 即： PA=p,2020/9/1,概率論基礎(chǔ)（續(xù)）,設(shè)A、B為兩事件，P A 0，把事件A發(fā)生的條件下事件B發(fā)生的概率稱之為條件概率，記為：,2020/9/1,概率論基礎(chǔ)（續(xù)）,定理（全概率公式）,如果,，且,則對(duì)中任一事件B，有：,2020/9/1,概率論基礎(chǔ)（續(xù)）,定理（貝葉斯定理）,如果,，,那么：,貝葉斯定理說(shuō)明了在已知x是y

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

5、定義在 上的單值函數(shù)，若對(duì)于任意實(shí),為隨機(jī)變量（Random Variable）。,數(shù) 集合 是隨機(jī)事件，則稱,2020/9/1,隨機(jī)實(shí)驗(yàn)舉例,例：隨機(jī)試驗(yàn)E：從一個(gè)裝有編號(hào)為0，1，2，9的球的袋中任意摸一球。則其樣本空間 :,2020/9/1,隨機(jī)變量及其分布,定義（分布函數(shù)）,2020/9/1,隨機(jī)變量及其分布（續(xù)）,離散型隨機(jī)變量的分布函數(shù)F(X)定義為 ：,因此的分布列也完全刻畫了離散型隨機(jī)變量取值的規(guī)律。這樣，對(duì)于離散型隨機(jī)變量，只要知道它的一切可能取值和取這些值的概率，也就是說(shuō)知道了它的分布，也就掌握了這個(gè)離散型隨機(jī)變量的統(tǒng)計(jì)規(guī)律。,2020/9/1,常見的離散型分布,退化分布（

6、單點(diǎn)分布）： 貝努里分布（兩點(diǎn)分布，0-1分布）：,2020/9/1,常見的離散型分布（續(xù)）,二項(xiàng)分布（貝努里分布）： 泊松（Poisson）分布：,2020/9/1,隨機(jī)變量的數(shù)學(xué)期望,離散型隨機(jī)變量的分布只能描述其概率特征，無(wú)法反映出其變化情況，而隨機(jī)變量的某種平均值卻可以更好地描述隨機(jī)變量的變化。 隨機(jī)變量所有取值的平均值稱之為隨機(jī)變量的數(shù)學(xué)期望。,2020/9/1,隨機(jī)變量的數(shù)學(xué)期望（續(xù)）,定義（數(shù)學(xué)期望）設(shè)為離散型隨機(jī)變量，其概率分布為： 若 則稱：,2020/9/1,隨機(jī)變量的方差,隨機(jī)變量的數(shù)學(xué)期望描述了隨機(jī)變量一切可能取值的平均水平，而隨機(jī)變量的方差可以描述隨機(jī)變量取值與其數(shù)學(xué)

7、期望值的偏離程度。,2020/9/1,隨機(jī)變量的方差（續(xù)）,定義（方差）,由定義，顯然D() 0；當(dāng)?shù)目赡苋≈导性贓()附近時(shí)，D()較??；否則D()較大。 可見，方差大小反映了與E()的偏離程度（或取值的分散程度）。,2020/9/1,方差的計(jì)算,2020/9/1,方差的計(jì)算（續(xù)）,例 設(shè)L表示最長(zhǎng)為k比特二進(jìn)制的非負(fù)數(shù)集合0, 1k?，F(xiàn)隨機(jī)的從L中取出一個(gè)數(shù)，證明所取數(shù)為k比特的概率為1/2。,證明： 由于L最長(zhǎng)為k比特，因此非負(fù)數(shù)集合L0, 1, 2, , 2k-1。該集合可以分為兩個(gè)不相交的子集合：長(zhǎng)度不等于k比特的數(shù)的集合L1和長(zhǎng)度等于k比特的數(shù)的集合L2： L10, 1, 2,

8、, 2k-1-1 L22k-1, 2k-1+1, 2k-1,2020/9/1,總結(jié),網(wǎng)絡(luò)與信息安全中的概率論方法,概率論中的幾個(gè)定理,隨機(jī)變量及其分布,第2章 信息安全數(shù)學(xué)基礎(chǔ)（概率論）,概率論基礎(chǔ),2020/9/1,概率論中的幾個(gè)定理,馬爾可夫不等式 契比雪夫不等式 切比雪夫大數(shù)定理 貝努里大數(shù)定理 辛欽大數(shù)定理 兩兩獨(dú)立取樣 完全獨(dú)立取樣 霍弗丁不等式,2020/9/1,貝努里試驗(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)。 例如，

9、拋擲一枚硬幣的試驗(yàn)就屬于貝努里試驗(yàn)。假設(shè)在任何一次試驗(yàn)中：P“成功”p，P“失敗”1p 那么： Pn次試驗(yàn)中有k次為“成功” 其中， 表示從n件物體中取出k件物品的不同取法。,2020/9/1,貝努里試驗(yàn)（續(xù)）,如果隨機(jī)變量取值為 ,并且對(duì)每一個(gè)p， 有： 那么稱 服從貝努里分布。,2020/9/1,馬爾可夫不等式,定理（馬爾可夫不等式）令X為一非負(fù)隨機(jī) 變量， 為一實(shí)數(shù)，則有 ；等價(jià)地，有 。 證明： 馬爾可夫（Markov）不等式常用于不了解隨機(jī)變量的整體分布情況，它只要求了解隨機(jī)變量的期望在它的一個(gè)取值范圍內(nèi)的界。因此，利用馬爾可夫不等式，可以得到一個(gè)隨機(jī)變量偏離其均值“更緊”的界。,2

10、020/9/1,契比雪夫不等式與大數(shù)定理,2020/9/1,契比雪夫不等式與大數(shù)定理（續(xù)）,2020/9/1,契比雪夫不等式與大數(shù)定理（續(xù)）,2020/9/1,貝努里大數(shù)定理,2020/9/1,貝努里大數(shù)定理（續(xù)）,2020/9/1,兩兩獨(dú)立取樣,2020/9/1,兩兩獨(dú)立取樣,2020/9/1,完全獨(dú)立取樣,2020/9/1,霍弗丁不等式,2020/9/1,總結(jié),網(wǎng)絡(luò)與信息安全中的概率論方法,概率論中的幾個(gè)定理,隨機(jī)變量及其分布,第2章 信息安全數(shù)學(xué)基礎(chǔ)（概率論）,概率論基礎(chǔ),2020/9/1,密碼體制,定義（密碼體制）,其中，P表示明文空間，C表示密文空間，K表示密鑰空間，E和D分別表示加

11、密算法和解密算法。,從概率論的角度來(lái)看，明文取值代表了隨機(jī)變量X，密文的取值代表了隨機(jī)變量Y，密鑰取值代表隨機(jī)變量K，而PX=x，PY=y，PK=k分別表明文空間、密文空間和密鑰空間所發(fā)生的概率。,2020/9/1,密碼體制,2020/9/1,密碼體制（續(xù)）,2020/9/1,密碼體制（續(xù)）,2020/9/1,密碼體制（續(xù)）,2020/9/1,密碼體制的完善保密性,（密碼體制的完善保密性）對(duì)于密碼體制 ，如果對(duì)于 ，有： ，則稱該密碼體制具有完善保密性。 依據(jù)上述定義，如果一個(gè)密碼體制具有完善保密性，則對(duì)于給定密文y，明文為x的后驗(yàn)概率等于明文x的先驗(yàn)概率。,2020/9/1,密碼體制的完善保

12、密性（續(xù)）,2020/9/1,密碼體制的完善保密性（續(xù)）,2020/9/1,密碼體制的完善保密性（續(xù)）,2020/9/1,密碼體制的完善保密性（續(xù)）,所以移位密碼具有完善保密性。,2020/9/1,生日悖論問題（續(xù)）,2020/9/1,生日悖論問題（續(xù)）,2020/9/1,生日悖論問題（續(xù)）,2020/9/1,生日悖論問題（續(xù)）,2020/9/1,生日悖論問題（續(xù)）,2020/9/1,生日悖論問題（續(xù)）,從計(jì)算復(fù)雜性來(lái)看，發(fā)生碰撞的計(jì)算次數(shù)的復(fù)雜度為O( )，即對(duì)于一個(gè)輸出空間大小為n的隨機(jī)函數(shù)，只需計(jì)算大約 個(gè)函數(shù)值，就可以以一個(gè)不可忽略的概率發(fā)現(xiàn)一個(gè)碰撞：對(duì)于兩個(gè)不同的隨機(jī)函數(shù)輸入，其輸出

13、相同。 這個(gè)結(jié)論對(duì)于密碼系統(tǒng)與密碼協(xié)議的設(shè)計(jì)有著深刻影響。 例如：當(dāng)用隨機(jī)函數(shù)來(lái)隱藏一組秘密信息，如果這個(gè)隨機(jī)函數(shù)的輸出空間不夠大，就可以通過隨機(jī)的計(jì)算這個(gè)隨機(jī)函數(shù)的函數(shù)值來(lái)找出這組秘密信息中的一部分。這種攻擊被稱為平方根攻擊或者生日攻擊。 輸出空間的大小n在密碼學(xué)中是非常重要的安全因素，通常稱之為安全參數(shù)。,2020/9/1,總結(jié),網(wǎng)絡(luò)與信息安全中的概率論方法,概率論中的幾個(gè)定理,隨機(jī)變量及其分布,第2章 信息安全數(shù)學(xué)基礎(chǔ)（概率論）,概率論基礎(chǔ),2020/9/1,參考書,參考書 楊義先等，信息安全理論與技術(shù)，郵電出版社 Mao Wenbo， Modern Cryptography: Theory and Practice， 電子工業(yè)出版社，2004 Bruce Schneier, Applied Cryptography, Protocols, algorithms, and source code in C (2nd Edition)( 應(yīng)用密碼學(xué) 協(xié)議、算法與C源程序， 吳世忠、祝世雄、張文政等譯)