第3章〓对称密码体系 本章先介绍对称密码体系的概念、结构和特点,之后详细阐述对称密码体系的两类算法: 流密码和分组密码。流密码部分重点说明其构造算法和工作原理; 分组密码部分主要介绍Feistel密码结构。然后通过介绍一些有代表性的加密算法,如DES、AES和IDEA,强化读者对对称加密算法的理解。最后介绍分组密码的常用工作模式。 3.1 3.1〓对称密码体系概述 对称密码算法(Symmetric Algorithm)也称传统密码算法、单钥密码算法,它包括许多数据加密方法。公钥密码技术出现之前,对称密码系统已被使用了多年。对称密码体系的基本模型如图31所示,其基本特征是: 数据加密和解密使用同一个密钥。在算法公开的前提下所有秘密都在密钥中,因此密钥本身应该通过另外的秘密信道传递。对称密码体系的安全性依赖于两个因素: 其一,加密算法强度至少应该满足当敌手已知算法时通过截获密文不能导出明文或者发现密钥,更高的要求是敌手即使拥有部分密文以及相应明文段落也不能导出明文或者发现密钥系统; 其二,发送方和接收方必须以安全的方式传递和保存密钥副本,对称加密的安全性取决于密钥的保密性而不是算法的机密性。 图31对称密码体系的基本模型 对称加密算法可以分成两类: 一类为流算法,是一次只对明文中单个位(有时为字节)加密或解密的运算; 另一类为分组算法,是一次只对明文的一组固定长度的字节加密或解密的运算。现代计算机密码算法一般采用的都是分组算法,一般分组的长度为64位,这是由于这个长度大到足以防止分析破译,但又小到足以方便使用。 对称算法的加密和解密表示为 Ek(M)=C Dk(C)=M 常用的对称加密体系有五个组成部分。 (1) 明文M: 原始数据信息。 (2) 加密算法Ek: 以密钥k为参数,对明文M进行多种置换和转换的规则和步骤,结果即为密文。 (3) 密钥k: 加密与解密算法的参数,直接影响对明文进行变换的结果。 (4) 密文C: 对明文进行变换的结果。 (5) 解密算法Dk: 加密算法的逆变换,以密文C为输入、密钥k为参数,变换结果为明文。 对称密码体系的优点是算法实现的效率高、速度快,缺点是密钥的管理过于复杂。如果按照上述方法,任何一对发送方和接收方都有他们各自商议的密钥,那么很明显,假设有N个用户进行对称加密通信,则需要产生N(N-1)把密钥,每个用户要记住或保留N-1把密钥,当N很大时,记住是不可能的,而保留起来又会引起密钥泄露可能性的增加。常用的对称加密算法有DES、AES和IDEA等。 3.2 3.2〓流密码 3.2.1流密码简介 香农证明了“一次一密”密码体制在理论上是不可破译的,促使人们长期以来一直寻求某种能仿效“一次一密”密码的密码体制,流密码就是所寻求的方法之一。流密码也称序列密码(Stream Cipher),具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点。因此在实际应用中,特别是在专用或机密机构中保持着优势,典型的应用领域包括世界军事、无线通信、外交通信。 流密码加密时先将文本、声音、图像等原始明文转换成01串,然后将它与密钥流逐位异或生成密文流传送给接收者,接收者将密文流与相同的密钥流逐位异或恢复出明文。在流密码中,将明文分成一定长度的分组,分别对各个分组用同一密钥流序列的不同部分进行加密产生相应的密文。相同的明文分组因为处于明文序列中的不同位置,所对应的密钥流位也不同,因此会加密成不同的密文组。 流密码系统可以用一个六元组(M,C,K,Z,Ek,Dk)来描述。其中,M表示明文空间,C表示密文空间,K表示密钥空间,Z表示密钥流生成算法,Ek和Dk表示密钥流与明文(密文)的加密和解密规则,通常为异或运算。对密钥k∈K,由Z确定一个密钥流。流密码系统加解密的原理如图32所示。 图32流密码系统加解密的原理 流密码的加密是用一个密钥流序列(伪随机)和明文序列相异或来产生密文,解密过程相同,即用同一密钥流序列和密文序列相异或来获得明文。 设二进制序列M=M1M2…Mi…Mn是明文序列,Mi∈GF(2),i≥1; 二进制序列C1C2…Ci…Cn作为密文比特流,Ci∈GF(2),i≥1; 序列k=k1k2…ki…kn作为密钥流序列,同样ki∈GF(2),i≥1。加密过程可表示为Ci=Miki,解密操作表示为Mi=Ciki,i≥1。表示按位异或运算。 密钥流序列的伪随机性决定了流密码的安全性。当密钥流序列是由无记忆离散的二进制均匀分布信源产生的随机序列时,产生该序列的密码就是“一次一密”密码,在理论上它已经被证明是安全的。但是,用产生真正随机序列的方法来产生完全相同的随机序列几乎是不可能的。实际使用“一次一密”密码时要求信息的收发双方必须持有加解密信息所用的密钥流副本。已经证明仅当密钥数目与明文数目至少一样多时,“一次一密”才是完全保密的,即密钥必须至少和明文一样长且不重复使用。而很长的密钥序列不便于存储和分配,流密码的设计就是研究如何用一个短的密钥生成一个周期长且安全的密钥流。利用这种方法能够重复产生相同的密钥序列,但产生的序列不是真正的随机序列,而是伪随机的,这就要求伪随机序列满足真随机序列的一些随机特性。要实现保密通信,只需要在信息的发送方和接收方之间传送一个短的密钥。 3.2.2流密码的结构 根据明文和密文的消息流与密钥流序列的关系,可将流密码分为同步流密码和自同步流密码两类。 1. 同步流密码 在同步流密码中,密钥流的产生独立于明文和密文。发送方和接收方只要有相同的密钥和初始内部状态,就能产生相同的密钥流。同步流密码加密结构如图33所示。 图33同步流密码加密结构 由于密钥流与明文串无关,所以同步流密码中的每个密文字符ci不依赖于之前的明文mi-1,…,m1。所以同步流密码的一个重要特点就是无错误传播: 在传输期间一个密文字符被改变只影响该符号的恢复,不会对后继的符号产生影响。但是,在同步流密码中发送方和接收方必须是同步的,用同样的密钥且该密钥操作在同样的位置时才能保证正确解密。如果在传输过程中密文字符有插入或删除导致同步丢失,密文与密钥流将不能对齐,导致无法正确解密。要正确还原明文,密钥流必须再次同步。与同步流密码相反,自同步流密码有错误传播现象,但可以自行实现同步。 2. 自同步流密码 在自同步流密码中,密钥流的产生与之前已经产生的若干密文有关,其加密结构如图34所示。 其中,密钥流ki的生成过程如图35所示。 图34自同步流密码加密结构 图35同步流密码的密钥流生成过程 用函数表示为 σi=F(σi-1,ci-1,…,ci-k) ki=G(σi,k) ci=E(ki,mi) 其中,k是种子密钥; σi是密钥流生成器的内部状态(初始状态记为σ0); F是状态转移函数; G是生成密钥流的函数; E是自同步流密码的加密变换,它是ki与mi的函数。 由此可见,如果自同步流密码中某一符号出现传输错误,则将影响到它之后k个符号的解密运算,亦即,自同步流密码有错误传播现象。等到该错误移出寄存器后寄存器才能恢复同步,因而一个错误至多影响k个符号。在k个密文字符之后,这种影响将消除,密钥流自行实现同步。由于密文流参与了密钥流的生成,使得密钥流的理论分析复杂化,目前的流密码研究结果大部分都是关于同步流密码的,因为这些流密码的密钥流的生成独立于消息流,从而使它们的理论分析成为可能。 3.2.3反馈移位寄存器与线性反馈移位寄存器 如前所述,序列密码的安全强度取决于密钥流生成器生成的密钥流的安全性(如周期、游程分布、线性复杂度等)。有多种产生同步密钥流生成器的方法,最普遍的是使用一种称为线性反馈移位寄存器(Linear Feedback Shift Register,LFSR)的设备。 采用LFSR作为基本部件的主要原因如下: (1) LFSR的结构非常适合硬件实现; (2) LFSR的结构便于使用代数方法进行理论分析; (3) 产生的序列的周期可以很大; (4) 产生的序列具有良好的统计特性。 1. 反馈移位寄存器 图36所示为一个反馈移位寄存器的流程图,信号从左到右。a表示存储单元,取值为0或1,ai的个数n称为反馈移位寄存器的级。在某一时刻,这些级的内容构成该反馈移位寄存器的一个状态,共有2n个可能的状态,每一个状态对应于F上的一个n维向量,用(a1,a2,…,an)表示。函数f是一个n元布尔函数,称之为反馈函数。 图36反馈移位寄存器流程图 在主时钟确定的周期区间上,每一级存储器ai都将其存储内容向下一级ai-1传递,最右一级存储器的内容作为该时刻的输出,根据该时刻寄存器的状态计算f(a1,a2,…,an)作为最左一级寄存器在下一时刻的内容。显然,一个反馈移位寄存器的逻辑功能完全由该移位寄存器的反馈函数所标志。 2. 线性反馈移位寄存器 如果反馈函数形如f(a1,a2,…,an)=cna1cn-1a2…c1an,其中,系数ci=0,1,这里的加法运算为模2加,乘法运算为普通乘法,则称该反馈函数是a1,a2,…,an的线性函数,对应的反馈移位寄存器称为线性反馈移位寄存器,用LFSR表示。否则,称为非线性反馈移位寄存器(NonLinear Feedback Shift Register,NLFSR)。LFSR的示意图如图37所示。 图37线性反馈移位寄存器流程图 显然,根据LFSR中反馈函数的系数ci(i=1,…,n)取值的不同,这样的反馈函数有2n种。令ai(t)表示t时刻第i级寄存器的内容,则第t+1时刻寄存器的内容为: ai(t+1)=ai+1(t),i=1,2,…,n-1 an(t+1)=cna1(t)cn-1a2(t)…c1an(t) 通常称多项式cnxn+cn-1xn-1+…+c1x1+1为上述LFSR的特征多项式。 图384级线性反馈移位寄存器示例 LFSR的特征多项式与它的反馈函数是一一对应的,如果知道了LFSR的特征多项式,便立即可以求得该移位寄存器的反馈函数,反之亦然。 例31图38为一个4级线性反馈移位寄存器,状态转移关系为 ai(t+1)=ai+1(t),i=1,2,3 a4(t+1)=a1(t)a4(t) 假设初始状态为(a1,a2,a3,a4)=(0,1,1,0),则可根据反馈函数计算出该线性反馈移位寄存器在各时刻的所有状态,如表31所示。 表31各时刻的所有状态 t a4 a3 a2 a1 t a4 a3 a2 a1 0011081110 1001191111 21001100111 30100111011 40010120101 50001131010 61000141101 71100150110 由计算过程可见,在t=15时刻该寄存器的状态恢复至t=0时刻的状态,因此之后的状态将开始重复。这个移位寄存器输出的序列就是011001000111101011001000111101……,序列的周期为15,也称该移位寄存器的周期为15(=24-1)。 为了从直观上描述这一LFSR的状态转移情况,可以使用一些方框以及连接这些方框的箭头组成的图形,即为状态转移图,如图39所示。 图39状态转移图 例32图310所示是一个特征多项式为x3+x+1的线性反馈移位寄存器。 图3103级线性反馈移位寄存器示例 根据特征多项式可知,该LFSR的反馈函数为f(a1,a2,a3)=a1a3。假设初始状态为(a1,a2,a3)=(1,1,1),其状态转移图如图311所示。 图3113级LFSR的状态转移图 在状态转移图中,从初始状态开始,沿着箭头所指示的路径依次取出最右边的分量便得到该LFSR的输出序列: 1110100 1110100……,周期为7(=23-1)。3级移位寄存器的所有可能状态数为23=8 (含状态(0,0,0)),而本例中从初始状态(1,1,1)开始可以得到所有非(0,0,0)的状态。 若以状态转移图中任一状态作为初始状态,沿箭头所指示的路径依次取出最右边的分量还可得到另外6个序列: 1101001 1101001……; 1010011 1010011……; 0100111 0100111……; 1001110 1001110……; 0011101 0011101……; 0111010 0111010……。全部7个序列取自同一个状态转移图,将这7个序列之一经过适当的移位可以得到其余任一序列,称这7个序列是移位等价的。 例33图312所示为一个4级LFSR,其特征多项式为x4+x3+x2+x+1。 ① 如取初始状态为(a1,a2,a3,a4)=(1,1,1,1),则其状态转移图如图313所示。 图3124级LFSR 图313初始状态转移图一 对应的输出序列为11110 11110……,周期为5。 ② 如取初始状态为(a1,a2,a3,a4)=(0,0,0,1),则其状态转移图如图314所示。 对应的输出序列为00011 00011……,周期为5。 ③ 如取初始状态为(a1,a2,a3,a4)=(1,0,1,0),则其状态转移图如图315所示。 图314初始状态转移图二 图315初始状态转移图三 对应的输出序列为10100 10100……,周期为5。 以上15个状态连同状态(0,0,0,0)即为4级移位寄存器所有可能的24=16个状态。 3.2.4m序列及其伪随机性 1. m序列与最长线性移位寄存器 根据LFSR的状态转移图可以看出,一个n级LFSR序列的周期最大只能为2n-1: 有的LFSR序列周期可能远小于这个值,但也有的LFSR序列的周期可以达到这个值。如果以GF(2)上n次多项式cnxn+cn-1xn-1+…+c1x+1为连接多项式的n级LFSR所产生的非零序列的周期为2n-1,则称这个序列为n级最大周期线性移位寄存器序列,简称m序列。显然,如果一个n级LFSR产生了m序列,则该LFSR的状态转移图仅由两个圈构成,其中一个是由全零状态构成的长度为1的圈,另一个是由全部其余2n-1个状态构成的长度为2n-1的圈。换句话说,如果一个n级LFSR输出的非零序列是m序列,则其余2n-2个非零序列也是m序列,它们一起构成了一个移位等价类。这里把产生周期为2n-1的m序列的n级LFSR称为最长线性移位寄存器。 显而易见,一个序列是否是m序列应当与产生这一序列的LFSR的连接多项式有密切的关系。事实上,已证明下面的结论是正确的: 如果以GF(2)上n次多项式cnxn+cn-1xn-1+…+c1x+1为连接多项式的n级LFSR所产生的非零序列是m序列,则cnxn+cn-1xn-1+…+c1x+1必为GF(2)上的不可约多项式。这一结果表明一个LFSR为最长移位寄存器的必要条件是它的连接多项式为不可约多项式。 但是,连接多项式为不可约的假设尚不足以保证该LFSR输出的非零序列是m序列。例如,对于GF(2)上4次不可约多项式x4+x3+x2+x+1,对应的LFSR的非零序列周期为5,而非24-1。关于m序列的充分必要条件是: 以GF(2)上n次多项式cnxn+cn-1xn-1+…+c1x+1为连接多项式的n级LFSR所产生的非零序列是m序列cnxn+cn-1xn-1+…+c1x+1为GF(2)上的n次本原多项式。 因此,一个n级LFSR为最长移位寄存器的充要条件是它的连接多项式为GF(2)上的n次本原多项式。例如,多项式x3+x+1是GF(2)上的3次本原多项式,可以验证以此为连接多项式的LFSR的输出序列均为m序列。在实践中,经常使用GF(2)上的本原三项式,这是因为它只需要一个抽头,所以电路设计最简单。 由以上的讨论可知,本原多项式的概念不论是在理论上还是实践上均起重要作用。由代数学的知识知道,当2n-1为素数时,GF(2)上的每一个n次不可约多项式均为n次本原多项式。形如2n-1的素数称为梅森(Mersenne)数,如n=2,3,5,7,13等。 2. m序列的安全性 LFSR的输出序列就是流密码的密钥流。一个LFSR可以输出足够长的二进制位以匹配明文的二进制位。要解密密文,只需要运行具有相同初始状态的LFSR即可。对于给定的整数n,由于m序列是周期最长的,是否可以用m序列直接作为密钥流实现流密码?或者说将LFSR作为密码序列产生器,安全吗?下面通过一个简单的例子来描述m序列直接在流密码中使用时可能遇到的问题。 例34m序列的破译。假设在某个流密码体制中,其密钥流生成器是一个5级LFSR,如图316所示。设攻击者得到密文串10110 10111和相应的明文串01100 11111,并知道该流密码体制中的LFSR是5级的。因此,攻击者可计算出相应使用的密钥流为11010 01000。 图3165级LFSR 由于 a6=c5a1+c4a2+c3a3+c2a4+c1a5 a7=c5a2+c4a3+c3a4+c2a5+c1a6 a8=c5a3+c4a4+c3a5+c2a6+c1a7 a9=c5a4+c4a5+c3a6+c2a7+c1a8 a10=c5a5+c4a6+c3a7+c2a8+c1a9 攻击者可根据密钥流建立如下方程组: 0=c51+c41+c30+c21+c10(1) 1=c51+c40+c31+c20+c10(2) 0=c50+c41+c30+c20+c11(3) 0=c51+c40+c30+c21+c10(4) 0=c50+c40+c31+c20+c10(5) 由(5)知c3=0; 从而由(2)知c5=1; 从而由(4)知c2=1; 从而由(1)知c4=0; 从而由(3)知c1=0。这样,攻击者就知道了该LFSR的具体结构。 攻击者利用这一结构和已经掌握的部分密钥流,就可以计算出之后所有的密钥序列。因此,相应的流密码毫无安全性可言。 上述分析可以推广到一般情况: 对于一个n级的LFSR,如果攻击者可以得到2n个明文密文对,就可以获得该LFSR的具体代数结构。 3. Golomb随机性假设 流密码的安全性取决于密钥流的安全性,要求密钥流序列有好的随机性,以使密码分析者对它无法预测。也就是说,即使截获其中一段,也无法推测后面是什么。如果密钥流是周期的,要完全做到随机性是困难的。严格地说,这样的序列不可能做到随机,只能要求截获比周期短的一段密钥流时不会泄露更多信息,这样的序列称为伪随机序列。之所以把这种序列称为伪随机序列,是因为产生这种序列是按照完全确定的方式进行的,而不像随机序列那样元素的出现是随机的。 下面先说明游程的概念: 设{ai}=(a1a2a3…)为0、1序列,例如00110111,其前两个数字是00,称为0的2游程; 接着是11,是1的2游程; 再下来是0的1游程和1的3游程。 Golomb提出了度量伪随机序列随机性的三条规则,称为Golomb随机性假设。简单起见,假设所述伪随机序列为二元序列a1,a2,…,ai,…,an,…(ai∈{0,1}),其周期为n。 (1) 在每一周期内,0的个数与1的个数近似相等。 (2) 在每一周期内,长度为i的游程数占游程总数的1/2i。 (3) 定义自相关函数为C(τ)=∑ni=1(-1)ai+ai+τ,这是一个二值函数: C(τ)=n,τ≡0 mod n c,其他 其中,c为一个常数。 例如,在周期为7的序列1110010……中,每一周期内有4个1,3个0,4个游程,且有2个长度为1的游程、1个长度为2的游程、1个长度为3的游程。自相关函数为: C(τ)=7,τ≡0 mod n -1,其他 m序列是满足Golomb随机性假设的典型代表。 4. m序列的伪随机性 m序列之所以在电子工程的许多领域获得广泛的应用,主要是由于它具有与随机序列类似的性质,满足Golomb的三个随机性假设。下面不加证明地给出其相应的结论,感兴趣的读者可以自己尝试给出其正确性证明。 (1) 在n级m序列的一个周期段内,1出现的次数恰为2n-1,0出现的次数恰为2n-1-1。 (2) 在n级m序列的一个周期段内,游程总数为2n-1; 长为k(1≤k≤n-2)的0游程(或1游程)数为2n-2-k; 长为n-1的游程只有1个,为0游程; 长为n的游程也只有1个,为1游程。 (3) 自相关函数是二值的,且为 C(τ)=2n-1,τ≡0 mod (2n-1)-1,其他 需要说明的是,对于密钥流序列而言,Golomb随机性假设只是判别二元周期序列的随机性标准的必要条件,并不是充分的。这是因为,由其中很小一部分就可简单地确定出整个密钥序列。 5. 线性复杂度 除了要求伪随机序列具有长周期、满足Golomb的三个随机性假设外,还要求适用于流密码的伪随机序列满足高的线性复杂度(Linear Complexity)。给定二元序列a1,a2,…,ai,…,an,…(ai∈{0,1}),其线性复杂度定义为能够输出该序列的最短线性移位寄存器的级数。 例如,给定序列011 011……,连接多项式为x2+x+1的LFSR可以生成该序列,连接多项式为x3+1的LFSR也可以生成该序列。但连接多项式为x+1的LFSR则无法做到这一点,所以,该序列的线性复杂度为2。序列线性复杂度的概念在密码学中的重要意义是通过以下结论体现出来的: 如果序列的线性复杂度为l(l≥1),则只要知道序列中任意相继的2l位,就可确定整个序列。由此可见,序列线性复杂度是流密码安全性的重要指标,作为密钥流序列,其线性复杂度很小是不安全的。通常认为一个安全的密钥流应该满足以下三个基本条件: 周期充分长; 随机统计特性好(即基本满足Golomb的随机性假设); 线性复杂度大。这里长周期一般指不少于1016,而线性复杂度为序列长度的一半是比较合适的。 3.2.5线性移位寄存器的非线性组合 由于直接使用LFSR的m序列是不安全的,因此线性移位寄存器序列不能直接作为密钥流使用。如果在LFSR的基础上加入非线性化的手段,便可产生适合于流密码应用的密钥序列。 为了使密钥流生成器输出的二元序列尽可能复杂,应保证其周期尽可能大、线性复杂度和不可预测性尽可能高,常使用多个LFSR来构造二元序列,称每个LFSR的输出序列为驱动序列。这样LFSR作为驱动源以其输出推动了一个非线性组合函数所决定的电路产生出非线性序列。实际上,这就是所谓的非线性前馈序列生成器。线性移位寄存器用来保证密钥流的周期长度,非线性组合函数用来保证密钥流的各种密码性能,以抗击各种可能的攻击。许多专用流密码算法都是用这种方法构成,通常可将这种方法分为三类: 滤波生成器、组合生成器和钟控生成器。 1. 滤波生成器 滤波生成器(Filter Generator)是一种常见的密钥流生成器,由一个n级线性移位寄存器和一个m(m