第1章 古典密码

1、第第1 1章章 古典密码古典密码 密码学的起源和发展 密码学有着悠久而神秘的历史，人们很难密码学有着悠久而神秘的历史，人们很难 对密码学的起始时间给出准确的定义。对密码学的起始时间给出准确的定义。 三个阶段：三个阶段： 1949年之前密码学是一门艺术年之前密码学是一门艺术 19491975年密码学成为科学年密码学成为科学 1976年以后密码学的新方向年以后密码学的新方向公钥密码学公钥密码学 第1阶段从古代到1949年 这一时期可以看作是科学密码学的前夜时 期，这阶段的密码技术可以说是一种艺术 ，而不是一种科学，密码学专家常常是凭 知觉和信念来进行密码设计和分析，而不 是推理和证明。 主要特点：

2、数据的安全基于算法的保密。 第1阶段从古代到1949年 隐写术（公元前440年出现在古希腊战 争中）。 当时为了安全传送军事情报，奴隶主剃光奴隶 的头发，将情报写在奴隶的光头上，待头发长 长后将奴隶送到另一个部落，再次剃光头发， 原有的信息复现出来，从而实现这两个部落之 间的秘密通信。 第1阶段从古代到1949年 密码学用于通信的另一个记录是斯巴达人 于公元前400年应用Scytale加密工具在军官 间传递秘密信息。 l 时间：公元前405年，雅典和斯巴达之间的伯罗奔 尼撒战争已进入尾声的时候。 l 起因：斯巴达军队逐渐占据了优势地位，准备对 雅典发动最后一击。原来站在斯巴达一边的波斯 帝国突

3、然改变态度，停止了对斯巴达的援助，意 图使雅典和斯巴达在持续的战争中两败俱伤，以 便从中渔利。 l 截获信使：斯巴达军队捕获了一名从波斯帝国回 雅典送信的雅典信使。斯巴达士兵仔细搜查这名 信使，可搜查了好大一阵，除了从他身上搜出一 条布满杂乱无章的希腊字母的普通腰带外，别无 他获。 l 破译密码：斯巴达军队统帅莱桑德把腰带上的字 母用各种方法重新排列组合，怎么也解不出来。 最后，当他无意中把腰带呈螺旋形缠绕在手中的 剑鞘上时，奇迹出现了。原来腰带上那些杂乱无 章的字母，竟组成了一段文字。是雅典间谍送回 的一份情报！ l 战争结果：斯巴达军队根据这份情报马上改变了作战计划 ，先以迅雷不及掩耳之势

4、攻击毫无防备的波斯军队，并一 举将它击溃，解除了后顾之忧。随后，斯巴达军队回师征 伐雅典，终于取得了战争的最后胜利。 l 影响:后来，这种密码通信方式在希腊广为流传。现代的 密码电报，据说就是受了它的启发而发明的。 第1阶段从古代到1949年 我国古代也早有以藏头诗、藏尾诗、漏格诗及 绘画等形式，将要表达的真正意思或“密语” 隐藏在诗文或画卷中特定位置的记载，一般人 只注意诗或画的表面意境，而不会去注意或很 难发现隐藏其中的“话外之音”。 第1阶段从古代到1949年 到了20世纪20年代，随着机械和机电技术的成 熟，以及电报和无线电需求的出现，引起了密 码设备方面的一场革命发明了转轮密码机 （

5、简称转轮机，Rotor），转轮机的出现是密码 学发展的重要标志之一。 1.丘吉尔牺牲考文垂丘吉尔牺牲考文垂 l 1940年11月12日，德军空军司令部按希特勒指令发 出命令，派空军机群于1415日对英国内陆的中心 实行猛烈轰炸，具体目标是英国的重要城市考文垂 城，并将此计划命名为“月光奏鸣曲”。 l 所使密码机：“英尼格码”(又称“哑谜”)。 l 但是，德国不知道的是，早在 1939年8月，英情报机关就截 获并破译了这个“超级密码” 。 l 两难选择:一是采取主动措施保卫考文垂。不过这样一来 ，德国人极有可能怀疑自己的密码被破译，以后就会更换 新的密码系统，“超级机密”将失去作用。 l 另一种

6、方案是让考文垂的防务措施原封不动，对空袭作出 合乎常情的反应，用牺牲考文垂来保住“超级机密”。 l 14日下午，丘吉尔考虑再三，最后忍痛作出决定：考文垂 不做防御疏散。 l 考文垂虽然遭受了惨重的损失，但历史证明丘吉尔这一“丢卒保车” 的办法，为最终打败德国法西斯做出了巨大贡献。英国情报机构利用 它掌握的“超级机密”，多次截获敌人的重大情报，给予德军以沉重 的打击，最终迫使希特勒放弃了在英国登陆作战的“海狮计划”。 l 1942年11月，在北非阿拉曼战场上，“超级机密”提供的情报又发挥 重大作用。由于英国蒙哥马利将军对德国隆美尔的非洲军团的战略战 术计划、实力部署、后勤供给事先了如指掌，仅仅1

