第5章
Feistel结构分组密码
Feistel结构是分组密码经典结构之一,具有加解密结构相同或相似的特点,实际使
用中占用软硬件存储资源少。基于此结构设计的分组密码有很多,本章介绍两个典型分
组密码:DES和Camellia。 
5.1 DES 
1973年,美国国家标准局开始研究除国防部外的其他部门计算机系统的数据加密标
准,并于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的
公告。1977年1月,美国政府正式颁布IBM 公司设计的方案DES作为非机密数据的数
据加密标准。
5.1.1 DES 设计
DES基于Feistel结构设计,主要由S盒查询、比特移位、异或运算构成。DES的分
组长度为64比特,密钥长度为56比特,迭代16轮,共使用16个轮密钥K1、K2,…,K16, 
这些轮密钥都是由主密钥K 生成的。DES的加密流程如图5-1所示。图5-1中Li 和
Ri 的长度都是32比特,最后一轮不进行左右交换,直接输入逆初始置换。
1. 加密变换
DES加密流程分为3个步骤: 
(1)初始置换。
对明文64比特进行初始置换(IP),如表5-1所示,输出仍然是64比特,然后分成左
右两个32比特L0 和R0。
表5-1 初始置换
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 


图5-1 DES 的加密流程

(2)轮函数迭代
。
基于Feistel结构进行16 轮迭代,第
i 
轮表示如下
:
.当1≤i≤15 时,有Li=Ri-1,Ri=Li-1..F(Ki,Ri-1)。
.当i=16 时,有Li=Li-1..F(Ki,Ri-1),Ri=Ri-1。
(3)逆初始置换。
IP
进行逆初始置换(-1)。IP-1是IP 的逆,如表52所示。最后输出当前明文对应的
密文。

表5-
2 
逆初始置换

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 

82 


第5章Feistel结构分组密码
续表

34 2 42 10 50 18 58 26 

33 1 41 9 49 17 57 25 

第(2)步中
F 
函数是DES 的核心,主要包含扩展函数E、轮密钥异或、S盒查询和置
换函数
P 
四个组件,其执行过程如图5-2所示。


图5-2 DES 的
F 
函数

①扩展函数
E 
将32 比特的输入扩展为48 比特的输出,如表5-3所示。
表5-
3 
扩展函数
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 

②轮密钥异或将E(Ri-1)与轮密钥Ki 
按位进行模二加运算,并将运算结果从左到
右分为8组,每组6位,即
E(Ri-1)..Ki=B1B2B3B4B5B6B7B8 
其中,Bj 
的长度为6位,1≤j≤8 。
③S 盒查询就是将每个Bj 
查询S盒后缩减为4位,共8个S盒S1,S2,…,S8,每个
S盒有4行16 列数据。具体S盒查询参考3.

