第 8章 分组密码
8,1 分组密码概述
? 定义 8.1 一个分组密码是一种映
射,
记为 E(X,K) 或
称为明文空间,称为密文空间,
为密钥空间。
F F Fn t m2 2 2? ?
ntnk FFKFXXE 222,,),( ??
mF2
tF2
8,2 分组密码的设计原则
? 有关实用密码的两个一般设计原则是
Shannon提出的混乱原则和扩散原则。
? 混乱：人们所设计的密码应使得密钥
和明文以及密文之间的依赖关系相当
复杂以至于这种依赖性对密码分析者
来说是无法利用的。
? 扩散：人们所设计的密码应使得密钥
的每一位数字影响密文的许多位数字
以防止对密钥进行逐段破译，而且明
文的每一位数字也应影响密文的许多
位数字以便隐蔽明文数字统计特性。
? 软件实现的设计原则：使用子块和简
单的运算。密码运算在子块上进行，
要求子块的长度能自然地适应软件编
程，比如 8,16,32比特等。在软件
实现中，按比特置换是难于实现的，
因此我们应尽量避免使用它。子块上
所进行的一些密码运算应该是一些易
于软件实现的运算，最好是用一些标
准处理器所具有的一些基本指令，比
如加法、乘法和移位等。
? 硬件实现的设计原则：加密和解
密可用同样的器件来实现。尽量
使用规则结构，因为密码应有一
个标准的组件结构以便其能适应
于用超大规模集成电路实现。
? 其他原则,
? 简单性原则：包括规范的简单性
和分析的简单性。
? 必须能抗击所有已知的攻击，特
别是差分攻击和线性攻击。
? 可扩展性。要求能提供 128,192、
256比特的可变分组或密钥长。
8,3 分组密码的结构
Y ( r - 1) X= Y ( 0 ) Y ( 2 ) Y ( 1 ) Y ( r)
F F F ?
密钥 k
Z
(r)
Z
( 1)
Z
( 2)
图 8, 2
? Feistel网络与 SP网络，它们的主要区别在
于,SP结构每轮改变整个数据分组，而
Feistel密码每轮只改变输入分组的一半。
? AES和 DES分别是这两种结构的代表。
? Feistel网络（又称 Feistel结构）可把任何轮
函数转化为一个置换，它是由 Horst Feistel
在设计 Lucifer分组密码时发明的，并因 DES
的使用而流行。“加解密相似”是 Feistel型
密码的实现优点。
? SP网络（又称 SP结构）是 Feistel网络的一
种推广，其结构清晰,S一般称为混淆层，
主要起混淆作用。 P一般称为扩散层，主要
起扩散作用。 SP网络与 Feistel网络相比，
可以得到更快速的扩散，不过 SP网络的加
解密通常不相似。有关这两种结构的特点，
读者在了解了 DES和 AES算法之后再细细体
会。
8.4 分组密码的安全性
8.4.1 安全需求
? 如果不知道密钥的知识，攻击者从密
文恢复出明文是实际不可能的。
? 用固定的 k比特的秘密钥，加密 T个明
文，其中,最大化 T后仍能达
到一个可接受的安全性是现代分组密
码追求的目标。
? 几乎所有当代分组密码用更小的查表
（代替盒或 S盒）合并其他变换（线
性变换）模仿这样一个大的随机查表。
这种做法实际上是安全性和可接受的
复杂性的一个折中。
???????? NkT
8.4.2 安全模型
? 1）无条件安全性。
? 2）多项式安全性。
? 3）“可证明的安全性”。
? 4）实际的安全性。
? 5）历史的安全性。
8.4.3 分组密码作为一个伪随机置换
? 伪随机意味：在多项式时间内，加密
询问使得没有攻击者可以区分分组密
码和一真实的随机置换；相应于选择
明文攻击。
? 超伪随机意味：在多项式时间内，加、
解密询问使得没有攻击者可以区分分
组密码和一真实的随机置换。相应于
选择明、密文攻击。
? 分组密码也可以与单向函数联系。
8.4.4 攻击的分类
? 数据复杂度：实施一个攻击所需
输入的数据量，用长为 N的分组
作单位。
? 处理复杂度：执行一个攻击所花
的时间，时间单位可取攻击者不
得不亲自做的加密次数。
? 存储复杂度：需要记忆的字，单
位可取长为 N的分组。
? 组密码的攻击方法目前有：穷举
密钥搜索法、差分分析、截断差
分分析、不可能差分分析、高阶
差分分析、线性分析、差分线性
分析,Boomerang攻击、相关密
钥攻击、插值攻击、非双射攻击、
Slide攻击、攻击。
8.5 典型的分组密码算法 —— DES
? DES的历史
1971 IBM,由 Horst Feistel 领导
的密码研
究项目组研究出 LUCIFER算法。
并应用于
商业领域。
1973美国标准局征求标准,IBM提
交结果,
在 1977年，被选为数据加密标准。
8.5.1 DES的描述
? DES利用 56比特串长度的密钥 K来加密长度为 64位的明文，
得到长度为 64位的密文
? 该算法分三个阶段实现,
1,给定明文 X,通过一个固定的初始置换 IP来排列 X中的位，
得到 X0。
X0=IP（ X） =L0R0
其中 L0由 X0前 32位组成,R0由 X0的后 32位组成。
2.计算函数 F的 16次迭代,根据下述规则来计算
LiRi(1<=i<=16）
Li=Ri-1,Ri=Li-1 ? F(Ri-1,Ki)
其中 Ki是长为 48位的子密钥。子密钥 K1,K2,…, K16是
作为密钥 K（ 56位）的函数而计算出的。
3.对比特串 R16L16使用逆置换 IP-1得到密文 Y。
Y=IP-1（ R16L16）
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
PC1
? 57,49,41,33,25,17,9,C Half
? 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,D Half
? 7,62,54,46,38,30,22,
? 14,6,61,53,45,37,29,
? 21,13,5,28,20,12,4
S-box-1
? 0 1 2 3 4 5 6 7 8 9 a b c d e f COL
S[1]
? 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
?
DES一轮加密的简图
?
Li-1 Ri-1
F
+
Li Ri
Ki
? 对 F函数的说明,（类比于 S-DES） F（ Ri-1,Ki）
函数 F以 长度为 32的比特串 A=R（ 32bits） 作第一个输入，
以长度为 48的比特串变元 J=K(48bits)作为第二个输入。
产生的输出为长度为 32的位串。
(1)对第一个变元 A,由给定的扩展函数 E,将其扩展成 48
位串,E（ A）
(2)计算 E（ A） +J,并把结果写成连续的 8个 6位串,
B=b1b2b3b4b5b6b7b8
(3)使用 8个 S盒，每个 Sj是一个固定的 4?16矩阵，它的元
素取 0~15的整数。给定长度为 6个比特串，如
Bj=b1b2b3b4b5b6
计算 Sj(Bj)如下,b1b6两个比特确定了 Sj的行数,
r(0<=r<=3); 而 b2b3b4b5四个比特确定了 Sj的列数 c
（ 0<=c<=15）。 最后 Sj(Bj)的值为 S-盒矩阵 Sj中 r行 c列的
元素（ r,c）,得 Cj=Sj(Bj)。
(4) 最后,P为固定置换。
?
?
DES 轮函数 F（ ）
? DES中使用的其它特定函数,
初始置换 IP：见 140页图 4-4-3,从图中看出 X的第 58个
比特是 IP（ X）的第一个比特； X的第 50个比特是 IP
（ X）的第二个比特 …
逆置换 IP-1；扩展函数 E；置换函数 P。
? 从密钥 K计算子密钥,
实际上,K是长度为 64的位串，其中 56位是密钥，
8位是奇偶校验位（为了检错），在密钥编排的计算中，
这些校验位可略去。
(1),给定 64位的密钥 K，放弃奇偶校验位（ 8,16,…,
64）并根据固定置换 PC-1（见 144页图 4-4-9）来排列
K中剩下的位。我们写
PC-1(K)=C0D0
其中 C0由 PC-1（ K）的前 28位组成； D0由后 28位组成。
? (2)对 1<=i<=16,计算
Ci=LSi(Ci-1)
Di=LSi(Di-1)
LSi表示循环左移 2或 1个位置，取决于 i的 的值。
i=1,2,9和 16 时移 1个位置，否则移 2位置（ 143页表 4-
4-2）。
Ki=PC-2(CiDi),PC-2为固定置（ 见 145页图 4-4-10)。
? 注,一共 16轮，每一轮使用 K中 48位组成一个 48比特
密钥。可算出 16个表，第 i个表中的元素可对应上第 i
轮密钥使用 K中第几比特！如,
第 7轮的表 7,K7取 K中的比特情况,
52 57 11 1 26 59 10 34 44 51 25 19
9 41 3 2 50 35 36 43 42 33 60 18
28 7 14 29 47 46 22 5 15 63 61 39
4 31 13 38 53 62 55 20 23 37 30 6
轮密钥编排
K
PC-1
C0 D0
LS1 LS1
C1 D1
LS2 LS2
LS16 LS16
C16 D16
PC-2
PC-2
K1
K16
…
? 14,17,11,24,1,5,C half
? 3,28,15,6,21,10,(bits 1-28)
? 23,19,12,4,26,8,
? 16,7,27,20,13,2,
? 41,52,31,37,47,55,D half
? 30,40,51,45,33,48,(bits 29-56)
? 44,49,39,56,34,53,
? 46,42,50,36,29,32
? C half provides bits to S1-S4,D half to S5-S8
PC2
DES加密的一个例子
? 取 16进制明文 X,0123456789ABCDEF
密钥 K为,133457799BBCDFF1
去掉奇偶校验位以二进制形式表示的密钥是
000100100110100101011011110010011011
01111011011111111000
应用 IP，我们得到,
L0=11001100000000001100110011111111
L1=R0=111100001010101011110000101010
10
然后进行 16轮加密。
最后对 L16,R16使用 IP-1得到密文：
85E813540F0AB405
8.5.2 DES的设计思想和特点
? DES的核心是 S盒，除此之外的计算是属
线性的。 S盒作为该密码体制的非线性组
件对安全性至关重要。
? S盒的设计准则,
1,S盒不是它输入变量的线性函数
2.改变 S盒的一个输入位至少要引起两位
的输出改变
3,对 任何一个 S盒，如果固定一个输入
比特，其它输入变化时，输出数字中 0和
1的总数近于相等。
? DES的弱点,
? 1）存在一些弱密钥和半弱密钥。
? 2）在 DES的明文 m，密文 C与
密钥 k之间存在着互补的特性。
8.5.3 DES的工作方式（对其他分组密
码也适用）
? 1.电子密文方式
（ ECB）
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n
，?，,,?,
，?，,,?,
密文区块 i ＝加密（明文区块 i ）
ECB 模式
加密 加密
,
? 2.密文分组链接
方式 (CBC)
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n,?，,,?,
，?,
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n,,?,
密文区块 i ＝明文区块 i 加密 ( 明文区块 i － 1 )
CBC 模式
E CB 模式
IV
?
?
加密
加密
? 3.密文反馈方式
（ CFB）
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n,?，,,?,
，?,
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n
,
，?,
密文区块 i ＝明文区块 i 加密 ( 密文区块 i - 1)
CF B 模式
E CB 模式
IV
? ?
加 密
? 4.输出反馈模式
（ OFB）
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n,?,
，?,
，?,
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n
,
，?,
S
i
＝加密 (S
i
- 1 ),密文区块 i= 明文区块 i S
i
OFB 模式
IV
? ?
加密
S
i - 1
S
i
8.5.5 DES的安全性
? 对 DES的批评主要集中在以下几
点,
? DES的密钥长度（ 56位）可能太
小。
? DES的迭代次数可能太少。
? S盒中可能有不安全因素。
? DES的一些关键部分不应当保密。
8.6 典型的分组密码的分析方法
? 1.穷尽密钥搜索（强力攻击）
? 2.线性分析方法
? 3.差分分析方法
? 4.相关密钥密码分析
? 5.中间相遇攻击
8.6.1 差分分析法
? 差分分析方法是一种选择明文攻
击,
? 基本思想是通过分析特定明文差
分对相应密文差分影响来获得可
能性最大的密钥。
8.6.1.1 差分分析的理论依据
? 定义 8.6.1 设 Sj是一个给定的 S
－盒 是一对长度为 6
比特的串。称 Sj的输入异或是
的输出异或是 。
? 定理 8.6.1 设 Ej和 Ej× 是 S－盒 Sj
的两输入,Sj的输出异或是 Cjt，
记,则密钥比特 Jj出现在
集合 之中，即 。
? ? ? ?*,,81 jj BBj ??
jjj SBB,*? ? ? ? ?*jjjj BSBS ?
*jjj EEE ???
),,( * jjjj CEEte s t ? ),,( * jjjjj CEEt e s tJ ??
8.6.1.2 差分分析的应用实例
? 例 3 假定有下列的三对明文和密
文，这里明文具有确定的异或，
并且使用同一个密钥加密。为简
单起见，使用 16进制表示。
8.6.2 线性密码分析
? 是一种已知明文攻击
? 攻击者的目的是希望找到有效的
线性表达式
使其成功的概率 p≠1/2,且 |p-1/2|
最大。
? ? ? ? )( rKCP ????? ??
? 在已知Ｎ个明密文对时，线性攻击可
实施如下,
（ 1）对所有明文 P和密文 C,T表示
（ 8.5.2.2）左边为 0的次数。
（ 2）若 T>N/2，那么当 p>1/2时，猜测
K[k1…k l]=0；当 p<1/2时，猜测
K[k1…k l]=1；否则，当 p>1/2时，猜测
K[k1…k l]=1；当 p<1/2，猜测
K[k1…k l]=0；当 |p-1/2|充分小时，成
功的概率为
?
?
??
?
?
2
12
2/2
2
1
pN
x xde
8.7 美国高级数据加密标准 ——
AES
? 背景
从各方面来看,DES已走到了它生命的尽头。 其 56比特
密钥实在太小,虽然三重 DES可以解决密钥长度的问
题，但是 DES的设计主要针对硬件实现，而今在许多
领域，需要
用软件方法来实现它，在这种情况下，它的效率相对较
低。鉴于此,1997年 4月 15日美国国家标准和技术研究
所
（ NIST）发起征集 AES（ AES— Advanced Encryption
Standard）算法的活动，并成立了 AES工作组。目的是
为了确定一个非保密的、公开披露的、全球免费使用的
加密算法，用于保护下一世纪政府的敏感信息。也希望
能够成为保密和非保密部门公用的数据加密标准
（ DES）。
? 要求
该算法应比三重 DES快而且至少还
要一样的安全,
它应当具有 128比特分组长度和
256比特分组密钥长度（不过必
须支持 128和 192比特的密钥）,
此外，还应该具有较大的灵活性。
? 8,7,1 AES的评估准则
1）安全性；
2）代价，主要包括：许可要求，
在各种平台上的计算效率（速度）
和内存空间的需求；
3）算法和实现特性，主要包括：
灵活性、硬件和软件适应性、算
法的简单性等。
1998年 8月 20日,NIST在第一阶段讨论
（ AES1）中宣布了由 12个国家提出的 15个
候选算法,
1
999年 3月开始的第二阶段讨论（ AES2）,
1999年 8月 NIST选出 5个算法候选,
MARS,RC6,Rijndael,Serpent和 Twofish。
8,7,2 高级加密标准算法
AES—— Rijndael
? 最大优点是可以给出算法的最佳
差分特征的概率及最佳线性逼近
的偏差的界，由此，可以分析算
法抵抗差分密码分析及线性密码
分析的能力。
字节代换
行移变换
列变换
列变换
行移变换
字节代换
行移变换
字节代换
子密钥（ Nr - 1 ）
子密钥（ 0 ）
子密钥（ 1 ）
第一轮
子密钥（ Nr ）
最后一轮
第 Nr - 1 轮
明文块 密 文块
图 8, 5, 1 Rijn d a e l 加密流
? Rijndael算法的安全性
能有效地抵抗目前已知的攻击方
法的攻击。如：部分差分攻击、
相关密钥攻击、插值攻击
（ Interpolation attack）等。
对于 Rijndael，最有效的攻击还
是穷尽密钥搜索攻击。
先进分组密码的特点
? 可变密钥长度
? 混合操作
? 依赖数据的循环移位
? 依赖于密钥的循环移位
? 依赖密钥的 S盒子
? 冗长的密钥调度算法
? 可变的 F函数和可变的明文 /密文长度
? 可变的循环次数
? 在每次循环中都对两半数据进行操作
8.8 欧洲 21世纪数据加密标准
? NESSIE(New European
Schemes for Signature,Integrity,
and Encryption)是欧洲的信息社
会技术（ IST）委员会计划出资
33亿欧元支持的一项工程 —— 数
字签名、完整性和加密新欧洲方
案。
? 64比特分组密码 —— MISTY1
? 128比特分组密码 —— AES和
Camellia
? 256比特分组密码 ——
SHACAL-2
8.8.2 Camellia算法简介
? 1 加密过程
)128(
M
? ?
)64(1
kw
)64(2
kw
6 轮
)64(0
L
)64(0
R
)64(1
k
)64(2
k
)64(3
k
)64(4
k
)64(5
k
)64(6
k
FL
1?
FL
)64(1
kl
)64(2
kl
6 轮
)64(7
k
)64(8
k
)64(9
k
)64(10
k
)64(11
k
)64(12
k
FL
1?
FL
)64(3
kl
)64(4
kl
6 轮
)64(13
k
)64(14
k
)64(15
k
)64(16
k
)64(17
k
)64(18
k
)64(18
L
)64(18
R
? ?
)64(3
kw
)64(4
kw
)128(
C
F
?
F
?
F
?
F
?
F
?
F
?
)64(0
L
)64(1
k
)64(2
k
)64(3
k
)64(4
k
)64(5
k
)64(6
k
)64(0
R
)64(1
L
)64(1
R
)64(2
L
)64(2
R
)64(3
L
)64(3
R
)64(4
L
)64(4
R
)64(5
L
)64(5
R
图 8, 8, 1 1 2 8 比特密钥加密过程
? 2 解密过程
? 3密钥方案
? )64(6
F
?
F
?
? )64(2
?
? )64(1
F
?
F
?
? )64(4
? )64(3
F
?
F
?
? )64(5
?
)1 2 8()1 2 8( RL
KK ?
)128(L
K
)128(R
K
)128(A
K
)128(B
K
图 8, 8, 2 密钥方案
8.8.2.2 Camellia组件
? 1 F函数
? 2 FL和 FL-1函数
)((),( )64()64()64()64()64( ii kXSPkXFY ???
1
??? ?
?
?
)64(
X
)32(L
X
)32(R
X
)32(L
Y
)32(R
Y
)64(
Y
)32(iL
kl
)32(iR
kl
图 8, 8, 4 函数
FL
和 1?
FL
?
)32(iR
kl
?
)32(iL
kl
1
???
?
?
?
)32(L
Y
)32(R
Y
)64(
Y
)64(
X
)32(L
X
)32(R
X
? 3 P函数
? 4 S盒
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
7
8
'
1
'
7
'
8
1
7
8
z
z
z
P
z
z
z
z
z
z
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
10110111
11011011
11101101
01111110
11000111
01101011
00111101
10011110
P
ExCfghxs 6) ) )5(((,)8()8(1 ???
1)8(1)8(2 )(,???xsxs ?
1)8(1)8(3 )(,???xsxs ?
)(,1)8(1)8(4 ? ? ?xsxs ?
8.8.2.3 安全性
? 高水平的安全性和多平台的有效
性。
? 12轮以上不存在线性偏差和差分
特征概率大于的差分 /线性特征。
? 15轮以上不存在概率大于的差分
和线性特征。
特点,
? Camellia被仔细地设计以便能击退所有已知
的密码分析，设计者设想 10年到 20年安全期
限。
? 该密码非常适合软件、硬件实现，应用范围
包括从低耗智能卡到高速网络系统。用汇编
语言的优化实现在 Pentium Ⅲ 800MHz加密
速度超过每秒 276M比特，比优化的 DES实
现快多了。
? 另外，一个显著的特征是它的小的硬件设计。
硬件设计包括密钥方案，加密和解密，只占
用大约 1.1万个门，这在目前现存的 128比特
分组密码中是最小的，极好地迎合了当前无
线卡市场需求。
8,1 分组密码概述
? 定义 8.1 一个分组密码是一种映
射,
记为 E(X,K) 或
称为明文空间,称为密文空间,
为密钥空间。
F F Fn t m2 2 2? ?
ntnk FFKFXXE 222,,),( ??
mF2
tF2
8,2 分组密码的设计原则
? 有关实用密码的两个一般设计原则是
Shannon提出的混乱原则和扩散原则。
? 混乱：人们所设计的密码应使得密钥
和明文以及密文之间的依赖关系相当
复杂以至于这种依赖性对密码分析者
来说是无法利用的。
? 扩散：人们所设计的密码应使得密钥
的每一位数字影响密文的许多位数字
以防止对密钥进行逐段破译，而且明
文的每一位数字也应影响密文的许多
位数字以便隐蔽明文数字统计特性。
? 软件实现的设计原则：使用子块和简
单的运算。密码运算在子块上进行，
要求子块的长度能自然地适应软件编
程，比如 8,16,32比特等。在软件
实现中，按比特置换是难于实现的，
因此我们应尽量避免使用它。子块上
所进行的一些密码运算应该是一些易
于软件实现的运算，最好是用一些标
准处理器所具有的一些基本指令，比
如加法、乘法和移位等。
? 硬件实现的设计原则：加密和解
密可用同样的器件来实现。尽量
使用规则结构，因为密码应有一
个标准的组件结构以便其能适应
于用超大规模集成电路实现。
? 其他原则,
? 简单性原则：包括规范的简单性
和分析的简单性。
? 必须能抗击所有已知的攻击，特
别是差分攻击和线性攻击。
? 可扩展性。要求能提供 128,192、
256比特的可变分组或密钥长。
8,3 分组密码的结构
Y ( r - 1) X= Y ( 0 ) Y ( 2 ) Y ( 1 ) Y ( r)
F F F ?
密钥 k
Z
(r)
Z
( 1)
Z
( 2)
图 8, 2
? Feistel网络与 SP网络，它们的主要区别在
于,SP结构每轮改变整个数据分组，而
Feistel密码每轮只改变输入分组的一半。
? AES和 DES分别是这两种结构的代表。
? Feistel网络（又称 Feistel结构）可把任何轮
函数转化为一个置换，它是由 Horst Feistel
在设计 Lucifer分组密码时发明的，并因 DES
的使用而流行。“加解密相似”是 Feistel型
密码的实现优点。
? SP网络（又称 SP结构）是 Feistel网络的一
种推广，其结构清晰,S一般称为混淆层，
主要起混淆作用。 P一般称为扩散层，主要
起扩散作用。 SP网络与 Feistel网络相比，
可以得到更快速的扩散，不过 SP网络的加
解密通常不相似。有关这两种结构的特点，
读者在了解了 DES和 AES算法之后再细细体
会。
8.4 分组密码的安全性
8.4.1 安全需求
? 如果不知道密钥的知识，攻击者从密
文恢复出明文是实际不可能的。
? 用固定的 k比特的秘密钥，加密 T个明
文，其中,最大化 T后仍能达
到一个可接受的安全性是现代分组密
码追求的目标。
? 几乎所有当代分组密码用更小的查表
（代替盒或 S盒）合并其他变换（线
性变换）模仿这样一个大的随机查表。
这种做法实际上是安全性和可接受的
复杂性的一个折中。
???????? NkT
8.4.2 安全模型
? 1）无条件安全性。
? 2）多项式安全性。
? 3）“可证明的安全性”。
? 4）实际的安全性。
? 5）历史的安全性。
8.4.3 分组密码作为一个伪随机置换
? 伪随机意味：在多项式时间内，加密
询问使得没有攻击者可以区分分组密
码和一真实的随机置换；相应于选择
明文攻击。
? 超伪随机意味：在多项式时间内，加、
解密询问使得没有攻击者可以区分分
组密码和一真实的随机置换。相应于
选择明、密文攻击。
? 分组密码也可以与单向函数联系。
8.4.4 攻击的分类
? 数据复杂度：实施一个攻击所需
输入的数据量，用长为 N的分组
作单位。
? 处理复杂度：执行一个攻击所花
的时间，时间单位可取攻击者不
得不亲自做的加密次数。
? 存储复杂度：需要记忆的字，单
位可取长为 N的分组。
? 组密码的攻击方法目前有：穷举
密钥搜索法、差分分析、截断差
分分析、不可能差分分析、高阶
差分分析、线性分析、差分线性
分析,Boomerang攻击、相关密
钥攻击、插值攻击、非双射攻击、
Slide攻击、攻击。
8.5 典型的分组密码算法 —— DES
? DES的历史
1971 IBM,由 Horst Feistel 领导
的密码研
究项目组研究出 LUCIFER算法。
并应用于
商业领域。
1973美国标准局征求标准,IBM提
交结果,
在 1977年，被选为数据加密标准。
8.5.1 DES的描述
? DES利用 56比特串长度的密钥 K来加密长度为 64位的明文，
得到长度为 64位的密文
? 该算法分三个阶段实现,
1,给定明文 X,通过一个固定的初始置换 IP来排列 X中的位，
得到 X0。
X0=IP（ X） =L0R0
其中 L0由 X0前 32位组成,R0由 X0的后 32位组成。
2.计算函数 F的 16次迭代,根据下述规则来计算
LiRi(1<=i<=16）
Li=Ri-1,Ri=Li-1 ? F(Ri-1,Ki)
其中 Ki是长为 48位的子密钥。子密钥 K1,K2,…, K16是
作为密钥 K（ 56位）的函数而计算出的。
3.对比特串 R16L16使用逆置换 IP-1得到密文 Y。
Y=IP-1（ R16L16）
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
PC1
? 57,49,41,33,25,17,9,C Half
? 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,D Half
? 7,62,54,46,38,30,22,
? 14,6,61,53,45,37,29,
? 21,13,5,28,20,12,4
S-box-1
? 0 1 2 3 4 5 6 7 8 9 a b c d e f COL
S[1]
? 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
?
DES一轮加密的简图
?
Li-1 Ri-1
F
+
Li Ri
Ki
? 对 F函数的说明,（类比于 S-DES） F（ Ri-1,Ki）
函数 F以 长度为 32的比特串 A=R（ 32bits） 作第一个输入，
以长度为 48的比特串变元 J=K(48bits)作为第二个输入。
产生的输出为长度为 32的位串。
(1)对第一个变元 A,由给定的扩展函数 E,将其扩展成 48
位串,E（ A）
(2)计算 E（ A） +J,并把结果写成连续的 8个 6位串,
B=b1b2b3b4b5b6b7b8
(3)使用 8个 S盒，每个 Sj是一个固定的 4?16矩阵，它的元
素取 0~15的整数。给定长度为 6个比特串，如
Bj=b1b2b3b4b5b6
计算 Sj(Bj)如下,b1b6两个比特确定了 Sj的行数,
r(0<=r<=3); 而 b2b3b4b5四个比特确定了 Sj的列数 c
（ 0<=c<=15）。 最后 Sj(Bj)的值为 S-盒矩阵 Sj中 r行 c列的
元素（ r,c）,得 Cj=Sj(Bj)。
(4) 最后,P为固定置换。
?
?
DES 轮函数 F（ ）
? DES中使用的其它特定函数,
初始置换 IP：见 140页图 4-4-3,从图中看出 X的第 58个
比特是 IP（ X）的第一个比特； X的第 50个比特是 IP
（ X）的第二个比特 …
逆置换 IP-1；扩展函数 E；置换函数 P。
? 从密钥 K计算子密钥,
实际上,K是长度为 64的位串，其中 56位是密钥，
8位是奇偶校验位（为了检错），在密钥编排的计算中，
这些校验位可略去。
(1),给定 64位的密钥 K，放弃奇偶校验位（ 8,16,…,
64）并根据固定置换 PC-1（见 144页图 4-4-9）来排列
K中剩下的位。我们写
PC-1(K)=C0D0
其中 C0由 PC-1（ K）的前 28位组成； D0由后 28位组成。
? (2)对 1<=i<=16,计算
Ci=LSi(Ci-1)
Di=LSi(Di-1)
LSi表示循环左移 2或 1个位置，取决于 i的 的值。
i=1,2,9和 16 时移 1个位置，否则移 2位置（ 143页表 4-
4-2）。
Ki=PC-2(CiDi),PC-2为固定置（ 见 145页图 4-4-10)。
? 注,一共 16轮，每一轮使用 K中 48位组成一个 48比特
密钥。可算出 16个表，第 i个表中的元素可对应上第 i
轮密钥使用 K中第几比特！如,
第 7轮的表 7,K7取 K中的比特情况,
52 57 11 1 26 59 10 34 44 51 25 19
9 41 3 2 50 35 36 43 42 33 60 18
28 7 14 29 47 46 22 5 15 63 61 39
4 31 13 38 53 62 55 20 23 37 30 6
轮密钥编排
K
PC-1
C0 D0
LS1 LS1
C1 D1
LS2 LS2
LS16 LS16
C16 D16
PC-2
PC-2
K1
K16
…
? 14,17,11,24,1,5,C half
? 3,28,15,6,21,10,(bits 1-28)
? 23,19,12,4,26,8,
? 16,7,27,20,13,2,
? 41,52,31,37,47,55,D half
? 30,40,51,45,33,48,(bits 29-56)
? 44,49,39,56,34,53,
? 46,42,50,36,29,32
? C half provides bits to S1-S4,D half to S5-S8
PC2
DES加密的一个例子
? 取 16进制明文 X,0123456789ABCDEF
密钥 K为,133457799BBCDFF1
去掉奇偶校验位以二进制形式表示的密钥是
000100100110100101011011110010011011
01111011011111111000
应用 IP，我们得到,
L0=11001100000000001100110011111111
L1=R0=111100001010101011110000101010
10
然后进行 16轮加密。
最后对 L16,R16使用 IP-1得到密文：
85E813540F0AB405
8.5.2 DES的设计思想和特点
? DES的核心是 S盒，除此之外的计算是属
线性的。 S盒作为该密码体制的非线性组
件对安全性至关重要。
? S盒的设计准则,
1,S盒不是它输入变量的线性函数
2.改变 S盒的一个输入位至少要引起两位
的输出改变
3,对 任何一个 S盒，如果固定一个输入
比特，其它输入变化时，输出数字中 0和
1的总数近于相等。
? DES的弱点,
? 1）存在一些弱密钥和半弱密钥。
? 2）在 DES的明文 m，密文 C与
密钥 k之间存在着互补的特性。
8.5.3 DES的工作方式（对其他分组密
码也适用）
? 1.电子密文方式
（ ECB）
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n
，?，,,?,
，?，,,?,
密文区块 i ＝加密（明文区块 i ）
ECB 模式
加密 加密
,
? 2.密文分组链接
方式 (CBC)
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n,?，,,?,
，?,
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n,,?,
密文区块 i ＝明文区块 i 加密 ( 明文区块 i － 1 )
CBC 模式
E CB 模式
IV
?
?
加密
加密
? 3.密文反馈方式
（ CFB）
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n,?，,,?,
，?,
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n
,
，?,
密文区块 i ＝明文区块 i 加密 ( 密文区块 i - 1)
CF B 模式
E CB 模式
IV
? ?
加 密
? 4.输出反馈模式
（ OFB）
明文区块 1 明文区块 i - 1 明文区块 i 明文区块 n,?,
，?,
，?,
密文区块 1 密文区块 i - 1 密文区块 i 密文区块 n
,
，?,
S
i
＝加密 (S
i
- 1 ),密文区块 i= 明文区块 i S
i
OFB 模式
IV
? ?
加密
S
i - 1
S
i
8.5.5 DES的安全性
? 对 DES的批评主要集中在以下几
点,
? DES的密钥长度（ 56位）可能太
小。
? DES的迭代次数可能太少。
? S盒中可能有不安全因素。
? DES的一些关键部分不应当保密。
8.6 典型的分组密码的分析方法
? 1.穷尽密钥搜索（强力攻击）
? 2.线性分析方法
? 3.差分分析方法
? 4.相关密钥密码分析
? 5.中间相遇攻击
8.6.1 差分分析法
? 差分分析方法是一种选择明文攻
击,
? 基本思想是通过分析特定明文差
分对相应密文差分影响来获得可
能性最大的密钥。
8.6.1.1 差分分析的理论依据
? 定义 8.6.1 设 Sj是一个给定的 S
－盒 是一对长度为 6
比特的串。称 Sj的输入异或是
的输出异或是 。
? 定理 8.6.1 设 Ej和 Ej× 是 S－盒 Sj
的两输入,Sj的输出异或是 Cjt，
记,则密钥比特 Jj出现在
集合 之中，即 。
? ? ? ?*,,81 jj BBj ??
jjj SBB,*? ? ? ? ?*jjjj BSBS ?
*jjj EEE ???
),,( * jjjj CEEte s t ? ),,( * jjjjj CEEt e s tJ ??
8.6.1.2 差分分析的应用实例
? 例 3 假定有下列的三对明文和密
文，这里明文具有确定的异或，
并且使用同一个密钥加密。为简
单起见，使用 16进制表示。
8.6.2 线性密码分析
? 是一种已知明文攻击
? 攻击者的目的是希望找到有效的
线性表达式
使其成功的概率 p≠1/2,且 |p-1/2|
最大。
? ? ? ? )( rKCP ????? ??
? 在已知Ｎ个明密文对时，线性攻击可
实施如下,
（ 1）对所有明文 P和密文 C,T表示
（ 8.5.2.2）左边为 0的次数。
（ 2）若 T>N/2，那么当 p>1/2时，猜测
K[k1…k l]=0；当 p<1/2时，猜测
K[k1…k l]=1；否则，当 p>1/2时，猜测
K[k1…k l]=1；当 p<1/2，猜测
K[k1…k l]=0；当 |p-1/2|充分小时，成
功的概率为
?
?
??
?
?
2
12
2/2
2
1
pN
x xde
8.7 美国高级数据加密标准 ——
AES
? 背景
从各方面来看,DES已走到了它生命的尽头。 其 56比特
密钥实在太小,虽然三重 DES可以解决密钥长度的问
题，但是 DES的设计主要针对硬件实现，而今在许多
领域，需要
用软件方法来实现它，在这种情况下，它的效率相对较
低。鉴于此,1997年 4月 15日美国国家标准和技术研究
所
（ NIST）发起征集 AES（ AES— Advanced Encryption
Standard）算法的活动，并成立了 AES工作组。目的是
为了确定一个非保密的、公开披露的、全球免费使用的
加密算法，用于保护下一世纪政府的敏感信息。也希望
能够成为保密和非保密部门公用的数据加密标准
（ DES）。
? 要求
该算法应比三重 DES快而且至少还
要一样的安全,
它应当具有 128比特分组长度和
256比特分组密钥长度（不过必
须支持 128和 192比特的密钥）,
此外，还应该具有较大的灵活性。
? 8,7,1 AES的评估准则
1）安全性；
2）代价，主要包括：许可要求，
在各种平台上的计算效率（速度）
和内存空间的需求；
3）算法和实现特性，主要包括：
灵活性、硬件和软件适应性、算
法的简单性等。
1998年 8月 20日,NIST在第一阶段讨论
（ AES1）中宣布了由 12个国家提出的 15个
候选算法,
1
999年 3月开始的第二阶段讨论（ AES2）,
1999年 8月 NIST选出 5个算法候选,
MARS,RC6,Rijndael,Serpent和 Twofish。
8,7,2 高级加密标准算法
AES—— Rijndael
? 最大优点是可以给出算法的最佳
差分特征的概率及最佳线性逼近
的偏差的界，由此，可以分析算
法抵抗差分密码分析及线性密码
分析的能力。
字节代换
行移变换
列变换
列变换
行移变换
字节代换
行移变换
字节代换
子密钥（ Nr - 1 ）
子密钥（ 0 ）
子密钥（ 1 ）
第一轮
子密钥（ Nr ）
最后一轮
第 Nr - 1 轮
明文块 密 文块
图 8, 5, 1 Rijn d a e l 加密流
? Rijndael算法的安全性
能有效地抵抗目前已知的攻击方
法的攻击。如：部分差分攻击、
相关密钥攻击、插值攻击
（ Interpolation attack）等。
对于 Rijndael，最有效的攻击还
是穷尽密钥搜索攻击。
先进分组密码的特点
? 可变密钥长度
? 混合操作
? 依赖数据的循环移位
? 依赖于密钥的循环移位
? 依赖密钥的 S盒子
? 冗长的密钥调度算法
? 可变的 F函数和可变的明文 /密文长度
? 可变的循环次数
? 在每次循环中都对两半数据进行操作
8.8 欧洲 21世纪数据加密标准
? NESSIE(New European
Schemes for Signature,Integrity,
and Encryption)是欧洲的信息社
会技术（ IST）委员会计划出资
33亿欧元支持的一项工程 —— 数
字签名、完整性和加密新欧洲方
案。
? 64比特分组密码 —— MISTY1
? 128比特分组密码 —— AES和
Camellia
? 256比特分组密码 ——
SHACAL-2
8.8.2 Camellia算法简介
? 1 加密过程
)128(
M
? ?
)64(1
kw
)64(2
kw
6 轮
)64(0
L
)64(0
R
)64(1
k
)64(2
k
)64(3
k
)64(4
k
)64(5
k
)64(6
k
FL
1?
FL
)64(1
kl
)64(2
kl
6 轮
)64(7
k
)64(8
k
)64(9
k
)64(10
k
)64(11
k
)64(12
k
FL
1?
FL
)64(3
kl
)64(4
kl
6 轮
)64(13
k
)64(14
k
)64(15
k
)64(16
k
)64(17
k
)64(18
k
)64(18
L
)64(18
R
? ?
)64(3
kw
)64(4
kw
)128(
C
F
?
F
?
F
?
F
?
F
?
F
?
)64(0
L
)64(1
k
)64(2
k
)64(3
k
)64(4
k
)64(5
k
)64(6
k
)64(0
R
)64(1
L
)64(1
R
)64(2
L
)64(2
R
)64(3
L
)64(3
R
)64(4
L
)64(4
R
)64(5
L
)64(5
R
图 8, 8, 1 1 2 8 比特密钥加密过程
? 2 解密过程
? 3密钥方案
? )64(6
F
?
F
?
? )64(2
?
? )64(1
F
?
F
?
? )64(4
? )64(3
F
?
F
?
? )64(5
?
)1 2 8()1 2 8( RL
KK ?
)128(L
K
)128(R
K
)128(A
K
)128(B
K
图 8, 8, 2 密钥方案
8.8.2.2 Camellia组件
? 1 F函数
? 2 FL和 FL-1函数
)((),( )64()64()64()64()64( ii kXSPkXFY ???
1
??? ?
?
?
)64(
X
)32(L
X
)32(R
X
)32(L
Y
)32(R
Y
)64(
Y
)32(iL
kl
)32(iR
kl
图 8, 8, 4 函数
FL
和 1?
FL
?
)32(iR
kl
?
)32(iL
kl
1
???
?
?
?
)32(L
Y
)32(R
Y
)64(
Y
)64(
X
)32(L
X
)32(R
X
? 3 P函数
? 4 S盒
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
7
8
'
1
'
7
'
8
1
7
8
z
z
z
P
z
z
z
z
z
z
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
10110111
11011011
11101101
01111110
11000111
01101011
00111101
10011110
P
ExCfghxs 6) ) )5(((,)8()8(1 ???
1)8(1)8(2 )(,???xsxs ?
1)8(1)8(3 )(,???xsxs ?
)(,1)8(1)8(4 ? ? ?xsxs ?
8.8.2.3 安全性
? 高水平的安全性和多平台的有效
性。
? 12轮以上不存在线性偏差和差分
特征概率大于的差分 /线性特征。
? 15轮以上不存在概率大于的差分
和线性特征。
特点,
? Camellia被仔细地设计以便能击退所有已知
的密码分析，设计者设想 10年到 20年安全期
限。
? 该密码非常适合软件、硬件实现，应用范围
包括从低耗智能卡到高速网络系统。用汇编
语言的优化实现在 Pentium Ⅲ 800MHz加密
速度超过每秒 276M比特，比优化的 DES实
现快多了。
? 另外，一个显著的特征是它的小的硬件设计。
硬件设计包括密钥方案，加密和解密，只占
用大约 1.1万个门，这在目前现存的 128比特
分组密码中是最小的，极好地迎合了当前无
线卡市场需求。
