《信息安全》：数学基础思维导图

主要介绍了信息安全中的数学基础知识，详细内容可打开大图查看。

《信息安全》——数学基础

• 概率问题与概率论基本公式
  • 提出问题
    • 概率模型一
      • 盒子里有n个球，球的颜色都不一样。
      • 从盒子里取出一个球来，放回去。
      • 连续取k次。
      • 问去到相同颜色球的概率是多少？
    • 概率模型二
      • 把k封信扔进n个信箱
      • 求有信箱出现两封信的概率
  • 解决问题
    • 用A表示取到颜色相同的球的事件
    • 用Ã表示取到的球都是颜色不同的事件
    • 则
    • 且：
  • 结合公式
    • 当x足够小或者n充分大时，有估计式：
    • 所以：
    • 解释
      • 这里的x指抽取次数，n指物品的数量
      • 推导过程
  • 得出结论
    • 结论一
      • 连续取球k次
      • 取到相同颜色球的概率是
    • 结论二
      • 给定概率ε
      • 连续取多少次才能使颜色相同的球出现的概率达到ε
      • 答案是：
  • 实际意义
    • 即考虑在一个大的集体中
      • 抽取到两个个体有一个属性相同的概率是多少
    • 例子
      • k个人中有人生日相同的概率是
  • 抽象总结
    • 问题抽象
      • 把这些现象归纳为一个函数
      • 设函数；f:X→Y；对集合x上k个不同点：即
      • 有k个函数值：
      • 问：出现重复取值的概率有多大？
    • 分析
      • 设事件A表示存在：
      • 求：P(A)？
      • 从信息安全的角度，会问：k个函数值，以多大的概率发生碰撞
  • 问题扩展
    • 提出问题
      • 假设球来自甲乙两组，在k次摸球中，事件A表示颜色相同的球来自同一个组的概率
      • 即在一个大集体中
        • 抽取到两个个体有两个相同属性的概率是多少
    • 分析问题
      • 每个个体对应一个唯一的二元组别（a,b）
      • n个球中二元组别有2n个
      • 基本事件的个数是(2n)^k个
      • 事件Ã的概率
      • 计算得出事件A的概率
  • 概率论基本知识
    • 联合概率
    • 条件概率
    • 关系
    • 贝叶斯公式
    • 独立随机变量
    • 全概率公式
      • 如果事件 A1，A2，A3...An 满足：
      • 则对于任一事件A，
• 密码系统中的概率分布问题
  • 模型建立
    • 设有密码系统：(P,C,K,E,D)
      • P是明文空间
      • C是密文空间
      • K是密钥空间
      • E、D是什么？
    • 假定已经有明文空间和密钥空间的概率分布：
    • 我们可以导出密文空间的概率分布：
      • 对固定的密钥k属于K，令
      • 令
      • 密文y的产生当且仅当密钥k和明文x相互作用产生，这个明文x满足x=d_k(y)
      • • • 密钥空间和明文空间必须是独立地
      • 公式解释
  • 情况分析
    • 已知明文的概率分布，求密文的概率分布p(y|x)
      • 分析
        • 给定了一个明文
        • 用不同的密钥加密会得到不同的密文
        • 因此要给出一个特定密文的概率是多少时
        • 只需给出这个密文对应的密钥即可
      • 结论
    • 已知密文的概率分布，求明文的概率分布p(x|y)
      • 分析
        • 我们已经知道了p(y)和p(y|x)的概率分布
        • 可以直接计算出p(x|y)
      • 结论
  • 实际例子
    • 设定
      • 假设明文空间P={a,b}
        • 概率分布为
          • p(a)=1/4
          • p(b)=3/4
      • 密钥空间K={k1,k2,k3}
        • 概率分布为
          • p(k1)=1/2
          • p(k2)=1/4
          • p(k3)=1/4
      • 设密文空间C={1,2,3,4}
      • 加密算法为
    • 问题
      • 求密文概率分布
      • 已知明文求密文的概率分布
      • 已知密文求明文的概率分布
• 完善保密系统
  • 定义
    • 设(P,C,K,E,D)是一个密码系统
    • 若
      • 注意：
    • 则称为完善的保密系统
    • 即明文不会给密文提供任何信息，反之亦然
  • 例子
    • 系统模型
      • 移位密码系统
      • P=C=K={0,1,2,...25}
      • • 这里给出加密算法
      • • 这里给出密钥空间
      • 对于所有的k，有：
        • 这里给出密文空间
    • 系统性质
      • 密文的概率分布
        • 分析
          • 对于任意一个
          • 有且只有一个满足
          • 即
            • 只要确定了y和k
            • x就确定了
        • 结果
          • 自己推导的
          • 课程推导的
            • • 不懂
      • 已知明文求密文概率分布
        • 分析
          • 由于给定x
          • 再确定k就可以得到一个唯一的y
          • 故y的概率分布应该等于k的概率分布
        • 结果
          • • 故p(y|x)=p(y)
      • 已知密文的明文概率分布
        • 分析
          • 前面已经知道了p(y|x)和p(y)的值
          • 可以直接计算p(x|y)
        • 结果
  • 定理
    • 阐述
      • 设
        • 是一个加密系统
      • 满足：
      • 则Ω是一个完善的保密系统当且仅当：
    • 证明
      • 正向证明
        • 假设Ω是一个完善的保密系统
        • 则
        • 上式说明对任意的x属于P，y属于C，必定存在至少一个密钥k
        • 我的理解
          • 也就是能够将x加密成y的密钥k存在的概率加起来等于y的概率
          • 所以k必定存在
        • 其次，这个式子固定y，改变x
        • k也必须改变
        • 因为
          • 意思就是对于同一个k，不可能把两个不同的x加密为同一个y
          • 所以固定y变动x，k必须变动
          • 但这是哪来的条件？？？
        • 当x跑遍P时，k也就跑遍K
        • 因此固定y，每一个x对应唯一一个k
        • 所以所有的k的概率是相等的
        • 故结论成立
      • 反向证明
        • 假设密码系统满足：
        • 此时固定y
        • 由于k=1/|K|
        • 故可以确定x与k是一一对应的关系
          • 即
        • 故：