2.2　古典密码系统

密码技术源远流长，人类自从有了战争，就有了保密通信的需求。古埃及人、古希腊人在战争中设计了很多经典的密码算法。虽然大部分古典密码系统都存在安全漏洞，容易被破解。但是一些设计思想在现代密码学中被广泛采用，是现代密码系统的基石。

代换或代替（Substitution）和置换（Permutation）是古典密码系统中广泛使用的两种运算。所谓代换，指的是比特、字母、比特组合或者字母组合等明文中的元素，被映射成完全不同的另外一个元素。而所谓置换，指的是将明文中的元素重新排列，或者说，打乱明文中各个元素的排列顺序。

2.2.1　单表代换密码

单表代换密码是以代换运算为核心的一种密码算法，这种密码算法采用被称为明、密文字母映射表的表结构进行加解密运算。明、密文字母映射表反映了明文字母和密文字母之间的映射关系。在加密运算时，依据明、密文字母映射表，明文中的一个字母在密文中被一个特定字母替代。解密运算同样以明、密文字母映射表为基础，将密文中的字母映射为明文中的字母。凯撒密码（Caesar Cipher）是最具代表性的一种单表代换密码。

凯撒密码据传是古罗马凯撒大帝用来保护军事信息的密码系统。图2-2是一个典型的凯撒密码明、密文字母映射表。

对图2-2的映射表进行分析，将从A到Z的26个字母组成完整的字母表，可以看出明文中的字母在密文中被映射为字母表中该字母循环右移3位后对应的字母，例如，字母A在密文中对应于字母D，字母Y在密文中对应于字母B。

依据图2-2的凯撒密码明、密文字母映射表，一条消息的明、密文对应关系如下所示。

明文：ATTACK AT NINE THIRTY

密文：DWWDFN DW QLQH WKLUWB

对密文进行解密时，需要依据明、密文字母映射表将密文字母还原为明文字母。

从现代密码学的角度看，在凯撒密码系统中，加密和解密的密钥是字母偏移的位数，凯撒密码可以在[1,25]区间选取偏移位数。如果以数字1至26依次表示字母A至Z，以pi表示明文字母，ci表示对应的密文字母，k表示密钥（1≤k≤25），凯撒密码的加密算法可以表示为：

ci=E(k,pi)=(pi+k)mod 26

相对应的凯撒密码的解密算法可以表示为：

pi=D(k,ci)=(ci–k+26)mod 26

破解凯撒密码并不困难。凯撒密码的密钥空间为[1,25]区间的整数。采用穷举法逐个尝试可能的密钥。由于密钥空间中总共只有25个密钥，因此可以很快找到正确的密钥。

并不是所有单表代换密码都像凯撒密码一样不堪一击。图2-3是一个普通单表代换密码的明、密文字母映射表。该单表代换密码的明文字母和密文字母之间不像凯撒密码那样存在固定的映射关系。

按照图2-3的明、密文字母映射表，一条指令的明、密文对应关系如下所示。

明文：ATTACK AT NINE THIRTY

密文：KCCKQJ KC FEFO CUEWCX

对图2-3中的单表代换密码进行分析，在此密码系统中密钥是完整的明、密文字母映射表。密钥可以是26个字母按序排列的各种组合。如果采用穷举法进行破解，最多需要尝试26!次，约为4×1026次，可见破解的难度非常大。

对于图2-3所示的单表代换密码，统计分析法是破解的理想方法。单表代换密码的重要特点是明文字母在加密时由一个固定的密文字母代替。语言中的每个字母都有一些特性，例如，英文字母h在使用时经常出现在字母e的前面，但是几乎不会出现在字母e的后面。如果字母h在加密时被字母u替代，则字母u在密文中的特性与字母h在明文中的特性相同。统计分析法就是对密文中各个字母的特性进行分析，并依据已知的明文字母特性，确定明、密文之间的映射关系。

