4.1 密码技术的基本概念

4.1.1 密码系统的基本组成

典型密码系统的组成如图4.1所示。

由图4.1可见，一个典型的密码系统可以用数学符号描述如下：

S = {M，C，K，E，D}

式中，M 是明文空间，表示全体明文的集合。明文是指加密前的原始信息，即那些需要隐藏的信息，有时又用P（Plaintext）表示。对于给定的明文用小写m表示。

C是密文空间，表示全体密文的集合。密文是指明文被加密后的信息，一般是毫无识别意义的字符序列，对于给定密文用小写c表示。

K是密钥或密钥空间。密钥是指控制加密算法和解密算法得以实现的关键信息，可分为加密密钥和解密密钥，两者既可相同也可不同，一般由通信双方掌握。若加、解密钥相同，该密钥必须通过安全信道传送或在接收端用密钥发生器产生与发送端相同的密钥。

E是加密算法，D是解密算法，又称加密变换和解密变换。密码算法是指明文和密文之间的变换法则，其形式一般是计算某些量值或某个反复出现的数学问题的求解公式，或者是相应的程序。解密算法是加密算法的逆运算（或称逆变换），并且其对应关系应是唯一的。从数学角度看，可将算法视为常量，可以公开；而将密钥视为变量，应予以保密。

现代密码学的一个基本原则是：一切秘密寓于密钥之中。在设计密码系统时，总是假定密码算法是公开的，真正需要保护的是密钥，所以在分发密钥时，必须特别小心，只对数据加密，而通过不安全通道传送密钥不会起到保密的作用。

一个密码系统的主角有发送方、接收方和破译者。其加密过程如下：

① 在发送方，首先将给定明文m，利用加密器E及加密密钥k1，将明文加密成密文

② 然后将c利用公开信道送给接收方；

③ 接收方在收到密文后，利用解密器D及解密密钥k2，将c解密成明文

在密码系统中假设有破译者在公开信道中。破译者并不知道解密密钥k2，但欲利用各种方法得知明文m，或者假冒发送方发送一条伪造信息让接收者误以为真。

通常破译者会选定一个变换函数h，对截获的密文c进行变换，得到的明文是明文空间的某一个元素m′：

注意，一般m′≠m。

因此，为了保护信息的保密性，抗击密码分析，密码系统应满足下述要求：

（1）系统即使达不到理论上是不可破的，即pr{m′=m}=0，也应该是实际上不可破译的。这就是说，从截获的密文或某些已知明文、密文对要确定密钥或任意明文在计算上是不可行的。

（2）加密算法和解密算法适用于所有密钥空间的元素。

（3）系统便于实现和使用方便。

（4）系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。

4.1.2 密码体制分类

密码体制一般是指密钥空间和相应的加密运算的结构，同时也包含明文信源与密文的结构特征。这些结构特征是构造加密运算和密钥空间的决定性因素。密码体制从原理上可分为两类，即单钥密码体制和双钥密码体制。

1.单钥密码体制

单钥密码体制的加密密钥和解密密钥相同，或者虽然不相同但是由其中的任意一个可以很容易推导出另一个，也叫对称密码体制或秘密密钥密码体制。单钥密码系统如图4.2所示。

单钥密码体制的保密性主要取决于密钥的安全性，必须通过安全可靠的途径（如信使传送）将密钥送至接收端。如何产生满足保密要求的密钥是这类体制设计和实现的主要问题。另一重要问题是如何将密钥安全可靠地分配给通信对方。这在网络通信条件下更为复杂，包括密钥的产生、分配、存储、销毁等多方面的问题，统称为密钥管理。这是影响系统安全的重要因素，即使密码算法再好，若密钥管理问题处理不好，也很难保证系统的安全保密。

单钥密码体制对明文消息加密有两种方式：一是明文消息按字符（如二元数字）逐位加密，称为流密码（或序列密码）；另一种是将明文消息分组（含有多个字符），逐组进行加密，称为分组密码。

（1）序列密码体制

序列密码体制是军事、外交及商业场合使用的主要密码技术之一，也是各种密码体制中研究最为成熟的体制。

