密码学基础(古典密码 素材).ppt

1、BG,1,古典密码算法 2015-6-9,BG,2,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,3,当今的信息网络蕴含了表现为信息形式的多种巨大利益 政治的、军事的、经济的、商业的 通过网络非法获取和利用信息可能随时发生 互联网的开放性是根源 网络安全已成为网络设计、建设和维护的重要内容 密码学/密码算法成为保护网络信息的利器 以数学为工具，将信息明文变换为密文 成为保护信息的核心屏障,网络与密码算法,BG,4,密码学的目的 合法通信双方Alice和Bob在不安全的信道上进行安全通信，而破译者Oscar不能理解他们通信的内

2、容 “安全”指机密性、完整性、鉴别、不可抵赖 简单加密系统模型,简单加密系统模型,BG,5,密码系统 包含带参数 K 的变换EK() 、带参数 K 的逆变换DK() 、信息传送信道、密钥传送信道 变换EK得将明文消息P变换为密文C，这个过程称为加密 E为加密算法，K为密钥。E不同或K不同，密文C就不同 典型的密码系统,密码系统,BG,6,对密码算法的基本要求 加密能力强 当密文或明文密文对被截获时，破解密钥或明文在计算上是不可行的 安全性不依赖于密码算法本身的保密，而依赖于密钥 易于实现，使用方便,对密码算法的基本要求,BG,7,古典密码（Classical Cryptography） 密码算

3、法针对的基本操作对象是字符/字母 方法字符代换（Substitution）或字符置换（Permutation） 1949年之前 此类密码学还不是科学，而是艺术 产生了一些密码算法和加密设备 也出现简单的密码分析手段,古典密码,BG,8,古典密码分类,代换 Substitution,置换 Transposition,单表代换 Monoalphabetic ,多表代换 Polyalphabetic ,单字符单表代换,多字符单表代换,移位密码,单表密码,短语单表密码,Playfair密码,Beaufort密码,Vigenre密码,行变换密码,栅格密码,Hill密码,仿射密码,Autokey密码,转子

4、机,凯撒密码,一次性密码,BG,9,代换与置换,代换密码算法（Substitution Cipher） 将明文中的每一个字符均被替换成另一个字符（密文字符）。接收者对密文做反向替换就可以恢复出明文 置换密码算法（Permutation Cipher） 又称换位密码算法（Transposition Cipher）：改变明文中各个字母的位置次序，但明文字母（的出现及出现次数）保持不变,BG,10,代替密码,单表密码算法（ Monoalphabetic Cipher) 密码表仅 1 个固定 任何明文加密、密文解密均使用同一个密码表加密 明文中相同的字母必然被加密成相同的密文字母,BG,11,代替密码

5、,多表密码算法（Polyalphabetic Cipher) 密码表多个不固定 一条明文加密和解密同时使用多个密码表 明文中两个相同的字母可能被加密成不同的密文字母,BG,12,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,13,凯撒密码,恺撒密码（Caesar Cipher） Julius Caesar 发明，是已知最早的代换密码 明文字母用其后的第三个字母代替，作为其密文字母，即，将明文字母表循环左移三位作为密码表,BG,14,两个字母表 明文字母表 Pp0, p1, , p25 密文字母表 CC0, C1, , C25

6、 基本型凯撒密码等于如下变换 明文字母表 密文字母表 明文表和密文表共同构成密钥 加密 解密,凯撒密码,BG,15,让每个字母对应一个数值 则基本型凯撒密码可以表示为 加密： Ci = E(pi) = (pi+3) mod 26 解密： pi = D(Ci) = (Ci3) mod 26 密钥数量：1,凯撒密码,BG,16,凯撒密码,凯撒密码 实例 明文： meet me after the party 密文： PHHW PH DIWHU WKH SDUWB,BG,17,凯撒密码,特点 极为简单 密钥数为1，极其脆弱,BG,18,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码

7、单表密码 短语密码 仿射密码 攻击方法 小结,BG,19,移位密码（Shift Cipher） 明文字母用其后的第 k 个字母代替，作为其密文字母，即，将明文字母表循环左移 k 位作为密码表 明文字母用任一个密文字母代替，即， 明文字母表的任一个排列均构成一个对应的密码表 加密： Ci = E(pi) = (pi+k) mod 26 解密： pi = D(Ci) = (Cik) mod 26,移位密码,BG,20,移位密码,移位密码,BG,21,例如，k = 5 明文字母表： 密文字母表： 密钥数量：25,明文,密文,移位密码,BG,22,特点 非常简单 密钥数为25，仍非常脆弱,移位密码,B

