2.3 古典密码

古典密码是密码学的渊源，这些密码大都比较简单，可用手工或机械操作实现加解密，现在已很少采用了。然而，了解这些密码的原理，对于理解、分析现代密码和构造新的密码都是十分有益的。我们将从密码编码和密码分析两个方面对古典密码进行介绍。

古典密码分析的两个基本方法是穷举法和统计分析法。

单钥加密的古典算法有简单代换、多表代换、同态代换、多码代换、乘积密码等多种，是计算机出现之前的基于字符的密码。密码变换的基本手段是字符之间互相代替或者相互之间换位。现代的密码算法是对二进制位而不是对字母进行变换。大多数好的算法仍然是代替和换位的组合。

根据密码变换的规则，可以把古典密码分为代替密码（Substitution cipher）和置换密码（Permutation cipher）两大类。代替密码就是明文中的每一个字符被替换成密文中的另一个字符，接收者对密文做反向替换就可以恢复出明文。置换密码，又称换位密码（Transposition cipher），明文的字母保持相同，但顺序被打乱了。

2.3.1 古典密码的数学基础

在给出古典密码算法之前，先回顾一下算法中用到的一些数学概念。

2.3.1.1 同余

给定任意整数a和q，以q除a，余数是r，则可以表示为a = sq + r，0≤r＜q，其中s = ㊣a/q㊣，表示不大于a/q的最大整数。定义r为a mod q的剩余，记为r ≡ a mod q。若整数a和b有（a mod q）=（b mod q），则称a与b在mod q下同余。对于满足[r] = {a|a = sq+r，s∈Z}的整数集称为同余类。

对给定的余数r和自然数q>0，集合{a| a ≡ r mod q}称为r模q的剩余类，它包含除以q后余数为r的所有整数。

对模q的每个剩余类恰好选一个代表，它们构成一个完全剩余系。模q的最小非负完全剩余系是集合{0，1，2，…，q-1}。

2.3.1.2 模运算

在集合{0，1，2，…，q-1}上可以进行算术运算，就是所谓的模运算。

定义加法和乘法运算如下：

模加：[（a mod q）+（b mod q）] mod q =（a+b）mod q

模减：[（a mod q）-（b mod q）] mod q =（a-b）mod q

模乘：[（a mod q）×（b mod q）] mod q =（a×b）mod q

模运算有下述性质：

（1）若q|（a-b），则a ≡ b（mod q）

（2）（a mod q）=（b mod q）意味a ≡ b mod q

（3）对称性，a ≡ b mod q等价于b ≡ a mod q

（4）传递性，若a ≡ b mod q且b ≡ c mod q，则a ≡ c mod q

2.3.1.3 逆元

类似普通的加法，在模运算中，每个数也存在加法逆元，或者称为相反数。一个数 x 的加法逆元y是满足x+y ≡0 mod q的数。

例如，q = 8，2 + 6 ≡ 0 mod 8，在模8的情况下2和6就互为加法逆元。

在通常的乘法中，每个数存在乘法逆元，或者称为倒数。在模q的运算中，一个数 x 的乘法逆元y是满足x×y ≡1 mod q的数。但是并不是所有的数在模q下都存在乘法逆元。

例如3×3 ≡1 mod 8，在模8的情况下3的乘法逆元是3。

2.3.1.4 Zq中的整数模运算性质

定义集合Zq为小于q的所有非负整数集合：Zq= {0，1，2，…，q-1}。该集合也可看做模q的余数集合。如果在该集合上实行模运算，Zq中的整数保持如下性质：

（1）交换律：（w + x）mod q =（x + w）mod q

（w×x）mod q =（x×w）mod q

（2）结合律： [（w + x）+ y] mod q = [w +（x + y）] mod q

[（w×x）×y] mod q=[w ×（x×y）] mod q

（3）分配律： [w ×（x+y）] mod q=[（w×x）+（w×y）] mod q

（4）恒等：（0 + w）mod q = w mod q

（1×w）mod q=w mod q

