第2章古典密码学

第六节转轮密码及M-2091历史回顾二战中最著名的密码要算英格玛（ENIGMA，意为谜），它作为世界上第一部机械密码机，结束了手摇编码的历史，其工作原理奠定了当今计算机加密的基础。

鲍里斯·哈格林1934年，瑞士密码专家鲍里斯·哈格林(Boris Hagelin，1892—1983)为法国秘密机构设计了一台密码机。

他将该机改进成换字器M-209，为美国陆军所采用，二次大战期间这种密码机生产了140,000台。

2为了战胜英格玛，英国人在布莱榭丽公园的小木屋里建起了密码学校，这里聚集着各种不同寻常的怪才数学家、军事家、心理学家、语言学家、象棋高手、填字游戏专家，有些人专门负责处理细节，有些人则通过不合常理的思维跳跃来寻找灵感，到二战结束时，这里已经聚集了7000人。

二战成了密码史上的黄金年代。

军事科学家估计，盟军对密码的成功破译使二战至少提前一年结束。

3但是二战结束后，英国并没有透露英格玛已经被破解的秘密，直到20世纪70年代，各国转向计算机加密的研究，人们才知道布莱榭丽公园的故事。

但那时，很多无名英雄已经长眠地下了。

这其中，天才密码学家图灵的命运最为不幸，他不但没有因为破译英格玛受到奖励，反而因“同性恋”而被政府以“有伤风化罪”起诉，1954年，身心俱疲的图灵服毒自杀，时年42岁。

今天，信息学领域最重要的奖项被命名为“图灵奖”，也许这就是对他的补偿吧。

4当前形势密码，仍是现代战争的关键“计算机时代是继手工密码，机械密码以后，密码发展的第三个阶段，在这一阶段斗争就更复杂了。

”从“9·11”以后的反恐战的密码大战中，我们就可以看出它有多“复杂”。

52006年4月21日，驻阿富汗美军宣布，为了防止“基地”组织恐怖分子窃听，美军已紧急更换了全部通用密码。

美军此次急着更换密码，是因为一名已经脱离“基地”组织的“前恐怖分子”宣称，“基地”组织已于2005年初成功破译了驻阿美军的通用密码，并依靠破译密码全面掌握了美军活动动向。

每组中的两个字母H不ill 同体。制
P 中同行, 为紧靠各自右端的字母 P 中同列, 为紧靠各自下方的字母
密文 非同行同列, 为确定矩阵的对角字母
2. Vigenere体制
设明文m = m1m2…mn，k = k1k2…kn，则密文 c = Ek(m) = c1c2…cn，
其中ci = (mi + ki) mod 26, i = 1, 2, …, n。 当密钥的长度比明文短时，密钥可以周期性地
4. Vernam体制
Vernam密码在加密前首先将明文编码为(0, 1)字符串。
设明文m = m1m2…mn，k = k1k2…kn，其中mi , ki∈GF(2) ， 则密文c = c1c2…cn ，其中
ci = mi⊕ki , i ≥1。
在用Vernam密码对明文加密时，如果对不同的明文使 用不同的密钥，则这时Vernam密码为“一次一密”（onetime pad）密码，在理论上是不可破译的。如果存在不 同的明文使用相同的密钥，则这时Vernam密码就比较 容易被破译。
例2.5（P16）
2.3.2 多表古典密码的统计分析
在多表古典密码的分析中，首先要确定密钥字的长度, 也就是要首先确定所使用的加密表的个数，然后再分析确 定具体的密钥。
确定密钥字长的常用方法有：
设设 设
对任意
对任意
密文
对任意
密其密文中文其的中乘的法加都法是都模是q 模乘q法加. 法显.然显, 然简,单简乘单法
密加码法的密密码钥的量密为钥量为
其中的加法和乘法都是模q 加法和乘法.
显然, 简单仿射密码的密钥量为
2. 2 几种典型的古典密码体制
几种典型的单表 古典密码体制

• Ne是出现较多的字母组合，eN没出现，所以猜测 N h • 如果猜测正确，根据明文片段neCndNe，又可以猜测 C a
(可能为 ne and he 形式的明文)
6
YIFQFMendQFYVEaFMDePaVMnedhMDeVEJBTXaDDUMJ hDIFEFMDeaDMQeKaEYFaJMYnhadJaSenEXaHeUhMXe heUaDnJXYYSMnTMEYIFedDYVeVYFeUMneandheDeJJ XedGaHSMnhMDHhaMFQaHeJMXJedIEJYUaFdDJheDIn
XedGaHSMnhMDHhaMFQaHeJMXJedIEJYUaFdDJheDIn
•考虑频率排第二的M
D {r,s,t}
•片段nhM，这说明h可能是某单词的首字母，M可能代表元音
•所以猜测M {i,o}
• 密文中出现aM，因为ai比ao更常出现，所以猜测 M i
YIFQFiendQFYVEaFiDePaVinedhiDeVEJBTXaDDUiJ hDIFEFiDeaDiQeKaEYFaJiYnhadJaSenEXaHeUhiXe heUaDnJXYYSinTiEYIFedDYVeVYFeUineandheDeJJ XedGaHSinhiDHhaiFQaHeJiXJedIEJYUaFdDJheDIn
猜测 Iu, Vm
ourfriendfromEarisePaminedhisemEtBTXassUit hsurEriseasifeKaEorationhadtaSenEXaceUhiXe heUasntXooSinTiEouredsomemoreUineandhesett XedGacSinhischairfacetiXteduEtoUardsthesun

密码学教师：袁征2012年2月28日第二章古典密码及其破译序言古典密码是密码学的渊源，这些密码大都简单，可用手工或机械实现加解密，现在很少采用。

然而研究古典密码的原理，对理解、构造、分析现代密码都是十分有益的。

本章共分两节：第一节古典密码第二节古典密码的破译1、古典密码概述用你的经验如何设计一个密码算法？1、古典密码概述古典密码的形式很多，归纳起来有下面三种：类型一、代替密码体制类型二、移位密码体制类型三、乘积密码体制1、古典密码概述1. 用密码体制的概念，分析方格密码有什么特点？2. 能不能改进这个密码算法？1、古典密码概述1. 用密码体制的概念，分析单置换移位密码体制有什么特点？2. 能不能改进这个密码算法？1、古典密码概述1. 能不能把方格密码与单置换移位密码体制结合起来？2、基本数学知识1. 回顾学过的同余的概念、性质？2. 密码学中的运算基本上都是同余模运算。

例如：“凯撒密码”，它的原理是将26个英文字母分别用它后面的第3个英文字母代替，若分别以0~25表示英文字母a~z，用m表示“明文”，c表示密文，凯撒密码的加密算法是：E：c=m+3 (mod26) ，如下所示：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 ZD E F G H I J K L M N O P Q R S T U V W X Y Z A B C2、基本数学知识1. 7≡2(mod 5) ，2包含了整数中的什么数？二、剩余类环1.剩余类：所有模m和r(0≤r<m)同余的整数组成一个剩余类[r]。

例a：所有模5和2同余的整数组成一个剩余类[2]，该剩余类中的元素有无穷多个：2、7、12、17、22…例b：模5的剩余类有[0]、[1]、[2]、[3]、[4] 。

练习：模26的剩余类有那些？2. 欧拉函数：剩余类[r]中与m互素的同余类的数目用Φ(m)表示，称Φ(m)是m的欧拉函数。