2节中S1 的介绍。
Ki)。
④将8个S盒的输出经过表5-4的置换函数
P 
进行换位处理后就得到F(Ri-1, 

83


分组密码设计与评估
表5-4 置换函数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 
2. 密钥扩展算法
主密钥K 共56比特,在传输过程中加8比特奇偶校验位,分别位于8,16,24,32,40, 
48,56,64位。奇偶校验位用于检查密钥K 在分配以及传输过程中可能发生的错误。密
钥扩展算法的输入只有56比特,经过PC-1(见表5-5)打乱重新排列,从主密钥K 生成轮
密钥Ki(48位)的过程如图5-3所示。
表5-5 PC-1 
50 43 36 29 22 15 8 1 51 44 37 30 23 16 
9 2 52 45 38 31 24 17 10 3 53 46 39 32 
56 49 42 35 28 21 14 7 55 48 41 34 27 20 
13 6 54 47 40 33 26 19 12 5 25 18 11 4 
图5-3中Ci=LSi(Ci-1),Di=LSi(Di-1),其中LSi 表示对Ci-1和Di-1进行循环左
移变换,LS1、LS2、LS9、LS16是循环左移1比特输出变换,其余的LSi 是循环左移2比特
变换。PC-2(见表5-6)表示从数据状态56比特中选出48比特作为轮密钥Ki。
表5-6 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 
3. 解密变换
DES的解密过程和加密过程使用同一结构,只不过在16次迭代中使用轮密钥的次
序正好相反。解密时,第1次迭代使用轮密钥K16,第2次迭代使用轮密钥K15,以此类
推,第16次迭代使用轮密钥K1。
4. 设计特点
分组密码DES的主要特点也是Feistel结构的特点,即加密结构与解密结构相同。
84

第5章 Feistel结构分组密码 
图5-3 DES密钥扩展算法
除此之外,DES的组件大都是面向比特设计的,如初始置换IP、逆初始置换IP-1、扩展变
换E、置换P 以及密钥扩展算法中的压缩变换PC-1、PC-2等,与软件实现相比更适合硬
件实现,这与该分组密码设计之初的计算机发展水平有一定的关系。
5.1.2 DES 安全性评估
DES自1977年公布之后,经历了穷举攻击、滑动攻击、差分分析、线性分析等。20世
纪90年代初,Biham、Matsui等人分别用差分分析、线性分析攻破了全轮DES[3][40]。
Matsui在1994年的美密会上第一次通过实验给出了16轮DES的线性分析。这两种方
法在此后的对称密码分析方法中占据主要地位。
1. 差分分析
差分分析是一种选择明文攻击。在分组密码中由于非线性组件的引入,存在以一定
概率传播的差分路径,对于一定的输入/输出差分,所有路径概率之和就是对应的差分特
征概率。对于r 轮分组密码,输入差分ΔX0 为α,加密r-1轮后的输出差分ΔXr-1为β, 
且对应差分概率P(α→β)=p。恢复最后一轮密钥的步骤简述如下: 
第一步,明文采样。选择m 对明文,每对明文差分为α。
第二步,过滤正确对。根据差分特征的输出可以推导或观察到密文对的输出特点,可
以将一部分不是正确对的明文对过滤掉,这样可以避免错误对蕴含密钥的干扰,以提高
效率。第三步,提取信息。猜测最后一轮的部分密钥并解密得到r-1轮的输出,一般情况
下,若满足输出差分为β 的对数近似等于mp,则猜测的最后一轮部分密钥正确;否则猜
85

分组密码设计与评估
测的密钥错误。

上述第二步中过滤正确对也称为去噪阶段,主要目的是过滤掉错误对,排除干扰。假
设过滤系数为λ,0<λ≤1,该取值与差分区分器输出有关,表示过滤之后的明文对数量与
总明文对数量的比值。

在提取信息阶段设置两个参数:攻击猜测的密钥比特量
l 
和平均每对密文蕴含的密
钥个数v,
v 
的取值与算法组件(如S盒)的差分分布特性有关。
根据以上几个参数,正确密钥至少被统计了mp 
次,所有猜测密钥平均被统计了
mλv/2l 
次,这两者之比就是Biham 和Shamir给出的信噪比。
定义5-
1 
若采用计数原理对密码算法进行差分攻击,则正确密钥至少被统计的次

S

数与所有猜测密钥平均被统计的次数之比称为该计数系统中的信噪比,记为
N 
,表示

如下: 
S 
mp 
2lp N 
=mλv/2l 
=λv 
信噪比越大,正确密钥被统计的次数越多,这样能更有效地得到正确密钥。根据对
DES 算法的大量分析数据统计,信噪比的取值可以进一步确定所需的选择明文量: 
1 

m 
≈
c 

p 

其中,根据信噪比近似估算,hamr总结如下:

c 
为一个固定常数, Biam 和Shi

(1)当
S 
为12时,~40 。
N 
~
c 
取值为20

(2)当Sc 
取值为34。
N 
取值较大时,~

(3)当Sc 
需取更大的值。
N 
取值较小时,

接下来对DES 进行差分分析。DES 的
F 
函数使用了8个不同的6×4 规模的S盒, 
从任何一个S盒的差分分布表出发,都可以寻找差分路径。表5-7是第2个S盒(S2)的
部分差分分布表,结合
F 
函数的扩展变换
E 
和置换P,给出
F 
函数的差分路径。

表5-
7 
S2 
的差分分布表(部分) 

输入\输出0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 4 0 2 6 4 0 14 8 6 8 4 6 2 
2 0 0 0 2 0 4 6 4 0 0 4 6 10 10 12 6 
3 4 8 4 8 4 6 4 2 4 2 2 4 6 2 0 4 
4 0 0 0 0 0 6 0 14 0 6 10 4 10 6 4 4 
5 2 0 4 8 2 4 6 6 2 0 8 4 2 4 10 2 
6 0 12 6 4 6 4 6 2 2 10 2 8 2 0 0 0 
7 4 6 6 4 2 4 4 2 6 4 2 4 4 6 0 6 
8 0 0 0 4 0 4 0 8 0 10 16 6 6 0 6 4 

86 


第5章Feistel结构分组密码
续表

输入\输出0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
9 14 2 4 10 2 8 2 6 2 4 0 0 2 2 2 4 
10 0 6 6 2 10 4 10 2 6 2 2 4 2 2 4 2 

例5-
1 
如图5-4所示,当函数
F 
的输入差分为Δ=(04000000)H(H表示十六进制)
时,非零差分比特经过
E 
没有扩散,只是发生了移位,使得S2 活跃,其输入差分为
(001000)B(B表示二进制), 选择概率最大的输出差分1010B,再经过
P 
变换之后,函数
F 
的输出差分为Δ=(40080000)H。差分概率由S2 的差分分布表查得,即p(001000→ 

16 25 。若函数
F 
是随机函数,则对应的输出差分概率应该为随机概率2-32 。1010)=64 =0.

显然,上述差分概率远远大于此随机概率。
由例5-1的函数
F 
差分特征容易构造如图5-5所示的3轮差分路径。


图5-4 函数
F 
差分传播图5-5 DES 的3轮差分路径

例5-
2 
选取明文对(X,X'), 满足ΔX 
=
X 
..X'=(4008000004000000)H,此处采用
十六进制表示,忽略DES 算法中IP 和IP-1。
第1轮中函数F1 的输入差分为(04000000)H,利用例5-1中的差分传播,得到F1 的

输出差分(40080000)H,差分概率为2-2,与左边明文差分异或之后为0。
第2轮输入差分为(0400000000000000)H,即函数F2 的输入差分为0,输出必为0。
第3轮输入差分为(0000000004000000)H,进入函数F3 的输入差分与F1 相同,因

此输出差分(40080000)H,概率为2-2。
由此得到输出密文对(Y的差分为(4008000004000000)3轮差分路径概率为
2-2×2-2=2-4。
Y,') H,
值得注意的是,DES 的S盒是6比特输入、4比特输出,平均4个不同的输入值对应
同一个输出值,所以必然会存在输入差分非零、输出差分为零的情况。这种性质说明函数

87


分组密码设计与评估
F 
不是置换。

例5-
3 
如图5-6所示,设明文左边32 比特PL 
输入差分Δ=(19600000)H 时,该非
零差分会进入第2轮的函数F2 中,经过
E 
扩展置换,共引起3个S盒S1、S2、S3 活跃。
查表5-8~表5-10 对应的3个S盒的差分分布表,得S1、S2、S3 的输出差分为0的概率

14 810 1

分别为64 、64 、64,所以函数
F 
输出差分为0的概率为三者之积,即234 。


图5-6 函数
F 
的差分传播(输出差分为0) 
表5-
8 
S1 
的差分分布表(部分) 

输入\输出0 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 6 0 2 4 4 0 10 12 4 10 6 2 4 
2 0 0 0 8 0 4 4 4 0 6 8 6 12 6 4 2 
3 14 4 2 2 10 6 4 2 6 4 4 0 2 2 2 0 
4 0 0 0 6 0 10 10 6 0 4 6 4 2 8 6 2 

表5-
9 
S2 
的差分分布表(部分) 

输入\输出0 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
48 0 4 0 2 4 4 8 6 10 6 2 12 0 0 0 6 
49 0 10 2 0 6 2 10 2 6 0 2 0 6 6 4 8 
50 8 4 6 0 6 4 4 8 4 6 8 0 2 2 2 0 
51 2 2 6 10 2 0 0 6 4 4 12 8 4 2 2 0 
52 0 12 6 4 6 0 4 4 4 0 4 6 4 2 4 4 

88 


第5章 Feistel结构分组密码 
表5-10 S3 的差分分布表(部分) 
输入\输出0 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
41 0 2 8 4 0 4 0 6 4 10 4 8 4 4 4 2 
42 2 6 0 4 2 4 4 6 4 8 4 4 4 2 4 6 
43 10 2 6 6 4 4 8 0 4 2 2 0 2 4 4 6 
44 10 4 6 2 4 2 2 2 4 10 4 4 0 2 6 2 
45 4 2 4 4 4 2 4 16 2 0 0 4 4 2 6 6 
由于F 不是置换,所以DES算法存在2轮循环差分路径,即在加密2轮之后输出差
分与输入差分相同,如图5-7所示,这样的差分特征可以用来连接构造成倍轮数的差分路
径。当然,若F 函数为置换,那么不存在2轮循环差分路径,但是可能存在多轮循环差分
路径。
由上述2轮循环差分路径可以构造16轮差分路径,概率为1 
234 
.
è .
.
. ÷
8≈2-62.85,小于随机
置换概率2-64,由此可见16轮DES算法不能完全保证其输出密文的随机性。
构造差分特征之后是密钥恢复阶段,基于以上得到的差分路径,可以进行更多轮数
的密钥恢复攻击。为了描述简洁,下面只对4 轮DES进行密钥恢复攻击,如图5-8 
所示。
图5-7 DES的2轮循环差分路径 图5-8 密钥恢复阶段
例5-4 在例5-1的3轮差分路径之后再加一轮,写出恢复最后一轮部分密钥的
步骤。由
于3轮差分路径概率为2-4,所以选择25 对明文(X ,X'),满足差分ΔX =X .. 
X'=(4008000004000000)H。具体步骤如下: 
第一步,选择25 对明文,进行4轮加密,至少有2 对输出密文满足CL 的差分为
(40080000)H。
第二步,因为第4轮非零差分比特进入函数F4 后引起3个S盒活跃,见表5-11,即
S1、S3、S4,需要猜测对应的18比特密钥,得到F4 的输出,将这个差分与ΔCR 异或。
89

分组密码设计与评估
表5-11 非零差分比特扩散
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 
第三步,若得到差分(04000000)H,则猜测密钥正确;否则猜测密钥错误。
对于猜测的错误密钥,平均留下的密文对为2×2-12=2-11个;对于猜测的正确
密钥,至少有2个密文对满足3轮差分路径,所以多个密文推荐的密钥一般为正确
密钥。
Biham 等人在攻击全轮DES时,将2轮循环差分用在了第2~14轮,然后猜测第1 
轮和第16轮部分密钥,整个攻击的数据复杂度大约为247个选择明文。
2. 线性分析
线性分析的主要思想是寻找明文、密文和密钥之间有效的线性表达式,根据有效性以
一定概率猜测出对应的密钥比特。
1)线性表达式构建
根据分组密码结构可以构建有效的线性表达式,步骤如下: 
第一步,利用统计测试的方法给出分组密码中非线性组件(如S盒)的输入、输出之间
的一些线性逼近等式及其成立的概率。
第二步,结合轮函数中的线性变换组件构造每一轮的输入、输出之间的线性逼近等
式,并计算出其成立的概率。
第三步,将各轮的线性逼近等式按顺序级联起来,削除中间相同的变量,就得到了仅
涉及明文、密文和密钥的线性逼近,如式(5-1)所示: 
P[i1,i2,…,ia ] ..C[j1,j2,…,jb]=K [k1,k2,…,kc] (5-1) 
这里i1,i2,…,ia 、j1,j2,…,jb 和k1,k2,…,kc 表示固定的比特位置。对特定的分组密
码,随机给定明文P 和相应的密文C,很多情况下存在概率p ≠12
的式(5-1),通常用
p-12
刻画其有效性,称为线性逼近优势。
2)密钥比特猜测
假定已获得一个有效的线性表达式,可以通过基于最大似然方法的算法5-1推测一
个密钥比特K [k1,k2,…,kc]信息,其中N 是给定的已知明文的个数。
90