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

电子科技大学计算机科学与工程学院计算系统与网络平安

ComputerSystemandNetworkSecurity2023/7/13概率论根底子曰：君子不重那么不威；学那么不固；主忠信；无友不如己者；过那么勿惮改。君子要厚重，不厚重就没有威严，所学的东西也不会巩固；在与人相处中要以忠信为主；不能与德才不如自己的人做朋友；如果有了过失或错误不要害怕改正。〞重言，重行，重貌，重好〔言重那么有法，行重那么有德，貌重那么有威，好重那么有观〕学者言行貌好皆须学其庄重2023/7/13总结网络与信息平安中的概率论方法概率论中的几个定理随机变量及其分布第2章信息平安数学根底〔概率论〕概率论根底2023/7/13总结网络与信息平安中的概率论方法概率论中的几个定理随机变量及其分布第2章信息平安数学根底〔概率论〕概率论根底2023/7/13概率论根底进行一次试验，如果所得结果不能完全预知，但其全体的可能结果是的，那么称此试验为随机试验。随机试验的每一个可能的结果称为一个样本〔或样本点〕，因而一个随机试验的所有样本点也是确定的。随机试验的全体称为样本空间。习惯上，分别用ω与Ω表示样本与样本空间。2023/7/13概率论根底〔续〕定义〔概率的经典定义〕假设一个实验可以从样本空间Ω中等概率产生一个样本。假设随机事件A包含了m个样本，那么量m/n称为事件A在n次试验中发生的概率，记作P[A]，即：P[A]=m/n2023/7/13概率论根底〔续〕定义〔概率的统计定义〕相同条件下重复进行的n次试验中,事件A发生的频率稳定地在某一常数p附近摆动,且随n越大摆动幅度越小,那么称p为事件A的概率,记作P[A]。即：P[A]=p2023/7/13概率论根底〔续〕设A、B为两事件，P[A]>0，把事件A发生的条件下事件B发生的概率称之为条件概率，记为：2023/7/13概率论根底〔续〕定理〔全概率公式〕如果，且那么对Ω中任一事件B，有：2023/7/13概率论根底〔续〕定理〔贝叶斯定理〕如果，那么：贝叶斯定理说明了在x是y的概率的条件下，求y是x的概率。2023/7/13总结网络与信息平安中的概率论方法概率论中的几个定理随机变量及其分布第2章信息平安数学根底〔概率论〕概率论根底2023/7/13随机变量及其分布一般地，如果为某个随机事件，那么对于某次试验，要么发生，要么不发生，因此试验结果总可以用以下示性函数来表示：这就说明，不管随机试验的结果是否具有数量的性质，都可以建立一个样本空间和实数空间的对应关系，从而使得随机试验与数值发生联系，以便更好地研究随机试验的结果。为此，引入了随机变量的概念。2023/7/13随机变量及其分布〔续〕定义〔随机变量〕设随机试验E的样本空间为，是定义在上的单值函数，假设对于任意实为随机变量〔RandomVariable〕。数集合是随机事件，那么称2023/7/13随机实验举例例：随机试验E：从一个装有编号为0，1，2，…，9的球的袋中任意摸一球。那么其样本空间:={，，…，}

其中“摸到编号为的球”，=0,1,…,9.定义函数：，即()=，=0，1，…，9。2023/7/13随机变量及其分布定义〔分布函数〕=P{x}为的分布函数。设是上的随机变量，对xR，称：2023/7/13随机变量及其分布〔续〕离散型随机变量的分布函数F(X)定义为：因此ξ的分布列也完全刻画了离散型随机变量取值的规律。这样，对于离散型随机变量，只要知道它的一切可能取值和取这些值的概率，也就是说知道了它的分布，也就掌握了这个离散型随机变量的统计规律。2023/7/13常见的离散型分布退化分布〔单点分布〕：贝努里分布〔两点分布，0-1分布〕：2023/7/13常见的离散型分布〔续〕二项分布〔贝努里分布〕：泊松〔Poisson〕分布：2023/7/13随机变量的数学期望离散型随机变量的分布只能描述其概率特征，无法反映出其变化情况，而随机变量的某种平均值却可以更好地描述随机变量的变化。随机变量所有取值的平均值称之为随机变量的数学期望。2023/7/13随机变量的数学期望〔续〕定义〔数学期望〕设ξ为离散型随机变量，其概率分布为：假设那么称：2023/7/13随机变量的方差随机变量的数学期望描述了随机变量一切可能取值的平均水平，而随机变量的方差可以描述随机变量取值与其数学期望值的偏离程度。设是随机变量，E()是其数学期望，

则

表示

与E()之间的偏差大小，但由于绝对值对运算带来得不便，所以常用

代替之。又因为

仍是一随机变量，则用

来描述ξ与其E(ξ)的偏离程度的大小

2023/7/13随机变量的方差〔续〕定义〔方差〕由定义，显然D(ξ)≥0；当ξ的可能取值集中在E(ξ)附近时，D(ξ)较小；否那么D(ξ)较大。可见，方差大小反映了ξ与E(ξ)的偏离程度〔或取值的分散程度〕。2023/7/13方差的计算