密码分析使用的语言特性主要包括语言的频率特征、语言的连接特征及语言的重复特征。语言的频率特征是在密码分析中使用最多的一种语言特性。统计字母的使用频率的方法是将字母在文章中出现的次数除以文章中字母的总数。英语中26个字母的使用频率不同，有的偏高，有的偏低。虽然一个字母在不同文章中的使用频率存在差异，但是综合大量文章进行分析，各个字母的使用频率相对稳定。

图2-4是英文字母使用频率的分类情况。研究人员对大量的英语文章进行统计，按照字母使用频率的差异，将26个英文字母划分为极高使用频率、较高使用频率、中等使用频率、较低使用频率和低使用频率五个类别。例如，字母E属于极高使用频率类，统计结果表明字母E的使用频率在12.7%左右，远远高于其他字母。较高使用频率类中字母的使用频率处于6%至9%之间，包括字母T、A、O、I、N、S、H和R，这8个字母的使用频率依次降低，其中，字母T的使用频率最高，为9%左右，字母R的使用频率最低，为6%左右。

不仅每个字母的使用频率存在差异，英文中的字母组合也存在使用频率的差别。使用频率最高的30个双字母依次是：

TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA

ND OU EA NG AS OR TI IS ET IT AR TE SE HI OF

使用频率最高的20个三字母依次是：

THE ING AND HER ERE ENT THA NTH WAS ETH

FOR DTH HAT SHE ION INT HIS STH ERS VER

除了语言的频率特征，语言的连接特征和语言的重复特征也常被用于密码分析。语言的连接特征指的是字母连接在一起通常遵循固定规律。例如，与低频率的字母连接在一起的通常是元音字母；字母A通常出现在字母E之后，而很少出现在字母E之前。语言的重复特征指的则是在语言的使用过程中，经常有一些多个字母组成的字符串重复出现，例如，TION、TIOUS、NESS等字符串都是在英语中使用广泛的长字符串。

如果要破解单表代换密码，可以对密文的语言特性进行统计。由于明、密文字母一一对应，密文字母继承了明文字母的所有语言特性，通过密文分析推测出明文并不困难。总体上看，单表代换密码属于安全性较低的密码算法。

2.2.2　多表代替密码

多表代替密码由单表代换密码发展而来，这种密码算法也是以代替运算为核心。采用多表代替密码，一个明文字母在密文中可以使用不同字母替代，一个密文字母也可以对应于明文中的不同字母。多表代替密码能够弥补单表代换密码由于保留明文的语言特征，容易被攻击者采用统计分析法破解的缺点。

维吉尼亚密码（Vigenére Cipher）是最具代表性的一种多表代替密码。图2-5是维吉尼亚密码表，明文字母以小写形式出现在表中第一行，密钥字母以小写形式出现在表中第一列，表中其余各行分别代表采用特定密钥字母，明文字母对应的密文字母。

对维吉尼亚密码表进行分析。当密钥字母为a时，明文中的字母在密文中保持不变。例如，明文字母a对应于密文字母A，明文字母b对应于密文字母B。当密钥字母为b时，明文中的字母在密文中以26位字母表为基础，被该字母循环右移1位后所对应的字母替换。例如，明文字母a在加密后对应于字母B，明文字母b在加密后对应于字母C。密钥字母为c时，明文中的字母在密文中被该字母循环右移2位后所对应的字母替换。

维吉尼亚密码可以看作由26个凯撒密码组成。维吉尼亚密码中的密钥字母等价于凯撒密码中的偏移量，密钥字母a至密钥字母z分别对应于数字0至数字25的偏移量。

采用维吉尼亚密码，对于给定的明文字母pi和密钥字母k，可以通过维吉尼亚密码表确定相应的密文字母，密文字母位于明文字母pi所标识列和密钥字母k所标识行的交叉位置。如明文字母为c，密钥字母为e，则相应的密文字母为G；明文字母为l，密钥字母为g，则相应的密文字母为R。

