2.2 传统密码技术

以上讨论了密码技术的基本概念，本节将对传统的密码学的典型方法进行简要的论述和总结，使读者对密码学的全貌有一个完整的印象，理解现代密码学产生的背景，为今后比较传统密码学和现代密码学，研究和改进现代密码系统的途径打下基础。

2.2.1 换位密码

换位密码根据一定的规则重新安排明文字母，使之成为密文。常用的换位密码有两种，一种是列换位密码，另一种是周期换位密码。下面给出两个例子，分别说明它们的工作情况。

【例2-1】假定有一个密钥是type的列换位密码，我们把明文can you believe her写成4行4列矩阵，如表2-1所示。

表2-1 明文矩阵

按照密钥type所确定的顺序，按列写出该矩阵中的字母，就得出密文：

Y E V R N B E E CO L E A U I H

【例2-2】假设有一个周期是4的换位密码，其密钥是i＝1，2，3，4的一个置换f（i）＝3，4，2，l。明文同上例，加密时先将明文分组，每组4个字母，然后根据密钥所规定的顺序变换如下：

明文：M＝c a n y o u b e 1 i e v e h e r

密文：C＝N Y A C B E U O E V I L E R H E

2.2.2 代替密码

代替密码就是明文中每一个字符被替换成密文中的另一个字符，接收者对密文进行逆替换就恢复出明文来。在经典的密码学中，有几种类型的代替密码：

1.简单代替密码（Simple Substitution Cipher）

简单代替密码就是将明文字母表M中的每个字母用密文字母表C中的相应字母来代替。这一类密码包括移位密码、乘数密码、仿射密码、多项式代替密码以及密钥短语密码等。加密前一般首先要对字母表中的每个字母按照其位置进行编号，如用0，1，2，…，25分别表示英文字母a，b，c，…，z。

（1）移位密码。将明文字母表M的字母右移k个位置并对明文字母表长度q取模得到密文字母，是最简单的一类代替密码，其加密变换可表示为：e_k（m）＝（k＋m）mod q＝c，解密变换为：d_k（c）＝（m-k）mod q＝m，其中q为字母表M的长度，m为明文字符在字母表M中的位置，c为密文字母在字母表C中的位置。移位密码就是对英文26个字母进行移位代替的密码，其中q＝26。这种密码又被称为凯撒密码，因为古罗马的凯撒曾使用过k＝3时的这种密码。例如，使用凯撒密码加密，可将明文university加密成密文qlyhuvlwb。

（2）乘数密码。将明文字母乘以密钥k并对q取模得到密文字母。加密过程可表示为：

e_k（m）＝km mod q＝c

其中k和q为互素的，这样字母表中的字母会产生一个复杂的剩余集合。若k和q不互素，则会有一些明文字母被加密成相同的密文字母，而且不是所有的字母都会出现在密文字母表中。

（3）仿射密码。明文字母经过线性变换得到密文字母，加密的形式为：

e_k（m）＝（k₁m＋k₂）mod q＝c

其中要求k₁和q是互素的，理由同上。

简单代替密码由于使用从明文到密文的单一映射，所以明文中单字母出现频率分布与密文中相同，可以很容易地通过使用字母频率分析法进行破译。

2.多名或同音代替密码（Homophonic Substitution cipher）

在同音代替中，一个明文字母表的字母a，可以变换为若干个密文字母f（a），称为同音字母，因此，从明文到密文的映射f的形式是f：A→2C，其中A，C分别为明文和密文的字母表。

【例2-3】假定一个同音代替密码的密钥是一段短文，该文及其中各个单词的编号，如下所示：

（1）Canada’s large land mass and

（6）Scattered population make efficient communication

（11）a necessity.Extensive railway，road

（16）and other transportation systems，as

（21）well as telephone，telegraph，and

（26）cablenetworks，have helped to

（31）link communities and have played

（36）a vital part in the

（41）country’s development for future

在上表中，每一个单词的首字母都和一个数字对应，例如字母C与数字1，10，26 32，41对应；字母M和数字4，8对应等，加密时可以用与字母对应的任何一个数字代替字母，例如，如果明文为I Love her forever的密文可能是

392173792891443171413371314

3.多表代替密码（Polyalphabetic Substitution Cipher）

大多数多表代替密码是周期代替密码，当周期为1时，就是单表代替密码。多表代替密码的种类很多，这里只介绍其中的Vigenere密码和游动钥密码。

在Vigenere密码中，用户钥是一个有限序列k＝（k_l，k₂，k₃，…，k_d），我们可以通过周期性（周期为d）将k扩展为无限序列k_i，其中Ki＝K（i mod d），1≤i≤∞，从而得到工作钥K＝（K_l，K₂，K₃，…）。

如果用Ф和θ分别表示密文和明文字母，则Vigenere密码的变换公式为

Ф≡（θ＋k_i）（mod n）

该密码体制有一个参数n。在加解密时，同样把英文字母映射为0～25的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合。

【例2-4】在用户钥为cat的Vigenere密码（周期为3）中，加密明文Vigenere cipher的过程如下（n＝26）：

明文 M＝vig ene rec iph er

工作钥 K＝cat cat cat cat ca

密文 C＝XIZ GNX TEV KPA GR

在这个例子中，每个三字母组中的第一个、第二个和第三个字母分别移动（mod 26）2个、0个和19个位置。

游动钥密码是一种非周期性的Vigenere密码，它的密钥和明文信息一样长，而且不重复。

【例2-5】假定一个游动钥密码的密钥是美国1776年7月4日发布的独立宣言，从第一段开始，因此，明文the object of…

明文： M＝t h e o b j e c t o f…

密钥： K＝w h e n I n t h e c o…

密文： C＝P O I B J W X J X Q T…

