现代密码学理论与实践02古典密码课件

《现代密码学理论与实践02古典密码课件》由会员分享，可在线阅读，更多相关《现代密码学理论与实践02古典密码课件（70页珍藏版）》请在金锄头文库上搜索。

1、1,现代密码学 理论与实践,第二章 古典密码学 林喜军 ,2,主要内容,2.1 置换密码 2.2 代换密码 2.2.1 移位密码 2.2.2 单表代换密码 2.2.3 维吉尼亚密码 2.3 转轮机密码 2.4 古典密码的统计分析 2.4.1 单表代换密码的分析 2.4.2 维吉尼亚密码的分析,人类使用密码的历史几乎和使用文字的时间一样长。 破译者,3,2.1 置换密码,置换，又称易位，是古典密码中用到的一种最基本的处理技术； 置换密码是改变明文中各字母的相对位置，但明文字母本身的取值不变； 典型代表：周期置换密码,4,周期置换密码,工作原理 将明文按一定长度m进行分组，把每组的字母按位置变换规

2、则重排位置。 就是对位置1，2，m的一个置换,5,举例,例：m=6时，置换如下 明文 gohome 密文 HEGMOO 解密时需要逆置换-1,6,周期置换密码的密钥空间,密钥就是置换，在的描述中还包含了分组长度的信息。 密钥空间大小是多少？ m!,7,2.2 代换密码,代换，又称替换，是古典密码中用到的另一种最基本的处理技术 工作原理 先建立一张或多张代换表(明文字符到密文字符的对应关系、映射) 加密时将明文字符依次通过查表，找到相应的密文字符 明文字符被逐个替换后，生成无任何语义的字符串，即密文。,8,代换密码的密钥就是代换表 根据加解密时使用代换表多少的不同，代换密码又可分为两类 单表代换

3、密码：使用一张固定的代换表 多表代换密码：使用多张代换表,9,2.2.1 移位密码,移位密码是单表代换密码的一个特例 工作原理 加密:把明文中每个字母代换为字母表中其后的第k个字母。 解密:与加密相反，把密文中每个字母代换为字母表中其前的第k个字母。,k=5时的情况,10,移位密码举例凯撒密码,凯撒密码 ( k=3 ) 是移位密码的典型代表 加解密举例： 明文：veni, vidi, vici 密文：YHQL, YLGL, YLFL,11,移位密码是不安全的,密钥是什么？ 就是k 密钥最多有多少个？ 只有26个，k=0,1,25。 密钥空间很小 穷举攻击可以在很短时间内破译 因此，它是不安全的

4、,12,2.2.2 单表代换密码,单表代换密码使用一张固定的代换表 明文字母到密文字母的对应关系不一定像移位密码那样有规律。 代换表可以是字母表上的任意置换,13,文学作品中的单表代换密码,福尔摩斯探案集跳舞的小人,14,单表代换密码的密钥空间,密钥空间很大 26个字母的不同排列形成不同的密钥，共有26!=41026 个 穷举攻击在计算上是不可行的，即使1微秒试一个密钥，遍历全部密钥需要1013年。 正如前面提到的，很大的密钥空间并没有使单表代换密码成为安全的密码体制。 有其他攻击方法可以轻松破译它。,15,单表代换密码的弱点,密文字母的唯一性。 明文中相同的字母(比如a),在密文中总是以另一

5、个字母(比如E)代替。 即，明文中出现a的地方，在密文中相应的都会出现E 这导致明文中单字母的频率分布与密文中的相同。 这一弱点成为单表代换密码的硬伤,利用这一弱点进行攻击，比穷举攻击更加有效,16,1587年2月8日,苏格兰女王玛丽斯图亚特被送上断头台,En ma fin est mon commencement,历史的教训,17,单表代换密码改进同音密码,路易十四与“大密码” 铁面人,18,维吉尼亚密码最早记录在贝拉索于16世纪所著的书中。 19世纪时被误传为是法国外交官维吉尼亚所创，因此现在被称为“维吉尼亚密码”。 维吉尼亚密码以其简单易用而著称，同时初学者通常难以破解，因而又被称为“不