维吉尼亚密码在加密时，需要使用与明文信息等长的密钥。生成密钥的方法通常是选定一个关键字，采用不断重复关键字的方法得到与明文信息等长的密钥。每个明文字母与关键字中的一个字母对应，执行加密操作。例如，要加密的明文是“attack at nine thirty”，使用关键字“stay”，则明、密文对应关系如下所示：

密钥：staystaystaystayst

明文：attackatninethirty

密文：SMTYUDARFBNCLAIPLR

在示例中明文中的第一个字母是a，它所对应的密钥字母为s，通过维吉尼亚密码表可以确定相应的密文字母为S。明文中的第二个字母是t，对应的密钥字母为t，相应得到的密文字母为M。以此类推，可以得到完整的密文。

解密操作也是依据维吉尼亚密码表进行的。在对密文解密时，首先通过关键字的重复产生与密文等长的密钥。解密密文时，必须确定每个密文字母对应的密钥字母。在示例中，密文的第一个字母S对应的密钥字母是s，密文中第二个字母M对应的密钥字母是t。在此基础上，通过密钥字母在维吉尼亚密码表中定位行，在相应行中找到密文字母，密文字母所在列对应的明文字母即为解密结果。例如，示例中第一个密文字母S，参照维吉尼亚密码表，在由密钥字母s定位的行中找到密文字母S，S所在列对应的明文字母为a，即a是密文字母S对应的明文字母。

采用维吉尼亚密码进行加密，明文中的语言特性在密文中被隐藏，密文中每个字母的使用频率非常相近。破解维吉尼亚密码，其关键是确定关键字的长度，在此基础上，将维吉尼亚密码划分为几个凯撒密码来破解。

在示例中，关键字stay的长度为4，加密过程可以看成由4种凯撒密码组成，分别是按照密钥字母s进行偏移、按照密钥字母t进行偏移、按照密钥字母a进行偏移和按照密钥字母y进行偏移的。

从表2-1中可以看出，由密钥字母s加密的明文字母为a、c、n、t和t，相应得到的密文字母为S、U、F、L和L；由密钥字母t加密的明文字母为t、k、i、h和y，相应得到的密文字母为M、D、B、A和R，以此类推。

如果知道关键字的长度，则在破解过程中可以划分为4组凯撒密码采用穷举法破解。由于在维吉尼亚密码中密文字母的偏移有26种可能，而且4组必须结合在一起进行分析，因此穷举法共需尝试264次，即456 976次。关键字越长，需要尝试的次数也就越多。

2.2.3　置换密码算法

置换密码算法也被称为换位密码算法（Transposition Cipher），采用这种密码算法，明文和密文中出现的所有字母都是相同的，只是字母的排列顺序有变化，一般人难以通过密文获取明文信息。

举例来看，明文消息“attack at nine thirty”可以采用两行的形式交替书写，如图2-6所示。

在生成密文时，先输出第一行的字母，再输出第二行的字母。图2-6中加密结果是第一行字母“atcanntit”与第二行字母“taktiehry”的拼接，最终得到密文“atcanntittaktiehry”。

设计人员可以根据安全需求设计形式各样的置换密码。例如，可以将明文按行写入矩阵，并以一定顺序按列从矩阵中输出密文。还是以消息“attack at nine thirty”为例，在图2-7中，明文按行写入一个四列的矩阵，最后不足整行的位置以字母z填充。

输出密文时，可以指定先输出第三列字母，然后输出第二列字母，再输出第四列字母，最后输出第一列字母，产生的密文是四列字母的拼接。最终加密结果为“taniztkihyacnttaterz”。

算法的解密也非常简单。在获得密文以后，将密文划分为四组，分别是taniz、tkihy、acntt及aterz，把四组字母依次写入矩阵的第三列、第二列、第四列和第一列。将矩阵填满后，按行读取矩阵中的字母，即可以恢复明文。

置换密码算法比较简单，其主要问题是难以抵御选择明文攻击。攻击者如果能够大量地掌握明文和对应的密文结果，不难通过分析找出置换的具体方法，并相应进行解密。