第1章 古典密码

主讲人：侯红霞通信与信息工程学院第1章古典密码密码学的起源和发展密码学有着悠久而神秘的历史，人们很难对密码学的起始时间给出准确的定义。Phaistos圆盘

Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学

第1阶段—从古代到1949年这一时期可以看作是科学密码学的前夜时期，这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭知觉和信念来进行密码设计和分析，而不是推理和证明。主要特点：数据的安全基于算法的保密。第1阶段—从古代到1949年隐写术（公元前440年出现在古希腊战争中）。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。第1阶段—从古代到1949年密码学用于通信的另一个记录是斯巴达人于公元前400年应用Scytale加密工具在军官间传递秘密信息。时间：公元前405年，雅典和斯巴达之间的伯罗奔尼撒战争已进入尾声的时候。起因：斯巴达军队逐渐占据了优势地位，准备对雅典发动最后一击。原来站在斯巴达一边的波斯帝国突然改变态度，停止了对斯巴达的援助，意图使雅典和斯巴达在持续的战争中两败俱伤，以便从中渔利。截获信使：斯巴达军队捕获了一名从波斯帝国回雅典送信的雅典信使。斯巴达士兵仔细搜查这名信使，可搜查了好大一阵，除了从他身上搜出一条布满杂乱无章的希腊字母的普通腰带外，别无他获。破译密码：斯巴达军队统帅莱桑德把腰带上的字母用各种方法重新排列组合，怎么也解不出来。最后，当他无意中把腰带呈螺旋形缠绕在手中的剑鞘上时，奇迹出现了。原来腰带上那些杂乱无章的字母，竟组成了一段文字。是雅典间谍送回的一份情报！战争结果：斯巴达军队根据这份情报马上改变了作战计划，先以迅雷不及掩耳之势攻击毫无防备的波斯军队，并一举将它击溃，解除了后顾之忧。随后，斯巴达军队回师征伐雅典，终于取得了战争的最后胜利。影响:后来，这种密码通信方式在希腊广为流传。现代的密码电报，据说就是受了它的启发而发明的。第1阶段—从古代到1949年我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。第1阶段—从古代到1949年到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命——发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。德国的洛伦兹密码机恩尼格玛密码机(Enigma

)1.丘吉尔牺牲考文垂1940年11月12日，德军空军司令部按希特勒指令发出命令，派空军机群于14—15日对英国内陆的中心实行猛烈轰炸，具体目标是英国的重要城市考文垂城，并将此计划命名为“月光奏鸣曲”。所使密码机：“英尼格码”(又称“哑谜”)。但是，德国不知道的是，早在1939年8月，英情报机关就截获并破译了这个“超级密码”。两难选择:一是采取主动措施保卫考文垂。不过这样一来，德国人极有可能怀疑自己的密码被破译，以后就会更换新的密码系统，“超级机密”将失去作用。另一种方案是让考文垂的防务措施原封不动，对空袭作出合乎常情的反应，用牺牲考文垂来保住“超级机密”。14日下午，丘吉尔考虑再三，最后忍痛作出决定：考文垂不做防御疏散。考文垂虽然遭受了惨重的损失，但历史证明丘吉尔这一“丢卒保车”的办法，为最终打败德国法西斯做出了巨大贡献。英国情报机构利用它掌握的“超级机密”，多次截获敌人的重大情报，给予德军以沉重的打击，最终迫使希特勒放弃了在英国登陆作战的“海狮计划”。1942年11月，在北非阿拉曼战场上，“超级机密”提供的情报又发挥重大作用。由于英国蒙哥马利将军对德国隆美尔的非洲军团的战略战术计划、实力部署、后勤供给事先了如指掌，仅仅13天，德军就损失6万人和500多辆坦克。德国“沙漠之狐”惨败于非洲沙漠。2.“紫色”密码“紫色”（Purple）是美国军队给日本外务省（外交部）在第二次世界大战期间使用的一种机械式密码所起的名字。美国人习惯用颜色来命名日本人的各种密码。如此前日本外交官使用的密码被称为“红色”。“紫色”密码机由日本海军技术研究所的技师田道一雄设计制造。据称曾请日本的著名代数学家高木贞治（1875-1960）评价，得到答复说此机的密码有无数的变化，不可能被破解。日本政府相信了这位其实不大懂密码的大数学家的话，正式启用“紫色”密码机。事实上，“紫色”密码很快就被美国陆军所属的“信号情报局”破译，其中的关键人物是弗里德曼（WilliamF.Friedman,1891-1969）和罗烈（FrankByronRowlett，1908-1998）。中途岛事件(1942年6月3日)山本五十六之死事件(1943年4月18日)密码的破译导致二战提前两年结束。第2阶段—从1949年到1975年1949年Shannon发表了题为《CommunicationTheoryofSecrecySystems》(/wiki/files/shannon1949.pdf)的著名论文，把密码学置于坚实的数学基础之上，标志着密码学作为一门学科的形成，这是密码学的第一次飞跃。主要特点：数据安全基于密钥而不是算法的保密。克劳德.香农(ClaudeElwoodShannon，1916-2001)第3阶段—从1976年至今1976年，W．Diffie和M．Hellman在发表的文章《Newdirectionsincryptography

》(

/reports/DiffieHellman.pdf)中提出了公开密钥的思想，从而开创了公钥密码学的新纪元，导致了密码学上的一场革命，这是密码学的第二次飞跃。主要特点：公钥密码使得发送端和接收端无需密钥传输的保密通信成为可能。WhitfieldDiffieMartinHellman

