第二章-简单密码学(补充古典密码学)

数据加密与PKI技术

第2单元

简单密码学

（补充——古典密码学）湖南公安高等专科学校

计算机信息安全教研室欧阳伟

学习目标了解密码学的相关术语√理解古典加密和加密算法及分类√掌握DES算法的加密原理、过程理解非对称算法及分类掌握RSA算法的加密原理、过程掌握RSA与DES结合使用理解Hash函数了解AES算法掌握密钥管理相关知识简单密码学

密码学基础知识安全算法设计：对称算法安全算法设计：非对称算法安全算法设计：Hash函数安全算法设计：AES算法密钥的管理

密码学基础知识密码学的发展历程大致经历了三个阶段：古代加密方法（手工阶段）古典密码（机械阶段）近代密码（计算机阶段）密码学的发展历史古代加密方法：隐写术和古代行帮暗语及一些文字猜谜游戏，如Caesar密码表，“风紧，扯乎？”等等。古典密码：分为单表代替密码、多表代替密码以及轮转密码。如Playfair密码表、Vigenere密码和Hill密码、著名的Enigma是轮转密码。近代密码：自从1949年，Shannon发表了“保密系统的信息理论”，为密码学奠定了理论基础，才使密码学成为一门科学，分为对称加密算法与非对称加密算法。相关术语

发送者和接收者发送者及发送消息的人接收者及接收消息的人消息、加/解密和密文消息也被称为明文M用某种方法伪装消息以隐藏它的内容的过程称为加密加了密的消息称为密文C而把密文转变为明文的过程称为解密明文M（Message）待加密的信息密文C（cipher）明文经过加密变换的隐蔽的形式加密过程C=f（m，k1）＝Ek1(m)解密过程m=Dk2(C)先加密后再解密消息，原始的明文将恢复出来，下面的等式必须成立：

Dk2（Ek1（M））=M几种典型的古典密码体制古典密码是基于字符替换的密码，现在已很少使用了，但是它代表了密码的起源。下面将要介绍的是在计算机发明以前使用的一些经典的密码体制，包括了单表代替密码、多表代替密码及轮转密码等类型。这些密码体制虽然现在不再被使用，但是其对密码学的重要思想给了后人很好的启示。对于一个密码体制，如果明文字母对应的密文字母在密文中保持不变，则称其为单表密码体制；如果明文中不同位置的同一明文字母在密文中对应的密文字母不同，则称其为多表密码体制。

几种典型的单表古典密码体制一、Caesar密码古罗马随笔作家修托尼厄斯在他的作品中披露，凯撒常用一种“密表”给他的朋友写信。这里所说的密表，在密码学上称为“凯撒密表”。也就是凯撒在《高卢战记》中所使用的方式，其中密钥k＝3，比如hello！就表示为khoor(忽略空格和符号)，它的数学表达式为：

加密：c＝m＋k（mod26）解密：m＝c－k（mod26）加密步骤：1）先将26个英文字母编号:a,b,c,d……y,z;每个英文字母对应的数字分别是0,1,2,3……24,25,注意这里的编号是从0开始的，与我们平时的英文字母从1开始编号不一样。

Caesar密码表例2．1

恺撒（Caesar）密码是k＝3的情况。即通过简单的向右移动源字母表3个字母则形成如下代换字母表若明文为：pleaseconfirmreceipt则密文为：SOHDVEFRQILUPUHFHLSWM:a0b1c2d3e4f5g6h7i8j9k10l11m12C:DEFGHIJKLMNOPn13o14p15q16r17s18t19u20v21w22x23y24z25QRSTUVWXYZABC2）将原文m中的每一个字母向后推3位，得到字母表中相应编号的字母，比如a就变为了d，b就变为了e，依此类推，字母表中最后3个字母x,y,z则循环至字母表首，x变为a，y变为b，并忽略明文中的空格和标点符号。Caesar密码解密步骤：将密文c中的每一个字母向前推3位，得到字母表中相应编号的字母，比如d就变为了a，e就变为了b，依此类推，字母表中最前面3个字母a,b,c则循环至字母表末，比如a变为x，b变为y，c变为z。注意：在Caesar密码中，它的加密算法是：“字母表中字母往后推k位”，解密算法是：“字母表中字母往前推k位”。密钥则是“3”位。这里的k代表了密钥。