4.多字母代替密码（Polygram Substitution Cipher）

明文中的字符块成组被加密，这里介绍一种第一次世界大战使用过的二字母组代替密码（P1ayfair密码）、它的密钥是由25个英文字母（J被除去）组成的五阶方阵，如表2-2所示。

表2-2 Playfair密码的密钥方阵

每一对明文字母m₁和m₂，都根据以下5条规则进行加密：

（1）若m_l和m₂在密钥方阵中的同一行，则密文字母C₁和C₂分别是m_l和m₂右边字母（第一行看作在第五行的下边）。

（2）若m_l和m₂在同一列，则C₁和C₂分别是m₁和m₂右边的字母（第一行看作为第五行的下边）。

（3）若m₁和m₂在密钥方阵中的不同行和列，密文字母C₁和C₂分别是以m₁和m₂为顶点组成的长方形中的另两个顶点，其中C₁和m₁、C₂和m₂分别在同一行。

（4）若m₁＝m₂，则在m_l和m₂之间插进一个无效字母，例如x。

（5）若明文信息共有奇数个字母，则在明文末尾附加一个无效字母。

【例2-6】用Playfair密码加密明文bookstore，有：

明文 M＝bo xo ks to re

密文 C＝ID RG LP QD HG

2.2.3 转轮机

20世纪20年代，出现了转轮密码，而由德国发明家亚瑟·谢尔比乌斯发明的Enigma密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（如图2-2所示中显示了6条），把键盘的信号对应到显示器不同的小灯上去。在图2-2中可以看到，如果按下a键，那么灯B就会亮，这意味着a被加密成了B。同样可以看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果在键盘上依次键入cafe（咖啡），显示器上就会依次显示DBCE，这是最简单的加密方法之一———简单替换密码。

图2-2 Enigma密码机原理图

不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。如图2-3所示，它表示了连续键入3个b的情况。

当第一次键入b时，信号通过转子中的连线，灯A亮起来，放开键后，转子转动一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了C；同样地，第三次键入b时，灯E闪亮。

为使机器更安全，可以把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。

德国人为了战时使用，大大加强了其基本设计，军用的Enigma密码机有3个转轮，因此只有在26×26×26＝17576个字母后才会重复原来的编码。同时还在三个转轮的一侧加了一个反射器导致每个转轮对每一个明文字母操作两次，结构如图2-4所示。

图2-3 Enigma密码机原理图

图2-4 军用Enigma密码机原理图

但如此复杂的密码机在第二次世界大战中还是被破解了。首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父———图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分Enigma密码机的密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。

2.2.4 一次一密密码

1917年，Joseph Mauborgne少校和AT＆T公司的Gilbert Vernam发明了一次一密乱码本的加密方案。通常，一次一密乱码本是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并一起粘成一个乱码本，它最初用于电传打字机。发方用乱码本中的每一密钥字母准确地加密一个明文字符。加密是明文字符和一次一密乱码本密钥字符的模26加法。

每个密钥仅对一个消息使用—次。发方对所发的消息加密，然后销毁乱码本中用过的一页或用过的磁带部分。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。收方在解密消息后销毁乱码本中用过的一页或用过的磁带部分。新的消息则用乱码本中新的密钥加密。

例如，如果消息是：ONETIMEPAD，而取自乱码本的密钥序列是：TBFRGFARFM，那么密文就是：IPKLPSFHGQ，因为

（O＋T）mod 26＝I

（N＋B）mod 26＝P

（E＋F）mod 26＝K

……

如果窃听者不能得到用来加密消息的一次一密乱码本，这个方案是完全保密的。由于给出的密文消息相当于同样长度的任何可能的明文消息，且每一密钥序列都是等概率的（记住，密钥是以随机方式产生的），破译者没有任何信息用来对密文进行密码分析，密钥序列也可能是：POYYAEAAZX，解密出来是：SALMONEGGS，或密钥序列为：BXFGBMTMXM解密出来的明文为：GREENFLUID。

由于明文消息是等概率的，所以密码分析者没有办法确定哪一个明文消息是正确的。随机密钥序列异或一非随机的明文消息将产生完全随机的密文消息，即便现代的高速计算机对此也无能为力。

使用一次一密乱码本需要注意的是：

（1）密钥字母必须随机产生。对这种方案的攻击主要是针对用来产生密钥序列的方法伪随机数发生器通常只有非随机性，所以不能用于产生随机密钥序列。采用真随机源，它才是安全的。

（2）密钥序列不能重复使用。如果密码分析者有多个密钥重叠的密文，那么即使你用多兆字节的乱码本，他也能重构明文。分析者可以把每排密文移来移去，并计算每个位置的适配量。如果排列正确，则适配的比例会突然升高（准确的百分比与明文的语种有关）。从这一点来说，密码分析是容易的，它类似于重合指数法.只不过用两个“周期”，所以千万别重复使用密钥序列。

一次一密乱码本的想法很容易推广到二进制数据的加密，只需用由二进制数字组成的乱码本代替由字母组成的密乱码本，用异或代替一次一密乱码本的明文字符加法即可。解密时用同样的乱码本对密文异或，其他保持不变。这种方法现在主要用于高度机密的低带宽信道，而在高速宽带通信信道上工作还有很大的困难：密钥比特必须随机，密钥序列的长度要等于消息的长度，并且绝不能重复使用；必须准确地复制两份随机数比特，且销毁已经使用过的比特：要确保发方和收方完全同步，一旦收方有一比特的偏移（或者一些比特在传送过程中丢失了），消息就变成了乱码；如果某些比特在传送中出现差错，则这些比特就不能正确地解密。因此，尽管一次一密乱码本不能破译，但只能局限于某些应用。