信息安全數(shù)學基礎(概率論)課件

電子科技大學計算機科學與工程學院計算系統(tǒng)與網(wǎng)絡平安

ComputerSystemandNetworkSecurity2023/7/13概率論根底子曰：君子不重那么不威；學那么不固；主忠信；無友不如己者；過那么勿憚改。君子要厚重，不厚重就沒有威嚴，所學的東西也不會鞏固；在與人相處中要以忠信為主；不能與德才不如自己的人做朋友；如果有了過失或錯誤不要害怕改正。〞重言，重行，重貌，重好〔言重那么有法，行重那么有德，貌重那么有威，好重那么有觀〕學者言行貌好皆須學其莊重2023/7/13總結網(wǎng)絡與信息平安中的概率論方法概率論中的幾個定理隨機變量及其分布第2章信息平安數(shù)學根底〔概率論〕概率論根底2023/7/13總結網(wǎng)絡與信息平安中的概率論方法概率論中的幾個定理隨機變量及其分布第2章信息平安數(shù)學根底〔概率論〕概率論根底2023/7/13概率論根底進行一次試驗，如果所得結果不能完全預知，但其全體的可能結果是的，那么稱此試驗為隨機試驗。隨機試驗的每一個可能的結果稱為一個樣本〔或樣本點〕，因而一個隨機試驗的所有樣本點也是確定的。隨機試驗的全體稱為樣本空間。習慣上，分別用ω與Ω表示樣本與樣本空間。2023/7/13概率論根底〔續(xù)〕定義〔概率的經(jīng)典定義〕假設一個實驗可以從樣本空間Ω中等概率產生一個樣本。假設隨機事件A包含了m個樣本，那么量m/n稱為事件A在n次試驗中發(fā)生的概率，記作P[A]，即：P[A]=m/n2023/7/13概率論根底〔續(xù)〕定義〔概率的統(tǒng)計定義〕相同條件下重復進行的n次試驗中,事件A發(fā)生的頻率穩(wěn)定地在某一常數(shù)p附近擺動,且隨n越大擺動幅度越小,那么稱p為事件A的概率,記作P[A]。即：P[A]=p2023/7/13概率論根底〔續(xù)〕設A、B為兩事件，P[A]>0，把事件A發(fā)生的條件下事件B發(fā)生的概率稱之為條件概率，記為：2023/7/13概率論根底〔續(xù)〕定理〔全概率公式〕如果，且那么對Ω中任一事件B，有：2023/7/13概率論根底〔續(xù)〕定理〔貝葉斯定理〕如果，那么：貝葉斯定理說明了在x是y的概率的條件下，求y是x的概率。2023/7/13總結網(wǎng)絡與信息平安中的概率論方法概率論中的幾個定理隨機變量及其分布第2章信息平安數(shù)學根底〔概率論〕概率論根底2023/7/13隨機變量及其分布一般地，如果為某個隨機事件，那么對于某次試驗，要么發(fā)生，要么不發(fā)生，因此試驗結果總可以用以下示性函數(shù)來表示：這就說明，不管隨機試驗的結果是否具有數(shù)量的性質，都可以建立一個樣本空間和實數(shù)空間的對應關系，從而使得隨機試驗與數(shù)值發(fā)生聯(lián)系，以便更好地研究隨機試驗的結果。為此，引入了隨機變量的概念。2023/7/13隨機變量及其分布〔續(xù)〕定義〔隨機變量〕設隨機試驗E的樣本空間為，是定義在上的單值函數(shù)，假設對于任意實為隨機變量〔RandomVariable〕。數(shù)集合是隨機事件，那么稱2023/7/13隨機實驗舉例例：隨機試驗E：從一個裝有編號為0，1，2，…，9的球的袋中任意摸一球。那么其樣本空間:={，，…，}

其中“摸到編號為的球”，=0,1,…,9.定義函數(shù)：，即()=，=0，1，…，9。2023/7/13隨機變量及其分布定義〔分布函數(shù)〕=P{x}為的分布函數(shù)。設是上的隨機變量，對xR，稱：2023/7/13隨機變量及其分布〔續(xù)〕離散型隨機變量的分布函數(shù)F(X)定義為：因此ξ的分布列也完全刻畫了離散型隨機變量取值的規(guī)律。這樣，對于離散型隨機變量，只要知道它的一切可能取值和取這些值的概率，也就是說知道了它的分布，也就掌握了這個離散型隨機變量的統(tǒng)計規(guī)律。2023/7/13常見的離散型分布退化分布〔單點分布〕：貝努里分布〔兩點分布，0-1分布〕：2023/7/13常見的離散型分布〔續(xù)〕二項分布〔貝努里分布〕：泊松〔Poisson〕分布：2023/7/13隨機變量的數(shù)學期望離散型隨機變量的分布只能描述其概率特征，無法反映出其變化情況，而隨機變量的某種平均值卻可以更好地描述隨機變量的變化。隨機變量所有取值的平均值稱之為隨機變量的數(shù)學期望。2023/7/13隨機變量的數(shù)學期望〔續(xù)〕定義〔數(shù)學期望〕設ξ為離散型隨機變量，其概率分布為：假設那么稱：2023/7/13隨機變量的方差隨機變量的數(shù)學期望描述了隨機變量一切可能取值的平均水平，而隨機變量的方差可以描述隨機變量取值與其數(shù)學期望值的偏離程度。設是隨機變量，E()是其數(shù)學期望，

則