（5）对每一个w∈Zq，存在z，使得w + z ≡ 0 mod q，z称为w的加法逆元，记为-w。

（6）若a与q互素，如果（a×b）mod q =（a×c）mod q，那么b ≡ c mod q。

（7）如果q是一个素数，对每一个w∈Zq，都存在z，使得w×z ≡ 1 mod q，z称做w的乘法逆元w-1。

模26的最小非负完全剩余系，是模26的余数集合为{0, 1, 2, …, 25}。可以把字母表与模26的余数集合等同，参见表2.2，在此基础上对字符进行运算。

2.3.1.5 逆阵

设A =（aij）为一个l×m矩阵，B =（bjk）为一个m×n矩阵，可以定义矩阵乘法AB =（cik）（1≤i≤l，1≤k≤n）为如下形式：

矩阵乘法满足结合律，（AB）C = A（BC），但不满足交换律，AB=BA并不成立。

m×m矩阵中，有一个特殊矩阵，其主对角线的值为1，其余均为0，称其为单位矩阵Im。如2×2单位矩阵具有如下形式：

m×m矩阵A的逆矩阵A-1如果存在，则应满足AA-1 = A-1A = Im，并且如果A-1存在，其一定是唯一的。

设A=（aij）为一个m×m矩阵，对1≤i≤m，1≤j≤m，定义Aij为从矩阵A删除第i行，第j列后的新矩阵。A的行列式的值，一般记为detA。

一个实矩阵可逆当且仅当其所对应的行列式的值非零。

矩阵K在模26情形下存在可逆矩阵的充分必要条件是gcd（detK,26）= 1，gcd（a,b）表示a和b的最大公因子。

设K =（kij）为一个定义在Zn上的m×m矩阵，若K在Zn上可逆，则有K-1 =（detK）-1K*，这里K*为矩阵K的伴随矩阵。伴随矩阵K*其第i行，第j列的取值为（-1）i+jdetKji，Kji为从矩阵K删除第j行，第i列后的新矩阵。

2.3.2 代替密码

一个代替密码由代替规则、密文所用字符、明文中被代替的基本单位三个因素决定。通常假设明文和密文所用的字符相同，根据明文中被代替的基本单位可以把代替密码分为单字母密码和多字母密码。

单字母密码（Monoalphabetic cipher）又称简单代替密码（Simple substitution cipher），明文的一个字符用相应的一个密文字符代替，而且密文所用的字符与明文所用字符属同一语言系统。单字母密码又可划分为单表代替密码和多表代替密码。就是在对明文消息的代替过程中使用单一代替表还是多个代替表。

多字母密码（Polyalphabetic cipher）的明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置，也即明文的多个字符用相应的多个密文字符代替。

2.3.2.1 单表代替密码

单表代替密码就是将明文字母表M中的每个字母用密文字母表C中的相应字母来代替。典型的单表代替密码有：移位密码（Shift cipher）、乘数密码（Multiplicative cipher）、仿射密码（Affine cipher）、多项式密码（Polynomial cipher）、密钥短语密码（Key word cipher）。

下面分别对这些典型的单表代替密码进行介绍。

1．移位密码

设P = C = K = Z26，这里P代表明文空间。对k∈K，定义

当k = 3时，为恺撒密码。设明文为cipher，经恺撒密码加密的密文为FLSKHU。

实际算法为：∀x∈P有 e3（x）= x + 3（mod 26）= y，同时有，d3（y）= y -3（mod 26）。

给定加密的消息：PHHW PH DW WKH SDUWB。

由于（a）加解密算法已知；

（b）可能尝试的密钥只有25个（不包括0）。

通过强力攻击可以得到明文：meet me at the party。

移位密码很容易受到唯密文攻击。

2．乘数密码

加密函数取形式为ek（x）= kx（mod 26），k∈Z26，要求唯一解的充要条件是gcd（k, 26）= 1。该算法描述如下：

设

P = C = Z26，K = {k∈Z26 |gcd（a, 26）= 1}，

对k∈K，定义

