密码学基础（古典密码素材）ppt课件.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,古典密码（Classical Cryptography）密码算法针对的基本操作对象是字符/字母方法字符代换（Substitution）或字符置换（Permutation）1949年之前此类密码学还不是科学，而是艺术产生了一些密码算法和加密设备也出现简单的密码分析手段,古典密码,8,古典密码分类,代换Substitution,置换Transposition,单表代换Monoalphabetic ,多表代换Polyalphabetic ,单字符单表代换,多字符单表代换,移位密码,单表密码,短语单表密码,Playfair密码,Beaufort密码,Vigenre密码,行变换密码,栅格密码,Hill密码,仿射密码,Autokey密码,转子机,凯撒密码,一次性密码,9,代换与置换,代换密码算法（Substitution Cipher）将明文中的每一个字符均被替换成另一个字符（密文字符）。接收者对密文做反向替换就可以恢复出明文置换密码算法（Permutation Cipher）又称换位密码算法（Transposition Cipher）：改变明文中各个字母的位置次序，但明文字母（的出现及出现次数）保持不变,10,代替密码,单表密码算法（ Monoalphabetic Cipher)密码表仅 1 个固定任何明文加密、密文解密均使用同一个密码表加密明文中相同的字母必然被加密成相同的密文字母,11,代替密码,多表密码算法（Polyalphabetic Cipher)密码表多个不固定一条明文加密和解密同时使用多个密码表明文中两个相同的字母可能被加密成不同的密文字母,12,提 纲,概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结,13,凯撒密码,恺撒密码（Caesar Cipher）Julius Caesar 发明，是已知最早的代换密码明文字母用其后的第三个字母代替，作为其密文字母，即，将明文字母表循环左移三位作为密码表,14,两个字母表明文字母表 Pp0, p1, , p25密文字母表 CC0, C1, , C25基本型凯撒密码等于如下变换明文字母表 密文字母表明文表和密文表共同构成密钥加密解密,凯撒密码,15,让每个字母对应一个数值 则基本型凯撒密码可以表示为加密：Ci = E(pi) = (pi+3) mod 26解密：pi = D(Ci) = (Ci3) mod 26密钥数量：1,凯撒密码,16,凯撒密码,凯撒密码实例明文：meet me after the party密文：PHHW PH DIWHU WKH SDUWB,17,凯撒密码,特点极为简单密钥数为1，极其脆弱,18,提 纲,概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结,19,移位密码（Shift Cipher）明文字母用其后的第 k 个字母代替，作为其密文字母，即，将明文字母表循环左移 k 位作为密码表明文字母用任一个密文字母代替，即， 明文字母表的任一个排列均构成一个对应的密码表加密：Ci = E(pi) = (pi+k) mod 26解密：pi = D(Ci) = (Cik) mod 26,移位密码,20,移位密码,移位密码,21,例如，k = 5明文字母表： 密文字母表：密钥数量：25,明文,密文,移位密码,22,特点非常简单密钥数为25，仍非常脆弱,移位密码,23,提 纲,概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结,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 ,单表密码,25,密钥数量： 26! = 403,291,461,126,605,635,584,000,000 41026 = 400亿亿亿特点密钥数极大，安全性好密钥无规律，使用不便,单表密码,26,提 纲,概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结,27,短语密码,短语密码（Keyword Cipher）是单表密码的一种实用形式引入一个关键词（短语）来构造明文字母表的一个排列，从而构成对应的密码表密码表构造方法1指定一个关键词（词组、句子）去除关键词中的重复字母和空格，前置于密码表将剩余的字母依次按序后置于密码表密钥数量： 26!（ 41026 = 400亿亿亿）,28,实例关键词：GUANG ZHOU BAI YUN SHAN去重前置：GUANZHOBIYS剩余后置： TVWXCDEFJKLMPQR明文字母表：密文字母表：,短语密码,29,短语密码密码表构造方法2指定一个关键词，去重复、空格，按行排阵将剩余的字母依次继续按行排阵阵的各列构成密码表例：关键词=COLLEGE 阵：明文字母表密文字母表,短语密码,30,提 纲,概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结,31,仿射密码,仿射密码（Affine Cipher）用仿射变换构造密码表（密码表便于记忆）密码表两个字母表明文字母表 Pp0, p1, , pn-1密文字母表 CC0, C1, , Cn-1引入两个参数 、，使明文字母 P 用字母 aP+b 代替，作为其密文字母加密：Ci = E(pi) = (pi + ) mod n解密：pi = D(Ci) = 1(Ci ) mod n,32,仿射密码,实例取参数 =5, =8明文 = AFFINECIPHER密文 = IHHWVCSWFRCP,33,仿射密码,提示仿射加密函数要求和n互素，即gcd(, n)=1，否则， (pi + ) mod n 就不是一个单射函数当=1、 =3时，仿射密码就是著名的凯撒密码在解密时，需求解在有限域Zn上的乘法逆元1Zn，这可由扩展欧几里得算法求解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! （ 41026）,单表代换密码：小结,42,提 纲,概述单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码攻击方法小结,43,特征代换固定明文字符的代换字符固定位置相同密文字符与明文字符的位置相同优点简单得到密文所需的计算量小缺点继承密文继承了明文的统计特性（频率）跟随明文字符的跟随关系反映在密文中,单字符代换算法：小结,44,存在多种不同的破解途径攻击密文频度分析攻击密钥穷举密钥 改进思路：多角度同时抵御针对频度分析使频度呈现 “均匀分布”针对穷举密钥增大密钥空间如何做到？,代换密码算法：如何改进？,45,如何解密用短语代换密码的密文？如何代换密码加密中文？对于本次给出的四种代换密码，指出它们是沿着什么思路改进的？,进阶问题,46,生成26个字母表的一个全排列，画出计算机程序的流程图。生成短语代换密码的一个密码表，画出计算机程序的流程图。画出用短语代换密码加密明文和解密密文的计算机程序流程图。选取一个代换密码，利用邮件、微博或微信与你的朋友进行一次秘密通信。请一位第三方同学尝试破解密文，根据破解结果评价你选取的代换密码。调换角色，重做。,课后作业,47,单字母密码,单表代换密码移位（shift ）密码、乘数（multiplicative)密码仿射（affine ) 密码、多项式（Polynomial)密码密钥短语（Key Word)密码多表代换密码维吉尼亚（Vigenere)密码博福特（Beaufort）密码滚动密钥(running-key)密码弗纳姆(Vernam)密码转子机(rotor machine),