信息安全数学基础(概率论)

1、2022-3-21整理ppt电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院 计算系统与网络安全计算系统与网络安全Computer System and Network SecurityComputer System and Network Security2022-3-21整理ppt概率论基础概率论基础l子曰：君子不子曰：君子不重重则不威；学则不固；主忠信；无则不威；学则不固；主忠信；无友不如己者；过则勿惮改。友不如己者；过则勿惮改。l君子要厚重，不厚重就没有威严，所学的东西也不会坚君子要厚重，不厚重就没有威严，所学的东西也不会坚固；在与人相处中要以忠信为主；不能与德才不如

2、自己固；在与人相处中要以忠信为主；不能与德才不如自己的人做朋友；如果有了过失或错误不要害怕改正。的人做朋友；如果有了过失或错误不要害怕改正。” l重言，重行，重貌，重好重言，重行，重貌，重好 （言重则有法，行重则有德，（言重则有法，行重则有德，貌重则有威，好重则有观貌重则有威，好重则有观 ）l学者学者言行貌好言行貌好皆须学其庄重皆须学其庄重 2022-3-21整理ppt第第2 2章章 信息安全数学基础（概率论）信息安全数学基础（概率论）2022-3-21整理ppt第第2 2章章 信息安全数学基础（概率论）信息安全数学基础（概率论）2022-3-21整理ppt概率论基础概率论基础l进行一次试验，

3、如果所得结果不能完全预知，但进行一次试验，如果所得结果不能完全预知，但其全体的可能结果是已知的，则称此试验为其全体的可能结果是已知的，则称此试验为随机随机试验试验。 l随机试验的每一个可能的结果称为一个随机试验的每一个可能的结果称为一个样本样本（或（或样本点），因而一个随机试验的所有样本点也是样本点），因而一个随机试验的所有样本点也是确定的。随机试验的全体称为确定的。随机试验的全体称为样本空间样本空间。l习惯上，分别用习惯上，分别用与与表示样本与样本空间。表示样本与样本空间。 2022-3-21整理ppt概率论基础（续）概率论基础（续）l定义（概率的经典定义）假设一个实验可以从样定义（概率的经

4、典定义）假设一个实验可以从样本空间本空间中等概率产生一个样本。若随机事件中等概率产生一个样本。若随机事件A包包含了含了m个样本，则量个样本，则量m/n称为事件称为事件A在在n次试验中次试验中发生的概率，记作发生的概率，记作P A，即：，即： PA=m/n 2022-3-21整理ppt概率论基础（续）概率论基础（续）l定义（概率的统计定义）相同条件下重复进行的定义（概率的统计定义）相同条件下重复进行的n次试验中次试验中, 事件事件A发生的频率稳定地在某一常数发生的频率稳定地在某一常数p附近摆动附近摆动, 且随且随n越大摆动幅度越小越大摆动幅度越小, 则称则称p为事件为事件A的概率的概率, 记作记

5、作PA。 即：即：PA=p2022-3-21整理ppt概率论基础（续）概率论基础（续）l设设A、B为两事件，为两事件，P A 0，把事件，把事件A发生的条发生的条件下事件件下事件B发生的概率称之为条件概率，记为：发生的概率称之为条件概率，记为： PPPABB AA 2022-3-21整理ppt概率论基础（续）概率论基础（续）l定理（全概率公式）定理（全概率公式） 1niiAijAA 1 |niiiP BP B AP A如果如果，且，且则对则对中任一事件中任一事件B，有：，有：2022-3-21整理ppt概率论基础（续）概率论基础（续）l定理（贝叶斯定理）定理（贝叶斯定理） 0p x 0p y

6、| | p x p y xp x yp y如果如果，那么：那么：贝叶斯定理说明了在已知贝叶斯定理说明了在已知x是是y的概率的条件下，的概率的条件下，求已知求已知y是是x的概率。的概率。 2022-3-21整理ppt第第2 2章章 信息安全数学基础（概率论）信息安全数学基础（概率论）2022-3-21整理ppt随机变量及其分布随机变量及其分布l一般地，如果为某个随机事件，则对于某次试验，一般地，如果为某个随机事件，则对于某次试验，要么发生，要么不发生，因此试验结果总可以用要么发生，要么不发生，因此试验结果总可以用以下示性函数来表示：以下示性函数来表示：l这就说明，不管随机试验的结果是否具有数量的

