2010-5-14 1
第四章 分组密码
一、分组密码概述
二、分组密码运行模式
三,DES
四,AES
五、分组密码的分析
2010-5-14 2
一、分组密码概述
2010-5-14 3
分组密码概述
? 分组密码是许多系统安全的一个重要组成部分。
可用于构造
? 拟随机数生成器
? 流密码
? 消息认证码 (MAC)和杂凑函数
? 消息认证技术、数据完整性机构、实体认证协议以
及单钥数字签字体制的核心组成部分 。
2010-5-14 4
应用中对于分组码的要求
? 安全性
? 运行速度
? 存储量 (程序的长度、数据分组长度、高速缓
存大小 )
? 实现平台 (硬、软件、芯片 )
? 运行模式
2010-5-14 5
分组密码概述
明文序列 x1,x2,…,xi,…
加密函数 E,Vn× K?Vn
这种密码实质上是字长为 m的数字序列的代换密码 。
解密算法加密算法
密钥 k=(k0,k1,…,kt-1 ) 密钥 k=(k0,k1,…,kt-1 )
明文
x=(x0,x1,…,xm-1)
明文
x=(x0,x1,…,xm-1)
密文
x=(y0,y1,…,ym-1)
2010-5-14 6
分组密码概述
? 通常取 n=m。
? 若 n>m,则为有数据扩展的分组密码。
? 若 n<m,则为有数据压缩的分组密码。
2010-5-14 7
分组密码设计问题
分组密码的设计问题在于找到一种算法, 能
在密钥控制下从一个足够大且足够好的置换子
集中, 简单而迅速地选出一个置换, 用来对当
前输入的明文的数字组进行加密变换 。
2010-5-14 8
分组密码算法应满足的要求
? 分组长度 n要足够大：
防止明文穷举攻击法奏效 。
? 密钥量要足够大：
尽可能消除弱密钥并使所有密钥同等地好, 以防止
密钥穷举攻击奏效 。
? 由密钥确定置换的算法要足够复杂：
充分实现明文与密钥的扩散和混淆，没有简单的关
系可循, 要能抗击各种已知的攻击。
2010-5-14 9
分组密码算法应满足的要求
? 加密和解密运算简单,
易于软件和硬件高速实现 。
? 数据扩展：
一般无数据扩展, 在采用同态置换和随机化加密技术时
可引入数据扩展 。
? 差错传播尽可能地小 。
2010-5-14 10
代换网络
? 代换 是输入集 A到输出 A’上的双射变换,
fk,A?A＇
式中, k是控制输入变量, 在密码学中则为密
钥 。
? 实现代换 fk的网络称作代换网络 。 双射条件保
证在给定 k下可从密文惟一地恢复出原明文 。
2010-5-14 11
代换网络
? 代换 fk的集合：
S={fk?k?K}
? K是密钥空间 。 如果网络可以实现所有可
能的 2n!个代换, 则称其为全代换网络 。
? 全代换网络密钥个数必须满足条件：＃
{k}?2n!
2010-5-14 12
代换网络
? 密码设计中需要先定义代换集 S,而后还需
定义解密变换集, 即逆代换网络 S-1,它以
密文 y作为输入矢量, 其输出为恢复的明文
矢量 x。
? 要实现全代换网络并不容易 。 因此实用中
常常利用一些简单的基本代换, 通过组合
实现较复杂的, 元素个数较多的代换集 。
实用密码体制的集合 S中的元素个数都远小
于 2n!。
2010-5-14 13
代换盒 (S盒 )
在密码设计中, 可选 n=r?n0,其中 r和 n0都为正整数,
将设计 n个变量的代换网络化为设计 r个较小的子代换
网络, 而每个子代换网络只有 n0个输入变量 。 称每个子
代换网络为代换盒 (Substitution Box)
S盒
x5 x4 x3 x2 x1 x0
y3 y2 y1 y0
DES的 S盒
2010-5-14 14
DES的 S1-盒的输入和输出关系
? x5 x0 x5 x4 x3 x2 x1 x0
1 0 1 0 1 1 0 0
列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
行号
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13
(y3,y2,y1,
y0)=(0,0,1,0)
2010-5-14 15
扩散和混淆
? 扩散将明文的统计特性散布到密文中。
实现的方式是使明文的每一位影响密文
中多位的值。
2010-5-14 16
S盒的设计准则
迄今为止, 有关方面未曾完全公开有关 DES的 S盒的设计准
则 。 Branstead等曾披露过下述准则：
? P1 S盒的输出都不是其输入的线性或仿射函数 。
? P2 改变 S盒的一个输入比特, 其输出至少有两比特产生变
化, 即近一半产生变化 。
? P3 当 S盒的任一输入位保持不变, 其它 5位输入变化时 (共
有 25 =32种情况 ),输出数字中的 0和 1的总数近于相等 。
这三点使 DES的 S盒能够实现较好的混淆 。
2010-5-14 17
S盒的组合
问题, 如何将几个 S盒组合起来构成一个 n值较
大的组 。
将几个 S盒的输入端并行, 并通过坐标置换 (P-盒 )将各 S
盒输出比特次序打乱, 再送到下一级各 S盒的输入端, 起到
了 Shannon所谓的, 扩散, 作用 。 S盒提供非线性变换, 将
来自上一级不同的 S盒的输出进行, 混淆, 。 经过 P-盒的扩
散作用使 1均匀地分散到整个输出矢量中, 从而保证了输出
密文统计上的均匀性, 这就是 Shannon的乘积密码的作用 。
2010-5-14 18
Feistel网络
将 n bit明文分成为左右各半, 长为 n/2 bit的段, 以 L和 R表
示 。 然后进行多轮迭代, 其第 i轮迭代的输出为前轮输出的
函数
Li =Ri-1
Ri =Li-1 ?f(Ri-1,Ki)
式中, Ki是第 i轮用的子密钥, f是任意密码轮函数 。 称这种
分组密码算法为 Feistel网络 （ Feistel Network）, 它保证加
密和解密可采用同一算法实施
2010-5-14 19
迭代分组密码
? 若以一个简单函数 f,进行多次迭代, 就称其为迭代密码 。
? 每次迭代称作一轮 (Round)。 相应函数 f称作轮函数 。
? 每一轮输出都是前一轮输出的函数, 即 y(i)=f[y(i-1),k(i)],其
中 k(i)是第 i轮迭代用的子密钥, 由秘密密钥 k通过密钥生成
算法产生 。
子 密 钥 产 生 器k
k(1) k(2) k(r)
y(0) = x y(1) y(2) y(r-1) y(r)=y
2010-5-14 20
对合密码 (Involution Cipher)
加密函数 f(x,k),实现 F2n× F2t ? F2n的映射 。 其中, n是分
组长, t是密钥长 。 若对每个密钥取值都有 f[f(x,k),k]=x，
即
f(x,k)2 =I (恒等置换 )
则称其为对合密码, 以 fI表示 。
2010-5-14 21
I型迭代分组密码
? 以对合密码函数构造的多轮迭代分组密码 。
E[x,k]=fI[fI [ ? fI [fI[x,k(1)],k(2)] ?, k(r-1)],k(r)]
D[y,k] =fI [fI[? fI[fI[y,k(r)],k(r-1)] ?, k(2)], k(1)]
? 缺点：对任意偶数轮变换, 若对所有 i选择 k(2i-1) =k(2i)，
则加密的变换等价于恒等变换, 在实用中需要避免这
类密钥选择 。
2010-5-14 22
对合置换和 II型迭代分组密码
? 对合置换
令 P是对 x的置换, 即 P,F2n ? F2n, 若对所有 x?GF(2n)，
有 P[P[x]]=x,即 PP=I(恒等置换 ),以 PI表示 。
? II型迭代分组密码
每轮采用对合密码函数和对合置换级连, 即
F[x,k]＝ PI [fI [x,k]]
并选解密子密钥与加密子密钥逆序, 则加密解密可用同一器
件完成 。
DES,FEAL和 LOKI等都属此类 。
2010-5-14 23
III型迭代分组密码
群密码,若密钥与明文, 密文取自同一空间 GF(2n),且
y=x?k
式中, ?是 群运算, 则称其为群密码 。 显然 x可通过 k的逆元
求得 x=y?k-1
令 x?k为一群密码, 令 fI(x,kB)为一对合密码, 以
F[x,k]＝ fI (x?kA,kB)
为迭代函数, 可以 III型多轮迭代分组密码 。 在最后一轮
中, 另外加了一次群密码运算, 用以保证整个加, 解密
的对合性 。
2010-5-14 24
III型迭代分组密码
轮函数 F F
y(1) y(r-1) (a) 加密
x ? fI ··· ? fI ? y
kA(1) kB(1) kA(r) kB(r) kA(r+1)
F F
y ? fI ? ··· fI ? x
(b) 解密
kA(r+1)) -1 kB(r) (kA(r))-1 kB(1) (kA)-1
2010-5-14 25
IV型迭代分组密码
在 III型密码的轮函数基础上，再增加一个对
合置换 PI,构成 IV型迭代分组密码的轮函数
F[x,k]＝ PI[fI [x?kA,kB]]
2010-5-14 26
IV型迭代分组密码
轮函数 F y(1) y(r-1) F
x ? fI PI ··· ? fI PI PI ? y
kA(1) kB(1) kA(r) kB(r) kA(r+1)
(a) 加密
F F
y ? fI PI ? ··· ? fI ? x
(b) 解密
(kA(r+1)) -1kB(r) PI[kA(r)]-1 PI[kA(2)]-1 kB(1) (kA(1)) -1
第四章 分组密码
一、分组密码概述
二、分组密码运行模式
三,DES
四,AES
五、分组密码的分析
2010-5-14 2
一、分组密码概述
2010-5-14 3
分组密码概述
? 分组密码是许多系统安全的一个重要组成部分。
可用于构造
? 拟随机数生成器
? 流密码
? 消息认证码 (MAC)和杂凑函数
? 消息认证技术、数据完整性机构、实体认证协议以
及单钥数字签字体制的核心组成部分 。
2010-5-14 4
应用中对于分组码的要求
? 安全性
? 运行速度
? 存储量 (程序的长度、数据分组长度、高速缓
存大小 )
? 实现平台 (硬、软件、芯片 )
? 运行模式
2010-5-14 5
分组密码概述
明文序列 x1,x2,…,xi,…
加密函数 E,Vn× K?Vn
这种密码实质上是字长为 m的数字序列的代换密码 。
解密算法加密算法
密钥 k=(k0,k1,…,kt-1 ) 密钥 k=(k0,k1,…,kt-1 )
明文
x=(x0,x1,…,xm-1)
明文
x=(x0,x1,…,xm-1)
密文
x=(y0,y1,…,ym-1)
2010-5-14 6
分组密码概述
? 通常取 n=m。
? 若 n>m,则为有数据扩展的分组密码。
? 若 n<m,则为有数据压缩的分组密码。
2010-5-14 7
分组密码设计问题
分组密码的设计问题在于找到一种算法, 能
在密钥控制下从一个足够大且足够好的置换子
集中, 简单而迅速地选出一个置换, 用来对当
前输入的明文的数字组进行加密变换 。
2010-5-14 8
分组密码算法应满足的要求
? 分组长度 n要足够大：
防止明文穷举攻击法奏效 。
? 密钥量要足够大：
尽可能消除弱密钥并使所有密钥同等地好, 以防止
密钥穷举攻击奏效 。
? 由密钥确定置换的算法要足够复杂：
充分实现明文与密钥的扩散和混淆，没有简单的关
系可循, 要能抗击各种已知的攻击。
2010-5-14 9
分组密码算法应满足的要求
? 加密和解密运算简单,
易于软件和硬件高速实现 。
? 数据扩展：
一般无数据扩展, 在采用同态置换和随机化加密技术时
可引入数据扩展 。
? 差错传播尽可能地小 。
2010-5-14 10
代换网络
? 代换 是输入集 A到输出 A’上的双射变换,
fk,A?A＇
式中, k是控制输入变量, 在密码学中则为密
钥 。
? 实现代换 fk的网络称作代换网络 。 双射条件保
证在给定 k下可从密文惟一地恢复出原明文 。
2010-5-14 11
代换网络
? 代换 fk的集合：
S={fk?k?K}
? K是密钥空间 。 如果网络可以实现所有可
能的 2n!个代换, 则称其为全代换网络 。
? 全代换网络密钥个数必须满足条件：＃
{k}?2n!
2010-5-14 12
代换网络
? 密码设计中需要先定义代换集 S,而后还需
定义解密变换集, 即逆代换网络 S-1,它以
密文 y作为输入矢量, 其输出为恢复的明文
矢量 x。
? 要实现全代换网络并不容易 。 因此实用中
常常利用一些简单的基本代换, 通过组合
实现较复杂的, 元素个数较多的代换集 。
实用密码体制的集合 S中的元素个数都远小
于 2n!。
2010-5-14 13
代换盒 (S盒 )
在密码设计中, 可选 n=r?n0,其中 r和 n0都为正整数,
将设计 n个变量的代换网络化为设计 r个较小的子代换
网络, 而每个子代换网络只有 n0个输入变量 。 称每个子
代换网络为代换盒 (Substitution Box)
S盒
x5 x4 x3 x2 x1 x0
y3 y2 y1 y0
DES的 S盒
2010-5-14 14
DES的 S1-盒的输入和输出关系
? x5 x0 x5 x4 x3 x2 x1 x0
1 0 1 0 1 1 0 0
列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
行号
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13
(y3,y2,y1,
y0)=(0,0,1,0)
2010-5-14 15
扩散和混淆
? 扩散将明文的统计特性散布到密文中。
实现的方式是使明文的每一位影响密文
中多位的值。
2010-5-14 16
S盒的设计准则
迄今为止, 有关方面未曾完全公开有关 DES的 S盒的设计准
则 。 Branstead等曾披露过下述准则：
? P1 S盒的输出都不是其输入的线性或仿射函数 。
? P2 改变 S盒的一个输入比特, 其输出至少有两比特产生变
化, 即近一半产生变化 。
? P3 当 S盒的任一输入位保持不变, 其它 5位输入变化时 (共
有 25 =32种情况 ),输出数字中的 0和 1的总数近于相等 。
这三点使 DES的 S盒能够实现较好的混淆 。
2010-5-14 17
S盒的组合
问题, 如何将几个 S盒组合起来构成一个 n值较
大的组 。
将几个 S盒的输入端并行, 并通过坐标置换 (P-盒 )将各 S
盒输出比特次序打乱, 再送到下一级各 S盒的输入端, 起到
了 Shannon所谓的, 扩散, 作用 。 S盒提供非线性变换, 将
来自上一级不同的 S盒的输出进行, 混淆, 。 经过 P-盒的扩
散作用使 1均匀地分散到整个输出矢量中, 从而保证了输出
密文统计上的均匀性, 这就是 Shannon的乘积密码的作用 。
2010-5-14 18
Feistel网络
将 n bit明文分成为左右各半, 长为 n/2 bit的段, 以 L和 R表
示 。 然后进行多轮迭代, 其第 i轮迭代的输出为前轮输出的
函数
Li =Ri-1
Ri =Li-1 ?f(Ri-1,Ki)
式中, Ki是第 i轮用的子密钥, f是任意密码轮函数 。 称这种
分组密码算法为 Feistel网络 （ Feistel Network）, 它保证加
密和解密可采用同一算法实施
2010-5-14 19
迭代分组密码
? 若以一个简单函数 f,进行多次迭代, 就称其为迭代密码 。
? 每次迭代称作一轮 (Round)。 相应函数 f称作轮函数 。
? 每一轮输出都是前一轮输出的函数, 即 y(i)=f[y(i-1),k(i)],其
中 k(i)是第 i轮迭代用的子密钥, 由秘密密钥 k通过密钥生成
算法产生 。
子 密 钥 产 生 器k
k(1) k(2) k(r)
y(0) = x y(1) y(2) y(r-1) y(r)=y
2010-5-14 20
对合密码 (Involution Cipher)
加密函数 f(x,k),实现 F2n× F2t ? F2n的映射 。 其中, n是分
组长, t是密钥长 。 若对每个密钥取值都有 f[f(x,k),k]=x，
即
f(x,k)2 =I (恒等置换 )
则称其为对合密码, 以 fI表示 。
2010-5-14 21
I型迭代分组密码
? 以对合密码函数构造的多轮迭代分组密码 。
E[x,k]=fI[fI [ ? fI [fI[x,k(1)],k(2)] ?, k(r-1)],k(r)]
D[y,k] =fI [fI[? fI[fI[y,k(r)],k(r-1)] ?, k(2)], k(1)]
? 缺点：对任意偶数轮变换, 若对所有 i选择 k(2i-1) =k(2i)，
则加密的变换等价于恒等变换, 在实用中需要避免这
类密钥选择 。
2010-5-14 22
对合置换和 II型迭代分组密码
? 对合置换
令 P是对 x的置换, 即 P,F2n ? F2n, 若对所有 x?GF(2n)，
有 P[P[x]]=x,即 PP=I(恒等置换 ),以 PI表示 。
? II型迭代分组密码
每轮采用对合密码函数和对合置换级连, 即
F[x,k]＝ PI [fI [x,k]]
并选解密子密钥与加密子密钥逆序, 则加密解密可用同一器
件完成 。
DES,FEAL和 LOKI等都属此类 。
2010-5-14 23
III型迭代分组密码
群密码,若密钥与明文, 密文取自同一空间 GF(2n),且
y=x?k
式中, ?是 群运算, 则称其为群密码 。 显然 x可通过 k的逆元
求得 x=y?k-1
令 x?k为一群密码, 令 fI(x,kB)为一对合密码, 以
F[x,k]＝ fI (x?kA,kB)
为迭代函数, 可以 III型多轮迭代分组密码 。 在最后一轮
中, 另外加了一次群密码运算, 用以保证整个加, 解密
的对合性 。
2010-5-14 24
III型迭代分组密码
轮函数 F F
y(1) y(r-1) (a) 加密
x ? fI ··· ? fI ? y
kA(1) kB(1) kA(r) kB(r) kA(r+1)
F F
y ? fI ? ··· fI ? x
(b) 解密
kA(r+1)) -1 kB(r) (kA(r))-1 kB(1) (kA)-1
2010-5-14 25
IV型迭代分组密码
在 III型密码的轮函数基础上，再增加一个对
合置换 PI,构成 IV型迭代分组密码的轮函数
F[x,k]＝ PI[fI [x?kA,kB]]
2010-5-14 26
IV型迭代分组密码
轮函数 F y(1) y(r-1) F
x ? fI PI ··· ? fI PI PI ? y
kA(1) kB(1) kA(r) kB(r) kA(r+1)
(a) 加密
F F
y ? fI PI ? ··· ? fI ? x
(b) 解密
(kA(r+1)) -1kB(r) PI[kA(r)]-1 PI[kA(2)]-1 kB(1) (kA(1)) -1