表示

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

代替之。又因為

仍是一隨機變量，則用

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

2023/7/13隨機變量的方差〔續(xù)〕定義〔方差〕由定義，顯然D(ξ)≥0；當ξ的可能取值集中在E(ξ)附近時，D(ξ)較??；否那么D(ξ)較大?？梢?，方差大小反映了ξ與E(ξ)的偏離程度〔或取值的分散程度〕。2023/7/13方差的計算

2023/7/13方差的計算〔續(xù)〕例

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

證明：由于L最長為k比特，因此非負數(shù)集合L＝{0,1,2,…,2k-1}。該集合可以分為兩個不相交的子集合：長度不等于k比特的數(shù)的集合L1和長度等于k比特的數(shù)的集合L2：L1＝{0,1,2,…,2k-1-1}L2＝{2k-1,2k-1+1,…2k-1}2023/7/13總結網(wǎng)絡與信息平安中的概率論方法概率論中的幾個定理隨機變量及其分布第2章信息平安數(shù)學根底〔概率論〕概率論根底2023/7/13概率論中的幾個定理馬爾可夫不等式契比雪夫不等式切比雪夫大數(shù)定理貝努里大數(shù)定理辛欽大數(shù)定理兩兩獨立取樣完全獨立取樣霍弗丁不等式2023/7/13貝努里試驗

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

有：那么稱服從貝努里分布。2023/7/13馬爾可夫不等式定理〔馬爾可夫不等式〕令X為一非負隨機變量，為一實數(shù)，那么有；等價地，有。證明：馬爾可夫〔Markov〕不等式常用于不了解隨機變量的整體分布情況，它只要求了解隨機變量的期望在它的一個取值范圍內的界。因此，利用馬爾可夫不等式，可以得到一個隨機變量偏離其均值“更緊〞的界。2023/7/13契比雪夫不等式與大數(shù)定理

2023/7/13契比雪夫不等式與大數(shù)定理〔續(xù)〕2023/7/13契比雪夫不等式與大數(shù)定理〔續(xù)〕2023/7/13貝努里大數(shù)定理

2023/7/13貝努里大數(shù)定理〔續(xù)〕2023/7/13兩兩獨立取樣

2023/7/13兩兩獨立取樣2023/7/13完全獨立取樣

2023/7/13霍弗丁不等式

2023/7/13總結網(wǎng)絡與信息平安中的概率論方法概率論中的幾個定理隨機變量及其分布第2章信息平安數(shù)學根底〔概率論〕概率論根底2023/7/13密碼體制定義〔密碼體制〕其中，P表示明文空間，C表示密文空間，K表示密鑰空間，E和D分別表示加密算法和解密算法。從概率論的角度來看，明文取值代表了隨機變量X，密文的取值代表了隨機變量Y，密鑰取值代表隨機變量K，而P[X=x]，P[Y=y]，P[K=k]分別說明文空間、密文空間和密鑰空間所發(fā)生的概率。2023/7/13密碼體制2023/7/13密碼體制〔續(xù)〕2023/7/13密碼體制〔續(xù)〕2023/7/13密碼體制〔續(xù)〕2023/7/13密碼體制的完善保密性〔密碼體制的完善保密性〕對于密碼體制，如果對于，有：，那么稱該密碼體制具有完善保密性。依據(jù)上述定義，如果一個密碼體制具有完善保密性，那么對于給定密文y，明文為x的后驗概率等于明文x的先驗概率。2023/7/13密碼體制的完善保密性〔續(xù)〕2023/7/13密碼體制的完善保密性〔續(xù)〕2023/7/13密碼體制的完善保密性〔續(xù)〕2023/7/13密碼體制的完善保密性〔續(xù)〕所以移位密碼具有完善保密性。

2023/7/13生日悖論問題〔續(xù)〕2023/7/13生日悖論問題〔續(xù)〕2023/7/13生日悖論問題〔續(xù)〕2023/7/13生日悖論問題〔續(xù)〕2023/7/13生日悖論問題〔續(xù)〕2023/7/13生日悖論問題〔續(xù)〕從計算復雜性來看，發(fā)生碰撞的計算次數(shù)的復雜度為O()，即對于一個輸出空間大小為n的隨機函數(shù)，只需計算大約個函數(shù)值，就可以以一個不可忽略的概率發(fā)現(xiàn)一個碰撞：對于兩個不同的隨機函數(shù)輸入，其輸出相同。這個結論對于密碼系統(tǒng)與密碼協(xié)議的設計有著深刻影響。例如：當用隨機函數(shù)來隱藏一組秘密信息，如果這個隨機函數(shù)的輸出空間不夠大，就可以通過隨機的計算這個隨機函數(shù)的函數(shù)值來找出這組秘密信息中的一局部。這種攻擊被稱為平方根攻擊或者生日攻擊。輸出空間的大小n在密碼學中是非常重要的平安因素，通常稱之為平安參數(shù)。2023/7/13總結網(wǎng)絡與信息平安中的概率論方法概率論中的幾個定理隨機變量及其分布第2章信息平安數(shù)學根底〔概率論〕概率論根底2023/7/13參考書參考書楊義先等，信息平安理論與技術，郵電出版社MaoWenbo，ModernCryptography:TheoryandPractice

，電子工業(yè)出版社，2004BruceSchneier,AppliedCryptography,Protocols,algorithms,andsourcecodeinC(2ndEdition)(應用密碼學－協(xié)議、算法與C源