长沙学院毕业设计(论文)
一些规律进行攻击。为了说明分析过程，我们在这里给出一段从文献[SIN66]中摘选出来的例子。需要解密的密文是：
uzqsovuohxmopvgpozpevsgzwszopfpesxudbmetsxaiz vuephzhmdzshzowsfpappdtsvpquzwymxuzuhsx epyepopdzszufpombzwpfupzhmdjudtmohmq
首先把字母使用的相对频率统计出来，与英文字母的使用频率分布进行比较。如果已知消息足够长的话，只用这种方法就足够了，但是如果消息相对较短，我们就不能得打准确的字母匹配。我们可以尝试者将密文中的字母替换，看是否像一个消息的轮廓。更系统一点的方法是寻找其他的规律。例如，明文中有某些词可能是已知的，或者寻找密文字母中的重复序列，推导它们的等价明文。统计双字母组合（比如代表单音节的两个字母）的频率是一个很有效的工具。由此可以得到一个类似的字母相关频率图。最常用的一个字母组合是th。而我们的密文中，用得最多的字母是zw，它出现了三次。所以我们可以估计z对应于明文t，而w对应明文h。根据先前的假设，我们可以认为p对应e。现在我们意识到密文中的zwp很可能就是the，这是一个英语中最常用的三字母组合，这表明我们的思路是正确的。接下来注意到第一行中的序列zwsz。我们并不知道它是否为一个完整的单词，若是这样的话，它一个被翻译成th_t的形式，因此s很可能是明文a。
至此我们有以下结果：
uzqsovuohxmopvgpozpevsgzwszopfpesxudbmetsxaiz
t a e e te a that e e a a vuephzhmdzshzowsfpappdtsvpquzwymxuzuhsx
e t ta t ha e ee a e th t a epyepopdzszufpombzwpfupzhmdjudtmohmq e e e tat e the et
虽然只确定了4个字母，但是我们已经有眉目了。继续进行类似的分析、测试，很快就可以得出完整的明文，加上空格后如下：
it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in Moscow
单表代换密码容易被攻破，因为它带有原始字母使用频率的一些统计学特征。一种对策是对每个字母提供多种代换，就像一个读音可以代表多个单词的同音词一样，一个明文单元也可以变换成不同的密文单元。比如字母e可以替换成16、74、35和21，等等，循环或随机地选择其中一个即可。如果对每个明文元素（字母）分配的密文元素（如
11
长沙学院毕业设计(论文)
数字等）的个数与此明文元素的使用频率成一定的比例关系，那么使用频率信息就完全被隐藏起来了。伟大的数学家Carl Friedrich Gauss认为他已经用这种“同音词”方法设计出一种牢不可破的密码。然而，即使采用了同音词方法，明文中的每个元素仅仅只对密文中的一个元素产生影响，多字母语法模式（比如双字母音节）仍然残留在密文中，这样就降低了密码分析者分析的难度。代换密码必须考虑的一个问题是明文的语法模式和结构有多少仍然保存在密文中。有两个方法可以减少这种残留：一种是对明文中的多个字母一起加密，另一种是采用多表代换密码。
2.6 Playfair密码
Playfair密码的算法是基于使用一个5*5字母矩阵，该矩阵使用一个关键词构造。设关键词是monarchy，矩阵的构造方法是：由从左到右、从上到下填入关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间，字母I和J被看作一个字母，如下表所示。
字母矩阵表： M O N A R C H Y B D E F G I/J K
L P Q S T U V W X Z
Playfair密码系统根据下列规则一次对明文的两个字母加密：
（1） 相同对中的重复明文字母将用一个填充字母如X进行分隔，因此单词balloon将被分隔为ba lx lo on。
（2） 属于该矩阵相同行的明文字母将由其右边的字母代替，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为RM。
（3） 属于该矩阵相同列的明文字母将由其下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为CM。
（4） 否则，明文的其他字母将由与其同行，且与另一个字母同列的字母所代替。因此，hs被加密为BP，ud被加密为CZ。
Playfair密码相对于简单的单表密码是一个巨大的进步。首先，因为有26个字母，故有26?26=676个字母对，因此对单个的字母对进行判断要困难得多。此外，单个字母在使用频率的统计规律上比字母对要强得多。这样，利用使用频率分析字母对就更困难一些。因为这些原因，Playfair密码在很长一段时间内被认为是牢不可破的。第一次世界大战中英军就使用它作为陆军的标准加密体制，并且在第二次世界大战中，美军及其
12
长沙学院毕业设计(论文)
他一些盟军队用它来进行加密。
尽管Playfair密码被认为是较安全的，它仍然是相对容易攻破的，因为它的密文仍然完整地保留了明文语言的结构。几百个字母的密文就足够我们分析出规律了。
2.7 Hill密码
Hill密码是1929年由数学家Lester Hill发明的。希尔密码就是矩阵乘法密码，运用基本矩阵论原理的替换密码。每个字母当作26进制数字：A=0, B=1, C=2... 一串字母当成n维向量，跟一个n×n的密钥矩阵相乘，再将得出的结果模26。希尔密码的优点是完全隐藏了字符的频率信息，弱点是容易被已知明文攻击击破。
假设n=3，系统可以描述为：
c1?(k11p1?k12p2?k13p3)mod26 （2.6） c2?(k21p1?k22p2?k23p3)mod26 （2.7） c3?(k31p1?k32p2?k33p3)mod26 （2.8）
用列矢量和矩阵表示如下：
?c1??k11????c2?=?k21?c??k?3??31k12k22k32k13??p1????k23??p2?mod26 （2.9）
??k33???p3?或C?KPmod26
这里C和P是长度为3的列矢量，分别代表密文和明文，K是一个3?3矩阵，代表加密密钥。
运算按模26执行。例如，对明文“paymoremoney”，用加密密钥：
?17175??? K??211821? （2.10）
?2219???明文的前面3个字母用矢量（15 0 24）表示，则有：
K(15 0 24)=(375 819 486) mod 26 = (11 13 18) = LNS （2.11） 照此方式转换余下字母，可得整段明文对应的密文是LNSHDLEWMTRW。
解密则需要用到矩阵K的逆。矩阵K的逆矩阵K?1由等式KK?1?K?1K?I定义，其中I是单位矩阵。不一定所有的矩阵都有逆，但是如果有逆则一定能满足上式。对于刚才这个例子，K的逆是：
13
长沙学院毕业设计(论文)
?4915??? K?1??15176? （2.12）
?24017???可以验证如下：
?17175??4915??443442442??100????????? ?211821??15176???858495780?mod26=?010? （2.13）
?001??2219??24017??49452365?????????用一般术语，Hill密码可以表示如下：
C?Ek(P)?KPmod26 （2.14） P?Dk(C)?K?1Cmod26?K?1KP?P （2.15） 同Playfair密码相比，Hill密码的优点是完全隐蔽了单字母频率特性。实际上，Hill用的矩阵越大，所隐藏的频率信息就越多。因此，一个3?3的Hill密码不仅隐藏了单字母的频率特性，还隐藏了双字母的频率特性。尽管Hill密码足以抗惟密文攻击，但是它较易被已知明文攻击破解。对于一个m?m的Hill密码，假如我们有m个明密文对，每个长度都是m，定义Pj?(p1j,p2j,...,pmj)和Cj?(c1j,c2j,...,cmj)，使得对每个Cj和
Pj（1?j?m）都有Cj=KPj，其中K是未知矩阵形密钥。现在定义两个m*m的矩阵X?(pij)和Y?(cij)。那么我们可以得出矩阵等式Y?KX。若X可逆则可得K?YX?1。若X不可逆，那么我们可以另找X直到得到一个可逆的X。假设明文“Friday”经过一个2?2的Hill加密生成pqcfku。因此我们知道K（5 17）=（15 16）；K(8 3)=(2 5); K(0 24)=(10 20)。那么由这两个明密文对可得：
?152??58? ???K??mod26 （2.16）
165173????X的逆是：
?58??92?? ? ??? （2.17）
173115?????1?152??92??13760??78? K???mod26???????? （2.18）
?165??115??149107??193?该结果可以由第3个明密文对来验证。
14
