古典密码学精要.ppt

Page: 古典密码学 杨秋伟 湖南大学 计算机与通信学院 古典密码学组成 古典替换密码体制 古典单码加密法 古典多码加密法 古典换位密码体制 古典置换加密法 古典单码加密法：概述 单码加密是一种替换加密法，其中的每个明文只能被唯一的一个密文字母所替换。 例一：在给定的加密法中，明文的字母“a”在密文中可能总是显示为“n”； 例二(恺撒加密法)：将字母在字母表中的位置后移3位，即“a”到“d”， “b”到“e”，…， “z”到“c” 。 古典单码加密法：关键词加密 恺撒加密法的分析：简单移位加密法通过尝试所有25个密钥就可以很容易破解，所以替代加密法应具有更多的密钥。 关键词加密的构造 选择一个关键词，如果该关键词有重复的字母，去除除第一次出现之外的所有相同字母。例如，候选关键词为“success”，则使用“suce”； 将该关键词写在字母表的下方，并用字母表的其它字母按标准的顺序填写余下的空间。 古典单码加密法：关键词加密 例一：关键词加密 关键词为“magicnet” 字母表的描述形式 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 z m a g i c n e t b d f h j k l o p q r s u v w x y z 明文：help，密文：tcho 改进方案：允许关键词从字母表的任意位置开始。 古典单码加密法：关键词加密的分析 攻击者的优势和目标 优势：攻击者知道加密法是关键词加密 目标：试图发现关键词和明文 可用的信息 明文是标准的英语； 所用加密法为关键词加密法； 每个明文字母已被唯一的密文替代。 古典单码加密法：关键词加密的分析 语言的每个字母都有自身的特性，虽然采用了字母替换，但是特性依旧保持。例如，每个明文“t”被替换为“m”，那么在密文中， “m”将具有“t”的特性。 两个有用的特性 出现频率：例如，在标准英语中，出现频率最高的是字母“e”，而“x”和“z”则很少出现；字母的实际出现频率取决于具体文字的类型，科技文献的字母出现频率与文学文献有很大的不同； 首选关联集：在标准英语中，多个字母常一起出现或不出现，例如，元音字母“a”、 “i”和“o”互不相联。 古典密码学组成 古典替换密码体制 古典单码加密法 古典多码加密法 古典换位密码体制 古典置换加密法 古典多码加密法：概述 多码加密法是为了用来对付频率分析工具。 多码加密法也是一种替换加密法。 多码加密法的目的是通过用多个密文字母来替换同一个明文字母，从而消除字母的特性。 经典的古典多码加密：Playfair密码、Hill密码、Vigenere密码 古典多码加密法：Vigenere密码 Vigenere密码是基于关键词的加密系统。 Vigenere密码不同于单码关键词加密，它将关键词写在明文的上面，并不断重复书写，这样每个明文字母都与一个关键词的字母关联。 例一：关键词为“hold”，那么关键词-明文的关联如下 古典多码加密法：Vigenere密码 Vigenere表 古典多码加密法：Vigenere密码 加密过程：给定一个密钥字母k和一个明文字母p，密文字母就是位于k所在的行与p所在的列的交叉点上的那个字母。 解密过程：由密钥字母决定行，在该行中找到密文字母，密文字母所在列的列首对应的明文字母就是相应的明文。 例一：关键词为“hold”，那么关键词-明文-密文的关联如下 古典多码加密法：Vigenere密码的分析 攻击者的优势和目标 优势：攻击者知道加密法是关键词加密 目标：试图发现关键词和明文 可用的信息 多码加密的基础依旧是关键词加密 关键词在明文上重复书写，导致有可能一个字母对应多个替换 古典多码加密法：Vigenere密码的分析 关键词在明文上重复书写 密钥的重复部分与明文中的重复部分的关联，在密文中也产生一个重复部分 推测关键词的长度：为了使关键词本身与重复的明文对齐，重复明文之间的间距是关键词长度的整数倍 找到密文中重复的字符部分，并计算它们之间的“距离”(字符数)； 计算所有“距离”的因子； 最大公约数很可能就是关键词的长度。 古典多码加密法：Vigenere密码的分析 例一：假如确定关键词的长度，如何试图破解？ 如果Eve发现Alice和Bob的关键词长度为 6，那么她就知道每相隔6个字母都是用相同关键词字母加密的； 上表中：“a p l p d”都是用字符“h”加密的 只要密文足够多，可以生成合理的统计样本，破解Vigenere加密法的问题就变成了破解n个不同单码加密的问题。 古典替换密码体制：总结 替换密码体制：设P = C = K = Z26，这里P，