goodmonring就是一段明文，凯撒密表就是—种变换规则。这段明文经凯撒密表加密后，就变成了密文

JRRGPRQULQJ

收信者收到这段密文后，就要进行解密，解密也是用凯撒密表。在这个例子中，加密和解密都在用凯撒密表，但严格地说，加密时所用的变换与解密时所用的变换是两个变换。这两个变换间的关系是它们互为逆变换。也就是说，明文用其中一个变换进行加密产生密文后，若再用另一个变换对这密文进行解密，就会得到原来的明文。这种互逆的关系就如同我们所熟知的加法和减法互为逆运算的关系一样：加上一个数后再减去同一个数，就等于不加也不减。Caesar密码的攻击分析安全性分析移位密码是极不安全的（mod26），因为它可被穷举密钥搜索所分析：仅有26个可能的密钥，尝试每一个可能的加密规则，直到一个有意义的明文串被获得。平均地说，一个明文在尝试26/2＝13解密规则后将显现出来。Caesar密码的破解可以根据字母出现频率这一特性对其进行攻击，如果掌握了一定数量的密文，很容易就能够攻破恺撒密码，找出其中的密钥k值。比如在英文中，字母e出现最频繁，它的统计特性是12.7％,t=9.1%,a=8.2%,o=7.5%,x、z与q都很少为1％，j＝2％。Caesar密码Caesar密码攻击

如果在一篇用恺撒密码加密的密文中（假设它的字数很多，而且字母随机性很好），我们就可以从中发现出现频率最多的字母，假设它为e或者t或者a，将出现频率最低的字母假设为x或者z或者q，然后玩填字游戏，找到加密所使用的k，攻破这个加密体制。

求解k的表达式为：k＝c－m（mod26）注意：如果k为负数时，则加上26，使得k始终是一正数比如k＝－3，则k＋26＝（－3）＋26＝23，此时，应该k＝23。Caesar密码攻击即使使用唯密文攻击，恺撒密码也是一种非常容易破解的加密方式。可能有两种情况需要考虑：攻击者知道（或者猜测）密码中使用了某个简单的替换加密方式，但是不确定是恺撒密码；攻击者知道（或者猜测）使用了恺撒密码，但是不知道其偏移量。对于第一种情况，攻击者可以通过使用诸如频率分析或者样式单词分析的方法，马上就能从分析结果中看出规律，得出加密者使用的是恺撒密码。当密文长度足够大的情况下，可以先分析密文中每个字母出现的频率，然后将这一频率与正常情况下的该语言字母表中所有字母的出现频率做比较。例如在英语中，正常明文中字母E和T出现的频率特别高，而字母Q和Z出现的频率特别低。可以通过这一特点，分析密文字母出现的频率，可以估计出正确的偏移量。此外，有时还可以将频率分析从字母推广到单词，例如英语中，出现频率最高的单词是：the,of,and,a,to,in...。我们可以通过将最常见的单词的所有可能的25组密文，编组成字典，进行分析。比如QEB可能是the，MPQY可能是单词know（当然也可能是aden）。但是频率分析也有其局限性，它对于较短或故意省略元音字母或者其他缩写方式写成的明文加密出来的密文进行解密并不适用。Caesar密码攻击对于第二种情况，解决方法更加简单。由于使用恺撒密码进行加密的语言一般都是字母文字系统，因此密码中可能是使用的偏移量也是有限的，例如使用26个字母的英语，它的偏移量最多就是25（偏移量26等同于偏移量0即明文；偏移量超过26，等同于偏移量1-25）。因此可以通过穷举法，很轻易地进行破解。其中一种方法是在表格中写下密文中的某个小片段使用所有可能的偏移量解密后的内容——称为候选明文，然后分析表格中的候选明文是否具有实际含义，得出正确的偏移量，解密整个密文。例如，被选择出的密文片段是“EXXEGOEXSRGI”，从右表中的候选明文，我们可以很快看出其正确的偏移量是4。也可以通过在每一个密文单词的每一个字母下面，纵向写下整个字母表其他字母，然后可以通过分析，得出其中的某一行便是明文。偏移量候选明文0exxegoexsrgi1dwwdfndwrqfh2cvvcemcvqpeg3buubdlbupodf4attackatonce5zsszbjzsnmbd6yrryaiyrmlac…23haahjrhavujl24gzzgiqgzutik25fyyfhpfytshj另外，有证据表明，恺撒曾经使用过更为复杂的密码系统：“文法学家普罗布斯曾经写过一份独具创新的手稿，研究恺撒书信中包含有秘密信息的字母。”—格利乌斯,阿提卡之夜现在已经无法弄清恺撒密码在当时有多大的效果，但是有理由相信它是安全的。因为恺撒大部分敌人都是目不识丁的，而其余的则可能将这些消息当作是某个未知的外语。即使有某个敌人获取了恺撒的加密信息，根据现有的记载，当时也没有任何技术能够解决这一最基本、最简单的替换密码。现存最早的破解方法记载在公元9世纪阿拉伯的阿尔·肯迪的有关发现频率分析的著作中。替换密码二、替换密码这是也是一种变形的单表代替密码，首先它要确定一个关键字，然后将关键字放到字母表的最前面，比如关键字为cipher，则它的字母表为c,i,p,h,e,r,a,b,d,f,g,j……x,y,z.如果关键字中有的字母，则在字母表中忽略，依次排序。它的数学表达式为：

