计算系统与网络安全PPT教学课件-第2章_信息安全数学基础(概率论).ppt

2019/10/30,电子科技大学 计算机科学与工程学院,计算系统与网络安全 computer system and network security,2019/10/30,概率论基础,子曰：君子不重则不威；学则不固；主忠信；无友不如己者；过则勿惮改。 君子要厚重，不厚重就没有威严，所学的东西也不会坚固；在与人相处中要以忠信为主；不能与德才不如自己的人做朋友；如果有了过失或错误不要害怕改正。” 重言，重行，重貌，重好 （言重则有法，行重则有德，貌重则有威，好重则有观 ） 学者言行貌好皆须学其庄重,2019/10/30,总结,网络与信息安全中的概率论方法,概率论中的几个定理,随机变量及其分布,第2章 信息安全数学基础（概率论）,概率论基础,2019/10/30,总结,网络与信息安全中的概率论方法,概率论中的几个定理,随机变量及其分布,第2章 信息安全数学基础（概率论）,概率论基础,2019/10/30,概率论基础,进行一次试验，如果所得结果不能完全预知，但其全体的可能结果是已知的，则称此试验为随机试验。 随机试验的每一个可能的结果称为一个样本（或样本点），因而一个随机试验的所有样本点也是确定的。随机试验的全体称为样本空间。 习惯上，分别用与表示样本与样本空间。,2019/10/30,概率论基础（续）,对于随机试验，常常关心样本空间的某些部分（及一个或多个眼本）是否出现，称这种由部分样本组成的试验结果为随机事件，简称事件，通常用大写的字母a，b，表示。,2019/10/30,概率论基础（续）,“事件a与b都发生”这一事件称作事件a与b的交，记作ab或(ab) “事件a与b至少有一个发生”这一事件称作事件a与b的并，记作ab “事件a发生而b不发生”这一事件称作事件a与b的差, 记作 a-b 事件a不发生”这一事件称作事件a的对立事件，记作,2019/10/30,概率论基础（续）,定义（概率的经典定义）假设一个实验可以从样本空间中等概率产生一个样本。若随机事件a包含了m个样本，则量m/n称为事件a在n次试验中发生的概率，记作p a，即： pa=m/n,2019/10/30,概率论基础（续）,定义（概率的统计定义）相同条件下重复进行的n次试验中, 事件a发生的频率稳定地在某一常数p附近摆动, 且随n越大摆动幅度越小, 则称p为事件a的概率, 记作pa。 即： pa=p,2019/10/30,概率论基础（续）,设a、b为两事件，p a 0，把事件a发生的条件下事件b发生的概率称之为条件概率，记为：,2019/10/30,概率论基础（续）,定理（全概率公式）,如果,，且,则对中任一事件b，有：,2019/10/30,概率论基础（续）,定理（贝叶斯定理）,如果,，,那么：,贝叶斯定理说明了在已知x是y的概率的条件下，求已知y是x的概率。,2019/10/30,总结,网络与信息安全中的概率论方法,概率论中的几个定理,随机变量及其分布,第2章 信息安全数学基础（概率论）,概率论基础,2019/10/30,随机变量及其分布,一般地，如果为某个随机事件，则对于某次试验，要么发生，要么不发生，因此试验结果总可以用以下示性函数来表示： 这就说明，不管随机试验的结果是否具有数量的性质，都可以建立一个样本空间和实数空间的对应关系，从而使得随机试验与数值发生联系，以便更好地研究随机试验的结果。 为此，引入了随机变量的概念。,2019/10/30,随机变量及其分布（续）,定义（随机变量）,设随机试验e的样本空间为 ，,是定义在 上的单值函数，若对于任意实,为随机变量（random variable）。,数 集合 是随机事件，则称,2019/10/30,随机实验举例,例：随机试验e：从一个装有编号为0，1，2，9的球的袋中任意摸一球。则其样本空间 :,2019/10/30,随机变量及其分布,定义（分布函数）,2019/10/30,随机变量及其分布（续）,离散型随机变量的分布函数f(x)定义为 ：,因此的分布列也完全刻画了离散型随机变量取值的规律。这样，对于离散型随机变量，只要知道它的一切可能取值和取这些值的概率，也就是说知道了它的分布，也就掌握了这个离散型随机变量的统计规律。,2019/10/30,常见的离散型分布,退化分布（单点分布）： 贝努里分布（两点分布，0-1分布）：,2019/10/30,常见的离散型分布（续）,二项分布（贝努里分布）： 泊松（poisson）分布：,2019/10/30,随机变量的数学期望,离散型随机变量的分布只能描述其概率特征，无法反映出其变化情况，而随机变量的某种平均值却可以更好地描述随机变量的变化。 随机变量所有取值的平均值称之为随机变量的数学期望。,2019/10/30,随机变量的数学期望（续）,定义（数学期望）设为离散型随机变量，其概率分布为： 若 则称：,2019/10/30,随机变量的方差,随机变量的数学期望描述了随机变量一切可能取值的平均水平，而随机变量的方差可以描述随机变量取值与其数学期望值的偏离程度。,2019/10/30,随机变量的方差（续）,定义（方差）,由定义，显然d() 0；当的可能取值集中在e()附近时，d()较小；否则d()较大。 可见，方差大小反映了与e()的偏离程度（或取值的分散程度）。,2019/10/30,方差的计算,2019/10/30,方差的计算（续）,例 设l表示最长为k比特二进制的非负数集合0, 1k。现随机的从l中取出一个数，证明所取数为k比特的概率为1/2。,证明： 由于l最长为k比特，因此非负数集合l0, 1, 2, , 2k-1。该集合可以分为两个不相交的子集合：长度不等于k比特的数的集合l1和长度等于k比特的数的集合l2： l10, 1, 2, , 2k-1-1 l22k-1, 2k-1+1, 2k-1,2019/10/30,总结,网络与信息安全中的概率论方法,概率论中的几个定理,随机变量及其分布,第2章 信息安全数学基础（概率论）,概率论基础,2019/10/30,概率论中的几个定理,马尔可夫不等式 契比雪夫不等式 切比雪夫大数定理 贝努里大数定理 辛钦大数定理 两两独立取样 完全独立取样 霍弗丁不等式,2019/10/30,贝努里试验,定义（贝努里试验）假定一个试验只有两个结果，记为“成功”和“失败”。独立重复的进行该试验，如果每一次试验有且仅有两种可能的结果，并且它们的概率在整个试验的过程中是不变的，那么这样的试验被称为贝努里试验。 例如，抛掷一枚硬币的试验就属于贝努里试验。假设在任何一次试验中：p“成功”p，p“失败”1p 那么： pn次试验中有k次为“成功” 其中， 表示从n件物体中取出k件物品的不同取法。,2019/10/30,贝努里试验（续）,如果随机变量取值为 ,并且对每一个p， 有： 那么称 服从贝努里分布。,2019/10/30,马尔可夫不等式,定理（马尔可夫不等式）令x为一非负随机 变量， 为一实数，则有 ；等价地，有 。 证明： 马尔可夫（markov）不等式常用于不了解随机变量的整体分布情况，它只要求了解随机变量的期望在它的一个取值范围内的界。因此，利用马尔可夫不等式，可以得到一个随机变量偏离其均值“更紧”的界。,2019/10/30,契比雪夫不等式与大数定理,2019/10/30,契比雪夫不等式与大数定理（续）,2019/10/30,契比雪夫不等式与大数定理（续）,2019/10/30,贝努里大数定理,2019/10/30,贝努里大数定理（续）,2019/10/30,两两独立取样,2019/10/30,两两独立取样,2019/10/30,完全独立取样,2019/10/30,霍弗丁不等式,2019/10/30,总结,网络与信息安全中的概率论方法,概率论中的几个定理,随机变量及其分布,第2章 信息安全数学基础（概率论）,概率论基础,2019/10/30,密码体制,定义（密码体制）,其中，p表示明文空间，c表示密文空间，k表示密钥空间，e和d分别表示加密算法和解密算法。,从概率论的角度来看，明文取值代表了随机变量x，密文的取值代表了随机变量y，密钥取值代表随机变量k，而px=x，py=y，pk=k分别表明文空间、密文空间和密钥空间所发生的概率。,2019/10/30,密码体制,2019/10/30,密码体制（续）,2019/10/30,密码体制（续）,2019/10/30,密码体制（续）,2019/10/30,密码体制的完善保密性,（密码体制的完善保密性）对于密码体制 ，如果对于 ，有： ，则称该密码体制具有完善保密性。 依据上述定义，如果一个密码体制具有完善保密性，则对于给定密文y，明文为x的后验概率等于明文x的先验概率。,2019/10/30,密码体制的完善保密性（续）,2019/10/30,密码体制的完善保密性（续）,2019/10/30,密码体制的完善保密性（续）,2019/10/30,密码体制的完善保密性（续）,所以移位密码具有完善保密性。,2019/10/30,生日悖论问题（续）,2019/10/30,生日悖论问题（续）,2019/10/30,生日悖论问题（续）,2019/10/30,生日悖论问题（续）,2019/10/30,生日悖论问题（续）,2019/10/30,生日悖论问题（续）,从计算复杂性来看，发生碰撞的计算次数的复杂度为o( )，即对于一个输出空间大小为n的随机函数，只需计算大约 个函数值，就可以以一个不可忽略的概率发现一个碰撞：对于两个不同的随机函数输入，其输出相同。 这个结论对于密码系统与密码协议的设计有着深刻影响。 例如：当用随机函数来隐藏一组秘密信息，如果这个随机函数的输出空间不够大，就可以通过随机的计算这个随机函数的函数值来找出这组秘密信息中的一部分。这种攻击被称为平方根攻击或者生日攻击。 输出空间的大小n在密码学中是非常重要的安全因素，通常称之为安全参数。,2019/10/30,总结,网络与信息安全中的概率论方法,概率论中的几个定理,随机变量及其分布,第2章 信息安全数学基础（概率论）,概率论基础,2019/10/30,参考书,参考书 杨义先等，信息安全理论与技术，邮电出版社 mao wenbo， modern cryptography: theory and practice ， 电子工业出版社，2004 bruce schneier, applied cryptography, protocols, algorithms, and source code in c (2nd edition)( 应用密码学 协议、算法与c源程序， 吴世