第3阶段—从1976年至今受Diffie和Hellman的思想启迪，各种公钥密码体制被提出，特别是1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑。

RSA三杰

第1章古典密码1.密码学基本概念2.几种典型的古典密码体制3.古典密码的统计分析1.1密码学的基本概念密码学（cryptology）作为数学的一个分支，是密码编码学和密码分析学的统称。使消息保密的技术和科学叫做密码编码学（cryptography)破译密文的科学和技术就是密码分析学（cryptanalysis）

编码学研究的主要内容：序列密码算法的编码技术分组密码算法的编码技术公钥密码体制的编码技术加密算法、数字签名方案、密钥分配方案认证方案单向函数等传统且主流的研究方向密码分析学研究的主要内容（1）密码算法的安全性分析和破译的理论、方法、技术和实践（2）密码协议的安全性分析的理论与方法（3）安全保密系统的安全性分析和攻击的理论、方法、技术和实践从密码产生的那天起，密码编码和密码破译的斗争一刻也没有停止。双方在相生相克的斗争中此消彼长，不断地提高各自的密码研制技术，结果大大促进了密码学的发展。密码学是干什么的?密码学要解决的基本问题:

(1)信息的保密传输和存储问题;(2)信息的认证问题.

例:我收到你写给我1封信,那么我问:----信的内容是否被改动?----是否真是你写的信?----是否真是写给我信?----有没有人看过这封信？密码学能够解决的问题1.信息系统的安全与保密问题；2.电子商务、电子政务中的安全和保密问题；3.银行系统、证券系统、保险系统等的安全问题；4.商品、票据、信用卡等的防伪与审核问题。1.1密码学的基本概念密码学的基本目的是面对攻击者Oscar，在被称为Alice和Bob的通信双方之间应用不安全的信道进行通信时，保证通信安全。明文密文明文AliceBobOscar1.1密码学的基本概念密码体制的定义定义1.1.1密码体制：密码体制的构成包括以下要素：（1）M：明文消息空间，表示所有可能的明文组成的有限集。（2）C：密文消息空间，表示所有可能的密文组成的有限集。（3）K：密钥空间，表示所有可能的密钥组成的有限集。（4）E：加密算法集合。（5）D：解密算法集合。1.1密码学的基本概念明文密文明文AliceBob加密密匙解密密匙保密通信的一般机制1.1密码学的基本概念密码体制的分类对称密匙密码系统SymmetricKeyCryptosystem

加密密钥=解密密钥

非对称密匙密码系统AsymmetricKeyCryptosystem

加密密钥≠解密密钥

钥匙是保密的

加密密钥为公钥（PublicKey）解密密钥为私钥（PrivateKey）1.1密码学的基本概念1.1密码学的基本概念1.2古典密码体制1.棋盘密码2.移位密码3.代换密码4.维吉尼亚密码5.仿射密码6.置换密码7.Hill密码1棋盘密码棋盘密码是公元前2世纪前后由希腊作家Polybius提出来的，在当时得到了广泛的应用。棋盘密码的密钥如下表所示：123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ123451qwert2yui/jop3asdfg4hklzx5cvbnmsecurity3213512214231521security2移位密码移位密码的加密对象为英文字母，移位密码采用对明文消息的每一个英文字母向前推移固定位的方式实现加密。换句话说，移位密码实现了26个英文字母的循环移位。移位密码中，当取密钥k=3时，得到的移位密码称为凯撒密码，因为该密码体制首先被JuliusCaesar所使用。ABCDEFGHIJKLM00010203040506070809101112NOPQRSTUVWXYZ13141516171819202122232425假设明文为：security180402201708192425110901241502051804022017081924security加密解密zljbypcf3代换密码定义1.2.3代换密码体制：令是上所有可能置换构成的集合。对任意的置换这里和互为逆置换。，定义：ABCDEFGHIJKLMqwertyuiopasdNOPQRSTUVWXYZfghjklzxcvbnm假设明文为：securityktexloznsecurity加密：解密：4维吉尼亚密码单表代换密码---移位密码、仿射密码等等多表代换密码----维吉尼亚密码（Vigenèrecipher），它是由法国人BlaisedeVigenère在16世纪提出的。定义1.2.4维吉尼亚密码体制：令是一个正整数，。对任意的密钥定义:如果已经在26个英文字母和之间建立了一一对应的关系，则每一个密钥都相当于一个长度为m的字母串，被称为密钥字。security18040220170819241804022017081924like110810042912122428162928Mod260312122402160302DMMYCQDC加密密文5仿射密码仿射密码是移位密码的一个推广，其加密过程中不仅包含移位操作，而且使用了乘法运算。

令密钥空间为定义：对任意密钥定义1.2.5仿射密码的密码体制明文字符对应的整数为假设：仿射密码的密钥为

13key=(11,3)加密密文为：16解密6置换密码通过重新排列消息中元素的位置而不改变元素本身的方式，对一个消息进行变换。这种加密机制称为置换密码(也称为换位密码)。定义1.2.6置换密码体制令是一个正整数，K是上所有可能置换构成的集合。对任意的，定义：其中π和互为上的逆置换，为分组长度。对于长度大于分组长度的明文消息，可对明文消息先按照长度进行分组，然后对每一个分组消息重复进行同样的置乱加密过程，最终实现对明文消息的加密。假设：明文为：securitysecurityeuscirty1234123422441133加密1234123433114422解密security