ek（x）= kx（mod 26）

dk（y）= k-1y（mod 26），（x,y∈Z26）

当k = 9，对应的密码表为

设明文为cipher，经过加密得到密文为SUFLKX。

对于乘数密码，当且仅当a与26互素时，加密变换才是一一映射的，若a和26不互素，则会有一些明文字母被加密成相同的密文字母，而且不是所有的字母都会出现在密文字母表中。因此a的选择有11种：a = 3，5，7，9，11，15，17，19，21，23，25，可能尝试的密钥只有11个。

3．仿射密码

加密函数取形式为ek（x）= ax+b（mod 26），其中k∈K，K={（a,b）∈Z26×Z26|gcd（a, 26）=1}。该算法描述为：

设P = C = Z26

对k =（a,b）∈K，定义

ek（x）= ax + b（mod 26）

dk（y）= a-1（y-b）（mod 26），（x,y∈Z26）

q=26时，可能的密钥是26×12-1=311个。

例如，设k =（7，3），注意到7-1（mod 26）=15，加密函数是ek（x）= 7x + 3，相应的解密函数是dk（y）=15（y-3）=15y-19，易见

dk（ek（x））= dk（7x + 3）=15（7x + 3）-19 = x + 45-19 = x（mod 26）

若明文为pku，首先把字母p，k，u转换成为数字15，10，20，然后加密：

解密过程为：

4．密钥短语密码

仿射密码虽然比移位密码和乘数密码的密钥空间增大了许多，但还是不能抵抗强力攻击。密钥短语密码是以西文单词为密钥的换字表，例如：取university为密钥，首先找出其中发生重复的字母，去掉重复字母i，成为universty，其次，字母一共10个，从第11个字母开始，用universty按顺序进行代替配置，然后把其余17 个字母按自然顺序接在后面。这样得到以university为密钥的换字表，参见表2.4。

5．任意的单表代替密码算法

当然，也可以构造非自然顺序配置的换字表，明文字母与代替他的密文字母毫无关联，那么整个换字表就是它的密钥，参见表2.5。

设P = C = Z26，K是由26个符号0，1，…，25的所有可能置换组成。对任意π ∈K，定义e π（x）= π（x）= y且d π（y）= π -1（y）= x，π -1是π的逆置换。

置换π的表示如下：

任意的单表代替密码的密钥空间K很大，置换数目达26!≈4×1026，破译者进行穷举搜索是不行的，然而，可用统计的方式破译它。

实际上，移位密码、乘数密码、仿射密码算法都是任意单表代替密码的特例。

6．单表代替密码分析

从以上介绍可以看到，密码设计是利用数学来构造密码。而密码分析除了依靠数学、工程背景、语言学知识外，还要靠经验、统计、测试、眼力、直觉判断力……甚至有时还要靠点运气。密码破译在原则上遵循观察与经验，在方法上采用归纳与演绎，采取的步骤是分析、假设、推测和证实。语言的三大统计特性：语言的频率特征、连接特征和重复特征是进行密码破译的重要依据。

（a）语言的频率特征

在各种语言中，各个字母的使用次数是不一样的，有的偏高，有的偏低，这种现象叫偏用现象。对英文的任何一篇文章，一个字母在该文章中出现的次数称为这个字母（在这篇文章中）的频数。一个字母的频数除以文章的字母总数，就得到字母的使用频率。

美国密码学家William Friedman在调查了大量英文资料后，得出英文字母的普遍使用频率，参见表2.6。

从表中可以看出，不同字母的使用频率是不同的，英文字母e的使用频率最高，而z等字母的使用频率最低，根据字母的使用频率，可以对它们进行分类，如表2.7所示。

除了普遍的使用频率特征外，还有开头结尾的特征。有些文章的开头和结尾受到固定格式的限制，有时文章中间的某些特定部位，某些字母也会出现较高的使用频率。

使用频度最高的前30个双字母如表2.8所示。

使用频度最高的前20个三字母如表2.9所示。

此外，还有如下一些特征：

