第2章 对称密码

教学提示：对称密码早已被使用了数千年，它有各种形式，从简单的替换密码到较复杂的构造密码。不过，数学的发展和计算能力的不断进步使创建不可破解的密码成为可能。相对于其他的密码系统，对称密码还有其用武之地，在信息安全保护和网络安全中起着重要作用。

教学目标：在了解对称密码的前提下，掌握几种常见的对称加密技术；并在熟悉古典密码的前提下，了解对称密码的最新技术。

2.1 引言

密码学主要由密码编码学和密码分析学两个分支组成。密码编码学是使消息保密的技术和科学，它的主要任务是寻求生成高强度密码的有效算法，满足对消息进行加密或认证的要求。密码分析学是分析加密算法的技术和科学，它的主要任务是分析密码或进行相关分析，实现获取机密信息或进行诈骗破坏活动。这两个分支是相互对立、相互依赖的关系。正是两者之间的对立促进了密码学的快速发展。在现存的密码技术中，分组密码具有速度快、易于标准化、便于实现等特点，通常是信息与网络安全中实现数据加密、数字签名、认证及密钥管理的核心算法，在计算机通信和信息系统安全领域有着广泛的应用。分组密码算法（Block Cipher，BC）主要应用在网络上，可以非常方便地通过多种运算模式实现数据加密及信息认证等功能，较其他密码形式具备以下几个优势：

① 易于标准化。在各种网络数据通信中，信息遵循相关协议，尤其是在三网合一后的基于IP的标准，使分组密码算法的使用前景更加广阔。

② 使用分组密码算法容易实现同步。一个组的传输错误不会影响到其他组，丢失一个加密数据组也不会影响随后的加、解密。

在对称密码体制中，加密和解密的密钥是相同的或相互之间比较容易转换，因此对称密码体制的安全性主要取决于密钥的安全性。对称密码技术也称单钥密码技术，主要有分组密码与流密码这两个技术。在非对称密码体制中，加密密钥与解密密钥不同，加密密钥是公开的。本章主要介绍对称密码技术的概念、原理和一些具有代表性的对称加密算法，如DES、AES、3DES等。

首先，分析对称密码体系下的通信模型。保密通信的目的是确保通信双方可以通过一个公用信道安全地传输信息，其他人无法获取他们的通信内容。如图2-1所示是对称密码体系下的通信模型。

