---密码学基础(古典密码 素材)ppt课件

1 古典密码算法2015 6 9 2 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 3 当今的信息网络蕴含了表现为信息形式的多种巨大利益政治的 军事的 经济的 商业的 通过网络非法获取和利用信息可能随时发生互联网的开放性是根源网络安全已成为网络设计 建设和维护的重要内容密码学 密码算法成为保护网络信息的利器以数学为工具 将信息明文变换为密文成为保护信息的核心屏障 网络与密码算法 4 密码学的目的合法通信双方Alice和Bob在不安全的信道上进行安全通信 而破译者Oscar不能理解他们通信的内容 安全 指机密性 完整性 鉴别 不可抵赖简单加密系统模型 简单加密系统模型 5 密码系统包含带参数K的变换EK 带参数K的逆变换DK 信息传送信道 密钥传送信道变换EK得将明文消息P变换为密文C 这个过程称为加密E为加密算法 K为密钥 E不同或K不同 密文C就不同典型的密码系统 密码系统 6 对密码算法的基本要求加密能力强当密文或明文 密文对被截获时 破解密钥或明文在计算上是不可行的安全性不依赖于密码算法本身的保密 而依赖于密钥易于实现 使用方便 对密码算法的基本要求 7 古典密码 ClassicalCryptography 密码算法针对的基本操作对象是字符 字母方法 字符代换 Substitution 或字符置换 Permutation 1949年之前此类密码学还不是科学 而是艺术产生了一些密码算法和加密设备也出现简单的密码分析手段 古典密码 8 古典密码分类 代换Substitution 置换Transposition 单表代换Monoalphabetic 多表代换Polyalphabetic 单字符单表代换 多字符单表代换 移位密码 单表密码 短语单表密码 Playfair密码 Beaufort密码 Vigen re密码 行变换密码 栅格密码 Hill密码 仿射密码 Autokey密码 转子机 凯撒密码 一次性密码 9 代换与置换 代换密码算法 SubstitutionCipher 将明文中的每一个字符均被替换成另一个字符 密文字符 接收者对密文做反向替换就可以恢复出明文置换密码算法 PermutationCipher 又称换位密码算法 TranspositionCipher 改变明文中各个字母的位置次序 但明文字母 的出现及出现次数 保持不变 10 代替密码 单表密码算法 MonoalphabeticCipher 密码表仅1个 固定任何明文加密 密文解密均使用同一个密码表加密明文中相同的字母必然被加密成相同的密文字母 11 代替密码 多表密码算法 PolyalphabeticCipher 密码表多个 不固定一条明文加密和解密同时使用多个密码表明文中两个相同的字母可能被加密成不同的密文字母 12 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 13 凯撒密码 恺撒密码 CaesarCipher JuliusCaesar发明 是已知最早的代换密码明文字母用其后的第三个字母代替 作为其密文字母 即 将明文字母表循环左移三位作为密码表 14 两个字母表明文字母表P p0 p1 p25 密文字母表C C0 C1 C25 基本型凯撒密码等于如下变换明文字母表密文字母表明文表和密文表共同构成密钥加密解密 凯撒密码 15 让每个字母对应一个数值则基本型凯撒密码可以表示为加密 Ci E pi pi 3 mod26解密 pi D Ci Ci 3 mod26密钥数量 1 凯撒密码 16 凯撒密码 凯撒密码实例明文 meetmeaftertheparty密文 PHHWPHDIWHUWKHSDUWB 17 凯撒密码 特点极为简单密钥数为1 极其脆弱 18 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 19 移位密码 ShiftCipher 明文字母用其后的第k个字母代替 作为其密文字母 即 将明文字母表循环左移k位作为密码表明文字母用任一个密文字母代替 即 明文字母表的任一个排列均构成一个对应的密码表加密 Ci E pi pi k mod26解密 pi D Ci Ci k mod26 移位密码 20 移位密码 移位密码 21 例如 k 5明文字母表 密文字母表 密钥数量 25 明文 密文 移位密码 22 特点非常简单密钥数为25 仍非常脆弱 移位密码 23 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 24 单表密码 MonoalphabeticCipher 明文字母用任一个密文字母代替 即 明文字母表的任一个全排列均构成一个对应的密码表加密 Ci E pi pi ki mod26解密 pi D Ci Ci ki mod26当pi pj有Ci Cj ki kj 0 1 2 25例 明文字母表 密文字母表 ki 13172124 单表密码 25 密钥数量 26 403 291 461 126 605 635 584 000 000 4 1026 400亿亿亿特点密钥数极大 安全性好密钥无规律 使用不便 单表密码 26 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 27 短语密码 短语密码 KeywordCipher 是单表密码的一种实用形式引入一个关键词 短语 来构造明文字母表的一个排列 从而构成对应的密码表密码表构造方法1指定一个关键词 词组 句子 去除关键词中的重复字母和空格 前置于密码表将剩余的字母依次按序后置于密码表密钥数量 26 4 1026 400亿亿亿 28 实例关键词 GUANGZHOUBAIYUNSHAN去重前置 GUANZHOBIYS剩余后置 TVWXCDEFJKLMPQR明文字母表 密文字母表 短语密码 29 短语密码密码表构造方法2指定一个关键词 去重复 空格 按行排阵将剩余的字母依次继续按行排阵阵的各列构成密码表例 关键词 COLLEGE阵 明文字母表密文字母表 短语密码 30 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 31 仿射密码 仿射密码 AffineCipher 用仿射变换构造密码表 密码表便于记忆 密码表两个字母表明文字母表P p0 p1 pn 1 密文字母表C C0 C1 Cn 1 引入两个参数 使明文字母P用字母aP b代替 作为其密文字母加密 Ci E pi pi modn解密 pi D Ci 1 Ci modn 32 仿射密码 实例取参数 5 8明文 AFFINECIPHER密文 IHHWVCSWFRCP 33 仿射密码 提示仿射加密函数要求 和n互素 即gcd n 1 否则 pi modn就不是一个单射函数当 1 3时 仿射密码就是著名的凯撒密码在解密时 需求解 在有限域Zn上的乘法逆元 1 Zn 这可由扩展欧几里得算法求解Z26上所有与26互素的元素的乘法逆元 34 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 35 对单表代换密码的攻击 两种典型的攻击直接攻击文本方法 频度分析直接攻击密钥方法 暴力破解 穷举破解 两种攻击联合使用或单独使用可一举破解单表代换密码 36 直接攻击文本 频度分析9世纪阿尔 金迪 关于破译加密信息的手稿 西文语言的独到特征文章中字母的出现频度有统计规律 元音字母频度高 对单表代换密码的攻击 37 频度分析的步骤统计密码字母的频度排序按照已知频度分布替换密文字母 对单表代换密码的攻击 38 密文频度分析h 可能是e a i o 尝试h e d a l i r o 结果密文 明文 频度分析攻击 实例 39 直接攻击密钥 暴力破解前提 已知采用的是代换密码暴力破解的要点尝试所有可能的密码表 移位密码 最多仅需尝试25次 暴力破解的步骤选择一个密码表作逆代换检查逆代换后的文本是否有意义 有则结束 否则换另一个密码表 进入步骤2 对单表代换密码的攻击 40 实例 密文 明文 对单表代换密码的攻击 41 本质选取字母表的一个全排列作为对称密钥密钥数量26 4 1026 单表代换密码 小结 42 提纲 概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结 43 特征代换固定 明文字符的代换字符固定位置相同 密文字符与明文字符的位置相同优点简单 得到密文所需的计算量小缺点继承 密文继承了明文的统计特性 频率 跟随 明文字符的跟随关系反映在密文中 单字符代换算法 小结 44 存在多种不同的破解途径攻击密文 频度分析攻击密钥 穷举密钥 改进思路 多角度同时抵御针对频度分析 使频度呈现 均匀分布 针对穷举密钥 增大密钥空间 如何做到 代换密码算法 如何改进 45 如何解密用短语代换密码的密文 如何代换密码加密中文 对于本次给出的四种代换密码 指出它们是沿着什么思路改进的 进阶问题 46 生成26个字母表的一个全排列 画出计算机程序的流程图 生成短语代换密码的一个密码表 画出计算机程序的流程图 画出用短语代换密码加密明文和解密密文的计算机程序流程图 选取一个代换密码 利用邮件 微博或微信与你的朋友进行一次秘密通信 请一位第三方同学尝试破解密文 根据破