7、3天，德军就损失 6万人和500多辆坦克。德国“沙漠之狐”惨败于非洲沙漠。 2.“紫色紫色”密码密码 l “紫色”（Purple）是美国军队给日本外务省（外交 部）在第二次世界大战期间使用的一种机械式密码 所起的名字。美国人习惯用颜色来命名日本人的各 种密码。如此前日本外交官使用的密码被称为“红 色”。 l “紫色”密码机由日本海军技术研究所的技师田 道一雄设计制造。据称曾请日本的著名代数学家 高木贞治（1875-1960）评价，得到答复说此机 的密码有无数的变化，不可能被破解。日本政府 相信了这位其实不大懂密码的大数学家的话，正 式启用“紫色”密码机。 事实上，“紫色”密码很快就被美国陆军所

8、属的 “信号情报局”破译，其中的关键人物是弗里德 曼（William F. Friedman, 1891-1969）和罗烈（ Frank Byron Rowlett，1908-1998）。 n 中途岛事件(1942年6月3日) n 山本五十六之死事件(1943年4月18日) l 密码的破译导致二战提前两年结束。 第2阶段从1949年到1975年 1949年Shannon发表了题为 Communication Theory of Secrecy Systems (/wiki/files/shannon19 49.pdf)的著名论文，把密码学 置于坚

9、实的数学基础之上 ，标志着密码学作为一门 学科的形成，这是密码学 的第一次飞跃。 主要特点：数据安全基于 密钥而不是算法的保密。 第3阶段从1976年至今 1976年，WDiffie和M Hellman在发表的文章 New directions in cryptography ( /reports/Diffi eHellman.pdf)中提出了公开密 钥的思想，从而开创了公 钥密码学的新纪元，导致 了密码学上的一场革命， 这是密码学的第二次飞跃密码学的第二次飞跃 。 主要特点：公钥密码使得发送端和接收端无需密钥传输 的保密通信成为可能。

10、 第3阶段从1976年至今 受Diffie和Hellman 的思想启迪，各种公 钥密码体制被提出， 特别是1978年RSA 公钥密码体制的出现 ，成为公钥密码的杰 出代表，并成为事实 标准，在密码学史上 是一个里程碑里程碑。 第1章 古典密码 1.密码学基本概念密码学基本概念 2.几种典型的古典密码体制几种典型的古典密码体制 3.古典密码的统计分析古典密码的统计分析 1.1 密码学的基本概念 密码学（密码学（cryptology）作为数学的一个分支 ，是密码编码学和密码分析学的统称。 使消息保密的技术和科学叫做密码编码学密码编码学（ cryptography) 破译密文的科学和技术就是密码分析

11、学密码分析学（ cryptanalysis） 密码分析学研究的主要内容 （1） 密码算法密码算法 （2）密码协议密码协议 （3）安全保密系统安全保密系统 l 从密码产生的那天起，密码编码和密码破译的斗争 一刻也没有停止。 l 双方在相生相克的斗争中此消彼长，不断地提高各 自的密码研制技术，结果大大促进了密码学的发展 。 密码学能够解决的问题 1.1 密码学的基本概念 密码学的基本目的是面对攻击者Oscar，在被 称为Alice和Bob的通信双方之间应用不安全的 信道进行通信时，保证通信安全。 Oscar 1.1 密码学的基本概念 密码体制的定义 定义1.1.1 密码体制：密码体制的构成包括以下

12、要素： （1）M：明文消息空间，表示所有可能的明文组成的有限集 。 （2）C：密文消息空间，表示所有可能的密文组成的有限集 。 （3）K：密钥空间，表示所有可能的密钥组成的有限集。 （4）E：加密算法集合。 （5）D：解密算法集合。 1.1 密码学的基本概念 保密通信的一般机制 1.1 密码学的基本概念 密码体制的分类 对称密匙密码系统 Symmetric Key Cryptosystem 加密密钥=解密密钥 非对称密匙密码系统 Asymmetric Key Cryptosystem 加密密钥解密密钥 钥匙是保密的 加密密钥为公钥（Public Key） 解密密钥为私钥（Private Key