其主要原理是：以明文的位为加密单位，用某一个伪随机序列作为加密密钥，与明文进行“模2加”运算，获得相应的密文序列。这样即使对于一段全“0”或全“1”的明文序列，经过序列密码加密后也会变成类似于随机噪声的乱数据流。在接收端，用相同的随机序列与密文序列进行“模2加”运算后便可恢复明文序列，序列密码体制的基本形式如图4.3所示。

这种体制的优点是加/解密可以完全采用相同的算法实现，每一位数据的加密都与消息的其余部分无关，如果某一码元发生错误，不影响其他码元，即错误扩散小。此外它还具有速度快、实时性好、利于同步、安全程度高等优点。

由于序列密码算法的安全强度完全决定于所产生的伪随机序列的好坏。因此设计序列密码的关键问题是伪随机序列发生器的设计。当移位寄存器的阶数大于100阶时，才能保证系统必要的安全。

（2）分组密码

分组密码是在密钥的控制下一次变换一个明文分组的密码体制。它把一个明文分组空间映射到一个密文分组空间，当密钥不变时，对相同的明文加密就得到了相同的密文。

在进行加密时，首先将明文序列以固定长度进行分组，具体每组的长度由算法设计者确定，每一组明文用相同的密钥和加密函数进行运算。设其中一组m位的明文数据为X= (x0,x1, …,xm-1)，密钥为K=(k0,k1, …,kL-1)，在密钥K的控制下变换成一组n位的密文数据Y=(y0,y1, …,yn-1)。分组密码加、解密过程如图4.4所示。

通常分组密码都取n=m。若n＞m，则为数据扩展的分组密码。若n＜m，则为数据压缩的分组密码。在二元情况下，X 和Y 均为二元数字序列。为了使加密过程可进行逆向操作，每一种操作都必须产生一个唯一的密文分组，明文和密文之间是一对一的可逆操作。

与序列密码体制相比，分组密码体制在设计上的自由度比较小，但它容易检测出对信息的篡改，且不需要密钥同步，具有很强的适应性，特别适用于数据库加密。

单钥密码体制具有加解密算法简便高效、加解密速度快、安全性高的优点，其应用较为广泛。但该体制也存在一些问题，而且无法靠自身解决，一是密钥分配困难；二是需要的密钥量大，在有众多用户的网络通信下，为了使n个用户之间相互进行保密通信，将需要n(n-1)/2个密钥，n越大，所需代价越大；三是无法实现不可否认服务。

2.双钥密码体制

采用双钥体制的每个用户都有一对选定的密钥：一个是可以公开的，可以像电话号码一样注册公布，用k1表示；另一个则是秘密的，由用户自己秘密保存，用k2表示。这两个密钥之间存在着某种算法联系，但由加密密钥无法或很难推导出解密密钥。因此双钥密码体制又称为公钥密码体制或非对称密码体制。

双钥密码体制的主要特点是将加密和解密能力分开，因而可以实现多个用户加密的消息只能由一个用户解读，或者只由一个用户加密消息而使多个用户可以解读。前者可用于公共网络（如Internet）中实现保密通信，而后者可用于认证系统中对消息进行数字签名。

（1）加、解密过程

公钥体制用于保密通信的原理如图4.5所示。图4.5中假定用户A要向用户B发送机密消息m。若用户A在公钥本上查到用户B的公钥kB1，就可用它对消息m进行加密得到密文c=EkB1(m)，而后送给用户B。用户B收到后用自己的秘密钥kB2对c进行解密变换得到原来的消息m。

整个系统的安全性在于从对方的公开密钥kB1和密文中要推出明文或解密密钥kB2在计算上是不是可行的。但由于任一用户（一定范围的参与者）都可用用户B的公钥进行加密并向他发送机密信息，因而密文不具备认证性，即无法确定发送者是谁。

但在计算机系统中，时时刻刻都在进行着各种各样的信息交换。从安全的角度考虑，必须保证这个交换过程的有效性与合法性，认证就是证实信息交换过程合法有效的一种手段。

（2）认证过程

