第2章古典密码技术1

第1章密码学概述 第2章传统密码技术

第3章分组密码第4章公钥密码体制第5章散列函数与消息鉴别第6章数字签名技术第7章密钥管理技术第8章身份鉴别技术第9章序列密码第10章密码技术应用附录课程主要内容第2章传统密码技术

本章主要内容替代密码

置换密码转轮机密码

古典密码的统计分析

单表替代密码分析多表替代密码分析

第2章传统密码技术2.1替代密码(代换密码）替代是古典密码中用到的最基本的处理技巧之一

；代换：将明文字母替换为其他字母，数字或符号。如果把明文看成是二进制的序列的话，那么代换就是用密文位串来替代明文位串。单表替代：用一个替代表决定代换规则单字母替代：明文的一个字符用相应的一个密文字符代替，如Caesar密码多字母替代：明文中的字符映射到密文空间的字符还依赖于他在上下文中的位置，如Hill密码，Playfair密码多表替代：代换规则由多个代换表组成周期：如维吉尼亚（Vigenere）密码，转子机（rotorMachine）非周期：一次一密（Onetimepadding)第2章传统密码技术第2章传统密码技术2.1.1单表替代密码 单表替代密码对明文中的所有字母都使用一个固定的映射（明文字母表到密文字母表）。设A＝{a0,a1,…,an-1}为包含了n个字母的明文字母表；

B＝{b0,b1,…,bn-1}为包含n个字母的密文字母表，单表替代密码使用了A到B的映射关系：

f：A→B，f(ai)＝bj

一般情况下，f

是一一映射，以保证加密的可逆性。

加密变换过程就是将明文中的每一个字母替换为密文字母表的一个字母。而单表替代密码的密钥就是映射f或密文字母表。

下面给出几种典型的单表替代密码。第2章传统密码技术一般单表替代密码 明文空间M和密文空间C都是26个英文字母的集合，密钥空间

K={π：Z26→Z26|π是置换}，是所有可能置换的集合。对任意π∈K，定义:

加密变换：eπ(m)=π(m)=c

解密变换：dπ(c)=π-1(c)=m，

π-1是π的逆置换。

【例2.1】设置换π的对应关系如下：abcdefghijklmnopqrstuvwxyzqwertyuiopasdfghjklzxcvbnm

试用单表替代密码以π为密钥对明文消息message加密，然后写出逆置换，并对密文解密。解：以π为密钥用单表替代密码对明文消息message加密，所得密文消息为：π(m)π(e)π(s)π(s)π(a)π(g)π(e)=dtllqut

2.1.1单表替代密码（续）π第2章传统密码技术

一般单表替代密码算法特点：密钥空间K很大，|K|=26!=4×1026，破译者穷举搜索计算不可行，1微秒试一个密钥，遍历全部密钥需要1013

年。移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。密钥π不便记忆。针对一般替换密码密钥π不便记忆的问题，又衍生出了各种形式单表替代密码。移位密码

把26个英文字母与整数0，1，2，…，25一一对应，如表2.1所示。

2.1.1单表替代密码（续）表2.1字母数字映射表第2章传统密码技术加密变换，E={E:Z26→Z26,Ek(m)=m+k(mod26)|

m∈M,k∈K}解密变换，D={D:Z26→Z26,Dk(c)=c－k(mod26)|

c∈C,k∈K}

解密后再把Z26中的元素转换成英文字母。

显然，移位密码是前面一般单表替代密码的一个特例。当移位密码的密钥k=3时，就是历史上著名的凯撒密码（Caesar）。根据其加密函数特点，移位密码也称为加法密码。2.1.1单表替代密码（续）恺撒密码