THE的使用频率最高，是ING的三倍，若把the去掉，t在第II类中排在最后，h会降为第III类，th和he也不是常出现的字母组了。一半的单词以e，s，d，t结尾，一半的单词以t，a，s，w开头，y的使用频率90%都集中在单词的结尾。

（b）语言的连接特征

语言的第二个特征是连接特征，连接特征有如下几种：

● 后连接：字母q后面除了连接省略号外，几乎百分之百连接着u。

● 前连接：有些字母的前面总喜欢连接那么少数几个字母，如字母x的前面总是i和e，很少是o和a。

● 间断连接：在e和e之间，r的出现频率最高。

（c）语言的重复特征

两个字符以上的字符串重复出现的现象，叫做语言的重复特征。例如英语中th，tion，tious等就是重复出现的字符串。1863年，普鲁士军官Kasiski利用这一现象提出了一种重码分析法。

为了说明分析的过程，在这里给出一个例子。假设需要解密的密文是：

QRLLIQQPFVICXPFMTPZWRFNFOTFLPYWIGQPQHICQRGIVAKZWIQIBORGZWPFMQ PFZWIOGVIGFCHIVYIGQIJIGCFLILCGIBRXHIZWOVQOBCFCXKQPQPFZRPZPOFXRLNZWI CAPXPZKCZXICQZZOGICVZWIXCFMRCMIOBZWIOGPMPFCXZISZPQJIGKVIQPGCAXIARZ FOZIQQIFZPCX

这份密文一共206 个字母，先统计出密文中每个字母使用的次数，将密文字母按频数从多到少排列，参见表2.10。

将这种统计规律与表2.6和表2.7比较，可以得出的结论是：密文字母中的I可能相当于明文中的e，ZPQCFGOX可能对应于第II类字母集{t，a, o, i, n, s，h，r}中的某一个，WRV可能对应于第III类字母集{d, l}中的某一个，LMBKAH可能对应于第IV类字母集{c，u，m，w，f，g，y，p，b}中的某一个，NJYTSDEU可能对应于第V类字母集{v，k，j，x，q，z}中的某一个。

这里最常见的双字母组合ZW，出现了8次，把Z猜测其为T，W对应为H，I猜测其为E。密文中的ZWI很可能就是THE。次常见的双字母组合为WI和PF，两者均出现了6次，因为已经把WI猜测为HE，使用频度为第三的双字母组合为IN，所以把PF猜测为IN。

至此，有如下结果：

这样一来，QCGOX可能对应于第II类字母集{a, o, s，h，r}中的某一个，字母组合ZWIQI与these相似，可以把Q猜测为S。字母组合TPZW与with类似，所以可以把T猜测为W。字母组合IQQIFZPCX与essential相似，据此把C猜测为A，X猜测为L。字母组合CFCXKQPQ与analysis类似，因此，可以把K猜测为Y。字母组合CAPXPZK与ability类似，据此把A猜测为B。

至此，分析结果如下：

按着，发现字母组合ZWPFM与things类似，据此把M猜测为G。字母组合XCFMRCMI与language类似，据此把R猜测为U。字母组合VICXPFM与dealing类似，据此把V猜测为D。

至此，分析结果如下：

然后，发现字母组合QRLLIQQ与success类似，据此把L猜测为C。字母组合GICV与read类似，据此把G猜测为R。字母组合LCGIBRX与careful类似，据此把B猜测为F。字母组合HICQRGIV与measured类似，据此把H猜测为M。字母组合HIZWOVQ与methods类似，据此把O猜测为O。

继续分析，更进一步把JIGK猜测为very，把YIGQIJIGCFLI猜测为perseverance，把RFNFOTF猜测为unknown，把ZISZ猜测为text。

这样就得到如下的完整明文：

Success in dealing with unknown ciphers is measured by these four things in the order named：perseverance，careful methods of analysis，intuition，luck. The ability at least to read the language of the original text is very desirable but not essential.