加密：c＝m＋k（mod26）解密：m＝c－k（mod26）其中k即密钥，也就是关键字（如cipher）的字母个数。还有一点与Caesar密码不同，这里的字母表中字母顺序打乱了，不再是完全按英文字母顺序排列的，关键字不同，密码表的次序就不相同，保证了安全性，比Caesar密码更加健壮，单由于它仍然是单表替换密码，同样可用字母出现频率弱点进行攻击。替换密码例如，选用mountain，写出以下的字母序列： mountaibcdefghjklpqrsvwxyz

看出来了吗？就是在正常字母序列中抽掉你的密码mountain,由于mountain中有两个n，把第二个去掉。然后，把正常字母序列写在这个序列下面：

Abcdefghijklmnopqrstuvwxyz.......明文字母序

Mountaibcdefghjklpqrsvwxyz.........密文字母序

在加密的时候，用上面那个序列里的字母代替原文中的字母写成密文。例如，m代替a，o代替b。解密时方向相反。所以，加密heishere的结果是：btcqbtpt。

多表代换密码—Playfair密码三、Playfair密码最为著名的多表代换密码，它把明文中的双字母作为一个单元并将其转换成密文的“双字母音节”。

Playfair密码曾被英国军队作为一战中标准的加密体制，在英国陆军广泛使用，并且在二次世界大战中也被美军及其他一些盟国军队用它进行加密。它是由英国著名物理学家“Wheatston电桥”的设计者CharlesWheatston于1854年发明的。

Playfair算法是基于一个由密钥词构成的5×5字母矩阵，下面举例说明算法的加密步骤。Playfair密码体制Playfair密码表

playfirbcdeghkmnoqstuvwxz1234512345该密码体制的密钥是一个单词，比如playfair，将单词中后面重复的字母去掉，只保留不相同的字母，得到playfir，将剩下的字母排列成5×5矩阵的起始部分，矩阵的剩余部分则用26个字母表中未出现的字母填充，并将i与j作为一个字母对待（原因？）Playfair密码体制1）假设明文是meetattheschoolhouse,将空格标点符号忽略（几乎所有的加密算法都是如此）并将文本中每两个字母划分为一组，如果一组中是两个相同的字母，就在中间插入一个x再重新分组，最后如果单出一个字母则在最后一组的末尾加入x。这样上述明文就变成了meetatth

es

choxolhousex.现在使用矩阵来加密每两个字母组，规则如下：2）

如果m1和m2既不在明文中同一行，也不在同一列，则密文c1和c2分别为由m1和m2确定的矩形的其他两个角上的字母所代替，c1和m1同行，c2和m2同行。比如et变成了MN，因为M和e在同一行，N和t在同一行。3）

如果m1和m2在明文中同一行，则密文c1和c2分别为紧靠m1和m2右端相邻的字母，这里将第一列看作是最后一列的右端。如me变成了EG。Playfair算法加密步骤：Playfair密码体制Playfair算法加密步骤（续）：4）如果m1和m2在明文中同一列，则密文c1和c2分别为紧靠m1和m2下方的字母，这里将第一行看作是最后一行的下方，矩阵卷绕从最后一行转回到第一行，如ol变成了VR。按此方法，本例的密文如下：