7、这就说明，不管随机试验的结果是否具有数量的性质，都可以建立一个样本空间和实数空间的对性质，都可以建立一个样本空间和实数空间的对应关系，从而使得随机试验与数值发生联系，以应关系，从而使得随机试验与数值发生联系，以便更好地研究随机试验的结果。便更好地研究随机试验的结果。l为此，引入了为此，引入了随机变量随机变量的概念。的概念。 不发生发生AAA0112022-3-21整理ppt随机变量及其分布（续）随机变量及其分布（续）l定义（随机变量）定义（随机变量） 设随机试验设随机试验E的样本空间为的样本空间为 ，是定义在是定义在 上的单值函数，若对于任意实上的单值函数，若对于任意实为随机变量（为随机变量（

8、Random Variable）。）。 数数 集合集合 是随机事件，则称是随机事件，则称)(x)(:x)(2022-3-21整理ppt随机实验举例随机实验举例l例：随机试验例：随机试验E：从一个装有编号为：从一个装有编号为0，1，2，9的球的袋中任意摸一球。则其样本空间的球的袋中任意摸一球。则其样本空间 :019=， iii其中其中“摸到编号为摸到编号为 的球的球”， =0,1,9.iiiii定义函数定义函数 ：，即，即()=，=0，1，9。2022-3-21整理ppt随机变量及其分布随机变量及其分布l定义（分布函数）定义（分布函数） )(xF= Px为为的分布函数。的分布函数。设设是是上的随

9、机变量，对上的随机变量，对xR，称：称：2022-3-21整理ppt随机变量及其分布（续）随机变量及其分布（续）l离散型随机变量的分布函数离散型随机变量的分布函数F(X)定义为定义为 ：:( )iii xxF xPxpx 因此因此的分布列也完全刻画了离散型随机变量取值的规律。这样，对于离的分布列也完全刻画了离散型随机变量取值的规律。这样，对于离散型随机变量，只要知道它的一切可能取值和取这些值的概率，也就是说散型随机变量，只要知道它的一切可能取值和取这些值的概率，也就是说知道了它的分布，也就掌握了这个离散型随机变量的统计规律。知道了它的分布，也就掌握了这个离散型随机变量的统计规律。2022-3-

10、21整理ppt常见的离散型分布常见的离散型分布l退化分布（单点分布）：退化分布（单点分布）：l贝努里分布（两点分布，贝努里分布（两点分布，0-1分布）分布）： axaxxF10)(1aPpq101 , 0)1 (1xppxXPxx2022-3-21整理ppt常见的离散型分布（续）常见的离散型分布（续）l二项分布（贝努里分布）：二项分布（贝努里分布）： l泊松（泊松（Poisson）分布：）分布： nkqpknkPpnkBknk, 2 , 1 , 0),;()0(, 2 , 1 , 0!kekkPk2022-3-21整理ppt随机变量的数学期望随机变量的数学期望l离散型随机变量的分布只能描述其概

11、率特征，无离散型随机变量的分布只能描述其概率特征，无法反映出其变化情况，而随机变量的某种平均值法反映出其变化情况，而随机变量的某种平均值却可以更好地描述随机变量的变化。却可以更好地描述随机变量的变化。l随机变量所有取值的平均值称之为随机变量的随机变量所有取值的平均值称之为随机变量的数数学期望学期望。2022-3-21整理ppt随机变量的数学期望（续）随机变量的数学期望（续）l定义（数学期望）设定义（数学期望）设为离散型随机变量，其概率为离散型随机变量，其概率分布为：分布为：l若若 l则称：则称： 2121ppxx1iiix p 1( )iiiEx p为 的数学期望（或均值）2022-3-21整

12、理ppt随机变量的方差随机变量的方差l随机变量的数学期望描述了随机变量一切可能取随机变量的数学期望描述了随机变量一切可能取值的平均水平，而随机变量的值的平均水平，而随机变量的方差方差可以描述随机可以描述随机变量取值与其数学期望值的变量取值与其数学期望值的偏离程度偏离程度。2( )E设设是随机变量，是随机变量，E()是其数学期望，是其数学期望， ( )E则则 表示表示 与与E()之间的偏差大小，但由于绝对值对运算带来得不便，所以常用之间的偏差大小，但由于绝对值对运算带来得不便，所以常用 代替之。又因为代替之。又因为 2( )E仍是一随机变量，则用仍是一随机变量，则用 2( )EE来描述来描述与其

13、与其E()的偏离程度的大小的偏离程度的大小 2022-3-21整理ppt随机变量的方差（续）随机变量的方差（续）l定义（方差）定义（方差） 22( ),( )DEE 设 是一随机变量，若E则称E为随机变量 的方差，记为：( )。2D( )E即： ( )ED( ) 而称( ) 为 的（或），记为方差：标准差均由定义，显然由定义，显然D() 0；当；当的可能取值集中在的可能取值集中在E()附近时，附近时，D()较小；否则较小；否则D()较大。较大。可见，方差大小反映了可见，方差大小反映了与与E()的偏离程度（或取值的分散程的偏离程度（或取值的分散程度）。度）。 2022-3-21整理ppt方差的计

14、算方差的计算 22(1)( )( )( ( )DEE22(2)( )( ),PiiiiDExEppx（ ）=E(其中2022-3-21整理ppt方差的计算（续）方差的计算（续） l例例 设设L表示最长为表示最长为k比特二进制的非负数集合比特二进制的非负数集合0, 1k。现随机的从现随机的从L中取出一个数，证明所取数为中取出一个数，证明所取数为k比特的比特的概率为概率为1/2。 证明：证明：由于由于L最长为最长为k比特，因此非负数集合比特，因此非负数集合L0, 1, 2, , 2k-1。该。该集合可以分为两个不相交的子集合：长度不等于集合可以分为两个不相交的子集合：长度不等于k比特的数的比特的数

15、的集合集合L1和长度等于和长度等于k比特的数的集合比特的数的集合L2： L10, 1, 2, , 2k-1-1 L22k-1, 2k-1+1, 2k-111212122221212|11/2|kkkkiiLP xLp xiLLLL2022-3-21整理ppt第第2 2章章 信息安全数学基础（概率论）信息安全数学基础（概率论）2022-3-21整理ppt概率论中的几个定理概率论中的几个定理l马尔可夫不等式马尔可夫不等式 l契比雪夫不等式契比雪夫不等式 l切比雪夫大数定理切比雪夫大数定理 l贝努里大数定理贝努里大数定理 l辛钦大数定理辛钦大数定理 l两两独立取样两两独立取样 l完全独立取样完全独立

16、取样 l霍弗丁不等式霍弗丁不等式 2022-3-21整理ppt贝努里试验贝努里试验 l定义（贝努里试验）假定一个试验只有两个结果，定义（贝努里试验）假定一个试验只有两个结果，记为记为“成功成功”和和“失败失败”。独立重复的进行该试。独立重复的进行该试验，如果每一次试验有且仅有两种可能的结果，验，如果每一次试验有且仅有两种可能的结果，并且它们的概率在整个试验的过程中是不变的，并且它们的概率在整个试验的过程中是不变的，那么这样的试验被称为贝努里试验。那么这样的试验被称为贝努里试验。l例如，抛掷一枚硬币的试验就属于贝努里试验。例如，抛掷一枚硬币的试验就属于贝努里试验。假设在任何一次试验中：假设在任何

17、一次试验中：P“成功成功”p，P“失失败败”1p那么：那么： Pn次试验中有次试验中有k次为次为“成功成功”l其中，其中， 表示从表示从n件物体中取出件物体中取出k件物品的不同取件物品的不同取法。法。(1)kn knppk nk 2022-3-21整理ppt贝努里试验（续）贝努里试验（续）l如果随机变量取值为 ,并且对每一个p， 有：l那么称 服从贝努里分布贝努里分布。01pn(1) (k=0,1, )kn knnPkppnk n2022-3-21整理ppt马尔可夫不等式马尔可夫不等式 l定理（马尔可夫不等式）令定理（马尔可夫不等式）令X为一非负随机为一非负随机 变量，变量， 为一实数，则有为

18、一实数，则有 ；等价地，；等价地，有有 。l证明：证明：l马尔可夫（马尔可夫（Markov）不等式常用于不了解随机变量的整体）不等式常用于不了解随机变量的整体分布情况，它只要求了解随机变量的期望在它的一个取值分布情况，它只要求了解随机变量的期望在它的一个取值范围内的界。因此，利用马尔可夫不等式，可以得到一个范围内的界。因此，利用马尔可夫不等式，可以得到一个随机变量偏离其均值随机变量偏离其均值“更紧更紧”的界。的界。)(XEXP1)(XEXP() 0 x Xx vx vE Xp Xx xp Xxp Xx vp Xv v2022-3-21整理ppt契比雪夫不等式与大数定理契比雪夫不等式与大数定理

19、2022-3-21整理ppt契比雪夫不等式与大数定理（续）契比雪夫不等式与大数定理（续） 2022-3-21整理ppt契比雪夫不等式与大数定理（续）契比雪夫不等式与大数定理（续） 2022-3-21整理ppt贝努里大数定理贝努里大数定理 2022-3-21整理ppt贝努里大数定理（续）贝努里大数定理（续） 2022-3-21整理ppt两两独立取样两两独立取样 2022-3-21整理ppt两两独立取样两两独立取样 2022-3-21整理ppt完全独立取样完全独立取样 2022-3-21整理ppt霍弗丁不等式霍弗丁不等式 2022-3-21整理ppt第第2 2章章 信息安全数学基础（概率论）信息安

20、全数学基础（概率论）2022-3-21整理ppt密码体制密码体制l定义（密码体制）定义（密码体制）( , , ,)P C K E D密码体制是一个五元组：其中，其中，P表示明文空间，表示明文空间，C表示密文空间，表示密文空间，K表示密钥空间，表示密钥空间，E和和D分别表示加密算法和解密算法。分别表示加密算法和解密算法。 从概率论的角度来看，明文取值代表了随机变量从概率论的角度来看，明文取值代表了随机变量X，密文的，密文的取值代表了随机变量取值代表了随机变量Y，密钥取值代表随机变量，密钥取值代表随机变量K，而，而PX=x，PY=y，PK=k分别表明文空间、密文空间和密分别表明文空间、密文空间和密

21、钥空间所发生的概率。钥空间所发生的概率。 2022-3-21整理ppt密码体制密码体制2022-3-21整理ppt密码体制（续）密码体制（续） :( )|kk x dyP Yy XxP Kk :( ) :( )| ( )kk x dykk y C kp XxP KkP Xx YyP Kk P xdy2022-3-21整理ppt密码体制（续）密码体制（续）2022-3-21整理ppt密码体制（续）密码体制（续）1212,12122 ( ) (2) (2) 1/2 3/41/4 1/47/16kkk kkkP YP Kk P xdyP Kk P xdP Kk P xdP Kk P xbP Kk P

22、 xa2022-3-21整理ppt密码体制的完善保密性密码体制的完善保密性l（密码体制的完善保密性）对于密码体制（密码体制的完善保密性）对于密码体制 ，如果对于如果对于 ，有：，有： ，则称该密码，则称该密码体制具有完善保密性。体制具有完善保密性。l依据上述定义，如果一个密码体制具有完善保密依据上述定义，如果一个密码体制具有完善保密性，则对于给定密文性，则对于给定密文y，明文为，明文为x的后验概率等于的后验概率等于明文明文x的先验概率。的先验概率。( , , ,)P C K E D,xP yC | P x yP x2022-3-21整理ppt密码体制的完善保密性（续）密码体制的完善保密性（续）

23、26262626126 ( ) = ()(mod26) =()(mod26)1 =()(mod26)26kk Zk Zk Zk ZP YyP Kk P XdyP Kk P XykP XykP Xyk2022-3-21整理ppt密码体制的完善保密性（续）密码体制的完善保密性（续）26261()(mod26)261 =261 =1261 =26k Zk ZP YyP XykP Xx2022-3-21整理ppt密码体制的完善保密性（续）密码体制的完善保密性（续）261 | ()(mod26)=26k ZP y xP Kyx2022-3-21整理ppt密码体制的完善保密性（续）密码体制的完善保密性（续

24、） | | 1 26 =126 = P x P Y xP x yP yP xP x所以移位密码具有完善保密性。 2022-3-21整理ppt生日悖论问题（续）生日悖论问题（续）2022-3-21整理ppt生日悖论问题（续）生日悖论问题（续）2022-3-21整理ppt生日悖论问题（续）生日悖论问题（续）12121.111kkP KkPPPnnn2022-3-21整理ppt生日悖论问题（续）生日悖论问题（续）/1(1)nxx nxxeenn或11/11(1)21211111kki niik knkP Kknnniene(1)211k knP Kke 2022-3-21整理ppt生日悖论问题（续）

25、生日悖论问题（续）(1)22112 log112 log1k knekknkn 2022-3-21整理ppt生日悖论问题（续）生日悖论问题（续）l从计算复杂性来看，发生碰撞的计算次数的复杂度为从计算复杂性来看，发生碰撞的计算次数的复杂度为O( )，即对于一个输出空间大小为即对于一个输出空间大小为n的随机函数，只需计算大约的随机函数，只需计算大约 个函数值，就可以以一个不可忽略的概率发现一个碰撞：对个函数值，就可以以一个不可忽略的概率发现一个碰撞：对于两个不同的随机函数输入，其输出相同。于两个不同的随机函数输入，其输出相同。l这个结论对于密码系统与密码协议的设计有着深刻影响。这个结论对于密码系统与密码协议的设计有着深刻影响。l例如：当用随机函数来隐藏一组秘密信息，如果这个随机函例如：当用随机函数