其中文意思是：能否成功地破译未知的密码，在于以下4个因素，它们依次为：锲而不舍的精神，周密的分析方法，直觉和运气。至少能阅读原文语言的能力是十分需要的，但不是主要的。这段话是帕克· 希特的《军事密码破译手册》的开场白，揭示了密码分析的四要素。

根据以上信息，现在就可以给出这个加密过程所使用的加密变换的明密文字母的对应表，如表2.11所示。

观察到VWXYZ在字母中以4间隔开，所以把密文字母按从上到下，从左到右的顺序写到一个四行的表格中。

字母DEU并没有在密文中出现，但通过观察字母排列的规律，ciphers的意思是密码。其他字母刚好是按字母顺序的一个排列，这样就可以把空缺的字母填到空格中。看到这个密码实际上是在以ciphers为密钥字的密钥短语密码的基础上又进行了置换。

单表密码破译的过程实际上是一个假定，推翻，再假定，再推翻，直至破译的过程，可以按照以下步骤进行。

（1）对密文字母的频数、使用频率和连接次数进行统计。

（2）根据了解到的密码编制人员的语言修养，以及手中掌握的密文的统计规律，多方比较，对明文的语种和密码种类做出假定。

（3）将假定语种的字母频率与密文字母频率进行比较。

（4）首先找出密文中频率最高的字母。

（5）根据字母的频率特征、连接特征、重复特征，从最明显的单词或字母开始，试探进行。

（6）对破译的经验进行总结。

简单代替密码由于使用从明文到密文的单一映射，所以明文字母的单字母出现频率分布与密文中相同，即使使用任意单表代替的方法使密钥空间扩大到强力攻击难以进行的程度，仍然可以较容易地通过使用统计分析法进行唯密文的攻击。为了对抗频率分析，出现了多名或同音代替密码、多表代替密码和多字母代替密码，它们都是通过不同的途径试图减少密文所保留的明文的统计特性。

2.3.2.2 多名代替密码

与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。例如，A可能对应于5，12，21，B可能对应于7，9，18，27。当对字母的赋值个数与字母出现频率成比例时，密文符号的相关分布会近似于平的，可以挫败频率分析。然而，若明文字母的其他统计信息在密文中仍很明显时，那么同音代替密码仍然是可破译的。

2.3.2.3 多表代替密码

单字母出现频率分布与密文中相同，多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布，每个映射是简单代替密码中的一对一映射。多表代替密码是以一系列（两个以上）代换表依次对明文消息的字母进行代换，可以分为非周期多表代替密码和周期多表代替密码。非周期多表代替密码的代换表是非周期的无限序列，例如一次一密密码，对每个明文每次采用不同的代换表。周期多表代替密码的代换表个数有限，重复使用。典型的多表代换密码有：维吉尼亚密码（Vigenére cipher）、博福特密码（Beaufort cipher）、滚动密钥密码（Running-key cipher）、弗纳姆密码（Vernam cipher）、转轮密码机（Rotor machine）。

1．维吉尼亚密码

该密码实际上是贝拉索在1553 年发明的，19 世纪时被误认为是由法国密码学家维吉尼亚发明的，因此现在称为维吉尼亚密码，它是一种多表移位代替密码。

设d为一固定的正整数，d个移位代换表π =（π 1，π2，…，πd）由密钥序列K =（k1, k2, …, kd）给定，第i + td个明文字母由表πi决定，即密钥ki决定：

ek（xi+td）=（xi+td + ki）mod q = y

dk（yi+td）=（xi+td - ki）mod q = x

例如：q = 26，x = polyalphabetic cipher，K = RADIO

明文x=polyalphabeticcipher

密钥k=RADIORADIORADIORADIO

密文y=GOOGOCPKIPVTLKQZPKMF

我们称k =（k1, k2, …, kd）是长为d的密钥字，密钥空间大小为26d，即使对于很小的d，例如当d=5，265=1.1×107，使用穷举密钥法也需要很长时间。