明文M:meetattheschoxolhousex

密文C:EGMNFQQMKNBKSVVRGQXNKU如果要解密则是上述的逆过程。例2看过过《国家宝藏2》的朋友们一定记得里面的PLAYFAIR密码。在计算机不发达的过去，这种密码的安全性还是很高的。请对Iamlooking加密。1)密钥为HOWAREYOU。然后把这组密钥里重复的字母去掉，于是变成HOWAREYU。

2)做一5*5矩阵,如右图:HOWAREYUBCDFGIKLMNPQSTVXZ3)第三步：对明文Iamlooking分组，把空格去掉然后每两个字母分为一组:IAMLOXOKINGX

若某组中出现了同样字母，在这两个字母间加字母X，若最后一组仅有一个字母，则在其后加字母X。4)第四步：开始加密，对照刚才分组好的明文，在矩阵中找出相应的字母对的位置，然后按照下面的规则在矩阵中寻找明文字母对对应的密码字母对：

1.若明文对在矩阵中是对角关系，那么以这两字母连线为对角线作矩形，另一对角线两端的字母就是密码，比如：OX->AT

2.若明文对在矩阵中是同行关系，那么将这对字母均向右移一格，若有字母在右边界，则移动到同行左边首字母，例如BC->CE

3.若明文对在矩阵中是同列关系，那么将这对字母均向下移一格，如：IA->PB

依照规则1、2、3，将明文转换为密码：PBNMATRFGPIV

例2Playfair密码体制的破解Playfair算法的问题：如果用频率攻击的方法来破解，该体制是可以被攻破的，因为在英语中各种连字（即两个字母的组合，三个字母的组合等等）已经被制成了表格。我们看看最常用的连字：th,he,an,in,re,es,……而且对这些连字稍做变动又很快会产生新的结果，比如，连字re和er都很常见。如果在密文中像IG和GI这样的字母对出现的比较多的话，一个很自然的猜测就是e，i，r，g这些字母组成了矩阵的一个矩阵形式。该密码体制的另外一个弱点是每一个明文字母在密文中仅对应5种可能的字母（同一行的其它四个加上同列中下面相邻的字母）。除非这个密钥很长，否则矩阵的剩余行是可以预测出来的，所以，对于该体制来说仅用一段密文就可以攻破它。

古典密码的统计分析古典密码的统计分析单表古典密码体制的密文字母表实际上是明文字母表的一个排列，因此，明文字母的统计特性在密文中能够反映出来。当截获的密文足够多时，可以通过统计密文字母的出现频率，来确定明文字母和密文字母之间的对应关系。26个英文字母按出现频率的大小可以分为以下5类：a)

e：出现频率约为0.127.

b）t,a,o,i,n,s,h,r：出现频率约在0.06~0.09之间

c）d,l：出现频率约为0.04

d）c,u,m,w,f,g,y,p,b：出现频率约在0.015~0.028之间

e）v,x,q,z：出现频率小于0.01古典密码的统计分析在密码分析中，知道双字母和三字母的统计特性也是非常有用的。出现频率最高的30个双字母（按频率从大到小排列）如下：

thheineranreedones

stenattonthand

oueangasortiisetitar

tesehiof出现频率最高的20个三字母（按频率从大到小排列）如下：

theingandherereent

thanthwasethfordthhatsheioninthissth

ers

ver举例：各种各样的移位密码是在16世纪发明的，它们大多数来自于Vigenère方法，它是法国密码学家维吉尼亚于1586年提出一种多表替换密码,但是就加密性而言，Vigenère密码体制更复杂和高级，直到20世纪初，这种加密体制在很多地方仍然被认为是安全的，虽然早在19世纪，Babbage和Kasiski就展示了如何攻击它们。在1920年，由Fridman开发了另外一种加密方法，打破了Vigenère及其相关的密码方法。第一步：这个加密的密钥是一个向量，按如下方式选择。首先，确定一个密钥长度，如6，然后从0～25个整数中选择元素项满足这个长度的向量，如k＝（21，4，2，19，14，17），将其称为向量。这样，系统的安全性所依赖的就是既不能知道密钥内容也不能得知其长度。

