2.2 对称密码算法

在对称密码算法中，加密密钥和解密密钥相同，或者通过其中一方可以推导出另一方，并且需要通信的双方保管所使用的密钥。它是密码学中常见的一种密码算法。对称密码算法包括分组密码和序列密码两种类型。分组密码与序列密码是密码学中两种重要的密码算法，两者之间对信息加密的方式不同，各自的优势也不同，所以有不同的应用领域。

本节将分别讨论分组密码和序列密码，并介绍典型的应用算法。

2.2.1 分组密码

分组密码是现代密码学的一个重要分支。分组密码的加解密速度快、安全性好并得到许多密码芯片的支持，故在计算机通信和信息系统安全领域有广泛的应用，主要用于实现数据加密、数字签名、认证和密钥管理。根据加密算法的不同，分组密码分为对称分组密码和非对称分组密码。下面我们将介绍对称分组密码，并简要介绍一些典型的分组密码算法。

1.分组密码概述

分组密码（Block Cipher），也称块密码，是将明文消息编码表示后的数字序列划分成固定大小的分组，然后在密钥的控制下对各组分别进行加密变换，从而获得等长的二进制序列的一类算法。块的大小由加密变换的输入长度确定，通常为64的倍数。

在现代分组密码中，两个重要的思想就是扩散和混乱。扩散，是指要将算法设计成明文中每一位的变化尽可能多地影响到密文输出序列的变化，以便隐藏明文的统计特性，我们可以形象地将其描述为“雪崩效应”。混乱，是指在加解密变换过程中明文、密钥以及密文之间的关系要尽可能地复杂化，以防密码破译者通过建立并求解一些方程来进行破译。

分组密码与序列密码的不同之处在于：序列密码算法是对序列中的每一个位或者每一个字符进行加密，而分组密码则是以由若干位组成的组为单位进行加密变换，如图2-5所示。

分组密码的加密过程如下。

1）将明文分成m个明文组M₁，M₂，…，M_i，…，M_m。