2023/7/13方差的计算〔续〕例

设L表示最长为k比特二进制的非负数集合{0,1}k。现随机的从L中取出一个数，证明所取数为k比特的概率为1/2。

证明：由于L最长为k比特，因此非负数集合L＝{0,1,2,…,2k-1}。该集合可以分为两个不相交的子集合：长度不等于k比特的数的集合L1和长度等于k比特的数的集合L2：L1＝{0,1,2,…,2k-1-1}L2＝{2k-1,2k-1+1,…2k-1}2023/7/13总结网络与信息平安中的概率论方法概率论中的几个定理随机变量及其分布第2章信息平安数学根底〔概率论〕概率论根底2023/7/13概率论中的几个定理马尔可夫不等式契比雪夫不等式切比雪夫大数定理贝努里大数定理辛钦大数定理两两独立取样完全独立取样霍弗丁不等式2023/7/13贝努里试验

定义〔贝努里试验〕假定一个试验只有两个结果，记为“成功〞和“失败〞。独立重复的进行该试验，如果每一次试验有且仅有两种可能的结果，并且它们的概率在整个试验的过程中是不变的，那么这样的试验被称为贝努里试验。例如，抛掷一枚硬币的试验就属于贝努里试验。假设在任何一次试验中：P[“成功〞]＝p，P[“失败〞]＝1－p那么：P[n次试验中有k次为“成功〞]＝其中，表示从n件物体中取出k件物品的不同取法。2023/7/13贝努里试验〔续〕如果随机变量取值为,并且对每一个p，

有：那么称服从贝努里分布。2023/7/13马尔可夫不等式定理〔马尔可夫不等式〕令X为一非负随机变量，为一实数，那么有；等价地，有。证明：马尔可夫〔Markov〕不等式常用于不了解随机变量的整体分布情况，它只要求了解随机变量的期望在它的一个取值范围内的界。因此，利用马尔可夫不等式，可以得到一个随机变量偏离其均值“更紧〞的界。2023/7/13契比雪夫不等式与大数定理

2023/7/13契比雪夫不等式与大数定理〔续〕2023/7/13契比雪夫不等式与大数定理〔续〕2023/7/13贝努里大数定理

2023/7/13贝努里大数定理〔续〕2023/7/13两两独立取样

2023/7/13两两独立取样2023/7/13完全独立取样

2023/7/13霍弗丁不等式

2023/7/13总结网络与信息平安中的概率论方法概率论中的几个定理随机变量及其分布第2章信息平安数学根底〔概率论〕概率论根底2023/7/13密码体制定义〔密码体制〕其中，P表示明文空间，C表示密文空间，K表示密钥空间，E和D分别表示加密算法和解密算法。从概率论的角度来看，明文取值代表了随机变量X，密文的取值代表了随机变量Y，密钥取值代表随机变量K，而P[X=x]，P[Y=y]，P[K=k]分别说明文空间、密文空间和密钥空间所发生的概率。2023/7/13密码体制2023/7/13密码体制〔续〕2023/7/13密码体制〔续〕2023/7/13密码体制〔续〕2023/7/13密码体制的完善保密性〔密码体制的完善保密性〕对于密码体制，如果对于，有：，那么称该密码体制具有完善保密性。依据上述定义，如果一个密码体制具有完善保密性，那么对于给定密文y，明文为x的后验概率等于明文x的先验概率。2023/7/13密码体制的完善保密性〔续〕2023/7/13密码体制的完善保密性〔续〕2023/7/13密码体制的完善保密性〔续〕2023/7/13密码体制的完善保密性〔续〕所以移位密码具有完善保密性。

2023/7/13生日悖论问题〔续〕2023/7/13生日悖论问题〔续〕2023/7/13生日悖论问题〔续〕2023/7/13生日悖论问题〔续〕2023/7/13生日悖论问题〔续〕2023/7/13生日悖论问题〔续〕从计算复杂性来看，发生碰撞的计算次数的复杂度为O()，即对于一个输出空间大小为n的随机函数，只需计算大约个函数值，就可以以一个不可忽略的概率发现一个碰撞：对于两个不同的随机函数输入，其输出相同。这个结论对于密码系统与密码协议的设计有着深刻影响。例如：当用随机函数来隐藏一组秘密信息，如果这个随机函数的输出空间不够大，就可以通过随机的计算这个随机函数的函数值来找出这组秘密信息中的一局部。这种攻击被称为平方根攻击或者生日攻击。输出空间的大小n在密码学中是非常重要的平安因素，通常称之为平安参数。2023/7/13总结网络与信息平安中的概率论方法概率论中的几个定理随机变量及其分布第2章信息平安数学根底〔概率论〕概率论根底2023/7/13参考书参考书杨义先等，信息平安理论与技术，邮电出版社MaoWenbo，ModernCryptography:TheoryandPractice

，电子工业出版社，2004BruceSchneier,AppliedCryptography,Protocols,algorithms,andsourcecodeinC(2ndEdition)(应用密码学－协议、算法与C源