为了使用户A发给用户B的消息具有认证性，可以将公钥体制的公开密钥和私有密钥反过来使用，双钥认证体制如图4.6所示。用户A以自己的秘密钥kA2对消息m进行专用变换，将得到的密文c送给用户B，B收到后可用A的公开钥kA1对c进行公开变换就可得到恢复的消息。

由于kA2是保密的，只有A才能发送这个密文c，其他人无法伪造这个密文，在利用A的公钥进行解密后才能得到有意义的消息m。因此，可以验证消息m 确实来自于用户A，从而实现了对A所发消息的认证。

上述描述的过程并不提供保密功能，可以防篡改，但不能防止窃听。因为任何一个观察者都可用发送方的公开密钥解密密文，以验证签字消息。这就说明，认证和保密是信息安全中两个不同的方面。保密是为了防止明文信息的泄露，认证是为了防止黑客对系统的主动攻击。

为了同时实现保密性和确认性，要采用双重加/解密。具体过程是，发信者用自己的私钥对信息签名，再用接收方的公钥对信息加密后发出；收信者用自己的私钥与发送方的公钥一起对信息进行解密，即先用自己的私钥进行解密，再用发送方的公钥对签名进行验证。

与单钥体制相比，双钥体制有效解决了密钥分配困难问题，可以减少密钥量，对于多用户的商用密码系统及计算机网络具有十分重要的意义。此外，它还便于实现数字签名，可以圆满地解决对收、发双方的证实问题，为其在商业上的广泛应用创造了有利条件。

4.1.3 古典密码体制

古典密码是密码学的渊源，这些密码大都比较简单，可用手工或机械操作实现加/解密，现在已经很少采用。但是，研究这些密码的原理，对于理解、构造和分析现代密码是十分有益的。

1.代换密码

代换密码就是将明文的字母用其他字母或符号来代替，各字母的相对位置不变。按代换所使用的密文字母表的个数，可将代换密码分为单表代换密码、多字母代换密码和多表代换密码。

（1）单表代换密码

单表代换密码就是只使用一个密文字母表，并且用密文字母表中的一个字母来代替明文字母表中的一个字母。比较经典的单表代换密码是凯撒密码。

凯撒密码是把字母表中的每个字母用该字母后面第三个字母代替。例如，将字母a，b，c，d，…，w，x，y，z的自然顺序保持不变，但使之与D，E，F，G，…，Z，A，B，C分别对应（即相差三个字符）。例如，

明文：meet me after the toga party

密文：PHHW PH DIWHU WKH WRJD SDUWB

该替代具有以下特点：加密和解密算法是已知的，均为C=E(p)=(p +3) mod 26；需要尝试的密钥只有25个；明文和密文均按顺序排列，替代非常有规律，明文的语言是已知的且很容易识别。由这些特征，可以看出这种代替密码的保密性不强，可以采用强行攻击法和统计分析法进行破译。

（2）多字母代换密码

多字母代换密码就是每次对明文的多个字母进行代换。其优点是容易将字母的自然频度隐蔽或均匀化，从而有利于抗击统计分析。下面介绍两种主要的多字母代换密码。

① Playfair密码。它是最著名的多字母加密密码，它将明文中的每两个字母作为一个单元，并将这些单元转换为密文双字母组合。这样一来，就可以掩盖明文双字母在密文中的结构。

Playfair算法使用5×5字母矩阵，该矩阵用一个关键词（密钥）构造，在这里，关键词是monarchy。Playfair算法的用法如图4.7所示。

该矩阵的具体构造是：从左到右，从上到下填入该关键词的字母（去除重复字母），然后再按字母表顺序将余下的字母依次填入矩阵剩余空间。字母I和J被算作一个字母。

Playfair算法根据以下规则一次对明文的两个字母加密：

● 首先对明文进行分组，每两个字母为一对。如果属于相同对中的重复的明文字母，将用一个填充字母x进行分隔，如词balloon，被分隔为ba lx lo on。

● 属于该矩阵相同行的明文字母将由同行其右边的字母代替，而行的最后一个字母则由该行的第一个字母代替，如ar被加密成RM。

● 属于相同列的明文字母将由同一列其下面的字母代替，而列的最后一个字母则由该列第一个字母代替，如mu被加密成CM。