2）对每个明文分组分别作相同的加密变换，从而生成m个密文组C₁ ，C₂ ，…，C_i，…，C_m。在图2-5所示的加密过程中，分组密码以32位为一个分组对明文进行划分，明文单词“this”经过加密变换后得到密文“} kc {”。这些加密算法是对整个明文进行操作的，即除了其中的文字以外，还包括空格、标点符号和特殊字符等。

分组密码的解密过程和加密过程类似，进行的操作和变换也只是对应于加密过程的逆变换。首先将收到的密文分成m个密文分组C₁，C₂，…，C_i，…，C_m，它在相同的密钥作用下，对每个分组执行一个加密的逆变换，解密得到对应的明文分组M₁ ，M₂ ，…，M_i，…，M_m。

2.典型的分组密码算法

接下来，将介绍一些历史上得到广泛应用的典型分组密码算法。

（1）DES算法

DES算法的产生可以追溯到1972年，美国国家标准局（National Bureau of Standards，NBS），即现在的国家标准和技术研究院（National Institute of Standards and Technology，NIST）启动了一个研究加密算法的项目，目的是为了对计算机和计算机通信中的数据进行保护。很多公司参与到这一项目中并提供了一些建议，最后，IBM公司的Lucifer加密系统胜出。到1976年底，美国联邦政府决定使用这个算法，并对其进行了一些改动，将其更名为数据加密标准（DES）。不久之后，其他组织也认可并开始采用DES作为加密算法。之后的20多年，DES成为很多应用程序选用的加密算法。但是随着计算机计算能力的提升，DES的安全性逐渐变弱，之后被高级加密标准（Advanced Encryption Standard，AES）所取代。虽然DES被取代了，但它的设计思想对现代密码学的发展具有深远的意义。

DES是一种使用密钥加密的分组算法，加密和解密密钥相同，处理单位是位，其分组长度为64位，初始密钥长度为64位，含有8个奇偶校验位，故密钥有效长度为56位。其加密过程分为4步，即选择扩展运算、子密钥异或、选择压缩运算和置换运算。在计算能力得到大大提高之后，DES的密钥长度和分组长度显得过短，可以被穷举攻破。为了能够充分利用已有的DES软硬件资源，多重DES开始得到应用。多重DES是使用多个密钥，利用DES对明文进行多次加密。使用多重DES可以增加密钥量，大大提高抗穷举攻击的能力。

（2）AES算法

1997年，美国ANST（美国国家标准协会）向全球发起征集AES的活动，并且成立了AES工作小组，要求AES比三重DES快，至少与三重DES一样安全，数据分组长度为128位，密钥长度为128/192/256位。2000年，NIST将候选算法Rijndael选为新的AES，故AES也被称为Rijndael加密算法。自此，AES替代了原先的DES，并被全世界广泛使用。

AES的处理单位是字节，其加密过程分为4个步骤：字节代换、行移位、列混合和轮密钥加。当AES的密钥长度为128位时，迭代的轮数是10；密钥长度为192位时，迭代的轮数是12；密钥长度为256位时，迭代的轮数是14。AES算法具有稳定的数学基础，没有算法弱点，而且抗密码分析强度高，可以在多个平台上快速实现，不占用大量的存储空间和内存，所以得到了广泛的应用。

（3）IDEA算法

国际数据加密算法（International Data Encryption Algorithm，IDEA），是最强大的加密算法之一。IDEA是上海交通大学教授来学嘉与瑞士学者James Massey联合提出的，它在1990年被正式公布并在之后得到增强。这种算法是在DES算法的基础上发展而来的，类似于三重DES。由于DES的密钥长度太短，IDEA的密钥长度增加到128位，较长的密钥使得今后若干年内IDEA都是安全的。

尽管IDEA很强大，但它不像DES那么普及，原因主要有两个：第一，IDEA受到专利保护而DES不受专利保护，IDEA需要先获得许可证之后才能在商业应用程序中使用；第二，DES具有比IDEA更长的历史和跟踪记录。

2.2.2 序列密码

序列密码具有实现简单、加密和解密速度快、安全性能较好、没有或少有差错传播等优点。由于序列密码具有的优势，它可以适用于资源受限、体积小、运算速度高的应用场景。蓝牙加密算法和手机加密算法中就有序列密码的应用。接下来，将对序列密码进行详细介绍。

1.序列密码概述

序列密码又称为流密码，它的起源可以追溯到20世纪20年代的Vernam密码，是一种对称密码算法。序列密码将明文消息字符串在密钥流的控制下逐位进行加密和解密，所以具有加解密速度快、实现简单、便于硬件实施、没有或只有有限的错误传播的特点。因此，在实际应用中，特别是在专用或机密机构中，序列密码保持着一定的优势。序列密码典型的应用领域包括无线通信、外交通信等。

序列密码通过将明文或密文划分成字符或基本单元（如0、1数字），再分别与密钥流作用来进行加密或解密。序列密码算法的设计关键在于密钥序列产生器，它可以使生成的密钥序列具有不可预测性。根据通信双方使用的密钥是否相同，序列密码可以是对称密钥算法下的，也可以是公钥密码算法下的。本节的重点是介绍对称密钥算法，如果没有特殊说明，下面讨论的序列密码都属于对称密钥。

序列密码一般包含以下几个组成部分：明文序列m_i、密钥序列k_i、用于控制密钥序列产生器的种子密钥K和密文序列c_i。在序列密码中，加解密运算是简单的模2加运算，其安全性强度主要取决于密钥序列的随机性。序列密码的加解密过程如图2-6所示。

在图2-6中，KG是密钥流生成器，它主要分为两部分：驱动部分和组合部分。驱动部分一般使用线性反馈移位寄存器（Linear Feedback Shift Register，LFSR），用于产生控制生成器的状态序列，并控制生成器的周期和统计特性。组合部分主要负责对驱动部分的各输出序列进行非线性组合。在数据通信时，长时间通过安全信道传递密钥流在实际应用中很难实现，所以大多数序列密码算法都采用“种子密钥”的方式来构造伪随机序列。此时，密钥流生成器的工作是根据较短的“种子密钥”来构造统计性能良好的伪随机序列。在这种情形下，密钥序列元素k_i的产生是由第i时刻密钥流发生器中记忆元件（存储器）的内部状态σ_i和种子密钥k共同决定的，一般可以写作：k_i=f（k，σ_i）。

假设待加密消息流（明文流）为：

m=m₁m₂…m_i… m_i∈M

密钥流为：

k=k₁k₂…k_i… k_i∈K

加密后的密文流为：

c=c₁c₂… c_i…c_i∈C

则加密算法可以表示为：

c=c₁c₂…c_i…=E_k1（m₁）E_k2（m₂）…E_ki（m_i）…

解密算法可以表示为：

m=m₁m₂…m_i…=D_k1（c₁）D_k2（c₂）…D_ki（c_i）…

若c_i=E_ki（m_i）=m_i⊕k_i，则称这类序列密码为加法序列密码。

2.反馈移位寄存器

为了更好地理解序列密码的工作原理，下面对反馈移位寄存器做简单介绍。反馈移位寄存器由n位的寄存器（称为n级移位寄存器）和反馈函数（Feedback Function）组成。移位寄存器序列的理论由挪威的密码学家Ernst Selmer于1965年提出。移位寄存器用来存储数据，当受到脉冲驱动时，移位寄存器中所有位右移一位，最右边移出的位是输出位，最左端的一位由反馈函数的输出来填充，此过程称为进动一拍。反馈函数f（a₁，…，a_n）是n元（a₁，…，a_n）的布尔函数。移位寄存器根据需要不断地进动m拍，便有m位的输出，形成输出序列o₁o₂…o_m，如图2-7所示。

当反馈移位寄存器的反馈函数是异或变换时，这样的反馈移位寄存器称作线性反馈移位寄存器，如图2-8所示。

图2-8所示的是一个n级线性反馈移位寄存器的模型，移位寄存器中存储器的个数称为移位寄存器的级数，移位寄存器存储的数据是寄存器的状态，状态的顺序从左到右依次为从最高位到最低位。在所有状态中，（a₁，a₂，…，a_n）叫初态，并且从左到右依次称为第一级、第二级、…、第n级，也称为抽头1、抽头2、抽头3、…、抽头n。n级线性反馈移位寄存器主要是用来产生周期大、统计性能好的序列，可以产生2^n-1个有效状态。

非线性组合部分主要是增加密钥流的复杂程度，使密钥流能够抵抗各种攻击（对流密码的攻击手段主要是对密钥流进行攻击）。这样，以线性反馈移位寄存器产生的序列为基序列，经过不规则采样、函数变换等操作（即非线性变换），就可以得到安全又实用的密钥流。不规则采样是在控制序列作用下，对被采样序列进行采样输出，得到的序列称为输出序列。控制序列的控制方式有钟控方式和抽取方式等，函数变换有前馈变换和有记忆变换等。下面简单介绍两种具有代表性的序列模型。

（1）钟控模型

图2-9展示了一种钟控发生器的模型。当LFSR-1输出1时，时钟信号被采样，即能通过“与门”，并驱动LFSR-2进动一拍；当LFSR-1输出0时，时钟信号不被采样，即不能通过“与门”，此时LFSR-2不进动，重复输出前一位。

（2）前馈模型

Geffe发生器是前馈序列的一种典型模型，如图2-10所示。其前馈函数g（x）=（x₁x₂ ）⊕（x₂x₃）为非线性函数，即当LFSR-2输出1时，g（x）的输出位是LFSR-1的输出位；当LFSR-2输出0时，g（x）的输出位是LFSR-3的输出位。

序列密码通常分为同步序列密码和自同步序列密码两类。若密钥序列的产生独立于明文消息和密文消息，这样的序列密码称为同步序列密码。分组密码的输出反馈模式（OFB）就是同步序列密码的一个例子。若密钥序列的产生是密钥及固定大小的以往密文位的函数，这样的序列密码称为自同步序列密码或非同步序列密码，分组密码的密文反馈模式（CFB）就是自同步序列密码的一个例子。

（1）同步序列密码

图2-11所示，k_i表示密钥流，c_i表示密文流，m_i表示明文流。在同步序列密码中，密钥流的产生完全独立于消息流（明文流或密文流）。在这种工作方式下，如果传输过程中丢失一个密文字符，发送方和接收方就必须使他们的密钥生成器重新进行同步，这样才能正确地加/解密后续的序列，否则加/解密将失败。

图2-11所示的操作过程可以用以下函数描述。

其中，σ_i表示密钥流生成器的内部状态，F是状态转移函数，G是密钥流k_i产生函数，E是同步流密码的加密变换，D是同步流密码的解密变换。

由于同步流密码各操作位之间相互独立，因此，应用这种方式进行加解密时不会有错误传播。如果在操作过程中产生一位错误，也只会影响一位，不影响后续位，这是同步流密码的一个重要特点。

（2）自同步流密码

与同步流密码相比，自同步流密码是一种有记忆变换的密码，如图2-12所示。自同步流密码的每一个密钥字符是由前面n个密文字符参与运算推导出来的，其中n为定值。如果在传输过程中丢失或更改了一个字符，那么这一错误就要向前传播n个字符。因此，自同步流密码会出现错误传播现象。不过，在收到n个正确的密文字符之后，密码自身会实现重新同步。

图2-12所示的操作过程可以用以下函数进行描述。

式中，σ_i表示密钥流生成器的内部状态，c_i是密文，F是状态转移函数，G是密钥流k_i产生函数，E是同步流密码的加密变换，D是同步流密码的解密变换。

在自同步流密码系统中，密文流参与密钥流的生成，这使得对密钥流的分析会很复杂，从而导致对自同步流密码进行系统性的理论分析也会非常困难。因此，目前应用较多的流密码是同步流密码。

3.典型的序列密码算法

序列密码的算法很多，比较典型的有A5算法、RC4算法、HC算法和Rabbit算法等，这些序列密码的设计思想各有特点，本节主要对A5算法进行介绍。

A5算法是GSM系统中主要使用的序列密码加密算法，用于加密移动终端与基站之间传输的信息。该算法可以描述为由22位长的参数（帧号码，F _n）和64位长的参数（会话密钥，K _c）生成两个114位长的序列（密钥流）的黑盒子。这样设计的原因是GSM会话每帧含228位，通过与A5算法产生的228位密钥流进行异或来达到保密。A5算法主要有3种版本：A5/1算法限制出口，保密性较强；A5/2算法没有出口限制，但保密性较弱；A5/3算法则是更新的版本，它基于KASUMI算法，但尚未被GSM标准所采用。如果没有特殊说明，下面介绍的A5算法都是指A5/1算法。

A5算法是一种典型的基于线性反馈移位寄存器的序列密码算法，构成A5加密器主体的LFSR有3个，组成了一个集互控和停走于一体的钟控模型。其主体部分由3个长度不同的线性移位寄存器（A、B、C）组成，其中A有19位，B有22位，C有23位，它们的移位方式都是由低位移向高位。每次移位后，最低位就要补充一位，补充的值由寄存器中的某些抽头位进行异或运算的结果来决定，比如：运算的结果为“1”，则补充“1”，否则补充“0”。在3个LFSR中，A的抽头系数为：18，17，16，13；B的抽头系数为：21，20，16，12；C的抽头系数为：22，21，18，17。3个LFSR输出的异或值作为A5算法的输出值。A5加密器的主体部分如图2-13所示。

在图2-13中，A的生成多项式为

f_A（x）=x¹⁹+x¹⁸+x¹⁷+x¹⁴+1

B的生成多项式为

f_B（x）=x²²+x²¹+x¹⁷+x¹³+1

C的生成多项式为

f_C（x）=x²³+x²²+x¹⁹+x¹⁸+1

由此可见，3个线性反馈移存器的生成多项式均为本原多项式。

这3个加密器的移位是由时钟控制的，且遵循“少数服从多数”的原则，即从每个寄存器中取出一个中间位（图2-13中的x、y、z，位置分别为A、B、C的第9、11、11位）并进行判断，若在取出的3个中间位中至少有两个为“1”，则为“1”的寄存器进行一次移位，而为“0”的不进行移位。反之，若3个中间位中至少有两个为“0”，则为“0”的寄存器进行一次移位，而为“1”的不进行移位。显然，这种机制保证了每次至少有两个LFSR被驱动移位。

A5算法的初始密钥长度为64位。为了对该算法进行攻击，已知明文攻击法只需要确定其中两个寄存器的初始值就可以计算出另一个寄存器的初始值，这说明攻击A5算法一般要用2⁴⁰次尝试来确定两个寄存器的结构，而后从密钥流来决定第三个LFSR。A5算法设计巧妙、效率高，可以通过所有已知的统计校验标准。其唯一的缺点是移位寄存器的级数较短，其最短循环长度为4/3∗2^k（k是最长的LFSR的级数），总级数为19+22+23=64，这样就可以用穷尽搜索法来破译。而且目前，A5算法已经被攻破。如果能够采用更长的、抽头更多的线性反馈移位寄存器，A5算法会更加安全。

2.2.3 密码的工作模式

分组密码算法每次加密的明文数据的大小是固定的。通常明文的长度会超过分组密码的分组长度，此时就需要对分组密码算法进行迭代，迭代的方法就称为分组密码的工作模式。密码工作模式通常是基本密码、一些反馈和一些简单运算的组合。

常用的分组密码的工作模式有5种，即电子密码本模式、密文分组链接模式、密文反馈模式、输出反馈模式和计数器模式。其中，密文反馈模式可以看作是序列密码的工作模式，输出反馈模式是将分组密码作为同步序列密码算法来运行的一种方法。接下来，本节将详细介绍这5种密码工作模式及其工作过程。

1.电子密码本模式

电子密码本模式（Electronic Code Mode，ECB）是使用分组密码算法的最简单方式之一，即该模式只能加密长度等于密码分组长度的单块数据，若要加密变长数据，则数据必须先被划分为一些单独的密码块。

y_i=DES_k（x_i）

上式中的x_i表示分组后的第i个明文块，y_i表示加密后的密文块。在该模式下，每个分组独立进行加解密运算，一次处理一组明文块，每次使用相同的密钥进行加密，不同分组间没有任何关联。而且这种方式不必按次序进行，可以先加密中间的分组，然后是尾部分组，最后再加密最开始的分组。由此可见，在密钥一致的情况下，同一段明文总会产生一样的密文。图2-14展示的是ECB模式的工作过程。

在安全性方面，ECB模式的特点是：一段消息若有几个相同的明文组，那么密文也将出现几个相同的密文分组。对于很长的消息，该模式可能就不安全了。通常消息的开头和结尾都会被格式化，其中包含了关于发送者、接收者和日期等信息，这些信息会趋向于在不同消息的同一位置出现，密码分析者可以获得很多信息。然后，他就可以对明文发起统计攻击，而不用考虑密文分组的长度。如果消息是非结构化的，密码分析者可能利用这些规律性特征来进行破译。

所以，ECB模式特别适合于数据较少的情况，比如加密密钥。如果想安全传输一个DES或AES密钥，ECB模式是比较合适的。

2.密文分组链接模式

为了克服ECB模式的上述弱点，需要将重复的明文分组加密成不同的密文分组。满足这一要求的简单方法就是使用密文分组链接模式（Cipher Block Chaining，CBC）。链接是将一种反馈机制加入到分组密码中，加密算法的输入是当前的明文组和上一个密文组的异或结果，而使用的密钥是相同的。这就相当于将所有的明文组链接起来。加密算法的每次输入与本明文组没有固定的关联。因此，如果有重复的明文组，加密之后也看不出来。

图2-15展示了CBC模式的工作过程，其中初始向量为IV，密钥为K。第一个明文分组被加密后，其结果被存储在反馈寄存器中，在下一明文分组进行加密之前，它将与保存在反馈寄存器中的前一个分组的密文进行异或并作为下一次加密的输入。同样地，加密后的结果仍然保存在反馈寄存器中，直到最后一个分组加密后直接输出。由此可见，每一分组的加密都依赖于所有前面的分组。

在解密时，每个密文组分别进行解密，再与上一分组进行异或就可以恢复出明文。

从上述的工作原理可以看出，由于链接反馈机制的存在，CBC模式对线路中的差错比较敏感，会出现错误传播。密文中的小错误会转变为明文中很大的错误。在分组中出现错误后，紧接着第二分组的分组就不再受到错误影响，所以CBC模式的错误传播是有限的，它具有自恢复（Self-Recovering）能力。

虽然CBC模式的一个密文分组出错会影响两个分组的正确解密，但系统可以恢复并使后面的分组都不受影响。尽管CBC能很快将位错误进行恢复，但它却不能恢复同步错误。如果密文流中增加或丢失一位，那么所有后续分组都要移动一位，并且解密将全部是错误的。所以，任何使用CBC的加密系统都必须确保分组结构的完整性。

3.密文反馈模式

密文反馈模式（Cipher Feedback Block，CFB）是分组密码算法用于自同步序列密码算法的一个实例。典型的流密码输入某个初始值和密钥，然后输出位流，这个位流再和明文位进行异或运算。而在CFB模式里，与明文异或的位流是与明文相关的。

图2-16展示了CFB模式的工作过程。若设分组长度为n位，初始向量为IV（n位），密钥为K，则j位（bit）的CFB模式下（j在1～n之间），加密过程如下。

1）设一个n位长的队列，队列初始值为IV，并把明文消息分成M个j位的比特块。

2）依次对每个j位比特块明文P_j进行以下操作：用密钥K加密队列，把该密文最左端的j位与j位比特块明文P_j进行异或，即可获得其j位比特块的密文C_j；然后把该j位比特块密文C_j放入队列的最右端，并丢弃队列最左端的j位。

3）最后把全部j位比特块密文C₁…C_M依次连起来，即可得到消息密文C。

在CFB模式中，明文的一个错误就会影响所有后面的密文和解密过程。同样地，密文里单独一位的错误会引起明文的一个单独错误。除此之外，错误进入移位寄存器，导致密文变成无用的信息，直到该错误从移位寄存器的另一端移出，这会使加密明文产生更大的错误。

CFB模式对同步错误来说是可以自我恢复的。错误进入移位寄存器，就可以造成数据毁坏，直到它从另一端移出寄存器为止。

4.输出反馈模式

输出反馈模式（Output Feedback Block，OFB）是将分组密码作为同步序列密码算法来运行的一种方法，如图2-17所示。在OFB模式中，密码算法的输出会反馈到密码算法的输入中。OFB模式并不是通过密码算法对明文直接加密，而是通过将明文分组和密码算法的输出进行异或来产生密文分组，但OFB是将前一个j位输出分组送入队列最右边位置。解密是加密的一个逆过程。在OFB模式的加解密过程中，分组算法都以加密模式使用。由于反馈机制独立于明文和密文，这种方法有时也被称为“内部反馈”。

OFB模式有一个很好的特性就是大部分工作可以离线进行，甚至可以在明文存在之前。当消息最终到达时，它可以与算法的输出进行异或运算，从而产生密文。

OFB模式的优点如下。

1）明文模式可以得到隐藏。

2）分组密码的输入是随机的。

3）可以及时加密传送小于分组的数据。

OFB模式的缺点如下。

1）明文很容易被控制或篡改。

2）不利于并行计算。

3）任何对密文的改变都会直接影响明文。

5.计数器模式

计数器模式（Counter Mode，CTR）采用与明文分组相同的长度来加密不同的明文组，该模式的工作过程如图2-18所示。在该模式中，分组密码没有直接被用来加密明文，而是用于加密计数器的输出。计数器首先被初始化为一个值，然后随着消息块的增加，计数器的值会依次递增1，计数器加1后与明文分组进行异或得到密文分组。

使用计数器模式，不需要先生成前面所有的密钥位就可以直接生成第j个密钥位S_j。通过手动设置计数器到第j个内部状态，然后就可以产生该位。这对保障随机访问数据文件的机密性会非常有用，不需要解密整个文件就可以直接解密某个特殊的数据分组。

CTR模式的同步和错误扩散特性与OFB模式完全一样。由于没有反馈，CTR模式的加密和解密能够同时进行，这是CTR模式比CFB模式和OFB模式优越的地方。