医学第2讲古典密码体制

2020 2 27 1 应用密码学 张仕斌万武南张金全孙宣东编著 西安电子科技大学出版社 二00九年十二月 2020 2 27 2 第2章古典密码体制 2学时 2020 2 27 3 知识点 隐写术 替换 代替 密码技术 换位密码技术 古典密码体制的安全性分析 2020 2 27 4 1 隐写术 2020 2 27 5 诗情画意传 密语 水洗尘埃道未甞 甘于名利两相忘 心怀六洞丹霞客 口诵三清紫府章 十里采莲歌达旦 一轮明月桂飘香 日高公子还相觅 见得山中好酒浆 洗尘埃道未甞于名利两相忘怀六洞丹霞客诵三清紫府章里采莲歌达旦轮明月桂飘香高公子还相觅得山中好酒浆 2020 2 27 6 牛郎织女会佳期下弹琴又赋诗寺静惟闻钟鼓響停始觉星斗移多少黄冠归道观幾而作尽忘机几时得到桃源洞彼仙人下象棋 牛郎织女会佳期 月下弹琴又赋诗 寺静惟闻钟鼓響 音停始觉星斗移 多少黄冠归道观 见幾而作尽忘机 几时得到桃源洞 同彼仙人下象棋 诗情画意传 密语 2020 2 27 7 王先生 来信收悉 你的盛情真是难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把方能上街 苦矣 大约本月中旬我才能返回 届时再见 王先生 来信收悉 你的盛情真是难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把方能上街 苦矣 大约本月中旬我才能返回 届时再见 2020 2 27 8 隐写术 信息隐藏 的另外一些例子 悠扬琴声奏响 进军号角 显微镜里传递情报魔术般的密写术网络与数字幽灵量子技术隐形传递信息 2020 2 27 9 隐写术的优点 能够被某些人使用而不容易被发现他们间在进行秘密通信 加密则很容易被发现谁与谁在进行秘密通信 这种发现本身可能具有某种意义或作用 2020 2 27 10 隐写术的缺点 形式简单但构造费时 要求有大量的开销来隐藏相对较少的信息 一旦该系统的构造方法被发现 就会变得完全没有价值 隐写术一般无稳健性 2020 2 27 11 替换密码技术是基于符号替换的密码技术 这种密码技术是以符号的置换来达到掩盖明文信息 这类密码技术有 单字符单表替换密码技术 比如教材上 简单替代密码技术 多名码代替密码技术和多字母代替密码技术 单字符多表替换密码技术 比如教材上 多表代替密码技术 等 2 替换密码技术 代替密码就是明文中每一个字符被替换成密文中的另外一个字符 古典密码技术根据其基本原理大体上可以分为两类 替换密码技术和换位密码技术 2020 2 27 12 1 单字符单表替换密码技术 单字符单表替换密码技术是对明文中的所有字符都使用一个固定的映射 典型的单字符单表替换密码技术有 乘法密码技术 设A a0 a1 an 1 为明文字母表 B b0 b1 bn 1 为密文字母表 单字符单表替换密码技术使用了A到B的映射关系 f A B f ai bj 一般情况下 为保证加密的可逆性 f是一一映射 将明文中的每一个字母替换为密文字母表中的一个字母 单字符单表替换密码技术的密钥就是映射f或密文字母表 一般情况下明文字母表与密文字母表是相同的 这时的密钥就是映射f 2020 2 27 13 乘法密码技术的加密变换 Ek ai aj j ik modn gcd k n 1 乘法密码技术的解密变换 Dk aj ai i jk 1 modn 乘法密码技术的密钥是k 若n是素数 则有n 2个密钥 k 1时加密变换是恒等变换 应该予以抛弃 若n不是素数 则有 n 1个密钥 其中 n 为欧拉函数的值 2020 2 27 14 移位替换密码技术 是最简单的一种替换密码 移位密码的数学基础 假设a和b都是整数 m是一个固定的正整数 若m整除a b 即m a b时 称整数a b关于模m同余 记作a b modm 若m不能整除a b 则称a b关于模m不同余 正整数m称为模数 明显地 29 5 mod8 101 3 mod7 101 4 mod7 121 4关于模2不同余易知 a b modm a modm b modm 2020 2 27 15 模的同余性质 1 自反性 a a modm 2 对称性 若a b modm 则b a modm 3 传递性 若a b modm b c modm 则a c modm 4 a b modm a modm b modm 5 ab modm a modm b modm 6 若a b modm c d modm 则 l k Z 整数集合 有la kc lb kd modm 且ac bd modm 7 设f x 与g x 分别是两个整系数多项式 f x anxn an 1xn 1 a g x bnxn bn 1xn 1 b则 若a b modm 那么f a f b modm 若a b modm 且ak bk modm k 0 n 则f a g b modm 2020 2 27 16 移位密码实质上是正整数m上模运算 特别用Zm 0 1 m 1 表示模m的剩余类 定义Zm上的加法和乘法 它完全类似于普通的实数域上的数的加法和乘法 不同的仅是运算结果是取模以后的余数 定义 移位密码算法 设P C K Z26 对0 k 25 即k K x y Z26 定义加密函数 Ek x x k mod26 解密函数 Dk y y k mod26 2020 2 27 17 加密变换为 Ek ai aj j i k modn 0 k n解密变换为 Dk aj ai i j k modn j n k modn 由于i j k modn i k k modn i modn 所以解密与加密是可逆的 从解密变换中可以看出 Dk En k 2020 2 27 18 移位替换密码技术的密钥是k k唯一地确定了明文空间到密文空间的映射 故移位替换密码技术的密钥空间的元素个数为n 1 用密钥穷搜索方法很容易破译 密钥字密码技术 它利用一个密钥字来构造替换作为密钥 仿射密码技术 是加法密码技术和乘法密码技术的结合体 2020 2 27 19 k b为该算法的密钥 当b 0时 仿射密码技术退化为乘法密码技术 当k 1时 仿射密码退化为移位替换密码技术 2020 2 27 20 2 单字符多表替换密码技术 单字符多表替换密码技术在安全性方面比单字符单表替换密码技术高 单字符多表替换密码技术是用一系列 两个以上 替换表依次对明文的字母进行替换的加密方法 假设明文字母表为Zq 替换表序列为L L1L2 明文字母序列为m m1m2 则相应的密文序列为c L m L1 m1 L2 m2 如果替换序列是非周期的无限序列 则相应的密码技术为非周期多表代替密码技术 它对每个明文都采用了不同的替换表进行加密 也称为一次一密密码技术 它是一种理论上不可破译的密码技术 因为单字符单表替换密码技术中明文的字母与密文中的字母是一一对应的 明文中的字母统计特性在明文中没有得到改变 因此单字符单表替换密码技术很容易破译 而在实际应用中采用的都是周期多表替换密码技术 只使用了有限的替换表 替换表被重复使用以完成对明文的加密 例如周期为d 则替换表序列为 L L1L2 LdL1L2 Ld 当d 1时 单字符多表替换密码技术退化为单字符单表替换密码技术 2020 2 27 21 单字符多表替换密码技术有很多 典型的有 Vigenere 费杰尔或维吉尼亚 密码技术 定义 设m是一个正整数 设M C K Z26 m Z26m Z26 Z26 Z26表示Z26的m次直积 对于 k k1 k2 km K 定义 加密函数 Ek x1 x2 xm x1 k1 xm km mod26 解密函数 Dk y1 y2 ym y1 k1 ym km mod26 Vigenere密码技术本质上是一种多表简单加法密码技术Vigenere密码技术循环地使用每一个替换表完成明文字母到密文字母的转换 维吉尼亚密码一次加密m个明文字母 2020 2 27 22 具体的加密过程 设密钥K k1k2 km 明文与密文字母表中均包含了n个字母 又设明文m m1m2 密文为c c1c2 则ci mi ki modn 其中m为正整数 当密钥的长度比明文短时 密钥可以周期性地重复使用 直至完成明文中的每个字母的加密 2020 2 27 23 Vernam 弗纳姆 密码技术 其加密方法是 将明文和密钥分别表示成二进制序列 再把它们按位进行模二加法 设明文m m1m2 密钥k k1k2 其中mi ki GF 2 i 1 则密文c c1c2 其中ci miki 这里为模二加法 Hill 希尔 密码技术 它实际上是仿射密码技术的特例 其基本加密思想是将明文分组 如n个明文字母 通过线性变换将它们转换为n个密文字母的加密算法 解密时只需做一次逆变换即可 密钥就是变换矩阵 2020 2 27 24 2020 2 27 25 换位密码技术本质上就是一种置换密码技术 但它置换的不是字符 而是书写的位置 换位密码技术的数学表达式可以表示成 设明文为 m m1m2 则密文c c1c2 ci i 1 2 n 其中置换表为 3 换位密码技术 Hill密码技术可以较好地抗击统计分析攻击 但在面对已知明文的攻击就很容易被破译 特别是在已知密钥矩阵行数的情况下 因此 Hill密码技术并不安全 2020 2 27 26 例子 明文 cryptographyisanappliedscience密钥 encry密文 yripdncohniirgyaeepaspsctpalce 2020 2 27 27 为了保护信息的保密性 抗击密码分析 保密系统应当满足下述要求 系统即使达不到理论上是不可破的 也应当为实际上不可破的 就是说 从截获的密文或某些已知的明文密文对 要决定密钥或任意明文在计算上是不可行的 系统的保密性不依赖于对加密体制或算法的保密 而依赖于密钥 这是著名的Kerckhoff原则 加密和解密算法适用于所有密钥空间中的元素 系统便于实现和使用 2020 2 27 28 威胁古典密码安全的因素 频率分析考虑最可能的字母及单词重复结构分析持久性 组织性 创造性和运气明文已知且易于识别 2020 2 27 29 频率分析攻击 由于任何自然语言都有自己的统计规律 对于古典密码来说 密文中还保留了明文的统计特征 因此可以使用统计方法 频率分析 进行攻击 英文中的统计 频率 是有规律的 每个单字母中E出现频率最高 其次是T A O I N SH R等 V K J X Q Z最低 双字母频率最高的有TH HE 它们出现的频率小于IN ER等 还有THE ING等其他规律 2020 2 27 30 常见的三字母组合 THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH等 常见的双字母组合 TH HE IN ER RE AN ON EN AT 2020 2 27 31 2020 2 27 32 频率分析攻击的一般方法 第一步 对密文中出现的各个字母进行出现的频率统计第二步 根据密文中出现的各个字母的频率 和英语字母标准频率进行对比分析 做出假设 推论加密所用的公式第三步 证实上述假设或继续作其他假设 2020 2 27 33 移位密码安全性分析 移位密码是极不安全的 mod26 因为它可被穷举密钥搜索所分析 因为仅有26个可能的密钥 通过尝试每一个可能的密钥 直到获得一个有意义的明文串 一般情况 一个明文在尝试26 2 13个密钥后将显现出来 作为早期的密码 移位密码虽然脆弱 仅对明文进行了不透明的封装 但它可防止消息明文被人意外的获取 2020 2 27 34 对于仿射密码 c e p kp b mod26 因为k要和26互质 并且还要去掉1 密钥空间只有11个 不能经得起穷举分析 仿射密码安全性分析 2020 2 27 35 2020 2 27 36 第二