● 既不属于同行，又不属于同列的明文字母，将由与该字母同行，另一个字母同列的字母代替，如hs加密成BP，ea加密成IM（或JM）。

利用以上规则，对词balloon进行加密，加密结果是IBSUPMNA。

与单表代换密码相比，Playfair密码具有以下优点：一是在明文中相邻的两字母，在密文中不再相邻，使频率分析比较困难；二是虽然仅有26个字母，但有26×26=676种双字母组合，因此识别各种双字母组合要困难得多。

② Hill密码。Hill密码是由数学家Hill于1929年研制的。该密码是将m个连续的字母看成一组，并将其加密成m个密文字母。这种替代是由m个线性方程决定的，其中每个字母被分配一个数值（a=0，b=1，c=2，…，z=25）。若m=3，该系统可以描述如下：

该线性方程可以用列向量或矩阵表示：

或

式中，C和P是长度为3的列向量，分别表示密文和明文；K是一个3×3矩阵，表示加密密钥，操作要执行“模26”运算。

【例4.1】 若有一明文为“paymoremoney”，使用的加密密钥为

该明文的前3个字母pay被表示成向量(15 0 24)，利用密钥K对该明文进行加密后的密文为K(15 0 24)=(375819 486) mod 26=(11 13 18)=LNS。以这种方式继续运算下去，上述明文的密文为LNSHDLEWMTRW。

解密时，必须求出K的逆K-1，使KK-1=I，并将K-1作用于密文，即可恢复出明文。

因此，Hill密码系统可以用下式表示：

与Playfair密码相比，该密码的强度在于利用较大的矩阵不仅完全隐藏了单字母的频率，而且也隐藏了双字母的频率信息。

（3）多表代换密码

多表代换密码是以一系列（两个以上）代换表依次对明文消息的字母进行代换的加密方法。该技术是使用多个不同的单字母代换来加密明文信息，它具有以下特征：一是使用一系列相关的单字母代换规则；二是由一个密钥来选取特定的单字母代换。

最著名，也是最简单的一种算法是Vigenere密码。该密码由26个凯撒密码组成，其位移从0到25。每个密码由一个密钥字母表示，该密钥字母是代替明文字母a的密文字母。因此，一个位移为3的凯撒密码由密钥值d代表。

在使用该密码进行加解密时，通常需要构造一个Vigenere表格，见表4.1。26个密文表的每一个都是水平排列的（行），每个密文的左侧为其密钥字母。对应明文的一个字母表从顶部向下排列。

其加密过程是：给定一个密钥字母x和一个明文字母y，则密文字母位于x行和y列的交叉点上，此时密文为V。

当具体加密一个消息时，需要一个与消息同样长的密钥。通常，该密钥为一个重复关键词。例如，如果某关键词是deceptive，消息是“we are discovered save yourself”，那么

密钥：deceptivedeceptivedeceptive

明文：wearediscoveredsaveyourself

密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ

解密也同样简单，密文字母所在的行的位置决定列，该明文字母位于该列的顶部。

该密码的强度在于每个明文字母由多个密文字母对应，每个明文字母对应于该关键词的每个独特的字母，因此，该字母的频率信息是模糊的。

2. 置换密码

置换密码就是明文字母本身不变，根据某种规则改变明文字母在原文中的相应位置，使之成为密文的一种方法，又称为换位密码。换位一般以字节（一个字母）为单位，有时也以位为单位。

一种应用广泛的置换密码是将明文信息按行的顺序写入，排列成一个m×n矩阵，空缺的位用字符“j”填充。再逐列读出该消息，并以行的顺序排列。列的读出顺序为该密码的密钥。例如，

密钥： 4 3 1 2 5 6 7

明文： a t t a c k p

o s t p o n e

d u n t i l t

w o a m x y z

密文： TTNAAPTMTSUOAODWCOIXKNLYPETZ

一次置换密码容易识别，因为它具有与原明文相同的字母频率，必须进行多次置换，置换过程与第一次相同，经过多次置换后，该密码的安全强度具有较大改善。

以上各种加密方法，单独使用比较简单，但很容易被攻破。在实际加密中，通常将其中的两个或两个以上的方法结合起来，形成综合加密方法。经过综合加密的密文，具有很强的抗分析能力。

