第2章 传统密码系统.ppt

密码学基础 赵海燕zhaohaiyan 第2章传统密码系统 2 1隐写术 隐写术隐藏消息的存在 密码编码学隐藏消息的含义 代替 换位 水洗尘埃道未甞 甘于名利两相忘 心怀六洞丹霞客 口诵三清紫府章 十里采莲歌达旦 一轮明月桂飘香 日高公子还相觅 见得山中好酒浆 洗尘埃道未甞于名利两相忘怀六洞丹霞客诵三清紫府章里采莲歌达旦轮明月桂飘香高公子还相觅得山中好酒浆 藏头拆字诗 牛郎织女会佳期下弹琴又赋诗静惟闻钟鼓響停始觉星斗移少黄冠归道观幾而作尽忘机时得到桃源洞彼仙人下象棋 牛郎织女会佳期 月下弹琴又赋诗 寺静惟闻钟鼓響 音停始觉星斗移 多少黄冠归道观 见幾而作尽忘机 几时得到桃源洞 同彼仙人下象棋 王先生 来信收悉 你的盛情真是难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把方能上街 苦矣 大约本月中旬我才能返回 届时再见 王先生 来信收悉 你的盛情真是难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把方能上街 苦矣 大约本月中旬我才能返回 届时再见 网格式密码 传统信息隐藏和现代高技术手法的结合现代信息隐藏技术 数字水印人类贯穿未来战争与和平的智慧大较量 信息隐藏技术 隐写术的优点 能够被某些人使用而不容易被发现他们间在进行秘密通信 加密则很容易被发现谁与谁在进行秘密通信 这种发现本身可能具有某种意义或作用 隐写术的缺点 形式简单但构造费时 要求有大量的开销来隐藏相对较少的信息 一旦该系统的构造方法被发现 就会变得完全没有价值 隐写术一般无稳健性 2 2代替 明文中的字母由其他字母 数字或符号所取代的一种方法具体的代替方案称之为密钥 代替密码体制 加密 解密 著名的Caesar密码举例 设明文为 China 对应的数字为 278130 加密 C 对应着字母F h 对应着字母K i 对应着字母L n 对应着字母Q a 对应着字母D 所以明文 China 基于Caesar密码被加密为 FKLQD 解密 F 对应着C K 对应着H L 对应着I Q 对应着N D 对应着A 即 FKLQD 经Caesar密码解密恢复为 CHINA 不区分大小写 Caesar密码的特点 属于单字母简单替换密码已知加密与解密算法 C E P P 3 mod26P D C C 3 mod26明文语言集已知且易于识别结构过于简单 易被蛮力 穷举搜索 攻击方法分析 练习 请用穷举搜索法 破译如下用移位密码加密的密文 IXEVZUMXGVNEOYBKXEOTZKXKYZOTM 动手试试 请看我的 代替密码的实现方法分类 单表代替密码使用密钥的单表代替加密仿射加密多表代替密码Playfair密码Hill密码Vigenere密码 使用密钥的单表代替加密 设密钥为 spectacular 明文 ABCDEFGHIJKLMNOPQRSTUVWXYZ对应的密文 spectaulrbdfghijkmnoqvwxyz如果明文为 China 则对应的密文为 elrhs 练习 设密钥为 key 加密明文 cipher 得到的结果是什么 动手试试 请看我的 仿射加密 加密 解密 仿射加密要求 故密钥空间大小为 当k1 1时为通用Caesar变换 移位密码 如果同时k2 3 则为Caesar变换 仿射加密 仿射加密的例子 密钥 7 1 mod26 15加密函数 解密函数 设明文 China 首先转换为数字 2 7 8 13 0 加密 China 经仿射加密变换成 RAHQD 解密 原始消息 China 得到恢复 单表代替密码的特点 密钥量很小 不能抵抗穷尽搜索攻击没有将明文字母出现的概率掩藏起来 很容易受到频率分析的攻击汉语在加密方面的特性优于英语 频率分析攻击 常见的三字母组合 THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH等 常见的双字母组合 TH HE IN ER RE AN ON EN AT 频率分析攻击的一般方法 第一步 对密文中出现的各个字母进行出现的频率统计第二步 根据密文中出现的各个字母的频率 和英语字母标准频率进行对比分析 做出假设 推论加密所用的公式第三步 证实上述假设或继续作其他假设 一般单表代替密码 频率分析攻击案例 福尔摩斯探案 跳舞的小人 金甲虫 爱伦 坡 Playfair密码 基于一个5 5字母矩阵该矩阵使用一个关键词 密钥 来构造构造方法 从左至右 从上至下依次填入关键词的字母 去除重复的字母 然后再以字母表顺序依次填入其他的字母 字母I和J被算作一个字母 加密方法 P1 P2同行 对应的C1和C2分别是紧靠P1 P2右端的字母 其中第一列被看作是最后一列的右方 解密时反向 P1 P2同列 对应的C1和C2分别是紧靠P1 P2下方的字母 其中第一行看作是最后一行的下方 解密时反向 P1 P2不同行 不同列 C1和C2是由P1和P2确定的矩形的其它两角的字母 并且C1和P1 C2和P2同行 解密时处理方法相同 P1 P2 则插入一个字母于重复字母之间 并用前述方法处理若明文字母数为奇数时 则在明文的末端添加某个事先约定的字母作为填充 例 密钥是 PLAYFAIRISADIGRAMCIPHER 如果明文是 P playfaircipher明文两个一组 playfaircipher对应密文为 LAYFPYRSMRAMCD Playfair密码的特点 有676种双字母组合 因此识别各种双字母组合要困难得多各个字母组的频率要比单字母呈现出大得多的范围 使得频率分析困难得多Playfair密码仍然使许多明文语言的结构保存完好 使得密码分析者能够利用 Playfair的破译 统计英文中的双字母频率 找出频率最高的双字母例如re和er在英文中很常见 如果密文中IG和GI出现的频率很高 那么可以猜测e i r g这4个字母构成矩阵中的一个矩形 用类似的频率分析方法就可以破译 Hill密码 明文 密文 矩阵形式 例子 P HILL 对应 7 8 11 11 密钥 加密 9 8 8 24 JIIY 解密 7 8 11 11 HILL Hill密码的特点 Hill密码完全隐藏了单字母的频率字母和数字的对应可以改成其它方案 使得更不容易攻击成功能比较好地抵抗频率法的分析 对抗仅有密文的攻击强度较高易受已知明文攻击 Vigenere密码 例 p datasecurity k best首先将明文分解成长为4的序列 datasecurity每个序列用密钥best加密密文 EELTTIUNSMLR Vigenere的破译 用频率分析攻击很难破译Vigenere密码一般的破译方式 1 确定密钥长度2 确定密钥 例 1 确定密钥长度 将密文写在一张长纸条上 再以相同方式写在另一张长纸条上 将两张纸条上下放好 并且错开若干个字母的位置 可能的密钥长度 VVHQWVVRHMUSGJGTHKIHTSSEJCVVHQWVVRHMUSGJGTHKIHTSSEJCHLHLSFCBGVWCRLRYQTFSVG SFCBGVWCRLRYQTFSVGAH 位移为2时 记下上下两个字母相同的次数 然后统计不同位移下的相同字母次数 进行比较 位移的个数 123456相同的对数 141416142412当位移数是5的时候 相同的对数最多 那么5就是密码长度的最佳猜测 2 确定密钥当长度确定以后 例如确定为5 则首先观察第1 6 11 16 个字母 看哪个字母出现的频率最高 然后用频率分析攻击方法猜测密钥的第一个字母是什么 然后验证 确定了第1个密钥字母以后 再观察第2 7 12 个字母 进行频率分析攻击 接着用相同的方法确定剩下的密钥字母 完成破译 威胁代替密码的因素 频率分析考虑最可能的字母及单词重复结构分析持久性 组织性 创造性和运气明文已知且易于识别 2 3换位 换位就是重新排列消息中的字母 以便打破密文的结构特性典型处理方法 将明文按行写在一张格纸上 然后再按列的方式读出结果为了增加变换的复杂性 可以设定读出列的不同次序 即密钥 例子 明文 cryptographyisanappliedscience密钥 encry密文 yripdncohniirgyaeepaspsctpalce 换位密码的特点 多步换位有助于加强混乱易受频率分析攻击与代替密码技术结合 可以得到有效的强密码编码方案 ADFGX密码 在第一次世界大战期间 英国和德国分别使用的是Playfair和ADFGX密码 用现在的标准来看 它们都是相当弱的密码系统 但在当时却要花很大的力气去破解它们 ADFGX密码是一个典型的将代替和换位相结合的加密方案 ADFGX密码 首先将字母表中的字母放入一个5 5的矩阵 i和j作为同一个字母 行和列用A D F G X标记 例如 矩阵可以是 例如 s替换为FA z替换为DG 假设明文是KaiserWilhelm 则经过替换后变为XAFFGGFAAGDXGXGGFDXXAGFDGA ADFGX密码 接着选择一个关键字 如Rhein 用这个字标记矩阵的列 把第一步的结构组成如下矩阵 ADFGX密码 然后对列进行调整 使标记按照字母次序排列 最后 按照列的次序读出字母 标记忽略 得到密文 FAGDFAFXFGFAXXDGGGXGXGDGAA ADFGX密码 关键字和密文的长度决定了矩阵每一列的长度 初始矩阵和关键字必须经常变动 增加破译的难度 之所以选择字母ADFGX 是因为他们的莫尔斯码 不容易引起混淆 也是为了避免在传输中出现错误 这是早期将纠错码和密码学相结合的一种尝试 ADFGX密码最终被ADFGVX取代 这个密码系统用了6 6的初始矩阵 它允许使用所有的26个字母外加10个数字 55 2 4序列密码 序列密码 即流密码 以位或字节 一个字母或一个比特 做为处理单元序列密码是对称密码算法的一种具有实现简单 便于硬件实现 加解密处理速度快 没有或只有有限的错误传播等特点应用于无线通信 外交通信 56 序列密码体制 1949年 Shannon证明了只有一次一密密码体制是绝对安全的 序列密码体制是模仿一次一密密码体制的尝试 57 一次一密密码体制 概念 在流密码当中使用与消息长度等长的随机密钥 密钥本身只使用一次 方法 逐位计算明文位串和密钥位串的异或值 结果得到的密文不可能被破解优点 由于使用与消息等长的随机密钥 产生与原文没有任何统计关系的随机输出 因此一次一密方案不可破解 缺点 密钥在传递和分发上存在很大困难 58 序列密码体制 明文流 M m1m2m3 mn 密钥流 K k1k2k3 kn 密钥流由种子密钥通过密钥流生成器得到 加密 C c1c2c3 cn 其中ci Eki mi i 1 2 n 解密 M m1m2m3 mn 其中mi Dki ci i 1 2 n 59 1 同步序列密码模型 序列密码由一个六元组 P C K L E D 和一个密钥流生成器g组成 下图为同步序列密码模型 密钥流字母表 60 同步序列密码 特点 发送方和接收方是同步的 同样的密钥必须在同样的态进行加解密操作一个密文字符被改变 注意 不是删除 只影响该字符 不影响后继字符 61 2 自同步序列密码 密钥流的产生与密钥和已经产生的固定数量的密文有关 记忆变换 62 自同步序列密码 特点 由于解密取决于先前的t个密文字符 可以实现自同步 即同步丢失后可以自动重新建立正确的解密也正因为如此 一个密文字符被修改会影响到后续的t个字符的解密 63 序列密码和分组密码 分组密码的处理单元是一个分组序列密码的处理单元则是一个元素 如一个字母或一个比特 分组密码的加密变换不随时间变化序列密码使用随时间变化的加密变换 64 序列密码和分组密码 序列密码的优点转换速度快低错误传播硬件实现电路简单序列密码的缺点低扩散 混乱度不够 有意插入及修改的不敏感性 65 序列密码和分组密码 分组密码的优点扩散性敏感性分组密码的缺点加密速度慢错误传播 66 序列密码的许多研究成果并没有完全公开 因为它主要用于军事和外交等机密部门 目前公开的序列密码算法主要有RC4 SEAL等 目前的同步序列密码大多数都是二元序列密码 且加解密算法都是模2加 67 序列密码的安全性 序列密码的设计核心在于密钥流生成器的设计 密钥流生成器只有有限个状态 生成的密钥是周期序列 实际应用中的序列密码不可能真正实现一次一密 这个周期如果足够长 且随机性好 也有较强的安全性 68 2 5线性反馈移位寄存器 1 LFSR非常适合硬件实现 2 能产生大的周期序列 3 能产生好的统计特性的序列 4 其结构能够应用代数方法进行很好的分析 69 反馈移位寄存器 ai表示二值 0 1 的存储单元 它的个数n称为级级的某一时刻的内容构成一个状态共有2n个可能的状态 70 线性反馈移位寄存器LFSR 反馈函数 例