对称密码可分为分组密码(Block Cipher)和序列密码(Stream Cipher)。分组密码通常以一个固定大小作为每次处理的基本单元,而序列密码则是以一个单位元素(一个字母或一个比特)作为基本的处理单元,当然,当分组长度为单位长度时,分组密码也即为序列密码。
分组密码是将明文消息编码表示后的数字(简称明文数字)序列,划分成长度为n的组(可看作长度为n的矢量),每组分别在密钥的控制下变换成等长的输出数字(简称密文数字)序列。分组密码使用的是一个不随时间变化的固定变换,具有扩散性好、插入敏感等优点。分组密码的工作模式允许使用同一个分组密码的密钥对多于一块的数据进行加密,并保证其安全性。分组密码自身只能加密长度等于密码分组长度的单块数据,若要加密变长数据,则数据必须先被划分为一些单独的密码块。通常而言,最后一块数据也需要使用合适填充方式将数据扩展到匹配密码块大小的长度。一种工作模式描述了加密每一数据块的过程,并常常使用基于一个通常称为初始化向量(IV)的附加输入值进行随机化,以保证数据加密安全。下面介绍目前几种常用的分组密码工作模式。
1.电子密码本(ECB)
最简单的加密模式即为电子密码本(ECB,Electronic Codebook)模式。需要加密的消息按照块密码的块大小被分为数个块,并对每个块进行独立加密,如图1所示。
图1电子密码本模式
优点:实现简单、效率高;有利于并行计算;误差不会被传送。
缺点:不能隐藏明文的模式,相同的明文产生相同的密文;可能对明文实施主动攻击。
如图2所示,当黑客获得账号C对应的密文段后,即可以通过对银行A传送给银行B的密文段替换,成功实施ECB密文的重放攻击。
图2电子密码本加密示例
2.密码块链接(CBC)
在CBC模式中,每个明文块先与前一个密文块进行异或,然后再进行加密,即每个密文块都依赖于它前面的所有明文块。同时,为了保证每条消息的唯一性,在第一个块中需要使用初始化向量。加密过程如图3所示。
图3 CBC模式
优点:不易被主动攻击,安全性好于ECB,适合传输长度较长的报文,是目前SSL和IPSec安全协议的应用标准。
缺点:不利于并行计算;有误差传递效应;需要维护初始化向量IV。
3.密文反馈(CFB)
密文反馈(CFB,Cipher Feedback)模式类似于CBC,可以将块密码变为自同步的流密码,工作过程亦非常相似,加密过程如图4所示。
图4 CFB模式
优点:隐藏了明文模式;分组密码转化为流模式,增强了安全强度;可以及时加密传送小于分组的数据。
缺点:不利于并行计算;存在误差传送效应,即一个明文单元损坏可影响多个单元;需要维护一个IV。
分组密码包括DES、IDEA、SAFER、Blowfish和Skipjack等,最新的国际标准算法是AES,之前一直采用DES/3DES算法。在介绍具体的分组加密算法之前,有必要先了解一下分组密码中的一个核心变换——Feistel结构。大多数分组密码的结构本质上都是基于Feistel网络结构,因此,了解Feistel密码结构对于学习分组密码算法是非常有帮助的。
Feistel是用于分组加密过程中多次循环迭代的一种结构,可以有效提高安全性。在每个循环中,可以通过使用特殊的函数从初始密钥派生出的子密钥来应用适当的变换。Feistel加密算法的输入将分组的明文块分为左右两部分L和R,并生成密钥序列K=(K1,K2,…,Kn),进行n轮迭代,迭代完成后,再将左右两半合并到一起产生最终的密文分组。第i轮迭代的函数为:
Li=Ri−1
Ri=Li−1+F(Ri−1,Ki)
其中,Ki是第i轮的子密钥,“+”表示异或运算,F表示轮函数。一般地,各轮子密钥彼此各不相同,且轮函数F也各不相同。代换过程完成后,在交换左右两半数据,这一过程称为置换。Feistel网络的加密和解密过程如图5所示。
图5 Feistel网络加密和解密过程
因此,Feistel网络的安全性与以下参数有关。
(1)分组大小。
(2)密钥大小。
(3)子密钥产生算法:该算法复杂性越高,则密码分析越困难(Feistel网络结构本身就是加密算法或其重要组成部分,根据Kerchhoffs准则是无需保密的)。
(4)轮数n:单轮结构远不足以保证安全,一般轮数取为16。
(5)轮函数F:结构越复杂越难分析。
4.分组加密算法DES
DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准,是1972年美国IBM公司研制的对称密码体制加密算法。明文按64 bit进行分组,密钥长64 bit,密钥事实上是56 bit参与DES运算(第8、16、24、32、40、48、56、64 bit是校验位,使每个密钥都有奇数个1)分组后的明文组和56 bit的密钥按位替代或交换的方法形成密文组的加密方法。
DES算法具有极高安全性,到目前为止,除了用穷举搜索法对DES算法进行攻击外,还没有发现更有效的办法。而56 bit长的密钥的穷举空间为256,这意味着如果一台计算机的速度是每秒检测一百万个密钥,则它搜索完全部密钥就需要将近2285年的时间,可见,这是难以实现的。然而,这并不等于说DES是不可破解的。而实际上,随着硬件技术和Internet的发展,其破解的可能性越来越大,而且,所需要的时间越来越少。使用经过特殊设计的硬件并行处理要几个小时。为了克服DES密钥空间小的缺陷,研究人员又提出了三重DES的变形方式,即采用两个密钥共128 bit长度,仅加大了穷举密钥的计算复杂度,如图6所示。
图6三重DES的变形方式
5.分组加密标准AES
1997年4月15日,美国ANSI发起征集AES(Advanced Encryption Standard)的活动,并为此成立了AES工作小组。
1997年9月12日,美国联邦登记处公布了正式征集AES候选算法的通告。对AES的基本要求是比三重DES快,至少与三重DES一样安全,数据分组长度为128 bit,密钥长度为128/192/256 bit。
1998年8月12日,在首届AES候选会议(First AES Candidate Conference)上公布了AES的15个候选算法,任由全世界各机构和个人攻击和评论。
1999年3月,在第2届AES候选会议(Second AES Candidate Conference)上经过对全球各密码机构和个人对候选算法分析结果的讨论,从15个候选算法中选出了5个,分别是RC6、Rijndael、SERPENT、Twofish和MARS。
2000年4月13日至14日,召开了第3届AES候选会议(Third AES Candidate Conference),继续对最后5个候选算法进行讨论。
2000年10月2日,NIST宣布Rijndael作为新的AES。经过3年多的讨论,Rijndael终于脱颖而出。Rijndael由比利时的JoanDaemen和VincentRijmen设计。
AES算法基于排列和置换运算。排列是对数据重新进行安排,置换是将一个数据单元替换为另一个。AES使用几种不同的方法来执行排列和置换运算。AES是一个迭代的、对称密钥分组的密码,它可以使用128、192和256 bit密钥,并且用128 bit(16 B)分组加密和解密数据。与公共密钥密码使用密钥对不同,对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构,在该循环中重复置换和替换输入数据,如图7所示。
图7 AES算法设计
6.序列密码
序列密码是一个随时间变化的加密变换,具有转换速度快、低错误传播的优点,硬件实现电路更简单;其缺点是有低扩散、插入或修改等不敏感性。
序列密码涉及大量的理论知识,提出了众多的设计原理,也得到了广泛的分析,但许多研究成果并没有完全公开,因为序列密码目前更多应用于军事和外交等机密部门。目前,公开的序列密码算法主要有RC4、SEAL等。1949年,Shannon证明了只有一次一密的密码体制是绝对安全的,这给序列密码技术的研究以强大的支持,序列密码方案的发展是模仿一次一密系统的尝试,或者说“一次一密”的密码方案是序列密码的雏形。如果序列密码所使用的是真正随机方式的、与消息流长度相同的密钥流,则此时的序列密码就是一次一密的密码体制(One-Time Password)。若能以一种方式产生一随机序列(密钥流),这一序列由密钥所确定,则利用这样的序列就可以进行加密,即将密钥、明文表示成连续的符号或二进制,对应地进行加密,加解密时一次处理明文中的一个或几个比特。
序列密码加密和解密的基本框架如图8所示。
图8序列密码加密和解密
明文序列:m=m1m2m3…
密钥序列:k=k1k2k3…
密文序列:c=c1c2c3…
加密变换:ci=ki⊗mi(i=1,2,3…)
解密变换:mi=ki⊗ci(i=1,2,3…)
其中,密钥序列k1k2k3…由一个主控密钥K通过一个密钥流生成器生成。密钥流生成器的核心是一个伪随机数发生器,而密钥K即为该随机数发生器的种子。应用最广的随机数发生器为线性反馈移位寄存器(LFSR,Linear Feedback Shift Register)。LFSR给定前一状态的输出,将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数:对寄存器的某些位进行异或操作后作为输入,再对寄存器中的各比特进行整体移位。
LFSR可以产生一个周期较长的二进制序列形成安全的流密钥。当周期无限长即可形成上述的OTP一次一密系统,OTP是一种理想的安全流密码体制。一次一密系统应用面临现实的挑战如下。
(1)密钥配送:发送方需要把密钥发送给接收方,接收方才能解密。OTP密钥的长度和明文长度相同,若能把密钥安全有效地发送出去,为何不直接用这种方法发送明文。
(2)密钥的保存:OTP等同于将“保存明文”问题转化成“保存和明文等长的密钥”问题。
(3)密钥的复用:OTP不能重用过去用过的随机比特序列,否则如果密钥泄露之前所有的通信都将会被解密,这在密码学上被称作前向安全(Forward Security)。
(4)密钥的同步:明文很长时密钥也会一样长,如果密钥在同步时出现一点差错,后续所有密文将无法解密,有时也被称作后向安全(Backward Security)。
(5)密钥的生成:OTP需要生成大量的随机数,计算机程序生成的伪随机数往往无法满足需求,而无重现性的真正随机数生成难度极大。
因此在实际应用中,流密码的安全性主要依赖于主控密钥K的保密性和密钥流发生器的可靠性。密钥序列产生算法最为关键,其生成的密钥序列必须具有伪随机性。伪随机性主要体现在两个方面,一方面密钥序列是不可预测的,这将使攻击者难以破解密文;另一方面,密钥序列具有可控性。加密、解密双方使用相同的种子密钥可以产生完全相同的密钥序列。倘若密钥序列完全随机,则意味着密钥序列产生算法的结果不可控,在这种情况下,将无法通过解密恢复明文。此外,加密、解密双方还必须保持密钥序列的精确同步,这是通过解密恢复明文的重要条件。序列密码的优点在于安全程度高,明文中每一个比特位的加密独立进行,与明文的其他部分无关。此外,序列密码的加密速度快,实时性好;缺点则是密钥序列必须严格同步,在现实应用中往往需要为之付出较高的代价。
7.RC4序列密码
RC4是由RSA Security的Ron Rivest在1987年设计的一种高速简洁的流密码,被广泛用于常用协议中,包括无线网络安全算法、SSL/TLS、HTTPS等安全协议。RC4加密分为两步。
(1)Key-Scheduling Algorithm(KSA)密钥调度算法,采用可变长度的加密密钥产生密钥流生成器的初始状态。
(2)Pseudo-Random Generation Algorithm(PRGA)伪随机子密码生成算法,根据初始状态产生密钥流,并与明文相异或产生密文。
RC4采用的是XOR运算,一旦子密钥序列出现了重复,密文就有可能被破解。存在部分弱密钥,使子密钥序列在不到100 B内就出现重复。如果出现部分重复,则可能在不到10万字节内就能发生完全重复。因此,在使用RC4算法时,必须对加密密钥进行安全测试,避免弱密钥问题。