Vigenère密码Vigenère密码第二步：下面所举的例子就是利用k来加密信息，首先，取明文的第1个字母并将之移21位，然后将第2个字母移4位，第3个字母移2位等等，一旦得到了密钥的结尾，又从头开始，这样第7个字母又移位21位，第8个字母移4位等等，加密过程的密码流程表如下：（明文）hereishowitworks(密钥)21421914172142191417214219（密文）CITXWJCSYBHNJVML

这样对于这么一段明文就可以用Vigenère完全进行加密了，注意这里没有一个字母的频率比其他大很多，这是因为e在加密的过程中扩散成了几个字母的缘故。

详细算法介绍:例3对to

be

or

not

to

be

that

is

the

question加密。

当选定“have”作为密钥时，加密过程是：密钥第一个字母为[h]，明文第一个为[t]，因此可以找到在h行t列中的字母[a]，依此类推，得出对应关系如下：

密钥：ha

ve

ha

veh

av

eh

aveh

av

eha

vehaveha

明文：to

be

or

not

to

be

that

is

the

question

密文：ao

wi

vr

isa

tj

fl

tcea

in

xoe

lylsomvn

也可以用查表法来进行加密：例如密钥的字母为[d]，明文对应的字母[b]，在下图的表格第五行找到字母“d”，再在左边第三列找到字母“b”，两个字母的交叉点就是字母“E”，所以对应的密文字母为[e]。解密Vigenère密码Vigenère的解密步骤要解密这些信息，我们需要分两步走。第一步：找到密钥的长度。第二步：发现密钥。下面我们来讲述怎么样找到密钥的长度，并给出一种发现密钥的方法，然后解释用这种方法发现密钥的工作过程，最后给出了发现密钥的第二种方法。第一步：找到密钥长度。先在一张长纸条上写上密文，再在另一张纸条上写上同样的密文。将一张纸条放在另一张纸条上面，移动其中一张纸条，让其移动一个位置，然后记下两张纸条中相同的密文字母数量；然后再移动一个位置，记下相同密文字母的数量……这样重复移动13次即可，记下每次移动后的相同密文字母数量，从中比较，找出最多相同字母数量的那个移动次数，就是密钥的长度。（为什么会这样，后面会给出解释）解密Vigenère密码Vigenère的解密步骤续：

第二步：发现密钥。发现密钥的第一种方法现在我们假设我们确定了本例中密钥的长度是5，看一下第1、第6、第11个……这些字母，再看哪一个字母出现的频率最高，类似于对其进行Caesar密码攻击，找到其中的字母出现频率特性，这样就可以确定第一个向量的值，也就是k1；然后重复这个步骤，对第2、第7、第12个……字母进行相同的统计分析，得出第二个值k2；然后是对第3、第8、第13个……字母进行统计分析，……最终将所有的5个ki值全部找到，这样就得到了密钥向量中的所有值。解密Vigenère密码Vigenère的解密步骤续：

第二步：发现密钥。发现密钥的第二种方法首先我们要明白点积的概念和点积的计算。将所有的字母按照字母表顺序排列的统计频率小数点就是A0

＝（.082,.015，.028,……,.023,.001,.020,.001)。Ai就是A0右移i个位置的结果，例如A2＝（.020,.001,.082,.015……..,.023,.001）

这样A0

的点积等于A0×A0

＝(.082)2+

(.015)2+……=.066

将w*Ai计算出最大的一项,,,其中Ai依次从A0~A25中取值。一次一密密码一次一密密码

就是将要表达的明文全部用ASCII码表示成0和1的序列串，然后用和明文一样长的密钥（也是随机产生的0和1的序列串）进行异或运算，将运算结果传递给对方，形成密文。解密过程就是将密文和密钥同样的进行异或运算，得出原文的ASCII码表示，对照ASCII码表得出原文。因为这个随机的0和1的序列串非常难以做到随机性和很大值，所以代价很高，难点就是如何找到一个伪随机序列生成器，一般使用Geiger盖格计数管来产生，就是在很短的时间内计数滴答的声音，看它是偶数还是奇数，分别用0和1来代替。Enigma密码Enigma密码

最著名的轮转密码，德军在二战中始终使用的标准加密方法。于战争结束30年后才由英国政府解密档案，它在40年代被英国破解，一直没有公布。古典密码学作业古典密码学到此结束，相关课后作业需练习。