密码学基础（古典密码素材）ppt课件.ppt

《密码学基础（古典密码素材）ppt课件.ppt》由会员分享，可在线阅读，更多相关《密码学基础（古典密码素材）ppt课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、算法 网络与信息安全4n密码学的目的密码学的目的合法通信双方Alice和Bob在不安全的信道上进行安全安全通信，而破译者Oscar不能理解他们通信的内容“安全安全”指机密性、完整性、鉴别、不可抵赖机密性、完整性、鉴别、不可抵赖n简单加密系统模型简单加密系统模型简单加密系统模型密码系统密码系统 网络与信息安全5n密码系统密码系统包含带参数 K 的变换EK() 、带参数 K 的逆变换DK() 、信息传送信道、密钥传送信道l变换EK得将明文消息P变换为密文C，这个过程称为加密lE为加密算法，K为密钥。E不同或K不同，密文C就不同典型的密码系统密码系统小游戏角色1如何给你的朋友发一封由你自己加密的电子

3、邮件？角色2如何解密你朋友给你发来的加密邮件？ 网络与信息安全6n对密码算法的基本要求对密码算法的基本要求 加密能力强l当密文或明文密文对被截获时，破解密钥或明文在计算上是不可行的安全性不依赖于密码算法本身的保密，而依赖于密钥易于实现，使用方便对密码算法的基本要求 网络与信息安全7n古典密码（古典密码（Classical Cryptography）密码算法针对的基本操作对象是字符/字母方法字符代换代换（Substitution）或字符置换置换（Permutation）1949年之前此类密码学还不是科学，而是艺术产生了一些密码算法和加密设备也出现简单的密码分析手段古典密码古典密码 网络与信息安全

4、8古典密码分类古典密码分类代换代换Substitution置换置换Transposition单表代换单表代换Monoalphabetic 多表代换多表代换Polyalphabetic 单字符单字符单表代换多字符多字符单表代换移位密码移位密码单表密码单表密码短语单表密码短语单表密码Playfair密码密码Beaufort密码密码Vigenre密码密码行变换密码行变换密码栅格密码栅格密码Hill密码密码仿射密码仿射密码Autokey密码密码转子机转子机凯撒密码凯撒密码一次性密码一次性密码 网络与信息安全9代换与置换代换与置换n代换代换密码算法密码算法（Substitution Cipher）将明文

5、中的每一个字符均被替换成另一个字符（密文字符）。接收者对密文做反向替换就可以恢复出明文n置换置换密码算法密码算法（Permutation Cipher）又称换位密码算法（Transposition Cipher）：改变明文中各个字母的位置次序，但明文字母（的出现及出现次数）保持不变 网络与信息安全10代替密码代替密码n单表密码算法单表密码算法（ Monoalphabetic Cipher)密码表仅 1 个个固定l任何明文加密、密文解密均使用同一个密码表加密l明文中相同的字母必然被加密成相同的密文字母 网络与信息安全11代替密码代替密码n多表密码算法多表密码算法（Polyalphabetic C

6、ipher)密码表多个多个不固定l一条明文加密和解密同时使用多个密码表l明文中两个相同的字母可能被加密成不同的密文字母 网络与信息安全12提提 纲纲n概述移位密码单表密码短语密码仿射密码n攻击方法n小结 网络与信息安全13凯撒密码n恺撒密码恺撒密码（Caesar Cipher）Julius Caesar 发明，是已知最早的代换密码明文字母用其后的第三个其后的第三个字母代替，作为其密文字母，即，将明文字母表循环左移三位循环左移三位作为密码表 网络与信息安全14n两个字母表两个字母表明文字母表 Pp0, p1, , p25密文字母表 CC0, C1, , C25n基本型凯撒密码等于如下变换基本型凯

7、撒密码等于如下变换明文字母表 密文字母表明文表和密文表共同构成密钥密钥加密加密解密解密凯撒密码 网络与信息安全15n让每个字母对应一个数值让每个字母对应一个数值 则则基本型凯撒基本型凯撒密码可以表示为密码可以表示为l加密：Ci = E(pi) = (pi+3) mod 26l解密：pi = D(Ci) = (Ci3) mod 26n密钥数量：密钥数量：1凯撒密码 网络与信息安全16凯撒密码n凯撒密码凯撒密码n实例实例明文： meet me after the party密文： PHHW PH DIWHU WKH SDUWB 网络与信息安全17凯撒密码n特点特点极为简单密钥数为1，极其脆弱 网络

