搜索
现代密码学林喜军中国海洋大学信息安全实验室1古典密码学第2章2本章内容32.1置换密码2.2单表代换密码2.3多表代换密码2.4转轮机密码2.1置换密码45置换又叫易位(permutation)典型代表：周期置换密码置换古典密码的一种最基本的处理技术改变明文中各字符的相对位置但明文字符本身的取值不变6置换周期置换密码将明文按一定长度m进行分组，把每组的字符按位置变换规则π重排位置。工作原理对位置{1，2，…，m}的一个置换7置换周期置换密码m=6时，置换π如右图明文gohome……密文HEGMOO……解密时，需要逆置换π-1y123456π-1(y)361524x123456π(x)351642明文字符位置变换后的位置举个例子8置换周期置换密码的密钥空间Q:密钥空间大小是多少？m!就是置换π，π的描述中其实包含了分组长度m的信息密钥2.2单表代换密码910又叫替换、代替(substitution)代换古典密码的另一种最基本的处理技术改变明文中各字符的取值但明文字符的出现位置不变代换abcde...wxyzXYJMC...URBD明文：cryptography密文：JTBSWAFTXSKB11代换①建立一张或多张代换表(明文字符到密文字符的对应关系、映射)②加密时将明文字符依次通过查表，找到相应的密文字符③明文字符被逐个替换，生成无任何语义的字符串，即密文。12代换•代换密码的密钥就是代换表，根据使用代换表数量的不同，代换密码又可分为两类：①单表代换密码：使用一张代换表②多表代换密码：使用多张代换表13凯撒密码用字母表中后面第3个字母代换•举例：明文：veni,vidi,vici密文：YHQL,YLGL,YLFL凯撒密码abcde...wxyzDEFGH...ZABCJuliusCaesar(100BC–44BC)没有密钥，不安全14•加密:把明文中每个字母代换为字母表中其后的第k个字母•解密:与加密相反，把密文中每个字母代换为字母表中其前的第k个字母移位密码abcde...wxyzFGHIJ...BCDEK=5时的情况工作原理凯撒密码是k=3的移位密码15移位密码密钥空间很小穷举攻击可以在很短时间内破译不安全Q:密钥有多少个？26个，k=0,1，…,25Q:密钥是什么？k16简单代换密码《福尔摩斯探案集·跳舞的小人》简单代换密码使用一张固定的代换表明文字母到密文字母的对应关系不一定像移位密码那样有规律代换表可以是字母表上的任意置换17•密钥空间很大26个字母的不同排列形成不同的密钥，共有26!=4×1026个穷举攻击在计算上是不可行的，即使1微秒试一个密钥，遍历全部密钥需要1013年简单代换密码正如前面提到的，很大的密钥空间并没有使简单代换密码成为安全的密码体制18简单代换密码来玩一个密码分析的小游戏吧！游戏见附件119频率分析：简单代换密码的终结者简单代换密码的易用高效使它在密码领域独占鳌头。几个世纪以来，人们都认为它是安全可靠的，无法破译。然而，最终它还是被密码分析者征服了！20频率分析：简单代换密码的终结者9世纪是伊斯兰文明的黄金时期。阿拉伯人将中国、埃及等文明的著作翻译成阿拉伯语以供研究。从中国学到的造纸术使知识的传播更加方便。在这种大环境下，阿拉伯世界成为东西方文明交流的中转站，其成就对欧洲乃至全世界都产生了巨大影响。AbbasidCaliphate(850)21频率分析：简单代换密码的终结者频率分析最早记录于9世纪阿尔.金迪的革命性著作《关于破译加密信息的手稿》。这项伟大成就是语言学、统计学和宗教信仰之间的卓越联合，它在密码学历史上掀起一场革命。Al-Kindi(801-873)22频率分析：简单代换密码的终结者自然语言的特点：给定两篇英语文章，统计里面26个字母的出现频率。你会发现，两篇文章里a的出现频率差不多，b、c等字母的频率也都差不多，而且文章越长，频率越相近。为什么？因为它俩都来自同一种语言，语言特性是一样的。23频率分析：简单代换密码的终结者简单代换密码的软肋：加密过程中，明文字母与密文字母的映射关系始终固定不变。因此，密文字母与对应的明文字母的出现频率完全一样。参考文章明文密文字母频率相同字母频率相近字母频率相近同一种语言书写简单代换密码加密24频率分析：简单代换密码的终结者基本原理：1.找一篇与明文同种语言写的文章，统计出字母频率，以此作为参考。2.统计密文的字母频率3.比照参考文章，分析密文中的字母频率，找到字母之间的映射关系25频率分析：简单代换密码的终结者字母出现频率差别很大频率分布极不均匀26字母出现频率字母出现频率a0.082n0.067b0.015o0.075c0.028p0.019d0.043q0.001e0.127r0.060f0.022s0.063g0.020t0.091h0.061u0.028i0.070v0.010j0.002w0.023k0.008x0.001l0.040y0.020m0.024z0.001表中字母出现频率为字母出现次数除以文本字母总数频率分析：简单代换密码的终结者27•通过对26个英文字母出现频率的分析，可以有以下结果：①e出现的频率最大；②t、a、o、i、n、s、h、r出现的频率约在0.06～0.09之间；③d、l出现的频率约为0.04；④c、u、m、w、f、g、y、p、b出现的频率约在0.015～0.023；⑤v，k，j，x，q，z出现的频率小于0.01频率分析：简单代换密码的终结者28•除考虑单字母统计特性外，双字母、三字母的统计特性以及字母之间的连缀关系等信息也很有用。出现频率最高的30个双字母组合依次是：thheineranreedonesstenattonthandoueangasortiisetitartesehiof频率分析：简单代换密码的终结者29•出现频率最高的20个三字母组合依次是：theingandherereentthanthwasethfordthhatsheioninthissthersver•特别的，the出现的频率几乎是ing的3倍，这在密码分析中很有用。频率分析：简单代换密码的终结者30•统计资料还表明：超过一半的英文单词以e、s、d、t字母结尾。约一半的英文单词以t、a、s、w开头。•对于攻击者来说，这些都是十分有用的信息。•除此之外，对明文相关知识的掌握对破译密码也是十分重要的。频率分析：简单代换密码的终结者31•有了上述知识，下面便可以采用唯密文攻击对简单代换密码进行破译了。•基本思想①字母e比其它字母的频率高得多，可以预计大多数密文都将包含一个频率比其它字母都高的字母。②当出现这种情况时，猜测这个密文字母对应的明文字母是e。③然后，进一步比较密文中其他字母的频率统计分布，便可确定出密钥，从而破译简单代换密码。破译方法=统计分析+大胆猜测频率分析：简单代换密码的终结者32频率分析：简单代换密码的终结者频率分析举例见附件233古人应付频率分析的手段相比于阿拉伯世界，欧洲在密码领域落后几百年。直到15世纪，密码行业才逐渐繁荣起来，文艺复兴给它提供了广阔的发展空间。16世纪，欧洲人仍然使用简单代换密码，但密码分析者已经掌握了频率分析。有些意识到危机的国家开始想办法提出改进措施，例如：使用一些无意义的密文字符，加密时故意拼错几个单词。这些方法的目的只有一个：隐藏明文的统计特性。但是，这些伎俩在密码分析者面前都形同虚设。34古人应付频率分析的手段：命名密码在16世纪这个过渡时期，一种较为有效的改进方法是不仅对字母进行代换，还对常用单词进行代换，这种密码被称为命名密码。工作原理很简单:根据代换表，首先对明文中出现的常用单词进行代换，余下的字母再逐个代换。这样，相同的明文字母就被代换成不同的密文字符，从而隐藏了字母频率。35古人应付频率分析的手段：命名密码1587年2月8日,苏格兰女王玛丽·斯图亚特被推上断头台Enmafinestmoncommencement36古人应付频率分析的手段：命名密码路易十四路易十四的“大密码”发明者：罗西格诺父子方法：对法语音节进行代换威力：两百年后才被破译37古人应付频率分析的手段：同音密码abcde…●▽⊙￥Ø□◎☆℉★▲§＄※⊕明文字符密文字符进入17世纪，为克服简单代换密码的频率问题，密码编码者又提出一种行之有效的加密方法——同音密码。命名密码本质上也属于同音密码。38古人应付频率分析的手段：同音密码•十二宫杀手密码60年代末，美国加州出现一名自称Zodiac的连环杀手。他给报社寄去信，称信中408个符号的密文(408密码)包含他的身份信息。尽管408密码被密码爱好者海登夫妇破译，但信中并没有杀手的身份信息。Zodiac继续犯下多起谋杀案后，又写了一封340个符号的密文（340密码），要求报社将它放在头版头条。至今仍没有人破译340密码408密码的密文和明文39•置换密码、单表代换密码、维吉尼亚密码等对己知明文攻击都是非常脆弱的。•即使用唯密文攻击，大多数古典密码体制都容易被攻破，因为它们不能很好地隐藏明文消息的统计特征。40•企图使用计算机穷举密钥来破译某些单表代换密码(如密钥词组代换密码)是计算上不可行的。•但本质上，密文字母表是明文字母表的一种排列，因此可以利用自然语言的统计特性进行分析。•英文的每个字母出现的频率不一样，这正是频率分析的基础，也是单表代换密码的硬伤。•字母和字母组合的统计数据十分重要，它们提供了许多有用的信息。2.3多表代换密码4142多表代换密码命名密码、同音密码都属于单表代换密码，不能很好地隐藏频率特性。早在15世纪，阿尔伯提就提出单表代换密码最大的问题是加密时始终使用一张代换表的结果。如果同时使用两张不同的代换表，就可以改变字母频率。阿尔伯提依此设计了一个密码盘，它是有记载的最早的多表代换密码。他的思想被不断发展，最终成型于16世纪，维吉尼亚密码横空出世。BattistaAlberti(1404-1472)43维吉尼亚密码维吉尼亚密码多表代换密码的典型代表最早记录在贝拉索于16世纪所著的书中，19世纪时被误传为是法国外交官维吉尼亚所创，因此现在被称为“维吉尼亚密码”。曾被称为“不可破译的密码”。维吉尼亚44•该密码体制有一个参数m(密钥的长度)加解密时，将消息分为m个字母一组进行变换。变换时，使用26张代换表，根据不同的密钥字母，每个明文字母使用不同的代换表进行加解密。注意：在维吉尼亚密码中，代换表不再是密钥了。工作原理维吉尼亚密码45维吉尼亚密码的代换表如右图每行都由前一行向左移一位得到。实际就是26个移位密码的代换表。具体使用哪一行代换表，是基于密钥进行的，在代换过程中会不断变换。维吉尼亚密码46明文：ATTACKATDAWN密钥：LEMON(m=5)•加密明文：ATTACKATDAWN列密钥：LEMONLEMONLE行密文：LXFOPVEFRNHR(明文第1个字母A，对应密钥第1个字母L。查表得密文的第1个字母是L；其他明文字母依此类推）解密的过程与加密相反同一明文字母对应多个密文字母相同密文字母未必对应同一明文字母维吉尼亚密码47但这并不表示维吉尼亚密码无法用手工破译密钥空间与密钥长度m有关共有26m个密钥，即使m很小，穷举攻击也不太现实假设m=5，密钥空间超过1.1×107，已超出手工计算进行穷举攻击的能力范围。维吉尼亚密码48维吉尼亚密码的分析维吉尼亚密码被提出后，由于其加密速度慢，一度遇冷。直到17世纪，欧洲人还是使用同音密码等方法。但到了18世纪，密码分析技术已经相当盛行，单表代换密码的安全性捉襟见肘，人们被迫转向多表代换密码，维吉尼亚密码由此逐渐流行开来。19世纪，有线电报的出现更加促进维吉尼亚密码的应用和推广。欧洲的密码分析者对维吉尼亚密码的破译毫无头绪，故而将之称为“不可破译的密码”。49维吉尼亚密码的分析查尔斯.巴比奇破译维吉尼亚密码破译自动密钥密码(维吉尼亚发明)真正的计算机之父CharlesBabbage(1871-1791)50维吉尼亚密码的分析然而，查尔斯.巴比奇只是把自己的破译方法记录在小本子上九年后