这是对称密码体系下的一个最简单的两点间的通信模型。在图2-1中，发送者为Alice，接收者为Bob。该图显示了对称密码的加密、解密的过程。Alice想要Bob得到的真实消息称为明文。将明文转化为人们不能理解的没有规则、看起来随机的消息C称为密文。加密器产生密钥K并利用密钥K作用于明文，产生密文C。密钥K具有唯一性，即相对于相同的明文，不同的密钥加密生成不同的密文。用数学公式来描述以上过程：C=EK(M）。产生密文后，该密文就通过信道向Bob传送。

Bob为了恢复出Alice所发送的明文，要通过解密器和与发送方相同的密钥K从密文C中恢复最初的明文。该过程的数学描述为：M=DK(C)。

窃听者Eve可以得到加密和解密算法，可以从不安全的通道上得到密文C，但不能从安全通道得到密钥K。这样就要求对称密码满足以下条件：

① 从已知的密文或明文密文对，不可能计算出密钥或明文。

② 密钥空间应满足要求，且加密和解密算法适用于密钥空间所有的元素。

③ 应符合Kerchoff原则，即不依赖于算法，而依赖于密钥的保密。

对称算法有时又称为传统密码算法，所以本章先介绍对称密码体系中的几种古典密码。

2.2 古典密码

2.2.1 古典密码简介

从密码学发展历史来看，密码体系可分为古典密码和现代密码两大类。古典密码大致上可分为代换密码与置换密码两类。

数据可以表示为文字、声音、图像等形式。但不论数据以何种形式表示，当其被输入计算机中时，都是以某种编码的形式来存储的。现代密码学将这些数字化的信息加密和解密的算法作为研究的对象。而古典密码主要针对文字书信，以字符为基本加密和解密单元的密码，如字母表等。现代的加密技术中以信息块为基本加密单元，可应用于计算机系统中。由于计算机系统普遍采用二进制数据，所以基于二进制数据的加密方法是现代密码学研究的主要对象。

古典密码主要的用途是对文字信息进行加密和解密。文字由字母表中的字母组成，可根据字母在字母表中的排列顺序用数字信息对字母进行编码，如下所示。

字母 ： M N O P Q R S T U V W X Y Z

数字 ： 13 14 15 16 17 18 19 20 21 22 23 24 25 26

古典密码大多具有数学属性，根据其表示方法可以对字母进行算术运算，字母的加减等价于代数的运算。如果将字母表看成是循环的，那么字符的运算可以通过模运算来实现。

古典密码历史悠久，密码学在公元前400多年就已经产生了，《破译者》一书中曾记载道：“人类使用密码的历史几乎与使用文字的时间一样长。”下面将着重介绍一些典型的古典密码。

2.2.2 代换密码

代换密码就是将被加密明文的字符替换为密文中的另一种字符，接收者只要对密文做反向替换就可以恢复出原始明文。它使用代换的方式进行加密。

如图2-2所示就是一种代换密码，即第一个字母代换最后一个字母，第二个字母代换倒数第二个字母，依此类推。在代换加密体系中，使用了密钥字母表。它可以分为单表代换密码与多表代换密码两类。所谓的单表代换密码是指由一个字母表构成的替代密码，图2-2中的密码就是一种单表代换密码，明文与密文间是一一映射的。多表代换密码是由多个字母表构成的替代密码，明文中的同一字符可在密文中表现为多种字符，明文与密文之间是一对多的映射关系。例如，下面的密码就是一对多的多表代换密码。

明文：A B C D E F

密文：America Belgium China Denmark Egypt France

下面将具体地介绍代换密码加密法。

1.单表代换密码

单表代换密码的一种典型的算法是凯撒密码算法，又称为循环移位密码算法。这一著名的密码算法是公元前100年由罗马的凯撒发明的，所以该算法被称为凯撒密码算法。它的加密方法是把明文中所有字母都用它右边的第k个字母替代，且字母表是循环的。加密算法可以用如下公式表示：

c(x)=(p+k)mod 26，0<k≤25

p表示明文字母；k为密钥。

对应的解密算法为

p(x)=c-kmod 26

例如k=4时，明文{house}被加密为{lsyai}。

c(h)=(8+4)mod 26=12=l

c(o)=(15+4)mod 26=19=s

c(u)=(21+4)mod 26=25=y

c(s)=(23+4)mod 26=1=a

c(e)=(5+4)mod 26=9=i

上述k=4的凯撒密码，若对其进行解密，由于对称密码的特性，其密钥k仍为4，解密过程如下：

p(l)=(12-4)mod 26=8=h

p(s)=(19-4)mod 26=15=o

p(y)=(25-4)mod 26=21=u

p(a)=(1-4)mod 26=(-3)mod 26=23=s

p(i)=(9-4)mod 26=5 mod 26=5=e

凯撒密码的优点是密钥简单容易记忆。但明文与密文的映射关系过于简单，所以安全性较差。

在凯撒密码基础上，介绍一个更有代表性的密码算法（仿射密码），它的加密算法为

c(x)=(ap+b)mod m

其中a与m互素，通常m是英文字母的个数。其对应的解密函数为

p=[(a-b)/a]modm

其中1/a为a在Zm群的乘法逆元。由此可见，仿射密码的密钥K=(a，b)。而凯撒密码是仿射密码的一个特例。

对于凯撒密码而言，它只有25种可能的密钥，因此很容易通过穷举密钥的办法来找到密码所使用的密钥。对于仿射密码来说，因为与26互素的整数共有12个：1、3、5、7、9、11、15、17、19、21、23和25，所以仿射密码的密钥空间为12×26=312。显然这个密钥空间比较小，也可以通过穷举法攻击来恢复明文。这使得单表代换密码的安全性大大降低，因此使用多表代换密码来提高加密的安全性。

2.多表代换密码

单表代换密码比较容易被攻破，因为密钥空间不够大，而且无法改变明文字母使用频率的一些统计特性。改进的方法就是进行代换时采用多个代换规则，这种反复成为多表代换密码。周期代换密码是一种常用的多表代换密码，又称维吉尼亚（Vigenere）密码，它是由16世纪法国人Blaise de Vigenere发明的。这种代换法是循环地使用有限个字母来实现代换的一种方法。如果明文信息m1，m2，m3，…，mn，使用n个字母（分别为B1，B2，B3，…，Bn）代换法，那么，m1字母根据Bn的特征来代换，mn+1又将根据B1的特征来代换，mn+2又将根据B2的特征来代换，如此循环。可见B1，B2，B3，…，Bn就是加密的密钥。

Vigenere加密表以字母表以为基础把26个英文字母进行循环移位，排列成26×26的方阵。该方阵采用的算法为

c(a)=(a+Bi)modn，i=(1，2，3，…，n)

实际中，往往将某个容易记忆的词或者词组当做密钥。给一个信息加密时，只要将密钥重复，与明文对齐，通过查询维吉尼亚表，即可得到密文。

例2-1 已知key为密钥，明文为secret，通过Vigenere加密法，求其密文。

解：明文P=SECRET

密钥K=KEYKEY

密文E=CI AB I R

其加密过程就是以明文字母选择列，以密钥字母选择行，两者交点就是加密生成的密文字母。解密时，以密码字母选择行，从中找到密文字母，密文字母所在列的列名即是明文字母。

2.2.3 置换密码

公元前6世纪，古希腊人曾使用称为“Scytail”的棍子来加密信息。它是一个带状物，用纸带或皮带缠在一个圆柱上。送信人先在棍子上绕一张纸条，然后把信息竖写在纸条上，最后打开纸条送给送信人。如果不知道棍子的直径，就不能正确地恢复信息。人类有记载的通信密码始于公元前400多年，当时的古希腊人发明了置换密码。

置换密码采用移位法进行加密。它把明文中的字母重新排列，本身不变，但位置变了。例如，把明文中字母的顺序倒过来写，然后以固定长度的字母组发送或记录。比如明文为ITISYOURS，密文则为SRUOYSITI。

首先，看一下栅栏密码，与Scytail密码类似，加密时将明文按照纵向或者横向顺序置于表格中，当写完一列或一行，再从第二列或第二行纵向或横向写，而密文则以逆向的方式读取。

例2-2 如明文为INFORMATION SECURITY，通过列置换法求其密文。

解：

I N F O R M

A T T I O N

S E C R I T

Y

密文的形式为：

IASYNTEFTCOIRROIMNT

其解密比较简单，栅栏的行数是解密密文的关键。实际上，横列置换密码与Scytail密码本质上是相同的，其密钥是栅栏的行数或木棍的直径。横列置换密码并不安全，它的密钥空间很小。窃取者可以将密文置换成不同的矩阵组合来进行破解。

接下来，介绍一种通过矩阵置换进行加密的方法，其算法就是将明文中的字母按给定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵的字母来产生密文。

例2-3 明文为NEWSPAPER，置换矩阵为f=，求其密文。

解：将明文NEWSPAPER按行排在3×4矩阵中，如下：

根据置换矩阵，将按第2、4、1、3列排成密文。

得到密文：

ESNWAEPPR

密钥K=(m*n，f )，m为矩阵的行数，n为矩阵的列数。

解密的密钥与加密的密钥相同，用的置换矩阵仍为。

2.3 分组密码

分组密码是将明文进行分组，每个分组被当做一个整体来产生等长的密文分组。Shannon（信息论的创始人）在1945年提出可以用扰乱（Confusion）和扩散（Diffusion）交替的方法构造乘积密码。“扩散”指每一位明文编码的影响要尽可能地扩散到更多的密文中，“混淆”是将明文和密文之间的统计特征复杂化。Feistel 将这一思想应用在分组密码中，提出用替代和置换交替的方式来构造密码。而现在正在使用的所有重要的对称分组密码几乎都采用了Feistel密码结构。分组密码主要包括DES、AES、IDEA等，本章主要介绍分组密码的设计原理，以及DES和AES这两个具有重要影响和广泛应用的分组密码算法。

2.3.1 DES算法的描述

DES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。在当前DES作为一种加密方法而被广泛使用。DES的由来有一段历史，在1969年IBM成立了一个由HorstFeiste领导的计算机密码编码研究项目组，他们在1972年研制出一种被称为Lucifer的加密算法。它是一种Lucifer结构的分组密码，其中的分组长度是64bit，密钥长度是128bit。随后，IBM 的研究人员在Lucifer 的基础上做了进一步的研究。下面是DES算法的发展过程。

1972年美国商业部所属的美国国家标准局（NBS）开始实施计算机数据保护标准的开发计划。

1973年5月13日，NBS发布文告征集在传输和存储数据中保护计算机数据的密码算法。

1975年3月17日，首次公布DES算法的描述，认真地进行公开讨论。

1977年1月15日，DES正式被批准为无密级应用的加密标准，当年7月15日正式生效，以后每隔5年美国国家安全局（NSA）做出评估，并重新确定是否继续作为加密标准。

最近一次评估是在1994年1月，决定DES在1998年12月以后不再作为加密标准。

随着DES被广泛地应用，关于DES的攻击手段也得到了很大的发展，其中具有代表性的攻击有：差分密码分析攻击、线性分析、截断差分分析等。而本书将要对线性密码分析攻击法进行详细的研究和探讨。

2001年，高级加密标准AES成为取代DES的高级密码算法。DES是一种分组密码，明文、密文和密钥的分组长度都是64位，并且是面向二进制的密码算法。DES处理的明文分组长度为64位，密文分组长度也是64位，使用的密钥长度为56位（实际上函数要求一个64位的密钥作为输入，但其中用到的只有56位，另外8位可以用做奇偶校验位或者其他用途）。DES的解密过程和加密相似，解密时使用与加密同样的算法，不过子密钥的使用次序要反过来。DES的整个体制是公开的，系统的安全性完全靠密钥的保密。DES算法的加密过程经过了三个阶段，整体结构如图2-3所示。

首先，64位的明文在一个初始置换IP后，比特重排产生了经过置换的输入，明文组被分成右半部分和左半部分，每部分32位，以L0和R0表示，如图2-4所示。

接下来的阶段是由对同一个函数进行16次循环组成的，16轮迭代称为乘积变换或函数f。这个函数本身既包含换位又包含代替函数，将数据和密钥结合起来，最后1轮的输出由64位组成，其左边和右边两个部分经过交换后得到预输出。

最后阶段，预输出通过一个逆初始置换IP-1算法就生成了64位的密文结果（图2-5）。可将DES的加密过程用如下数学公式表示：

相对应的DES的解密过程由于DES的运算是对合运算，所以解密和加密可共用同一个运算，只是子密钥的使用顺序不同。解密过程可用如下数学公式表示：

下面再讲一下DES中的非线性变换f(Ri-1，Ki）。它的功能是将32比特的输入再转化为32比特的输出。其过程如图2-6所示。

对f变换说明如下：输入Ri-1（32比特）经过变换后，扩展为48比特。扩展后的比特串的下标如图2-7所示。

扩展后的比特串分为8组，每组6比特。各组经过各自的S盒后，又变为4比特（具体过程见后），合并后又成为32比特。该32比特经过P变换后，其下标如图2-8所示。

经过P变换后输出的比特串才是32比特的f(Ri-1，Ki)。

下面再讲一下S盒的变换过程。任取一S盒，如图2-9所示。

在其输入b1，b2，b3，b4，b5，b6中，计算出x=b1*2+b6，y=b5+b4*2+b3*4+b2*8，再从Si表中查出x行，y列的值Sxy。将Sxy化为二进制，即得Si盒的输出，如图2-10所示。

DES在算法结构上采用置换、代替、模2加等基本密码运算构成轮加密函数，对轮加密函数进行16次迭代。DES 算法是对合算法，工程上比较容易实现。DES算法中除了S盒是非线性变换外，其余变换都是线性变换，因此DES算法的安全关键在于S盒，其本质是数据压缩，把6位的数据压缩为4位数据。此外，S盒和置换P相互结合，具有较强的抗差分攻击和抗线性攻击能力。DES的子密钥产生和使用能确保原密钥的各位的使用次数基本相等，这也使得DES的保密性得到了进一步的增强。DES在总体上应该说是极其成功的，但在安全性上也有其不足之处。

密钥太短：IBM原来的Lucifer算法的密钥长度是128位，而DES采用的是56位，这显然太短了。1998年7月17日美国EEF（Electronic Frontier Founation）宣布，他们用一台价值25万美元的改装计算机，只用了56个小时就穷举出一个DES密钥。1999年EFF将该穷举速度提高到24小时。

存在互补对称性：将密钥的每一位取反。用原来的密钥加密已知明文得到密文分组，那么用此密钥的补密钥加密此明文的补便可得到密文分组的补。这表明，对DES的选择明文攻击仅需要测试一半的密钥，从而穷举攻击的工作量也就减半了。除了上述两点之外，DES 的半公开性也是人们对DES颇有微词的地方。

对DES安全性批评的意见中，较为一致的看法是DES密钥长度太短，不能抵御穷举搜索攻击，事实证明确实如此。1997年1月28日，美国的RSA数据安全公司悬赏10000美金破译长度为56比特的DES算法。其目的是调查Internet上分布式计算能力，并测试密钥长度为56比特的DES算法的相对强度。美国克罗拉多州程序员Veser从1997年3月起用了96天时间，在Internet上数万名自愿者的协同工作下，与1997年6月17日成功找到了DES的密钥，从而获得了RSA公司颁布的10000美元的奖励。因此Verser说：“对一个坚定的攻击者来说，56bit DES已经不再安全了。”这一事件表明：用穷举搜索方法破译 DES 已成为可能，从而使人们认识到随着计算能力增强，必须相应地增加算法的密钥长度。3-DES的设计和应用克服了DES的这一缺点，其密钥长度是DES的3倍。美国国家标准技术研究所在确定新的数据加密标准AES之前，曾把3-DES作为临时的数据加密标准。对于高度敏感的信息而言，3-DES 仍然是极好的和可靠的选择。由于3-DES是以DES为基础的，更改现有的软件去应用3-DES是很容易的事，所以3-DES得到了更为广泛的应用。

2.3.2 AES算法结构

1997年4月15日，美国国家标准和技术研究所（National Institute of Standards and Technololgy， NIST）发起征集AES算法的活动，并成立了专门的AES工作组，目的是为了确定一个非保密的、公开披露的、免费使用的分组密码算法，用于保护今后政府的敏感信息，并希望能够成为秘密和公开部门的数据加密标准。AES的基本要求是：比三重DES快，而且至少和三重DES一样安全，分组长度为128比特，密钥长度为128/192/256比特。1999年3月22日，举行了第二次AES候选会议，选出5个AES将成为新的公开的联邦信息处理标准（Federal Information Processing Standard， FIPS），成为用于保护美国政府组织敏感信息的特殊的加密算法。美国国家标准技术研究所（NIST）预测，AES会被广泛地应用于各种组织、学校及个人。入选AES的五种算法是MARS、RC6、Serpent、Twofish和Rijndael。2000年10月2日，美国商务部长宣布，经过三年世界著名密码专家的讨论， Rijndael数据加密算法最终成为AES标准。这一新加密标准将取代DES数据加密标准成为21世纪保护国家敏感信息的高级算法。

Rijndael 算法本质上是一种对称分组密码体制，采用代替/置换网络，每轮由三层组成：线性混合层确保多轮之上的高度扩散，非线性层由16个S盒并置起到混淆的作用，密钥加密层将子密钥异或到中间状态。Rijndael是一个迭代分组密码，其分组长度和密钥长度都是可变的，只是为了满足AES的要求才限定处理的分组大小为128位，而密钥长度为128位、192位或256位，相应的迭代轮数Nr为10轮、12轮、14轮。Rijndael汇聚了安全性能、效率、可实现性、灵活性等优点。最大的优点是可以给出算法的最佳差分特征的概率，并分析算法抵抗差分密码分析及线性密码分析的能力。Rijndael对内存的需求非常低，也使它很适合用于受限制的环境中，Rijndael的操作简单，并可抵御强大和实时的攻击。

Rijndael算法在整体结构上采用的是Square结构而不是Feistel结构，该结构由4个不同的阶段组成，包括1个混乱和3个代换（图2-11）。

① 字节代换（SubBytes），用一个S盒完成分组中的按字节的代换。

② 行移位代换（ShiftRows），一个简单的置换。

③ 列混淆（MixColumns），一个利用在域GF(28)上的算术特性的代换。

④ 轮密钥加（AddRoundKey），利用当前分组和扩展密钥的一部分进行按位异或（XOR）。

Rijndael算法中的加密、解密过程要经过多次数据变换操作，每一次变换操作会产生一个中间结果，称为状态（State），算法的执行过程如下。

① 给定一个明文M，将 State 初始化为M，并进行 AddRoundKey 操作，将轮密钥与 State异或。

② 对前Nr -1轮中的每一轮，用S盒进行一次SubBytes代替变换，对State做一次ShiftRows行移位操作，再对State做一次MixColumns列混淆操作，然后进行AddRoundKey操作。

③ 按照顺序分别进行SubBytes、ShiftRows、AddRoundKey操作。

④ 将最后的State中的内容定义为密文C。

AES的解密算法与加密不同，基本运算中除轮密钥加（AddRoundKey）不变之外，其余操作如SubBytes、ShiftRows、MixColumns都要求进行求逆变换。

在安全性方面，Rijndael加密、解密算法不存在像DES里出现的弱密钥，因此在加密、解密过程中，对密钥的选择就没有任何限制；并且根据目前的分析，Rijndael算法能有效抵抗现有已知的攻击。

在AES算法中，Nb表示相应与输入、输出或状态的128位分组的32位字的个数（128=Nb× 32，从而得到Nb=4）。

Nk表示相应于128、196、256位加密密钥长度的32位字的个数。

128=Nk×32，Nk=4

196=Nk×32，Nk=6

256=Nk×32，Nk=8

上述分别为10、12和14。

AES算法利用密钥K，执行一个密钥扩展历程，生成密钥次序表。密钥扩展生成Nb(Nr+1）个字：当Nr=0时为Nb个字，当Nr=1时为2 Nb个字，当Nr=2时为3 Nb个子，…，当Nr=10时为11 Nb个字。这样，结果密钥次序表示一个线性的四字节字的数组[wi]，其中0≤i<Nb(Nr+1)。

RotWord()以四字节[a0，a1，a2，a3]为输入，执行循环置换，比如[a0，a1，a2，a3]。

SubWord()以四字节字为输入，并把S盒应用到四个字节的每一个字节上，产生一个输出字（图2-12）。

2.3.3 其他分组密码

除了前面介绍的分组密码外，还有其他很多的分组密码，比如DES变形、RC系列分组密码（包括RC2、RC5、RC6等）、CLIPPER密码、SKIPJACK 算法、IDEA密码等。国际上目前公开的分组密码不下100种，在此不能一一介绍，本小节仅介绍KASUMI密码。

由于第三代移动通信的特殊性，3GPP（3Generation Patnership Project）要求新的密码算法应能提供相当高的安全性，能够抵抗现有的攻击，而且算法不要太复杂，硬件实现简单，电路的功耗低。3GPP在日本三菱公司的MISY1密码算法的基础上进行了改进，从而形成了KASUMI密码算法。

KASUMI 密码算法是一种分组密码，明文和密文的分组长度都是64位，密钥的长度为128位。在结构上KASUMI密码算法采用Feistel结构，对基本轮函数进行8轮迭代运算。64位的输入明文M被分为左右两半，各32位，左一半记为L0，右一半记为R0：

M =L 0‖R0

对于i, 1≤i≤8

其中RKi是第i轮迭代的轮密钥。每一轮的密码操作是：将第i-1轮的左一半Li-1直接作为第i轮迭代输出的右一半。而第i-1轮的左一半Li-1在第i轮的轮密钥RKi的控制下经过密码轮函数fi的变换，其输出再与第i-1轮的右一半Ri-1模2相加，结果作为第i轮迭代输出的左一半。经过8轮迭代后得到64位密文C=L8‖R8。

KASUMI密码算法采用的是Feistel结构，对基本轮函数进行8轮迭代，其安全性也主要取决于轮函数。经评测3GPP认为，KASUMI密码算法可以抵抗包括差分攻击和线性攻击在内的现有大部分攻击，在3G的应用环境中是安全的。

2.4 序列密码

序列技术在实际中具有重要的应用。例如，在扩频通信中，通常使用具有良好自相关特性和互相关特性的序列作为扩频码序列，在保密通信中也通常采用序列密码进行数据的加密传输。研究和设计具有良好自相关特性和互相关特性的序列族是扩频通信中序列设计追求的目标。

序列密码也称流密码（Stream Cipher），是由1917年的Vernam密码发展而来的，包括RC4和软件优化加密算法SEAL等算法，以及Vernam密码或一次性密码本的特殊情形。序列密码是世界各国军事和外交等领域使用的主流密码之一。

与分组密码不同，序列密码将消息当做连续的符号序列，用密码流加密。常用的加密是将明文序列和密钥流逐位在有限域上相加。用数字元器件或算法产生的密钥流通常是周期性重复的，前面介绍的Vigenere就是序列密码的特征，但现代序列密码的密钥流周期更长。

由于常见的加密仅仅将密钥流和明文诸位相加，因此序列密码设计的核心是生成密钥流。在密钥流生成算法中，线性反馈移位寄存器（LFSR）是重要的部件之一，但它产生序列的线性性质使它不能直接作为密钥流使用，因此常用非线性滤波和非线性组合两种方法将 LFSR 的输出转换为密钥流，以下将分别简介相关的方法。

序列密码以其加解密速度快，密文无扩展的独特优点在某些场合下备受青睐，因此，序列密码成为密码学研究中一个非常活跃的领域。序列密码加解密相对简单，其安全强度主要取决于种子序列的安全性，线性复杂度是衡量种子序列安全性的一个重要性能指标，具有较大线性复杂度的种子序列往往具有较大的安全性，因此，在序列密码的设计中通常要求产生的种子序列具有较高的线性复杂度。

2.4.1 线性反馈移位寄存器

移位寄存器是基本的数字电路元器件，它实现一段比特的位置移动，而 LFSR 一般指一种利用移位寄存器和反馈输入的数字序列生成方法。LFSR实现简单、效率高，并且可以借助代数等进行分析。n阶反馈移位寄存器的基本模型如图2-13所示，这是一个左移移位寄存器，寄存器每运动一次，n级寄存器的内容就向n-1级步进一次，即第2级的内容S1传送给第1级作为S0，依此类推，第n级内容传送给第n-1级，最后第n级的内容由反馈函数f(s0，s1，…，sn-1)传送。如果f(s，0 s，1 …，sn1-)是线性的，则此寄存器成为线性移位寄存器，反之称为非线性移位寄存器。

f(s0，s1，…，sn1-)的自变量取自相应寄存器中内容（0或1）。移位寄存器的状态序列为(s0， s1，…，sn-1)，如果处处用sn表示，则sn=f(s0，s1，…，，其中gi=1或0表示第i+1级寄存器参与或不参与反馈运算，表示成对应的多项式即为反馈多项式xn=f(x)=g0x+g1x+…+gn-1 xn-1=1+g1x+…+gn-1 xn-1，g(x)=1+g1x+……+gn-1 xn-1+xn为线性移位寄存器的连接多项式。

LFSR输出序列的主要性质之一是周期性。由于LFSR状态有限，当它重复出现时，产生的序列将具有周期性。LFSR 序列按周期性的不同又分为两种：当序列一开始就进入周期循环，即a j+T=aj对任何整数j≥0都成立，其中T表示周期；当a j+T=aj仅对整数j＞0成立，则是终归周期序列。由于非全零状态的数量为（2n-1），因此最大周期为（2n-1），此时称序列为最大周期LFSR序列，简称M序列。显然，对密码设计来说，M序列是最希望获得的LFSR序列，研究人员已经证明，当以上连接多项式f(x)是所谓的本原多项式时，LFSR产生的序列都是M序列。

LFSR输出序列的另一个性质是统计特性，其中M序列有如下性质。

1.符号频度

在一个周期中，“1”出现2n-1次，0出现（2n-1-1）次。

2.游程数量和长度

游程是指序列中统一符号连续出现的一段，如…10001…中的000。将一个周期的首尾相连，其游程总是为N=2n-1，其中0游程与1游程的数目各占一半，当n＞2和1≤i≤n-2时，游程分布如下。

① 长为i的0游程有N/2i+1个；

② 长为i的1游程有N/2i+1个；

③ 长为（n-1）的0游程有1个；

④ 长为n的1游程有1个。

M 序列已经有较好的随机性，但并不能直接作为序列密码的密钥流。Massey 曾提出的 B-M算法可以通过根据一段已知序列构造一个尽可能短的 LFSR 来产生全部序列。但由于序列密码常用的加密时将明文序列和密钥流逐位在有限域上相加，若直接将 LFSR 序列作为密钥流，已知明文攻击可以通过实施减法获得LFSR序列，进而可以用B-M算法构造LFSR。

例2-4 一个 GF（2）上的4阶移位寄存器，其初始状态为S0=(0001)，其连接多项式为g(x)=x4+x+1，写出线性移位寄存器的输出序列。

分析：由连接多项式 g(x)=x4+x+1知，其反馈函数为 f(s0，s1，s3)=s0+s1，则状态与输出序列为001101011110001，其推导过程如图2-14所示，它是周期为24-1=15的序列，显然这是一个有最大周期的序列。

2.4.2 非线性序列密码

使用非线性滤波和非线性组合生成密钥流是两种常用的序列密码构造方法。前者构造的密码也常被称为前馈序列密码。非线性滤波生成器如图2-15所示，采用非线性输出f对LFSR的状态进行非线性运算，它在每次新状态产生后抽取特定位置上的状态值作为输入，计算 f 的值，将这个值的序列作为密钥流；非线性组合生成器（图2-16）也采用非线性函数 f 并将这个函数值的连续输出作为密钥流，但它的输入来自多个 LFSR 的同步输出。在以上密码体制中，一般将 LFSR的初态作为密钥，但密钥也可包括非线性输出函数f；在GF(2)上，通常由ci=mi⊕ki得到明文。

序列密码依密钥流生成方式的不同而面临不同攻击。以上两类序列密码面临的攻击包括相关攻击、快速相关攻击、最佳防射逼近攻击、线性校验子攻击、线性一致性测试攻击、逆向攻击、代数攻击等，它们试图从不同角度获得密钥相关信息。但是，序列密码在当前仍在发展并被使用，它仍然是对称密码的可选方式之一。

2.4.3 RC4序列密码

RC4算法是Ron Rivest 于1987年为RSA数据安全公司设计的一种序列密码。在最初的7年之中因为专利没有公开，直到1994年9月有人把它的源代码张贴在Cypherpunks邮件列表中。RC4应用于很多领域的安全模块中，如在 SSL 协议中和无线 WEP 中互联网通信的保密性，还集成到Windows、Oracle Secure SQL Lotus Notes等系统中。此算法密钥长度可变，密钥的形式是所有9比特值的排列，更简单且易于软件实现。

RC4算法描述如下：

用1～256个字节（8到2048位）的可变长度密钥初始化一个256个字节的状态矢量S，S的元素记为是S[0]，S[1]，…，S[255]，从始至终置换后的S包含从0到255的所有8比特数。对于加密和解密，字节K由S中256个元素按一定方式选出一个元素而生成。每生成一个K值，S中的元素就被重新置换一次。

RC4包括两部分，KSA（Key Scheduling Algorithm）算法和伪随机序列产生算法（Pseudo Random Generation Algorithm，PRGA）。KSA算法把密钥变成一个S={0，1，2，……，N-1，N=2n}的初始排列。PRGA 利用排列产生一个伪随机序列作为密钥输出。假设给定一密钥 k的长度为 L比特，可表示为k[0]，k[1]，…，k[L-1]，RC4加密算法以伪C源代码表示如下。

（1）KSA（K）

初始化：for(i=0;i<=255;i++)
      S[i]=i;
        j=0;
        for(i=0;i<=255;i++)
        {
          j=(j+S[i]+k[i mod L]) (mod 256)
变换S[i]与S[j]：swap(S[i],S[j])
 }

（2）加密

PRGA(K)
两个数组元素S[i]与S[j]的和确定加密用的密钥
i=j=0;
对于每比特明文Mi
{
  i = (i+1)(mod 256)
  j=(j+S[i])(mod 256)
  swap(S[i],S[j])
  t=(S[i]+S[j])(mod 256)
  Ci=Mi⊕S[t]
}

RC4在 WEP 应用中，也存在两个较大的漏洞。第一个漏洞叫不变性缺陷，即存在着一个密钥类，在这个密钥类里面，很小的一部分密钥可以决定初始排列中（也就是KSA算法的输出）很大一部分比特数。第二个漏洞就是相关密钥缺陷。由于算法所使用的密钥中有一部分是公开的，即初始化向量IV。如在24位IV值中，有9000多个弱密钥。攻击者收集到足够的使用弱密钥的数据包后，就可对它们进行分析，只要试用很少密钥就可接入网络。利用认证与加密的安全漏洞，在几分钟时间内，WEP密钥即可被破译。但是，RC4对抗已知攻击方面，也表现出较强的非线性特征，对128位长密钥的RC4还没有非常有效的攻击方法。