第3章
分组密码体制
3.1 分组密码概述
在许多密码系统中,单钥分组密码是系统安全的一个重要组成部分,用分组密码易于
构造伪随机数生成器、流密码、消息认证码(MAC)和哈希函数等,还可进而成为消息认证
技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。实际应用
中对于分组密码可能会提出多方面的要求,除了安全性外,还有运行速度、存储量(程序的
长度、数据分组长度、高速缓存大小)、实现平台(硬件、软件、芯片)、运行模式等限制条件。
这些都需要与安全性要求之间进行适当的折中选择。
分组密码是将明文消息编码表示后的数字序列x0,x1,…,xi,…划分成长为n 的组
x=(x0,x1,…,xn-1),各组(长为n 的矢量)分别在密钥k=(k0,k1,…,kt-1)控制下变换
成等长的输出数字序列y=(y0,y1,…,ym -1)(长为m 的矢量),其加密函数E:Vn ×K
.Vm ,Vn 和Vm 分别是n 维和m 维矢量空间,K 为密钥空间,如图3-1所示。它与流密码
的不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关,而是与一组
长为n 的明文数字有关。在相同密钥下,分组密码对长为n 的输入明文组所实施的变换
是等同的,所以只须研究对任一组明文数字的变换规则。这种密码实质上是字长为n 的
数字序列的代换密码。
图3-1 分组密码框图
通常取m =n。若m >n,则为有数据扩展的分组密码。若m <n,则为有数据压缩的
分组密码。在二元情况下,x 和y 均为二元数字序列,它们的每个分量xi,yi ∈GF(2)。
下面主要讨论二元情况。设计的算法应满足下述要求:
(1)分组长度n 要足够大,使分组代换字母表中的元素个数2n 足够大,防止明文穷举
攻击法奏效。DES、IDEA、FEAL 和LOKI等分组密码都采用n=64,在生日攻击下用
232组密文成功概率为1/2,同时要求232×64bit=215Mbyte存储,故采用穷举攻击是不现
实的。
(2)密钥量要足够大(即置换子集中的元素足够多),尽可能消除弱密钥并使所有密
第3章分组密码体制
钥同等地好,以防止密钥穷举攻击奏效。但密钥又不能过长,以便于密钥的管理。DES
采用56 比特密钥,现在看来太短了,
IDEA 采用128 比特密钥。
(3)由密钥确定置换的算法要足够复杂,充分实现明文与密钥的扩散和混淆,没有简
单的关系可循,能抗击各种已知的攻击,如差分攻击和线性攻击;有高的非线性阶数,实现
复杂的密码变换;使对手破译时除了用穷举法外,无其他捷径可循。
(4)加密和解密运算简单,易于软件和硬件高速实现。如将分组
n
划分为子段,每段
长为8、16 或者32 。在以软件实现时,应选用简单的运算,使作用于子段上的密码运算易
于以标准处理器的基本运算,如加、乘、移位等实现,避免使用以软件难以实现的逐比特置
换。为了便于硬件实现,加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表
不同而已。这样,加密和解密就可使用同一器件实现。设计的算法采用规则的模块结构,如
多轮迭代等,以便于软件和VLSI快速实现。此外,差错传播和数据扩展要尽可能小。
(5)数据扩展尽可能小。一般无数据扩展,在采用同态置换和随机化加密技术时可
引入数据扩展。
(6)差错传播尽可能小。
要实现上述几点要求并不容易。首先,要在理论上研究有效而可靠的设计方法,而后
进行严格的安全性检验,并且要易于实现。
下面介绍设计分组密码的一些常用方法。
1.代换
3.1
如果明文和密文的分组长都为
n
比特,则明文的每一个分组都有2n
个可能的取值。
为使加密运算可逆(使解密运算可行), 明文的每一个分组都应产生唯一的一个密文分组,
这样的变换是可逆的,称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数
有2n
! 个。
图3-2表示n=4的代换密码的一般结构,4比特输入产生16 个可能输入状态中的
一个,由代换结构将这一状态映射为16 个可能输出状态中的一个,每一输出状态由4个
图3-2 代换结构
33
现代密码学(第5版)
密文比特表示。加密映射和解密映射可由代换表来定义,如表3-1所示。这种定义法是
分组密码最常用的形式,能用于定义明文和密文之间的任何可逆映射。
表3-
1
与图3-2对应的代换表
明文密文密文明文
1000 0011 0000 1110
1001 1010 0001 0011
1010 0110 0010 0100
1011 1100 0011 1000
1100 0101 0100 0001
1101 1001 0101 1100
1110 0000 0110 1010
1111 0111 0111 1111
但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小,如n=4,系统
则等价于古典的代换密码,容易通过对明文的统计分析而攻破。这个弱点不是代换结构
固有的,只是因为分组长度太短。如果分组长度
n
足够大,而且从明文到密文可有任意
可逆的代换,那么明文的统计特性将被隐藏而使以上的攻击不能奏效。
然而,从实现的角度来看,分组长度很大的可逆代换结构是不实际的。仍以表3-1为
例,该表定义了n=4时从明文到密文的一个可逆映射,其中,第二列是每个明文分组对
应的密文分组的值,可用来定义这个可逆映射。因此从本质上来说,第二列是从所有可能
的映射中决定某一特定映射的密钥。在这个例子中,密钥需要64 比特。一般,对
n
比特
的代换结构,密钥的大小是n×2n
比特。如对64 比特的分组,密钥大小应是64×264=
270≈1021 因此难以处理。实际中常将
n
分成较小的段,
r
· n0,其中,
比特, 例如可选n=
r
和n0 都是正整数,将设计
n
个变量的代换变为设计
r
个较小的子代换,而每个子代换只
有n0 个输入变量。一般n0 都不太大,称每个子代换为代换盒,简称为S盒。例如DES
中将输入为48 比特、输出为32 比特的代换用8个S盒来实现,每个S盒的输入端数仅为
6比特,输出端数仅为4比特。
3.2
扩散和混淆
1.
扩散和混淆是由Shannon提出的设计密码系统的两个基本方法,目的是抗击敌手对
密码系统的统计分析。如果敌手知道明文的某些统计特性,如消息中不同字母出现的频
率,或可能出现的特定单词或短语,而且这些统计特性以某种方式在密文中反映出来,敌
手就有可能得出加密密钥或其一部分,或包含加密密钥的一个可能密钥集合。在
Shannon称之为理想密码的密码系统中,密文的所有统计特性都与所使用的密钥独立。
图3-2讨论的代换密码就是这样的一个密码系统,然而是不实用的。
所谓扩散,就是将明文的统计特性散布到密文中去,实现方式是使得密文中每一位由
明文中多位产生。例如,对英文消息
M
=m1m2m3…的加密操作
k
yn
=chr(Σord(mn+i)(mod26))
i=1
34
明文密文
密文明文
0000
0001
0010
0011
0100
0101
0110
0111
1110
0100
1101
0001
0010
1111
1011
1000
1000
1001
1010
1011
1100
1101
1110
1111
0111
1101
1001
0110
1011
0010
0000
0101
第3章 分组密码体制
其中,ord(mi)是求字母mi 对应的序号,chr(i)是求序号i 对应的字母,密文字母yn 是由
明文中k 个连续的字母相加而得。这时明文的统计特性将被散布到密文,因而每一字母
在密文中出现的频率比在明文中出现的频率更接近于相等,双字母及多字母出现的频率
也更接近于相等。在二元分组密码中,可对数据重复执行某个置换再对这一置换作用以
一个函数,便可获得扩散。
分组密码在将明文分组依靠密钥变换到密文分组时,扩散的目的是使明文和密文之
间的统计关系变得尽可能复杂,以使敌手无法得到密钥。混淆是使密文和密钥之间的统
计关系变得尽可能复杂,以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计
关系,由于密钥和密文之间统计关系复杂化,敌手无法得到密钥。使用复杂的代换算法可
得预期的混淆效果,而简单的线性代换函数得到的混淆效果不够理想。
扩散和混淆成功地实现了分组密码的本质属性,因而成为设计现代分组密码的
基础。
3.1.3 Feistel密码结构
很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。Feistel提
出利用乘积密码可获得简单的代换密码,乘积密码指顺序地执行两个或多个基本密码系
统,使得最后结果的密码强度高于每个基本密码系统产生的结果,Feistel还提出了实现
代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思
想的具体应用。
1. Feistel 加密结构
图3-3是Feistel网络示意图,加密算法的输入是分组长为2w 的明文和一个密钥K 。
将每组明文分成左右两半L0 和R0,在进行完n 轮迭代后,左右两半再合并到一起以产
生密文分组。其第i 轮迭代的输入为前轮输出的函数:
Li =Ri-1
Ri =Li-1 ..F(Ri-1,Ki)
其中,Ki 是第i 轮用的子密钥,由加密密钥K 得到。一般,各轮子密钥彼此不同而且与
K 也不同。
Feistel网络中每轮结构都相同,每轮中右半数据被作用于轮函数F 后,再与左半数
据进行异或运算,这一过程就是上面介绍的代换。每轮轮函数的结构都相同,但以不同的
子密钥Ki 作为参数。代换过程完成后,再交换左、右两半数据,这一过程称为置换。这
种结构是Shannon提出的代换-置换网络(Substitution-PermutationNetwork,SPN)的特
有形式。
Feistel网络的实现与以下参数和特性有关:
(1)分组大小。分组越大则安全性越高,但加密速度就越慢。分组密码设计中最为
普遍使用的分组大小是64比特。
(2)密钥大小。密钥越长则安全性越高,但加密速度就越慢。现在普遍认为64比特
或更短的密钥是不安全的,通常使用128比特长的密钥。
35
现代密码学(第5版)
图3-3 Feistel网络
(3)轮数。单轮结构远不足以保证安全性,多轮结构可提供足够的安全性。典型地,
轮数取为16。
(4)子密钥产生算法。该算法的复杂性越高,则密码分析的困难性就越大。
(5)轮函数。轮函数的复杂性越高,密码分析的困难性也越大。
在设计Feistel网络时,还要考虑以下两个问题:
(1)快速的软件实现。在很多情况下,算法是被镶嵌在应用程序中,因而无法用硬件
实现。此时算法的执行速度是考虑的关键。
(2)算法容易分析。如果算法能被无疑义地解释清楚,就可容易地分析算法抵抗攻
击的能力,有助于设计高强度的算法。
2. Feistel 解密结构
Feistel解密过程本质上和加密过程是一样的,算法使用密文作为输入,但使用子密
钥Ki 的次序与加密过程相反,即第一轮使用Kn ,第二轮使用Kn-1,一直下去,最后一轮
使用K1。这一特性保证了解密和加密可采用同一算法。
图3-4的左边表示16轮Feistel网络的加密过程,右边表示解密过程,加密过程由上
而下,解密过程由下而上。为清楚起见,加密算法每轮的左右两半用LEi 和REi 表示,解
密算法每轮的左右两半用LDi 和RDi 表示。图3-4的右边还标出了解密过程中每一轮
36
第3章分组密码体制
的中间值与左边加密过程中间值的对应关系,即加密过程第
i
轮的输出是LEi
‖REi
(‖表示链接), 解密过程第16-
i
轮相应的输入是RDi‖LDi。
图3-4Feistel加解密过程
加密过程的最后一轮执行完后,两半输出再经交换,因此密文是RE16‖LE16 。解密
过程取以上密文作为同一算法的输入,即第一轮输入是RE16‖LE16,等于加密过程第
16 轮两半输出交换后的结果。现在显示解密过程第一轮的输出等于加密过程第16 轮输
入左右两半的交换值。
在加密过程中
:
LE16=RE15
RE16=LE15 ..F(RE15,K16)
在解密过程中:
LD1=RD0=LE16=RE15
RD1=LD0..F(RD0,K16)=RE16 ..F(RE15,K16)
=[LE15 ..F(RE15,K16)]..F(RE15,K16)
=LE15
所以解密过程第一轮的输出为LE15‖RE15,等于加密过程第16 轮输入左右两半交
换后的结果。容易证明这种对应关系在16 轮中每轮都成立。一般,加密过程的第
i
37
现代密码学(第5版)
轮有:
LEi=REi-
REi=LEi-1(1) ..F(REi-1,Ki)
因此
REi-1=LE
LEi-1=REi(i) ..F(REi-1,Ki)=REi
..F(LEi,Ki)
以上两式描述了加密过程中第
i
轮的输入与第
i
轮输出的函数关系,由此关系可得图3-4
右边显示的LDi
和RDi
的取值关系。
最后可以看到,解密过程最后一轮的输出是RE0‖LE0,左右两半再经一次交换后即
得最初的明文。
3.2
数据加密标准
DES(DataEncryptionStandard)是迄今为止世界上最为广泛使用和流行的一种分组
密码算法,它的分组长度为64 比特,密钥长度为56 比特,它是由美国IBM 公司研制的,
是早期的称为Lucifer密码的一种发展和修改。DES 在1975 年3月17 日首次被公布在
联邦记录中,在做了大量的公开讨论后于1977 年1月15 日被正式批准并作为美国联邦
信息处理标准,即FIPS-46,同年7月15 日开始生效。规定每隔5年由美国国家保密局
(NationalSecurityAgency,NSA)作出评估,并重新批准它是否继续作为联邦加密标准。
最后一次评估是在1994 年1月,美国决定1998 年12 月以后不再使用DES 。1997 年,
DESCHALL 小组经过近4个月的努力,通过Internet搜索了3×1016 个密钥,找出了
DES 的密钥,恢复出了明文。1998 年5月美国EFF(ElectronicsFrontierFoundation)宣
布,他们将一台价值20 万美元的计算机改装成的专用解密机,用56 小时破译了56 比特
密钥的DES 。美国国家标准和技术协会已征集并进行了几轮评估筛选,产生了称为AES
(AdvancedEncryptionStandard)的新加密标准。尽管如此,DES 对于推动密码理论的发
展和应用起了重大作用,对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重
要的参考价值,下面是这一算法的描述。
3.1
DES
描述
2.
图3-5是DES 加密算法的框图,其中明文分组长为64 比特,密钥长为56 比特。图
的左边是明文的处理过程,有3个阶段,首先是一个初始置换IP,用于重排明文分组的
64 比特数据。然后是具有相同功能的16 轮变换,每轮中都有置换和代换运算,第16 轮
变换的输出分为左右两半,并被交换次序。最后再经过一个逆初始置换IP-1(为IP 的
逆)从而产生64 比特的密文。除初始置换和逆初始置换外,DES 的结构和图3-3所示的
l密码结构完全相同。
Feiste
图3-5的右边是使用56 比特密钥的方法。密钥首先通过一个置换函数,然后,对加
密过程的每一轮,通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都
38
第3章 分组密码体制
图3-5 DES加密算法框图
相同,但由于密钥被重复迭代,所以产生的每轮子密钥不相同。
1. 初始置换
表3-2(a)和表3-2(b)分别给出了初始置换和逆初始置换的定义,为了显示这两个置
换的确是彼此互逆的,考虑下面64比特的输入M 。
表3-2 DES的置换表
(a)初始置换IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
(b)逆初始置换IP-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
(c)选择扩展运算E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
(d)置换运算P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
39
现代密码学(第5版)
M1 M2 M3 M4 M5 M6 M7 M8
M9 M10 M11 M12 M13 M14 M15 M16
M17 M18 M19 M20 M21 M22 M23 M24
M25 M26 M27 M28 M29 M30 M31 M32
M33 M34 M35 M36 M37 M38 M39 M40
M41 M42 M43 M44 M45 M46 M47 M48
M49 M50 M51 M52 M53 M54 M55 M56
M57 M58 M59 M60 M61 M62 M63 M64
其中,Mi 是二元数字。由表3-2(a),得X =IP(M )为
M58 M50 M42 M34 M26 M18 M10 M2
M60 M52 M44 M36 M28 M20 M12 M4
M62 M54 M46 M38 M30 M22 M14 M6
M64 M56 M48 M40 M32 M24 M16 M8
M57 M49 M41 M33 M25 M17 M9 M1
M59 M51 M43 M35 M27 M19 M11 M3
M61 M53 M45 M37 M29 M21 M13 M5
M63 M55 M47 M39 M31 M23 M15 M7
如果再取逆初始置换Y =IP-1(X )=IP-1(IP(M )),可以看出,M 各位的初始顺序将被
恢复。
2. 轮结构
图3-6是DES加密算法的轮结构,首先看图的左半部分。将64比特的轮输入分为
图3-6 DES加密算法的轮结构
40
第3章分组密码体制
各为32 比特的左、右两半,分别记为
L
和R。和Feistel网络一样,每轮变换可由以下公
式表示:
Li=Ri-
Ri=Li-1(1) ..F(Ri-1,Ki)
其中,轮密钥Ki
为48 比特,函数F(R,K)的计算如图3-7所示。轮输入的右半部分
R
为
32 比特,
R
首先被扩展成48 比特,扩展过程由表3-2(定义,其中将
R
的16 个比特各重复
c)
一次。扩展后的48 比特再与子密钥Ki
异或,然后再通过一个
S
盒,产生32 比特的输出。
该输出再经过一个由表3-2(d)定义的置换,产生的结果即为函数F(R,K)的输出。
图3-7 函数F(R,K)的计算过程
F
中的代换由8个
S
盒组成,每个
S
盒的输入长为6比特、输出长为4比特,其变换
关系由表3-3定义,每个
S
盒给出了4个代换(由一个表的4行给出)。
表3-
3
DES
的
S
盒定义
行
列0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
S1
0
1
2
3
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
0
1
2
3
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
0
1
2
3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
41
现代密码学(第5版)
续表
列
行 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
S4
0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
对每个盒Si,其6比特输入中,第1个和第6个比特形成一个2位二进制数,用来选
择Si的4个代换中的一个。在6比特输入中,中间4比特用来选择列。行和列选定后,
得到其交叉位置的十进制数,将这个数表示为4位二进制数即得这一S 盒的输出。例
如,S1的输入为011001,行选为01(即第1行),列选为1100(即第12列),行列交叉位置
的数为9,其4位二进制表示为1001,所以S1的输出为1001。
S 盒的每一行定义了一个可逆代换,图3-2(在3.1.1节)表示S1 第0行定义的代换。
3. 密钥的产生
再看图3-5和图3-6,输入算法的56比特密钥首先经过一个置换运算,该置换由
表3-4(a)给出,然后将置换后的56比特分为各为28比特的左、右两半,分别记为C0 和
D0。在第i 轮分别对Ci-1和Di-1进行左循环移位,所移位数由表3-4(c)给出。移位后
的结果作为下一轮求子密钥的输入,同时也作为置换选择2的输入。通过置换选择2产
生的48比特的Ki,即为本轮的子密钥,作为函数F (Ri-1,Ki)的输入。其中,置换选择
2由表3-4(b)定义。
42
第3章 分组密码体制
表3-4 DES密钥编排中使用的表
(a)置换选择1
PC-1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
(b)置换选择2
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
(c)左循环移位位数
轮 数1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
位 数1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
4. 解密
和Feistel密码一样,DES的解密和加密使用同一算法,但子密钥使用的顺序相反。
3.2.2 二重DES
为了提高DES的安全性,并利用实现DES的现有软硬件,可将DES算法在多密钥
下多重使用。
二重DES是多重使用DES时最简单的形式,如图3-8所示。其中,明文为P ,两个加
密密钥为K1 和K2,密文为
C =EK2 [EK1 [P]]
解密时,以相反顺序使用两个密钥:
P =DK1 [DK2 [C]]
因此,二重DES所用密钥长度为112比特,强度极大增加。然而,如果对任意两个密钥
K1 和K2,能够找出另一密钥K3,使得
EK2 [EK1 [P]]=EK3 [P]
图3-8 二重DES
43
现代密码学(第5版)
那么,二重DES 以及多重DES 都没有意义,因为它们与56 比特密钥的单重DES 等价。
但上式对DES 并不成立。将DES 加密过程64 比特分组到64 比特分组的映射看作
一个置换,如果考虑264 个所有可能的输入分组,则给定密钥后,DES 的加密将把每个输
入分组映射到一个唯一的输出分组。否则,如果有两个输入分组被映射到同一分组,则解
密过程就无法实施。对264 个输入分组,总映射个数为(264)! >(101020 )。
17
另一方面,对每个不同的密钥,DES 都定义了一个映射,总映射数为256<10。
因此,可假定用两个不同的密钥两次使用DES,可得一个新映射,而且这一新映射不
出现在单重DES 定义的映射中。这一假定已于1992 年被证明。所以使用二重DES 产
生的映射不会等价于单重DES 加密。但对二重DES 有以下一种称为中途相遇攻击的攻
击方案,这种攻击不依赖于DES 的任何特性,因而可用于攻击任何分组密码。其基本思
想如下:
如果有
C=EK2[EK1[P]]
那么
X
=EK1[P]=DK2[C]
如果已知一个明文密文对(P,C), 攻击的实施可如下进行:首先,用256 个所有可能的K1
对
P
加密,将加密结果存入一个表中并对该表按
X
排序,然后用256 个所有可能的K2 对
C
解密,在上述表中查找与
C
解密结果相匹配的项,如果找到,则记下相应的K1 和K2。
最后再用一个新的明文密文对(P'
,C')检验上面找到的K1 和K2,用K1 和K2 对P'两
次加密,若结果等于C'
,就可确定K1 和K2 是所要找的密钥。
对已知的明文P,二重DES 能产生264 个可能的密文。而可能的密钥个数为2112,所
以平均来说,对一个已知的明文,有2112/264=248 个密钥可产生已知的密文。而再经过另
外一对明文密文的检验,误报率将下降到248-64=2-16 。所以在实施中途相遇攻击时,如
果已知两个明文密文对,则找到正确密钥的概率为1-2-16 。
3.3
两个密钥的三重DES
2.
抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密,从而可使已知明
文攻击的代价增加到2112 。然而,这样又会使密钥长度增加到56×3=168 比特,因而过
于笨重。一种实用的方法是仅使用两个密钥做三次加密,实现方式为加密—解密—加密,
简记为EDE(Encrypt-Decrypt-Encrypt), 如图3-9所示,即:
C=EK1[DK2[EK1[P]]
]
第2步解密的目的仅在于使得用户可对一重DES 加密的数据解密
。
此方案已在密钥管理标准ANSX.
917 和ISO8732 中被采用。
3.4
3个密钥的三重DES
2.
3个密钥的三重DES 密钥长度为168 比特,加密方式
为
C=EK3[DK2[EK1[P]]
]
令K3=K2 或K1=K2,则变为一重DES
。
44
第3章分组密码体制
图3-9 两个密钥的三重DES
3个密钥的三重DES 已在因特网的许多应用(如PGP 和S/MIME)中被采用
。
3.3
差分密码分析与线性密码分析
3.1
差分密码分析
3.
差分密码分析是迄今已知的攻击迭代密码最有效的方法之一,其基本思想是:通过
分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。
对分组长度为
n
的
r
轮迭代密码,两个
n
比特串Yi
和Yi
* 的差分定义为
ΔYi=Yi
..Yi
*-1
其中,..表示
n
比特串集上的一个特定群运算,Yi
* -1表示Yi
* 在此群中的逆元。
由加密对可得差分序列:
ΔY0,ΔY1,…,ΔYr
其中,0 是明文对,和Y*1≤i≤r) 它们同时也是第i+1 轮
Y0 和Y* Yi i
(是第
i
轮的输出,
的输入。第
i
轮的子密钥记为Ki,
F
是轮函数,且Yi=F(1,)。
Yi-Ki
定义3-
1
r-轮特征(r-roundcharacteristic)
Ω
是一个差分序列:
α0,αr
其中,0 的差分,i(
α1,…,
是第
i
轮输出Yi i
的差分。
α0是明文对Y0 和Y* α1≤i≤r) 和Y*
定义3在rα1,…,定
义
-
2
-轮特征Ω=α0,αr
中,
Ω
=P(Y)αα
即pΩ
表示在输入差分为α1的条件下,轮函数
F
的输出差分为α的概率。
pi
ΔF(=i|ΔY=i1)
ii-
i
定义3--α1,…,rΩ
定义为
3
r轮特征Ω=α0,α的概率p
pΩ = Π(r) pΩi
i=1
对r-轮迭代密码的差分密码分析可综述为如下的算法:
(1)找出一个(1)r-=α1,…,r-1,
几乎最大。
r--轮特征Ω(1)α0,α使得它的概率达到最大或
(2)均匀随机地选择明文Y0 并计算Y*0 的差分为α0, 0
0,使得Y0 和Y* 找出Y0 和Y*
45
现代密码学(第5版)
在实际密钥加密下所得的密文Yr 和Yr* 。若最后一轮的子密钥Kr(或Kr 的部分比特)
有2m 个可能值Kj r(1≤j≤2m ),设置相应的2m 个计数器Λj(1≤j≤2m );用每个Kjr
解密密
文Yr 和Yr* ,得到Yr-1和Yr*-1,如果Yr-1和Yr*-1的差分是αr-1,则给相应的计数器Λj 加1。
(3)重复步骤(2),直到一个或几个计数器的值明显高于其他计数器的值,输出它们
对应的子密钥(或部分比特)。
一种攻击的复杂度可以分为两部分:数据复杂度和处理复杂度。数据复杂度是实施
该攻击所需输入的数据量;而处理复杂度是处理这些数据所需的计算量。这两部分主要
用来刻画该攻击的复杂度。
差分密码分析的数据复杂度两倍于成对加密所需的选择明文对(Y0,Y0* )的个数。差
分密码分析的处理复杂度是从(ΔYr-1,Yr,Yr* )找出子密钥Kr (或Kr 的部分比特)的计
算量,它实际上与r 无关,而且由于轮函数是弱的,所以此计算量在大多数情况下相对较
小。因此,差分密码分析的复杂度取决于它的数据复杂度。
3.3.2 线性密码分析
线性密码分析是对迭代密码的一种已知明文攻击,它利用的是密码算法中的“不平衡
(有效)的线性逼近”。
设明文分组长度和密文分组长度都为n 比特,密钥分组长度为m 比特。记明文分组
为P[1],P[2],…,P[n],密文分组为C[1],C[2],…,C[n],密钥分组为K [1],K [2],…,
K [m ]。定义A[i,j,…,k]=A[i]..A[j]..…..A[k]。
线性密码分析的目标就是找出以下形式的有效线性方程:
P[i1,i2,…,ia]..C[j1,j2,…,jb]=K [k1,k2,…,kc]
其中,1≤a≤n,1≤b≤n,1≤c≤m 。
如果方程成立的概率p≠12
,则称该方程是有效的线性逼近。如果p-12
是最大
的,则称该方程是最有效的线性逼近。
设N 表示明文数,T 是使方程左边为0的明文数。如果T >N2
,则令:
K [k1,k2,…,kc]=
0, p >12
1, p <12
ì
.
í
..
..
如果T <N2
,则令:
K [k1,k2,…,kc]=
0, p <12
1, p >12
ì
.
í
..
..
从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程,可得关于
密钥的一组线性方程,从而确定出密钥比特。
46
第3章分组密码体制
1
研究表明,当
充分小时,攻击成功的概率为
p-2
1∞ -x2
e2dx
1
-2 N
p-2
2π∫
1
1
这一概率只依赖于N
,并随着
N
或
的增加而增加。
p-2
p-2
如何对差分密码分析和线性密码分析进行改进,降低它们的复杂度仍是现在理论研
究的热点,目前已推出了很多改进方法,例如,高阶差分密码分析、截段差分密码分析
(TruncatedDiferentialCryptanalysis)、不可能差分密码分析、多重线性密码分析、非线
性密码分析、划分密码分析和差分-线性密码分析。针对密钥编排算法的相关密钥攻击、
基于Lagrange插值公式的插值攻击及基于密码器件的能量分析(PowerAnalysis)。另
外还有错误攻击、时间攻击、Square攻击和Davies攻击等。
3.4
分组密码的运行模式
分组密码在加密时明文分组的长度是固定的,而实用中待加密消息的数据量是不定
的,数据格式可能是多种多样的。为了能在各种应用场合使用DES,美国在FIPSPUS74
和81中定义了DES的4种运行模式,如表3-5所示。这些模式也可用于其他分组密码,
下面以DES为例来介绍这4种模式。
表3-
5
DES的运行模式
模式描述用途
电码本(ECB)模式
密码分组链接(CBC)模式
每个明文组独立地以同一密钥加密
加密算法的输入是当前明文组与前一密文
组的异或
传送短数据(如一个加密
密钥)
传送数据分组;
认证
密码反馈(CFB)模式
输出反馈(OFB)模式
每次只处理输入的
j
比特,将上一次的密文
用作加密算法的输入以产生伪随机输出,该
输出再与当前明文异或以产生当前密文
与CFB类似,不同之处是本次加密算法的输
入为前一次加密算法的输出
传送数据流;
认证
有扰信道上(如卫星通
信)传送数据流
3.1
电码本模式
4.
电码本(ElectronicCodeBook,ECB)模式是最简单的运行模式,它一次对一个64比
特长的明文分组加密,而且每次的加密密钥都相同,如图3-10所示。当密钥取定时,对明
文的每一个分组,都有一个唯一的密文与之对应。因此可以形象地认为有一个非常大的
电码本,对任意一个可能的明文分组,电码本中都有一项与之对应的密文。
如果消息长于64比特,则将其分为长为64比特的分组,最后一个分组如果不够
64比特,则需要填充。解密过程也是一次对一个分组解密,而且每次解密都使用同一密
47
现代密码学(第5版)
钥。图3-10 中,明文由分组长为64 比特的分组序列P1,P2,…,PN
构成,相应的密文分
组序列是C1,C2,…,CN
。
图3-10ECB 模式示意图
ECB 在用于短数据(如加密密钥)时非常理想,因此如果需要安全地传递DES 密钥,
ECB 是最合适的模式。
ECB 的最大特性是若同一明文分组在消息中重复出现,则产生的密文分组也相同。
ECB 用于长消息时可能不够安全,如果消息有固定结构,密码分析者有可能找出这
种关系。例如,如果已知消息总是以某个预定义字段开始,那么分析者就可能得到很多明
文密文对。如果消息有重复的元素而重复的周期是64 的倍数,那么密码分析者就能够识
别这些元素。以上这些特性都有助于密码分析者,有可能为其提供对分组的代换或重排
的机会。
3.2
密码分组链接模式
4.
为了解决ECB 的安全缺陷,可以让重复的明文分组产生不同的密文分组,密码分组
链接(CipherBlockChaining,CBC)模式就可满足这一要求。
图3-11 是CBC 模式的示意图,它一次对一个明文分组加密,每次加密使用同一密
钥,加密算法的输入是当前明文分组和前一次密文分组的异或,因此加密算法的输入不会
显示出与这次的明文分组之间的固定关系,所以重复的明文分组不会在密文中暴露出这
种重复关系。
解密时,每一个密文分组被解密后,再与前一个密文分组异或,即:
DK
[Cn
]..Cn-1=DK
[EK
[Cn-1..Pn
]]..Cn-1
因而产生出明文分组。
=Cn-1..Pn
..Cn-1=Pn
(设Cn
=EK
[Cn-1..Pn
])
时,
在产生第一个密文分组时,需要有一个初始向量IV 与第一个明文分组异或。解密
IV 和解密算法对第一个密文分组的输出进行异或以恢复第一个明文分组。
48
第3章分组密码体制
图3-11CBC模式示意图
IV对于收发双方都应是已知的,为使安全性最高,可使用
IV应像密钥一样被保护,
ECB加密模式来发送IV 。保护IV的原因如下:如果敌手能欺骗接收方使用不同的IV
值,敌手就能够在明文的第一个分组中插入自己选择的比特值,这是因为:
C1=EK
[
IV..P1]
P1=IV..DK
[C1]
用X(表示64比特分组
X
的第
i
个比特, i)IV(C1](由异或的
i) 那么P1(=i)..DK
[i),
性质得:
P1('=i)i)
i)IV(
'
..DK
[C1](
其中,撇号表示比特补。上式意味着如果敌手篡改了IV中的某些比特,则接收方收到的
P1 中相应的比特也发生变化。
由于CBC模式的链接机制,CBC模式对加密长于64比特的消息非常合适。
CBC模式除能够获得保密性外,还能用于认证。
3.3
密码反馈模式
4.
如上所述,DES是分组长为64比特的分组密码,但利用密码反馈(CipherFedBack,
CFB)模式或OFB模式可将DES转换为流密码。流密码不需要对消息填充,而且运行是
实时的。因此如果传送字母流,可使用流密码对每个字母直接加密并传送。
流密码具有密文和明文一样长这一性质,因此,如果需要发送的每个字符长为8比
特,就应使用8比特密钥来加密每个字符。如果密钥长超过8比特,则造成浪费。
图3-12是CFB模式示意图,设传送的每个单元(如一个字符)是
j
比特长,通常取
49
现代密码学(第5版)
j=8,与CBC 模式一样,明文单元被链接在一起,使得密文是前面所有明文的函数。
图3-12 CFB 模式示意图
加密时,加密算法的输入是64 比特移位寄存器,其初值为某个初始向量IV 。加密算
法输出的最左(最高有效位)j比特与明文的第一个单元P1 异或,产生出密文的第一个单
元C1,并传送该单元。然后将移位寄存器的内容左移j位并将C1 送入移位寄存器最右
边(最低有效位)j位。这一过程继续到明文的所有单元都被加密为止。
解密时,将收到的密文单元与加密函数的输出进行异或。注意这时仍然使用加密算
法而不是解密算法,原因如下:
设Sj(X)是X的j个最高有效位,那么C1=P1..Sj(E(IV)), 因此
05
第3章分组密码体制
P1=C1..Sj(E(
可证明以后各步也有类似的这种关系。
IV))
CFB模式除能获得保密性外,还能用于认证。
3.4
输出反馈模式
4.
输出反馈(OutputFedBack,OFB)模式的结构类似于CFB,如图3-13所示。不同之
处如下:OFB模式是将加密算法的输出反馈到移位寄存器,而CFB模式是将密文单元反
馈到移位寄存器。
图3-13 OFB模式示意图
15