6、可破译的密码”。 应用：南北战争中的南军,维吉尼亚,2.2.3 维吉尼亚密码,19,维吉尼亚密码是多表代换密码的典型代表 多表代换密码使用多个代换表,以隐藏单字母出现的频率分布，每个代换表都可以看成是一个单表代换密码中的代换表。 多表代换密码的工作原理 将明文划分为长度相同的消息单元，称为明文分组 对明文成组地进行代换，根据每次使用的不同的代换表，同一个明文字母可以变换成不同的密文字母。 从而改变了单表代换密码中密文唯一 性的弱点，使密码分析更加困难。,20,维吉尼亚密码的工作原理,该密码体制有一个参数m(密钥的长度) 加解密时，将消息分为m个字母一组进行变换。 变换时，使用26张代换表，根据

7、不同的密钥字母，每个明文字母使用不同的代换表进行加解密。 注意：在维吉尼亚密码中，代换表不再是密钥了。,21,维吉尼亚代换表 每行都由前一行向左偏移一位得到。 实际就是26个移位密码的代换表 具体使用哪一行代换表，是基于密钥进行的，在代换过程中会不断地变换。,22,明文：ATTACKATDAWN 密钥：LEMON (m=5) 加密 明文：ATTAC KATDA WN 列 密钥：LEMON LEMON LE 行 密文：LXFOP VEFRN HR (明文第1个字母A，对应密钥第1个字母L。使用表格L行代换表进行加密，得到密文的第1个字母L。其他明文字母依此类推） 解密的过程与加密相反。,举例,2

8、3,维吉尼亚密码的密钥空间,密钥空间与密钥长度m有关 共有26m个密钥，即使m很小，穷举攻击也不太现实 假设m=5，密钥空间超过1.1107 ，已超出手工计算进行穷举攻击的能力范围。 但这并不表示维吉尼亚密码无法用手工破译。,24,维吉尼亚密码的弱点,对所有多表代换密码的破译都是以字母频率为基础的。 同一个明文字母可被加密成不同密文字母，简单的频率分析行不通。 破译的关键在于它的密钥是重复使用的。 故而，维吉尼亚密码的弱点 当相同字母间隔密钥长度倍数时，被加密成相同字母 破译的突破口 利用此弱点，寻找密钥长度,明文：ATTAC KATDA WN 密钥：LEMON LEMON LE 密文：LXF

9、OP VEFRN HR,25,2.3 转轮机密码,产生背景 大量密码体制被攻破 无线电的普遍使用，增加了对密码技术的需求 转轮机密码是密码技术与电子和机械技术相结合的产物。 人们摆脱了手工作坊式的操作，使得加解密变得更加简单易用，而且可以构造更复杂的密码体制。 它标志着加密机械化的开始,26,转轮机的典型代表 Enigma,发明者：德国工程师亚瑟谢尔比乌斯 起初用于商用，后来主要应用于军事。 在二战期间，不但德国使用Enigma，意大利、日本等轴心国成员也都在使用 人们估计，约有十万台Enigma被制造出来。 二战结束后，盟军把缴获的Enigma卖给了一些发展中国家。,27,Enigma的结构

10、,基本结构 一个键盘、若干灯泡、一系列转轮 键盘一共有26个键，键盘上方是标示了字母的26个小灯泡 当某个键被按下时，与相应密文字母对应的小灯泡就亮了起来。 在显示器的上方是几个转轮，每个转轮是26个字母的任意组合。,28,Enigma的工作原理,每个转轮有26个输入引脚和26个输出引脚， 内部连线将每个输入引脚连接到一个对应的输出引脚，这样每个转轮内部相当于一个单表代换密码。 当按下某一键时，电信号从第一个转轮的输入引脚进入，通过内部连线经过每个转轮，从最后一个转轮的输出引脚输出对应密文字母（点亮）。,29,Enigma的工作原理(续),这些转轮被称作转子。 为了实现复杂的多表代换，打破明文

11、与密文之间固定的代换关系，在每次击键输出密文字母后，转子都要发生转动。 以此改变相邻转子之间的对应关系，从而实现复杂的多表代换功能。 实际上，转子的初始设置就是密钥,30,Enigma的工作原理(续),对于3个转子的情况(德国国防军版)，根据每个轮子转动快慢不同，分为慢转子、中转子和快转子 快转子转动26次后，中转子就转动一个位置；中转子转动26次后，慢转子就转动一个位置。 在加密（或解密）263 =17,576个字母后，所有转子就会恢复到初始状态。 有n个转轮的转轮机是一个周期长度为26n 的多表代换密码。 另外，还利用键盘和第一个转子之间的连接板实现的简单代换，以增加输出的复杂性来对抗穷举

12、攻击。,初始设置,AB BI CE ,AE BQ CT ,32,对Enigma的破译,1931，德国密码处工作的施密特向法国情报人员提供了两份有关Enigma的操作和转子内部线路的资料(这说明保密算法比较困难)。 但是法国人无法破译它。法军认为，凡尔赛条约限制了德军的发展，即使无法破译德军的密码，将来在战场上相遇也不会吃多大亏。 在得出德军密码“无法破译”的结论之后，法国人就再也没有用心地研究它了。,33,对Enigma的破译(续),波兰是一战后新独立的国家，但夹在德、苏两大军事强国之间，而两国都对波兰领土垂涎三尺。 残酷的国际形势迫使波兰需要时刻了解德、苏的内部信息。 波兰从法国那里得到施密

13、特透露的情报，并成功破译了Enigma。(破译突破口是德国人使用Enigma不当造成的） 二战爆发后，英、法获知了破译Enigma的方法，并投入大量人力和资金对改进型Enigma进行破译。 盟军设计的专门用来破译Enigma的机器“炸弹” 也大大提高了布莱切利庄园的工作效率。,34,对破译Enigma做出贡献的人,雷耶夫斯基、罗佐基、佐加尔斯基 波兰三杰,1954年7月7日，图灵自杀，时年42岁,35,2.4 古典密码的统计分析,置换密码、单表代换密码、维吉尼亚密码等对己知明文攻击都是非常脆弱的。 即使用唯密文攻击，大多数古典密码体制都容易被攻破，因为它们不能很好地隐藏明文消息的统计特征。 下

14、面就针对单表代换密码、维吉尼亚密码，介绍利用英文语言的统计特征和密码特点，运用唯密文攻击破译古典密码的基本方法。,36,2.4.1 单表代换密码的分析,本质上，密文字母表是明文字母表的一种排列。 企图使用计算机穷举密钥来破译某些单表代换密码(如密钥词组代换密码)也是计算上不可行的。 但可以利用自然语言的统计特性进行分析。 英文的每个字母出现的频率不一样。 这正是进行统计分析的基础，也是单表代换密码的硬伤。 字母和字母组合的统计数据十分重要，它们提供了有关密钥的许多信息。,37,表中字母出现频率为字母出现次数除以文本字母总数,38,通过对26个英文字母出现频率的分析，可以有以下结果： e出现的频

15、率最大； t、a、o、i、n、s、h、r出现的频率约在0.060.09之间； d、l出现的频率约为0.04； c、u、m、w、f、g、y、p、b出现的频率约在0.0150.023； v，k，j，x，q，z出现的频率小于0.01。,39,除考虑单字母统计特性外，双字母、三字母的统计特性以及字母之间的连缀关系等信息也很有用。 出现频率最高的30个双字母组合依次是： th he in er an re ed on es st en at to nt ha nd ou ea ng as or ti is et it ar te se hi of,40,出现频率最高的20个三字母组合依次是： the i

16、ng and her ere ent tha nth was eth for dth hat she ion int his sth ers ver 特别的，the出现的频率几乎是ing的3倍，这在密码分析中很有用。,41,此外，统计资料还表明 超过一半的英文单词以e、s、d、t字母结尾。 约一半的英文单词以t、a、s、w开头。 对于攻击者来说，这些都是十分有用的信息。 除此之外，对明文相关知识的掌握对破译密码也是十分重要的。 (回想一下纳瓦霍语密码的优势),42,破译方法 = 统计分析 + 大胆猜测,有了上述知识，下面便可以采用唯密文攻击对单表代换密码进行破译了。 基本思想 字母e比其它字母的频率高得多，可以预计大多数密文都将包含一个频率比其它字母都高的字母。 当出现这种情况时，猜测这个密文字母对应的明文字母是e。 然后