8、G,23,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,24,单表密码（Monoalphabetic Cipher） 明文字母用任一个密文字母代替，即， 明文字母表的任一个全排列均构成一个对应的密码表 加密： Ci = E(pi)=(pi+ki) mod 26 解密： pi = D(Ci)=(Ciki) mod 26 当 pipj 有 CiCj, ki, kj = 0,1,2,25 例： 明文字母表： 密文字母表： ki : 13 17 21 24 ,单表密码,BG,25,密钥数量： 26! = 403,291,461,12

9、6,605,635,584,000,000 41026 = 400亿亿亿 特点 密钥数极大，安全性好 密钥无规律，使用不便,单表密码,BG,26,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,27,短语密码,短语密码（Keyword Cipher） 是单表密码的一种实用形式 引入一个关键词（短语）来构造明文字母表的一个排列，从而构成对应的密码表 密码表构造方法1 指定一个关键词（词组、句子） 去除关键词中的重复字母和空格，前置于密码表 将剩余的字母依次按序后置于密码表 密钥数量： 26!（ 41026 = 400亿亿亿）,B

10、G,28,实例 关键词： GUANG ZHOU BAI YUN SHAN 去重前置： GUANZHOBIYS 剩余后置： TVWXCDEFJKLMPQR 明文字母表： 密文字母表：,短语密码,BG,29,短语密码 密码表构造方法2 指定一个关键词，去重复、空格，按行排阵 将剩余的字母依次继续按行排阵 阵的各列构成密码表 例：关键词=COLLEGE 阵： 明文字母表 密文字母表,短语密码,BG,30,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,31,仿射密码,仿射密码（Affine Cipher） 用仿射变换构造密码表（密码

11、表便于记忆） 密码表 两个字母表 明文字母表 Pp0, p1, , pn-1 密文字母表 CC0, C1, , Cn-1 引入两个参数 、，使明文字母 P 用字母 aP+b 代替，作为其密文字母 加密： Ci = E(pi) = (pi + ) mod n 解密： pi = D(Ci) = 1(Ci ) mod n,BG,32,仿射密码,实例 取参数 =5, =8 明文 = AFFINECIPHER 密文 = IHHWVCSWFRCP,BG,33,仿射密码,提示 仿射加密函数要求和n互素，即gcd(, n)=1，否则， (pi + ) mod n 就不是一个单射函数 当=1、 =3时，仿射密码

12、就是著名的凯撒密码 在解密时，需求解在有限域Zn上的乘法逆元1Zn，这可由扩展欧几里得算法求解 Z26上所有与26互素的元素的乘法逆元：,BG,34,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,35,对单表代换密码的攻击,两种典型的攻击 直接攻击文本 方法频度分析 直接攻击密钥 方法暴力破解（穷举破解） 两种攻击联合使用或单独使用可一举破解单表代换密码,BG,36,直接攻击文本频度分析 9世纪阿尔-金迪:关于破译加密信息的手稿 西文语言的独到特征 文章中字母的出现频度有统计规律：元音字母频度高,对单表代换密码的攻击,BG,

13、37,频度分析的步骤 统计密码字母的频度 排序 按照已知频度分布替换密文字母,对单表代换密码的攻击,BG,38,密文 频度分析 h: 可能是 e, a, i, o 尝试 h e, d a, l i, r o, 结果 密文: 明文:,频度分析攻击：实例,BG,39,直接攻击密钥暴力破解 前提已知采用的是代换密码 暴力破解的要点 尝试所有可能的密码表（移位密码：最多仅需尝试25次） 暴力破解的步骤 选择一个密码表 作逆代换 检查逆代换后的文本是否有意义，有则结束，否则换另一个密码表，进入步骤2,对单表代换密码的攻击,BG,40,实例,密文,明文,对单表代换密码的攻击,BG,41,本质 选取字母表的

14、一个全排列作为对称密钥 密钥数量 26! （ 41026）,单表代换密码：小结,BG,42,提 纲,概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结,BG,43,特征 代换固定明文字符的代换字符固定 位置相同密文字符与明文字符的位置相同 优点 简单得到密文所需的计算量小 缺点 继承密文继承了明文的统计特性（频率） 跟随明文字符的跟随关系反映在密文中,单字符代换算法：小结,BG,44,存在多种不同的破解途径 攻击密文频度分析 攻击密钥穷举密钥 改进思路：多角度同时抵御 针对频度分析使频度呈现 “均匀分布” 针对穷举密钥增大密钥空间 如何做到？,代换密码算法：如何改进？,BG,45,如何解密用短语代换密码的密文？ 如何代换密码加密中文？ 对于本次给出的四种代换密码，指出它们是沿着什么思路改进的？,进阶问题,BG,46,生成26个字母表的一个全排列，画出计算机程序的流程图。 生成短语代换密码的一个密码表，画出计算机程序的流程图。 画出用短语代换密码加密明文和解密密文的计算机程序流程图。 选取一个代换密码，利用邮件、微博或微信与你的朋友进行一次秘密通信。 请一位第三方同学尝试破