在Vigenére密码中，一个字母可被映射为d个可能的字母之一，所以分析起来比单表代换更困难，但算法依然保留了字符频率的某些统计信息，分析的第一步是确定密钥字的长度d，确定d的方法最常用的有两种。一种叫Kasiski测试法，是普鲁士军官Kasiski在1863年提出的一种重码分析法，另一种方法是William Friedman在1920年提出的重合指数法（Index of coincidence）。

对于明文To be or not to be that is the question（生存，还是死亡，这是个问题），使用Vigenére密码加密，密钥字取为run。

密钥：runrunrunrunrunrunrunrunrunrun

明文：tobeornottobethatisthequestion

密文：KIOVIEEIGKIOVNURNVJNUVKHVMGZIA

观察到密文字母串KIOV在密文中重复了两次，后一个相当于前一个向后移动了9个字母的距离，密文字母串NU也在密文中重复了两次，后一个相当于前一个向后移动了6个字母的距离，密钥字RUN的长度为3，9和6都是3的倍数。KIOV的重复是因为密钥字母串RUNR的重复与明文字母串tobe的重复正好合拍。重复明文字母串的距离正好是密钥长度的倍数。合拍现象是意大利的乔瓦·尼·波塔于1602年首先发现的。但他没有很好地利用这个现象，直到200年后，Kasiski抓住了这个现象，所以Vigenére密码被安全地使用了200年。间距是密钥长度整数倍的相同明文子串对应相同的密文，反过来，密文中两个相同子串对应明文相同的可能性很大，这就是重码分析法，这里面有偶然重复和真重复，但它们之间距离的因子可能就是密钥长度。Kasiski提出，对一份用周期性多表密码加密的密文，确定其中所有重复出现的字母串，计算它们之间的距离，并对这些距离进行因子分解，出现频率较高的因子很可能是密钥的长度。这就是Kasiski实验。

为了解释重合指数法，先来看一个概率问题，设x是一个长度任意的英文字母串，即x =x1x2x3…xm，其中xi是字母，m不确定。现在问：从x中随机地抽取两个字母，它们为相同字母的概率是多少？答案是26 ×（1/26）2 = 1/26 = 0.0385。如果x是一篇随便选取的英语文章，令p1表示a出现的概率，p2表示b出现的概率，……，p26表示z出现的概率，那么，抽到两个相同字母的概率就是p12 + p22 + … + p262 = 0.0687。这说明了随机的字母串与作为语言的明文字母串之间的差别。一个事实是对于单表代替密码加密得到的密文，0.0687这个数据不变。我们可以把0.0687作为标准来检验一个密文是不是单表代替的加密产物。

设y是一个长度为n密文，即y = y1y2y3…ym，其中yi是密文字母，同样来求从中抽到两个相同字母的概率是多少？为此，设NA为字母A在这份密文中的频数，设NB为字母B在这份密文中的频数，依次类推。从n个密文字母中抽取两个字母的方式有Cn2 = n（n-1）/2，而其中NA个A组成一对A的方式有：

2CNA= NA（NA -1）/2

于是从y中抽到两个字母都为A的概率为[NA（NA -1）]/[n（n-1）]，因此，从y中抽到两个相同字母的概率为：

这个数据称为这份密文的重合指数。根据概率论中的大数定律，如果y是用单表加密的，那么当n较大时，重合指数很可能接近于0.0687。假设密钥字的长度是d，把密文一行一行写在一个有d个列的表格里，对各列密文字母串计算相应的重合指数，以此为根据判断d的假设是否正确。

通过Kasiski实验、重合指数和直觉判断，最终可以确定d。

2．滚动密钥密码

对于周期代换密码，当密钥的长度 d 和明文一样长时，就成为滚动密钥密码。Vigenére本人建议密钥与明文一样长。一种设置密钥的方法是先设置一个密钥字，然后用明文来做加密的密钥。下面的例子中beijing为密钥字。

密钥：beijingmeetatnineinthe

明文：meetatnineintheevening

密文：NIMCIGTURIBNMUMRZMABUK