4.1.4 初等密码分析

在信息传输和处理过程中，除了正常的接收者外，还有非授权者，他们通过各种办法（如电磁侦听、声音窃听、搭线窃听等）来窃取机密信息，并通过各种信息推出密钥和加密算法，从而读懂密文，这种操作叫做破译，也叫密码分析。

密码破译是利用计算机硬件和软件工具，从截获的密文中推断出原来明文的一系列行动的总称，又称为密码攻击。密码攻击可分为被动攻击和主动攻击两类。仅对截获的密文进行分析而不对系统进行任何篡改的行为，称为被动攻击，如窃听；当密码破译后，采用删除、更改、增添、重放、伪造等方法向密文中加入假消息的过程，称为主动攻击。被动攻击的隐蔽性更好，难以发现，但主动攻击的破坏性很大。

通常，密码分析是敌方为了窃取机密信息所做的事情，但这也是密码体制设计者的工作，设计者的目的是根据目前敌方的分析能力，找出自己体制存在的弱点，对体制加以改进，以提高体制的安全性。例如，IDEA密码算法就是根据敌方较强的差分密码分析，对原始的IDEA进行了修改，使其不易受到差分密码的攻击。

1. 密码分析的方法

密码破译中有一个假设，即假定密码破译者拥有所有使用算法的全部知识，密码体制的安全性仅依赖于对密钥的保护。也就是说，密码破译者除了不知道密钥之外，他有可能了解整个密码系统。密码攻击的方法有穷举法和分析法两类。

（1）穷举法

穷举法，又称强力法或完全试凑法，它对截收的密报依次用各种可能的密钥试译，直到得到有意义的明文；或者在不变密钥下，对所有可能的明文加密直到得到的密文与截获密文一致为止。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的，如破译成本太高或时间太长。

为了减小搜索计算量，可以采用较有效的改进试凑法。它将密钥空间划分成几个（如q个）等可能的子集，对密钥可能落入哪个子集进行判断，至多需进行q次试验。在确定了正确密钥所在的子集后，就对该子集再进行类似的划分并检验正确密钥所在的集。依次类推，最终判断出所用的正确密钥。该方法的关键在于如何实现密钥空间的等概率子集的划分。

（2）分析破译法

分析破译法有确定性和统计性两类。

确定性分析法利用一个或几个已知量（如已知密文或明密文对）用数学关系式表示出所求未知量（如密钥等）。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。

统计性分析法是利用明文的已知统计规律进行破译的方法。密码破译者对截获的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比，从中提取出明文和密文之间的对应或变换信息。密码分析之所以能够破译密码，最根本的是依赖于明文中的冗余度。

理论上，除一文一密的密码体制外，没有绝对安全的密码体制。所以，称一个密码体制是安全的，一般是指密码体制在计算上是安全的，即密码分析者为了破译密码，穷尽其时间、存储资源仍不可得，或者破译所耗费的费用已超出了因破译密码而获得的收益。

2. 密码分析的等级

根据密码分析者对明、密文掌握的程度，密码攻击主要分为以下4个等级。

（1）唯密文攻击。密码分析者仅根据截获的密文进行的密码攻击。

（2）已知明文攻击。密码分析者已经掌握了一些相应的明、密文对，据此对加密系统进行的攻击。

（3）选择明文攻击。密码分析者可以选择一些明文，并可取得相应的密文，这就意味着攻击者已经掌握了装有加密密钥的加密装置（但无法获得解密装置里的密钥），并且可使用任意的密文做解密试验，这对密码分析者而言是很理想的。例如，在公开密钥密码体制中，分析者可以用公开密钥加密其他任意选择的明文。

（4）选择密文攻击。密码分析者可以选择一定的密文，并获得对应的明文。例如，在公钥体制中，分析者可选择所需的密文，并利用公开密钥对所有可能的明文加密，再与明文对照，最后解密选定的密文。

这4类攻击的强度依次增大。密码分析的成功除了靠上述的数学演绎和归纳法外，还要利用大胆的猜测和对一些特殊或异常情况的敏感性。