字母表：(密码本）密文：ABCDEFGHIJKLMNOPQRSTUVWXYZ明文：xyzabcdefghijklmnopqrstuvw

i：0123456789……..加密算法：C=E（p）=（p+3）mod（26）解密算法：P=D（C）=（C-3）mod（26）破译以下密文：密文：PHHWPHDIWHOWKHSDUWB明文：meetmeaftertheparty 第2章传统密码技术2.1.1单表替代密码（续）K=3第2章传统密码技术2.1.1单表替代密码（续）是替换密码的一个特例加密函数的形式为：

K={(k1，k2)|k1，k2∈Z26，gcd(k1，26)=1}

对任意m∈M，c∈C，k=(k1，k2)∈K，加密变换为：c=Ek(m)=k1m+k2(mod26)解密变换为：

m=Dk(c)=k1－1(c－k2)(mod26)仿射密码第2章传统密码技术【例2.3】设明文消息为china，密钥试用仿射密码对其进行加密，然后再进行解密。解：利用扩展的欧几里德算法（参见附录A.1.2）可计算出

加密变换为：

解密变换为：

明文消息对应的数字依次为2，7，8，13，0，用仿射密码对明文进行加密如下：

2.1.1单表替代密码（续）第2章传统密码技术密文消息为unwpc。而解密过程如下：

即恢复明文消息为china。

仿射密码要求gcd(k1,26)=1，否则就会有多个明文字母对应一个密文字母的情况。由于与26互素的整数有12个，故仿射密码密钥空间大小为|K|=12×26=312。

若将仿射密码的加密函数换为多项式函数时，即为多项式密码。密钥短语密码

选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就可构造出一个字母替代表。如密钥为key时，替代表如表2.2所示。2.1.1单表替代密码（续）第2章传统密码技术

表2.2密钥为key的单表替代密码

当选择上面的密钥进行加密时，若明文为“china”，则密文为“yfgmk”。显然，不同的密钥可以得到不同的替换表。2.1.2多表替代密码单表替代密码表现出明文中单字母出现的频率分布与密文中相同，多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母 出现的频率分布，每个映射是简单替代密码中的一对一映射,多表替 代密码将明文字母划分为长度相同的消息单元，称为明文分组，对 明文成组地进行替代，同一个字母有不同的密文，改变了单表替代 密码中密文的唯一性，使密码分析更加困难。

第2章传统密码技术多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉尼亚密码和Hill密码等均是多表替代密码。1.维吉尼亚密码维吉尼亚密码是最古老而且最著名的多表替代密码体制之一，与位移密码体制相似，但维吉尼亚密码的密钥是动态周期变化的。该密码体制有一个参数n。在加解密时，同样把英文字母映射为0－25的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合，因此可表示

加密变换定义如下：设密钥k=(k1,k2,…,kn),明文m=(m1,m2,…,mn),加密变换为：

其中ci=(mi+ki)(mod26)，i=1,2,…,n

Ek(m)=(c1,c2,…,cn),对密文c=(c1,c2,…,cn),解密变换为：

Dk(c)=(m1,m2,…,mn),其中mi=(ci

－ki)(mod26)，i=1,2,…,n2.1.2多表替代密码（续）第2章传统密码技术【例2.4】设密钥k=cipher，明文消息appliedcryptosystem，试用维吉尼亚密码对其进行加密，然后再进行解密。解：由密钥k=cipher，得n=6，密钥对应的数字序列为(2，8，15，7，4，17)。然后将明文按每6个字母进行分组，并转换这些明文字母为相应的数字，再用模26加上对应密钥数字，其加密过程如表2.3所示。

表2.3密钥为cipher的维吉尼亚密码加密过程

密文为：cxtsmvfkgftkqanzxvo。解密使用相同的密钥，但用模26的减法代替模26加法，这里不再赘述。2.1.2多表替代密码（续）第2章传统密码技术

置换密码又称为换位密码；置换密码通过改变明文消息各元素的相对位置，但明文消息元素本身的取值或内容形式不变；在前面的替代密码中，则可以认为是保持明文的符号顺序，但是将它们用其它符号来替代；置换密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。下面再给出几种典型的置换密码算法。2.2置换密码(PermutationCipher)第2章传统密码技术2.2置换密码最简单的例子是栅栏技术：明文：meetmeaftertheparty写为：mematrhpryetefeteat密文：mematrhpry

etefeteat第2章传统密码技术2.2置换密码

列置换密码把消息一行一行的写出，然后按列读取，但把列的次序打乱，列的次序就是密钥；密钥：

4312567明文：

attackpostponeduntiltwoamxyz密文：ttnaaptmtsuoaodwcoixknlypetz第2章传统密码技术2.2置换密码例：设m=6，设置密钥置换：加密的密钥置换解密的密钥置换123456351642K=123456361524K-1=明文组中的第5个字符与第4个字符进行置换对明文cryptography进行加密，首先将明文分成6个字母长的明文组：crypto|graphy；然后将每个明文组按密钥置换K重新排列：加密的密钥置换123456351642K=cryptoytcopr（crypto）K=graphyahgypr（graphy）K==YTCOPR=AHGYPR第2章传统密码技术2.2置换密码用编号表示内部引线的三转轮机(a)初始情况 （b）经过一次按键后的情况第2章传统密码技术2.3转轮机第2章传统密码技术2.4传统密码的统计分析在对密码进行安全分析时，一般假设密码分析者知道密码体制，这就是Kerckhoffs假设，密码分析重点在获取密钥。移位密码、仿射密码、维吉尼亚密码、置换密码等对己知明文攻击都是非常脆弱的。即使用惟密文攻击，大多数古典密码体制都容易被攻破。大多数古典密码体制都不能很好隐藏明文消息的统汁特征。下面就针对单表替代密码、多表替代密码和Hill密码来介绍利用英文语言的统计特征和密码特点，运用惟密文攻击或已知明文攻击等方式破译古典密码的基本方法。第2章传统密码技术2.4.1单表替代密码分析

本质上，密文字母表是明文字母表的一种排列。但企图使用计算机穷举一切密钥来破译密钥词组替代密码也是计算不可行的。穷举不是攻击密码的惟一方法，密码分析者便可利用语言的统计特性进行分析。如果明文语言的这种统计特性在明文中有所反映，密码分析者便可通过分析明文和密文的统计规律而破译密码。通过对大量英文语言的研究可以发现，每个字母出现的频率不一样，e出现的频率最高。如果所统计的文献足够长，便可发现各字母出现的频率比较稳定。如表2.4所示（表中字母出现频率为字母出现次数除以文本字母总数）。第2章传统密码技术表2.426个英文字母出现频率统计表

2.4.1单表替代密码分析（续）字母出现频率字母出现频率a0.0856n0.0707b0.0139o0.0797c0.0279p0.0199d0.0378q0.0012e0.1304r0.0677f0.0289s0.0607g0.0199t0.1045h0.0528u0.0249i0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m