因为滚动密钥密码工作在流密码状态，根据密钥字可以把先收到的密文恢复成明文，然后就可以用已收到的密文对应的明文作为密钥字来解密接下来收到的密文。

即使采用这个方案，它也是易受攻击的，因为密钥和明文具有同样的频率分布特征。

3．弗纳姆密码

1918年，Gillbert Vernam建议密钥与明文一样长并且与明文没有统计关系，他采用的是二进制数据：

加密：Ci = Pi ⊕ Ki

解密 Pi = Ci ⊕ Ki

其中，Pi是明文的第i个二进制位，Ci是密文的第i个二进制位，Ki是密钥的第i个二进制位，密文是明文和密钥逐位异或得到的。

弗纳姆密码的核心是构造和消息一样长的随机密钥。尽管周期很长增加了破解的难度，但是如果密文足够多，或者使用已知的明密文序列，该方案是可以破解的。

4．转轮密码机

加密和解密机的发明和商业化促进了密码学的发展，直到19世纪，密码机还是机械的，随着电传打字机的出现，电动密码机开始在保密通信中大显身手。在第二次世界大战中，转轮密码机的使用相当普遍。如日本制造的紫密（Purple）、德国制造的恩尼格玛（Enigma）和瑞典制造的哈格林密码机（Hagelin），美国军方称为M-209。

转轮密码机实际上是多表代替密码的一种实现，主要利用机械运动和简单电子线路。它有一个键盘和若干转轮，每个转轮由绝缘的圆形胶板组成，胶板正反两面边缘线上有金属凸块，每个金属凸块上标有字母，字母的位置相互对齐。胶板正反两面的字母用金属连线接通，形成一个代替运算。不同的转轮固定在一个同心轴上，它们可以独立自由转动，每个转轮可选取一定的转动速度。例如，一个转轮可能被导线连通以完成用F代替A，用U代替B，用L代替C，等等。为了防止密码分析，有的转轮密码机还在每个转轮上设定不同的位置号，使得转轮的位置、转轮的数量、转轮上的齿轮结合起来，增大机器的周期。

德国人使用的恩尼格玛实现了一个非常复杂的可变代替密码，它使用一系列的转轮，每个转轮的内部连线各不相同。一个转轮的一个输入-输出连线状态给定了一种代替表，每加密一个字母，转轮转一格，输入-输出连线状态就跟着发生了变化，代替表就相应变一个。恩尼格玛共有3个转轮，在每个转轮的边缘上，标记着26个英文字母，每个转轮的26种内部连线状态可以通过这些字母的26种位置来表示。经过巧妙的设计，每次转轮旋转的时候，它都会停留在这26 种位置之一。假设从转轮的左面“输入一个字母信号”，经过转轮内部特定走向的导线连接后，输出的字母信号也就不再对应刚才输入的字母了。输入的字母K，经过转轮内部的导线，最终从转轮的另一侧输出，并变成了R。在转轮组内，转轮相互接触的侧面之间，都有相对应的电路触点，可以保证转轮组的内部构成通路。于是，输入的字母K，经过第一个转轮，变成输出字母R；之后这个R进入第二个转轮，假设它又变成了C；而后，这个C再进入第三个转轮，假设又变成了Y。这样，初始字母K历经层层变换，变成了谁也认不出来的Y。3个转轮的变换相当于连续使用了3个代替表，因此，它们合起来连续加密的总效果就是3个转轮各自能力的乘积。每个转轮都有26个位置，3个转轮组合起来，就能生成26×26×26=17576种不同的变化。图2.4给出了恩尼格玛转轮组的示意图，为了简单，内部只画了三组连线。

2.3.2.4 多字母密码

不同于前面介绍的代替密码都是每次加密一个明文字母，多字母代替密码将明文字符划分为长度相同的消息单元，称为明文组，对字符块成组进行代替，这样一来使密码分析更加困难。多字母代替的优点是容易将字母的自然频度隐蔽或均匀化，从而有利于抗击统计分析。因为可以用矩阵变换方便地描述多字母代换密码，有时又称其为矩阵变换密码。典型的多字母密码有Hill密码和Playfair密码。

