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

* 仿射密码 仿射密码（Affine Cipher） 用仿射变换构造密码表（密码表便于记忆） 密码表 两个字母表 明文字母表 P＝{p0, p1, …, pn-1} 密文字母表 C＝{C0, C1, …, Cn-1} 引入两个参数 ?、?，使明文字母 P 用字母 aP+b 代替，作为其密文字母 加密： Ci = E(pi) = (?pi + ?) mod n 解密： pi = D(Ci) = ??1(Ci ? ?) mod n * 仿射密码 实例 取参数 ?=5, ?=8 明文 = AFFINECIPHER 密文 = IHHWVCSWFRCP 明文 A F F I N E C I P H E R pi 0 5 5 8 13 4 2 8 15 7 4 17 (5pi+8) 8 33 33 48 73 28 18 48 83 43 28 93 (5pi+8) mod 26 8 7 7 22 21 2 18 22 5 17 2 15 Ci I H H W V C S W F R C P * 仿射密码 提示 仿射加密函数要求?和n互素，即gcd(?, n)=1，否则， (?pi + ?) mod n 就不是一个单射函数 当?=1、? =3时，仿射密码就是著名的凯撒密码 在解密时，需求解?在有限域Zn上的乘法逆元??1?Zn，这可由扩展欧几里得算法求解 Z26上所有与26互素的元素的乘法逆元： * 提 纲 概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结 * 对单表代换密码的攻击 两种典型的攻击 直接攻击文本 方法——频度分析 直接攻击密钥 方法——暴力破解（穷举破解） 两种攻击联合使用或单独使用可一举破解单表代换密码 * 直接攻击文本——频度分析 9世纪阿尔-金迪:《关于破译加密信息的手稿》 西文语言的独到特征 文章中字母的出现频度有统计规律：元音字母频度高 对单表代换密码的攻击 * 频度分析的步骤 统计密码字母的频度 排序 按照已知频度分布替换密文字母 对单表代换密码的攻击 * 密文 频度分析 h: 可能是 e, a, i, o… 尝试 h ? e, d ? a, l ? i, r ? o, …… 结果 密文: 明文: 频度分析攻击：实例 * 直接攻击密钥——暴力破解 前提——已知采用的是代换密码 暴力破解的要点 尝试所有可能的密码表（移位密码：最多仅需尝试25次） 暴力破解的步骤 选择一个密码表 作逆代换 检查逆代换后的文本是否有意义，有则结束，否则换另一个密码表，进入步骤2 对单表代换密码的攻击 * 实例 密文 明文 对单表代换密码的攻击 * 本质 选取字母表的一个全排列作为对称密钥 密钥数量 26! （? 4?1026） 单表代换密码：小结 * 提 纲 概述 单表代换算法 单符号代换算法 凯撒密码 移位密码 单表密码 短语密码 仿射密码 攻击方法 小结 * 特征 代换固定——明文字符的代换字符固定 位置相同——密文字符与明文字符的位置相同 优点 简单——得到密文所需的计算量小 缺点 继承——密文继承了明文的统计特性（频率…） 跟随——明文字符的跟随关系反映在密文中 单字符代换算法：小结 * 存在多种不同的破解途径 攻击密文——频度分析 攻击密钥——穷举密钥 …… 改进思路：多角度同时抵御 针对频度分析——使频度呈现 “均匀分布” 针对穷举密钥——增大密钥空间 …… 如何做到？ 代换密码算法：如何改进？ * 如何解密用短语代换密码的密文？ 如何代换密码加密中文？ 对于本次给出的四种代换密码，指出它们是沿着什么思路改进的？ 进阶问题 * 生成26个字母表的一个全排列，画出计算机程序的流程图。 生成短语代换密码的一个密码表，画出计算机程序的流程图。 画出用短语代换密码加密明文和解密密文的计算机程序流程图。 选取一个代换密码，利用邮件、微博或微信与你的朋友进行一次秘密通信。 请一位第三方同学尝试破解密文，根据破解结果评价你选取的代换密码。 调换角色，重做。 课后作业 * 单字母密码 单表代换密码 移位（shift ）密码、乘数（multiplicative)密码 仿射（affine ) 密码、多项式（Polynomial)密码 密钥短语（Key Word)密码 多表代换密码 维吉尼亚（Vigenere)密码 博福特（Beaufort）密码 滚动密钥(running-key)密码 弗纳姆(Vernam)密码 转子机(rotor machine) * This mathematical description uses mod