13、） 1.1 密码学的基本概念 1.1 密码学的基本概念 1.2 古典密码体制 1.棋盘密码棋盘密码 2.移位密码移位密码 3.代换密码代换密码 4.维吉尼亚密码维吉尼亚密码 5.仿射密码仿射密码 6.置换密码置换密码 7.Hill密码密码 1 棋盘密码棋盘密码 棋盘密码是公元前2世纪前后由希腊作家Polybius提出来的，在当时得到了 广泛的应用。棋盘密码的密钥如下表所示： 12345 1ABCDE 2FGHI/JK 3LMNOP 4QRSTU 5VWXYZ 12345 1 qwert 2 yui/jop 3 asdfg 4 hklzx 5 cvbn m 2 移位密码移位密码 移位密码的加密对

14、象为英文字母，移位密码采用对明文消息的每一个英 文字母向前推移固定位的方式实现加密。换句话说，移位密码实现了26 个英文字母的循环移位。 移位密码中，当取密钥k=3时，得到的移位密码称为凯撒密码，因为该密 码体制首先被Julius Caesar所使用。 ABCDEFGHIJKLM 00 01 02 03 04 05 06 07 08 09 10 11 12 NOPQRSTUV W XYZ 13 14 15 16 17 18 19 20 21 22 23 24 25 ( )(7)mod26 key exx ( )(7)mod26 key dyy 3 代换密码代换密码 定义定义1.2.3 代换密码

15、体制：代换密码体制： 26 MCZK 26 Z KxMyC( )( )e xx 1 ( )( )d yy 1 令是上所有可能置换构成的集合。对任意的置换 这里和互为逆置换。 ， 定义： ABCDEFGHIJKLM qwertyuiopasd NOPQRSTUVWXYZ fghjklzxcvbnm 4 维吉尼亚密码维吉尼亚密码 单表代换密码-移位密码、仿射密码等等 多表代换密码-维吉尼亚密码（Vigenre cipher），它是由法国人Blaise de Vigenre在16世纪提出的。 定义定义1.2.4 维吉尼亚密码体制：维吉尼亚密码体制： 令是一个正整数， 26 ()mMCKZ 。对任意的

16、密钥 12 (,) m keyk kkK 12 (,) m x xxM 12 (,) m y yyC定义: 121122 (, ,) (,)mod26 keymmm ex xxxk xkxk 121122 ( ,) (,)mod26 keymmm dy yyyk ykyk 如果已经在26个英文字母和之间建立了一一对应的关系，则每一个密 钥都相当于一个长度为m的字母串，被称为密钥字。 Mod 26 5 仿射密码仿射密码 仿射密码是移位密码的一个推广，其加密过程中不仅包含移位操作，而且 使用了乘法运算。 12 ( )()mod26 key exk x k 1 12 ( )()mod26 key d

17、yky k 1226261 ( ,):gcd( ,26)1Kk kZZk 26 MCZ 12 (,)keyk kKxMyC 令密钥空间为 定义： 对任意密钥 定义定义1.2.5 仿射密码的密码体制仿射密码的密码体制 明文字符对应的整数为明文字符对应的整数为 仿射密码的密钥为仿射密码的密钥为 12 ( )()mod26 key exk xk (11 133)mod2616y 密文为：密文为： 1 11 mod2619 1 12 ( )()mod26 key dykyk 19 (163)mod2613x 6 置换密码置换密码 通过重新排列消息中元素的位置而不改变元素本身的方式，对一个消息进 行变换

18、。这种加密机制称为置换密码(也称为换位密码)。 定义定义1.2.6 置换密码体制置换密码体制 令 2m 是一个正整数， 26 ()mMCZ K是 1,2, m Zm上所有可能置换构成的集合。对任意的 12 (,) m x xxM K 12 (,) m y yyC，定义： 12(1)(2)( ) ( ,)(,) mm e x xxxxx 111 12 (1)(2)( ) ( ,)(,) m m dy yyyyy 其中和 互为上的逆置换，为分组长度。对于长度大于分组长度的明文消息， 可对明文消息先按照长度进行分组，然后对每一个分组消息重复进行同样的置 乱加密过程，最终实现对明文消息的加密。 1 4m ( (1), (2), (3), (4)(2,4,1,3) 1 7 Hill密码密码 1929年Hill提出了一种多表代换密码-Hill密码。该算法保留了置换密码的加 密框架，所不同的是将分组后的每个部分，采用线性变换的方式得到密文。 定义定义1.2.7 Hill密码体制密码体制 令 2m 是一个正整数， 26 ()mMCZ K是定义在 26 Z上的所有大小为 mm 的可逆矩阵的集合。对任意的 A K ，定义： ( ) mod 26 A exAx 1 (