8、与信息安全18提提 纲纲n概述凯撒密码单表密码短语密码仿射密码n攻击方法n小结 网络与信息安全19n移位移位密码密码（Shift Cipher）明文字母用其后的第其后的第 k 个个字母代替，作为其密文字母，即，将明文字母表循环左移循环左移 k 位位作为密码表明文字母用任一个任一个密文字母代替，即， 明文字母表的任一个排列排列均构成一个对应的密码表l加密：Ci = E(pi) = (pi+k) mod 26l解密：pi = D(Ci) = (Cik) mod 26移位密码 网络与信息安全20n移位密码移位密码移位密码 网络与信息安全21n例如，例如，k = 5明文字母表： 密文字母表：n密钥密钥

9、数量数量：25明文明文密文密文移位密码 网络与信息安全22n特点特点非常简单密钥数为25，仍非常脆弱移位密码 网络与信息安全23提提 纲纲n概述凯撒密码移位密码短语密码仿射密码n攻击方法n小结 网络与信息安全24n单表单表密码（密码（Monoalphabetic Cipher）明文字母用任一个任一个密文字母代替，即， 明文字母表的任一个全全排列排列均构成一个对应的密码表l加密：Ci = E(pi)=(pi+ki) mod 26l解密：pi = D(Ci)=(Ciki) mod 26当 pipj 有 CiCj, ki, kj = 0,1,2,25n例例：明文字母表：密文字母表： ki : 13

10、17 21 24 单表密码a b c d e f g h ij k l m n o p q r s t u v w x y zN S X C H M R W B G L Q V A F K P U Z E J O T Y D I 网络与信息安全25n密钥密钥数量数量： 26! = 403,291,461,126,605,635,584,000,000 41026 = 400亿亿亿n特点特点密钥数极大，安全性好密钥无规律，使用不便单表密码 网络与信息安全26提提 纲纲n概述凯撒密码移位密码单表密码仿射密码n攻击方法n小结 网络与信息安全27短语密码n短语短语密码密码（Keyword Cipher

11、）是单表密码的一种实用形式引入一个关键词关键词（短语）来构造明文字母表的一个排排列列，从而构成对应的密码表密码表构造方法1l指定一个关键词（词组、句子）l去除关键词中的重复字母和空格，前置于密码表l将剩余的字母依次按序后置于密码表n密钥密钥数量：数量： 26!（ 41026 = 400亿亿亿） 网络与信息安全28n实例实例关键词：GUANG ZHOU BAI YUN SHAN去重前置：GUANZHOBIYS剩余后置： TVWXCDEFJKLMPQR明文字母表：密文字母表：a b c d e f g h i j k l m n o p q r s t u v w x y zG U A N Z H

12、 O B I Y S T VWX C D E F J K L M P Q R短语密码 网络与信息安全29n短语短语密码密码密码表构造方法2l指定一个关键词，去重复、空格，按行排阵l将剩余的字母依次继续按行排阵l阵的各列构成密码表n例：例：关键词关键词=COLLEGE 阵：阵：明文字母表密文字母表短语密码 网络与信息安全30提提 纲纲n概述凯撒密码移位密码单表密码短语密码n攻击方法n小结 网络与信息安全31仿射密码n仿射密码仿射密码（Affine Cipher）用仿射变换构造密码表（密码表便于记忆）n密码表密码表两个字母表l明文字母表 Pp0, p1, , pn-1l密文字母表 CC0, C1,

13、 , Cn-1引入两个参数 、 ，使明文字母 P 用字母 aP+b 代替，作为其密文字母l加密：Ci = E(pi) = (pi + ) mod nl解密：pi = D(Ci) = 1(Ci ) mod n 网络与信息安全32仿射密码n实例实例取参数 =5, =8明文 = AFFINECIPHER密文 = IHHWVCSWFRCP明文明文AFFINECIPHERpi055813428157417(5pi+8)83333487328184883432893(5pi+8) mod 26877222121822517215CiIHHWVCSWFRCP 网络与信息安全33仿射密码n提示提示仿射加密函数