1．Playfair密码

Playfair密码将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。Playfair密码基于一个密钥词构成的5×5变换矩阵，I与J视为同一字符。

本例中使用的密钥词是cipher。填充矩阵的方法是先将密钥词（去掉重复字母）从左到右，从上到下填在空格中，再将剩余的字母按字母表的顺序从左到右，从上到下填在剩余的空格中。按成对字母加密的规则：

（1）如果该字母对中的两个字母是相同的加分隔符，比如x，例如balloon可以先变成ba lx lo on。

（2）如果该字母对落在矩阵的同一行，取它们右边的字母来代替，每行最右边的字母由最左边的字母代替，例如he变成EC。

（3）如果该字母对落在矩阵的同一列，取它们下面的字母来代替，每行最下边的字母由最上面的字母代替，例如dm变成MT。

（4）如果该字母对落在矩阵的其他位置，取交叉位置的字母代替，例如kt变成MQ，OD变成TR。

下表给出了Playfair密码的一些加密实例。

双字母替代比单字母替代能减少明文的结构仍保留在密文中的程度。首先，虽然仅有26个字母，Playfair有26×26=676种字母对组合，因此识别各种双字母组合困难得多，此外，字符出现概率一定程度上被均匀化，基于字母频率的攻击比较困难，但依然保留了相当的结构信息。

2．Hill密码

Hill密码是基于矩阵的线性变换，假设K是一个m×m矩阵，在Z26上可逆，即存在K-1使得：KK-1=I（在Z26上），对每一个密钥K，定义

eK（x）= xK（mod 26）和 dK（y）= yK-1（mod 26）

这里，明文与密文都是m元的向量（x1, x2, …, xm），（y1, y2, …, ym），Z26为模26的最小非负完全剩余系。在这个集合上的可逆矩阵Am×m是指行列式detAm×m的值 ∈，它为Z26中全体可逆元的集合，即= {a∈Z26|（a,26）=1} = {3，5，7，9，11，15，17，19，21，23，25}。

例如，当m = 2时，明文元素x =（x1, x2），密文元素y =（y1, y2）

（y1, y2）=（x1, x2）K

若，可得

若对明文hill加密，它可分成2个元素hi，ll，分别对应于[7 8]，[11 11]，有

于是对hill加密的结果为XIYJ。

为了解密，可计算

因此，得到了正确的明文hill。

Hill密码完全隐藏了字符（对）的频率信息，采用唯密文攻击希尔密码是很难攻破的。但线性变换的安全性很脆弱，易被已知明文攻击击破。

对于一个m×m的Hill密码K，假定有m个明文-密文对，明文和密文的长度都是m，可以把明文和密文对记为：Pj =（p1j, p2j, …, pmj）和Cj =（C1j, C2j, …, Cmj），

Cj =PjK，1≤ j≤m

定义m×m的方阵X =（Pij），Y =（Cij），得到Y=XK mod 26，K=X-1Ymod 26，若X不可逆，我们总可以找到一个可逆的X。

假设明文“friday”经过2×2的Hill密码加密为密文“PQCFKU”，因此，我们有[5 17]K =[15 16]，[8 3]K=[2 5]，[0 24]K=[10 20]。那么由前两个明密文对可得：

因此，

此结果可以由第三个明密文对来验证。

2.3.3 置换密码

在换位密码中，明文的字母保持相同，但顺序被打乱了。由于密文字符与明文字符相同，密文中字母的出现频率与明文中字母的出现频率相同，密码分析者可以很容易地由此进行判别。虽然许多现代密码也使用换位，但由于它对存储要求很大，有时还要求消息为某个特定的长度，因而比较少用。把明文按行写入，按列读出是一种简单的换位方法。置换密码完全保留字符的统计信息，但使用多轮加密可提高安全性。

2.3.4 古典密码算法小结

根据前面的介绍，可以给出如图2.5所示的古典密码分类汇总图。