14、要求和n互素，即gcd(, n)=1，否则， (pi + ) mod n 就不是一个单射函数当=1、 =3时，仿射密码就是著名的凯撒密码在解密时，需求解在有限域Zn上的乘法逆元1Zn，这可由扩展欧几里得算法求解Z26上所有与26互素的元素的乘法逆元： 网络与信息安全34提提 纲纲n概述n单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码n小结 网络与信息安全35对单表代换密码的攻击 n两种典型的攻击两种典型的攻击直接攻击文本方法频度分析直接攻击密钥方法暴力破解（穷举破解）n两种攻击两种攻击联合使用联合使用或或单独使用单独使用可一举破解单表可一举破解单表代换密码代换密码 网络与信

15、息安全36n直接攻击文本直接攻击文本频度分析频度分析9世纪阿尔-金迪:关于破译加密信息的手稿n西文语言的独到特征西文语言的独到特征文章中字母的出现频度有统计规律：元音字母频度高对单表代换密码的攻击 网络与信息安全37n频度分析的步骤频度分析的步骤1.统计密码字母的频度2.排序3.按照已知频度分布替换密文字母对单表代换密码的攻击 网络与信息安全38n密文密文n频度分析频度分析 h: 可能是 e, a, i, on尝试尝试 h e, d a, l i, r o, n结果结果 密文: 明文:频度分析攻击：实例 网络与信息安全39n直接攻击直接攻击密钥密钥暴力破解暴力破解前提已知采用的是代换密码n暴力

16、破解的要点暴力破解的要点尝试所有可能的密码表（移位密码：最多仅需尝试25次）n暴力破解的步骤暴力破解的步骤1.选择一个密码表2.作逆代换3.检查逆代换后的文本是否有意义，有则结束，否则换另一个密码表，进入步骤2对单表代换密码的攻击 网络与信息安全40n实例实例密文密文明文明文对单表代换密码的攻击 网络与信息安全41n本质本质选取字母表的一个选取字母表的一个作为对称作为对称密钥密钥n密钥数量密钥数量26! （ 41026）单表代换密码：小结 网络与信息安全42提提 纲纲n概述n单表代换算法单符号代换算法凯撒密码移位密码单表密码短语密码仿射密码n攻击方法 网络与信息安全43n特征特征代换固定明文字

17、符的代换字符固定位置相同密文字符与明文字符的位置相同n优点优点简单得到密文所需的计算量小n缺点缺点继承密文继承了明文的统计特性（频率）跟随明文字符的跟随关系反映在密文中单字符代换算法：小结 网络与信息安全44n存在多种不同的破解途径存在多种不同的破解途径攻击密文频度分析攻击密钥穷举密钥 n改进思路：多角度同时抵御改进思路：多角度同时抵御针对频度分析使频度呈现 “均匀分布”针对穷举密钥增大密钥空间n如何做到？如何做到？代换密码算法：如何改进？ 网络与信息安全451.如何解密用短语代换密码的密文？如何解密用短语代换密码的密文？2.如何代换密码加密中文？如何代换密码加密中文？3.对于本次给出的四种代

18、换密码，指出它们是沿对于本次给出的四种代换密码，指出它们是沿着什么思路改进的？着什么思路改进的？进阶问题 网络与信息安全461.生成生成26个字母表的一个全排列，画出计算机程序的个字母表的一个全排列，画出计算机程序的流程图。流程图。2.生成短语代换密码的一个密码表，画出计算机程序生成短语代换密码的一个密码表，画出计算机程序的流程图。的流程图。3.画出用短语代换密码加密明文和解密密文的计算机画出用短语代换密码加密明文和解密密文的计算机程序流程图。程序流程图。4.选取一个代换密码，利用邮件、微博或微信与你的选取一个代换密码，利用邮件、微博或微信与你的朋友进行一次秘密通信。朋友进行一次秘密通信。请一位第三方同学尝试破解密文，根据破解结果评价你选取的代换密码。调换角色，重做。课后作业 网络与信息安全47单字母密码单字母密码n单表代换密码移位（shift ）密码、乘数（multiplicative)密码仿射（affine ) 密码、多项式（Polynomial)密码密钥短语（Key Word)密码n多表代换密码维吉尼亚（Vigenere)密码博福特（Beaufort）密码滚动密钥(running-key)密码弗纳姆(Vernam)密码转子机(rotor machine)