2012-3-19 1
第三章 分组密码
一、分组密码的一般模型
二,DES与 IDEA
三,AES 算法 —— Rijndael
四、分组密码分析方法 *
五、分组密码工作模式
2012-3-19 2
一,分组密码的一般模型
2012-3-19 3
分组密码概述
? 分组密码,
将消息编码表示后的数字（通常是 0和 1）序列 x1,
x2,…,xi,… 划分为长为 n的组,各
组（长为 n的矢量）分别在密钥 的
控制下变换成等长的输出数字序列
（长为 m的矢量）。
? ?0 1 1,,,nx x x x ??
? ?0 1 1,,,tk k k k ??
? ?0 1 1,,,my y y y ??
加 密 算 法 解 密 算 法
明 文
? ?0 1 1,,,nx x x x ??
密 文
密 钥 密 钥
明 文
? ?0 1 1,,,tk k k k ??
? ?0 1 1,,,my y y y ?? ? ?0 1 1,,,nx x x x ??
? ?0 1 1,,,tk k k k ??
分 组 密 码 框 图
2012-3-19 4
? 分组密码是一种满足下列条件的映射 E,
? 对每个, 是从 到 的置换
?,密钥为 时的加密函数
?,密钥为 时的解密函数
? 密钥规模,bit
? 密钥长度等于密钥规模当且仅当,
Eg:DES真正的密钥规模 =56bit,且 也就是密钥长度
22mmkF S F??
? ?,Ek? 2mF 2mF
? ?,Ek?
kkS?
k
? ?,Dk? k
2l o g klS?
2tkSF?
ll
2012-3-19 5
分组密码设计问题
分组密码的设计问题在于找到一
种算法, 能在密钥控制下从一个足
够大且足够好的置换子集中, 简单
而迅速地选出一个置换, 用来对当
前输入的明文的数字组进行加密变
换 。
2012-3-19 6
分组密码算法应满足的要求
? 分组长度 n要足够大,
防止明文穷举攻击法奏效 。
? 密钥量要足够大,
尽可能消除弱密钥并使所有密钥同等地好, 以防止密钥穷
举攻击奏效 。
? 由密钥确定置换的算法要足够复杂,
充分实现明文与密钥的扩散和混淆，没有简单的关系可循
,要能抗击各种已知的攻击
2012-3-19 7
分组密码算法应满足的要求
? 加密和解密运算简单,
易于软件和硬件高速实现 。
? 数据扩展,
一般无数据扩展, 在采用同态置换和随机化加密技术时
可引入数据扩展 。
? 差错传播尽可能地小
2012-3-19 8
二,DES与 IDEA
2012-3-19 9
数据加密标准 （ DES）
? DES的历史
– 1971年 IBM,由 Horst Feistel领导的密码研究项目
组研究出 LUCIFER算法, 并应用于商业领域 ;
– 1973年,美国标准局征求标准, IBM提交结果 ;
– 1977年, 被选为数据加密标准 ;
– 虽然 DES已有替代的数据加密标准算法, 但它仍
是迄今为止得到最广泛应用的一种算法, 也是一
种最有代表性的分组加密体制 。
2012-3-19 10
DES加密过程
? DES利用 56bit长度的密
钥 K来加密长度为 64bit
的明文，得到长度为
64bit的密文
? 该算法分 三个阶段 实现
? IP和 IP-1在密码意义上
作用不大，它们的作用
在于打乱原来输入 x的
ASCII码字划分的关系
，并将原来明文的校验
位 x8,x16,?,x64变成为 IP
输出的一个字节。
逆初始置换
乘积变换
（ ） 16轮迭代
6 4 b i t 密文数据
6 4 b i t 明文数据
初始置换
输入
输出
将 6 4 b i t 明 文 位 置 进 行 置
换 得 到 一 个 乱 序 的 6 4
b i t 明 文 组 而 后 平 分 成
左 右 两 段 I P 中 各 列 元 素 位 号 数
相 差 为 8 相 当 于 将 原 明 文 各 字
节 按 列 写 出 各 列 比 特 经 过
奇 偶 采 样 置 换 后 再 对 各
行 进 行 逆 序 将 阵 中 元
素 按 行 读 出 构 成
置 换 输 出
将 1 6 轮 迭 代 后 给 出 的 6 4
b i t 组 进 行 置 换 得 到 输 出
的 密 文 组 输 出 为 阵 中
的 元 素 按 行 读 得
的 结 果
2012-3-19 11
一轮加密的简图
?
Li-1 Ri-1
F
+
Li Ri
Ki
A=R(32 bits) J=K(48 bits)
E
E(A)为 48 bits +
B1 B2 B3 B4 B5 B6 B7 B8
S1 S2 S3 S4 S5 S6 S7 S8
C1 C2 C3 C4 C5 C6 C7 C8
P
32 bits F(A,J)
B 写成 8个 6比特串
2012-3-19 12
? 对 F函数的说明,F（ Ri-1,Ki） 函数 F以 长
度为 32的比特串 A=R（ 32bits） 作第一个
输入，以长度为 48的比特串变元
J=K(48bits)作为第二个输入。产生的输
出为长度为 32的位串。
– 对第一个变元 A,由给定的扩展函数 E,将其
扩展成 48位串 E（ A） ；
– 计算 E(A)+J,并把结果写成连续的 8个 6位串,
B=b1b2b3b4b5b6b7b8
2012-3-19 13
– 使用 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)。
– 最后, P为一个固定置换 。
2012-3-19 14
选择压缩运算 S
4 8 b i t 寄存器
S1
3 2 b i t 寄存器
S3S2 S5 S6 S7 S8S4
6bit
4bit
2012-3-19 15
子密钥的生成
? 从密钥 K计算子密钥,实际上,K是长
度为 64的位串，其中 56位是密钥,8位是奇偶
校验位（为了检错），在密钥编排的计算中
，这些校验位可略去。
– 给定 64位的密钥 K,放弃奇偶校验位 （ 8,16，
…, 64） 并根据固定置换 PC-1来排列 K中剩下的
位 。 PC-1(K)=C0D0 。 其中 C0由 PC-1（ K） 的前 28
位组成； D0由后 28位组成 。
– 对 1<=i<=16,计算 Ci=LSi(Ci-1) Di=LSi(Di-1)
LSi表示循环左移 2或 1个位置, 取决于 i的 的值 。
2012-3-19 16
子密钥的生成
i=1,2,9和 16 时移 1个位置，否则移 2位置。
Ki=PC-2(CiDi),PC-2为固定置换 。
一共 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
2012-3-19 17
子密钥的生成
K(64bit)
PC-1
C0 D0
LS1 LS1
C1 D1
LS2 LS2
LS16 LS16
C16 D16
PC-2
PC-2
K1
K16
…
除去第 8,16,?,64位 (8个校验位 )
28bit
2012-3-19 18
DES加密的一个例子
? 取 16进制明文 X,0123456789ABCDEF
密钥 K为,133457799BBCDFF1
去掉奇偶校验位以二进制形式表示的密钥是
0001001001101001010110111100100110110111
1011011111111000
应用 IP，我们得到,
L0=11001100000000001100110011111111
L1=R0=11110000101010101111000010101010
然后进行 16轮加密。
最后对 L16,R16使用 IP-1得到密文：
85E813540F0AB405
DES解密和加密使用同一算法，但子密钥
使用的顺序相反
2012-3-19 19
DES的安全性
? 互补性, DES算法具有下述性质。若明文组 x逐位
取补，密钥 k逐位取补，即 y=DESk(x),则有
?这种互补性会使 DES在选择明文破译下所需
的工作量减半 。
?绝大多数消息并无明文补分组 。
? 弱密钥和半弱密钥,DES算法在每次迭代时都
有一个子密钥供加密用 。 如果给定初始密钥 k,各
轮的子密钥都相同, 即有 k1=k2= … =k16,就称给定
密钥 k为弱密钥 (Weak key)。
)( xD E Sy K?
2012-3-19 20
DES的安全性
若 k为弱密钥，则有,
DESk(DESk(x))=x DESk-1(DESk-1(x))=x
即以 k对 x加密两次或解密两次都可恢复出
明文 。 其加密运算和解密运算没有区别 。
?弱密钥下使 DES在选择明文攻击下的搜索量减
半
? 如果随机地选择密钥, 弱密钥所占比例极小,
而且稍加注意就不难避开 。 因此, 弱密钥的存
在不会危及 DES的安全性 。
2012-3-19 21
DES的安全性
? DES的密钥长度可能太小
? DES的迭代次数可能太少
? S盒中可能有不安全因素
? DES的关键部分不应当保密
2012-3-19 22
三重 DES
1.两重 DES加密的强度一定等
价于 112 bit 密钥的密码的强
度吗？考虑对任意密钥 k1和
k2,能够找出另一密钥 k3，使
Ek2[Ek1[P]] = Ek3[P],这种假设
成立吗？
2.若有明文密文对 (P,C)满足 yi=Ek2[Ek1[P]]，则
可得 z=Ek1[P]=Dk2[C]。考虑这种攻击的情
况。
3.使用三个不同的密钥做三次加密就能抵抗中
途相遇攻击吗？
2012-3-19 23
三重 DES
? 使用两个密钥做三次加密，实现方法为加密
— 解密 — 加密,简记 EDE(encrypt-decrypt-
encrypt)。
E ED
P
A
B
C
K 1
K 2 K 1
加 密
D DE
C
B
A
P
K 1
K 2
K 1
解 密
2012-3-19 24
三重 DES
? 加密,y=Ek1[Dk2[Ek1 [x]]]
? 解密,x=Dk1[Ek2[Dk1[y]]]
? 破译它的穷举密钥搜索量为 2112?5× 1035量级，而用
差分分析破译也要超过 1052量级。此方案仍有足够的
安全性。
? 没有针对三重 DES的攻击方法，它是一种较受欢迎的
DES替代方案 。
? 此方案已在 ANSI X9.17和 ISO 8732标准中采用，并
在保密增强邮递 (PEM)系统中得到利用。
2012-3-19 25
IDEA算法
? IDEA的历史
– 1990年, 瑞士的来学嘉 （ Xuejia Lai） 和
James Massey于 1990年公布了 IDEA密码算
法第一版, 称为 PES (Proposed Encryption
Standard)；
– 1991年, 为抗击差分密码攻击, 他们增强了
算法的强度, 称 IPES（ Improved PES)；
– 1992年, 改名为 IDEA（ International Data
Encryption Algorithm） 。
2012-3-19 26
IDEA加密过程
? IDEA是一个分组长度为
64bit的分组密码算法
，密钥长度为 128bit（
抗强力攻击能力比 DES
强），同一算法既可加
密也可解密。
? IDEA的“混淆”和“扩
散”设计原则来自三种
运算，它们易于软、硬
件实现（加密速度快）
,
Z6
F2 F1
Z5
G1 G2
异
或
运
算
模
2
^
1
6
加
模
(
2
^
1
6
)
+
1
2012-3-19 27
1.在 IDEA的模乘
运算中，为什
么将模数取为
216+1，而不是
216？
1.在其模加运算中，为什么模数取为
216而不是 216+1？
2012-3-19 28
IDEA加密的总体方案图
循环 2
循环 8
循环 1
输出变换
64位密文
64位明文
Z1
Z6
Z7
Z12
Z43
Z48
Z49
Z52
子密钥生成器
128bit密钥
Z1 Z52
16
2012-3-19 29
IDEA加密的单个循环图
X1 X2 X3 X4
Z1
Z2
Z3
Z4
Z5
Z6
W11 W12 W13 W14
2012-3-19 30
IDEA的密钥生成
? 56个 16bit的子密钥从 128bit的密钥中生
成前 8个子密钥直接从密钥中取出；
? 对密钥进行 25bit的循环左移，接下来的
密钥就从中取出；
? 重复进行直到 52个子密钥都产生出来。
2012-3-19 31
IDEA的解密
? 加密解密实质相同，但使用不同的密钥；
? 解密密钥以如下方法从加密子密钥中导出,
– 解密循环 I的头 4个子密钥从加密循环 10－ I的头
4个子密钥中导出；解密密钥第 1,4个子密钥
对应于 1,4加密子密钥的乘法逆元； 2,3对应
2,3的加法逆元；
– 对前 8个循环来说，循环 I的最后两个子密钥等
于加密循环 9－ I的最后两个子密钥；
2012-3-19 32
IDEA简介 (Cont.)
? 实现上的考虑
–使用子分组,16bit的子分组；
–使用简单操作（易于加法、移位等操
作实现） ；
–加密解密过程类似；
–规则的结构（便于 VLSI实现）。
2012-3-19 33
IDEA的安全性
? IDEA能抗差分分析和相关分析；
? IDEA似乎没有 DES意义下的弱密钥；
? IDEA是 PGP的一部分；
? Bruce Schneier 认为 IDEA是 DES的最好
替代，但问题是 IDEA太新，许多问题没
解决。
2012-3-19 34
三,AES算法 -Rijindael
2012-3-19 35
AES的历史
? 1997年 1月, 美国 NIST向全世界密码学界发出征集 21
世纪高级加密标准 （ AES—— Advanced Encryption
Standard） 算法的公告, 并成立了 AES标准工作研究
室, 稍后 制定了对 AES的评估标准 ；
? 1998年 8月, 在首届 AES候选会议上公布了 AES的 15个
候选算法, 任由全世界各机构和个人攻击和评论；
? 2000年 4月, 召开了第三届 AES候选会议, 继续对最后
的五个候选算法进行讨论；
? 2000年 10月, NIST宣布 Rijndael作为新的 AES,至此
,经过三年多的讨论, Rijndael终于脱颖而出 。
2012-3-19 36
AES的评估准则
? AES是公开的；
? AES为单钥体制分组密码；
? AES的密钥长度 128/192/256bit;
? AES适于用软件和硬件实现；
? AES可以自由地使用，或按符合美国国
家标准 （ ANST） 策略的条件使用；
2012-3-19 37
AES的评估准则
? 满足以上要求的 AES算法，需按下述条
件判断优劣
– 安全性
– 代价：各种实现的计算效率（速度和存储
需求），包括软件实现、硬件实现和智能
卡实现等；
– 算法和实现特性：包括算法的灵活性、简
洁性及其它因素。
2012-3-19 38
Rijndael算法设计原理
? Rijndeal密码的设计力求满足以下标准,
– 抵抗所有的已知攻击
– 在多个平台上速度快，编码紧凑
– 设计简单
– Rijndael没有采用 Feistel结构，轮函数由 3
个不同的可逆均匀变换构成的，称为 3个
层
– 均匀变换是指状态的每个 bit都用类似的方
法处理
2012-3-19 39
宽轨迹策略
?, 宽轨迹策略, 是针对抗差分分析和线性分析提出
的；
? 优点：可以给出算法的最佳差分特征的概率即最佳
线性逼近的偏差边界，由此可以分析算法抵抗差分
密码及线性密码分析的能力；
? 实现方法：轮函数 3层中的每层都有它自己的功能,
– 线性混合层：确保多轮之上的高度扩散；
– 非线性层：将具有最优的“最坏情况非线性特性”的
S盒并行使用；
– 密钥加层：单轮子密钥简单的异或到中间状态上，实
现一次性掩盖。
2012-3-19 40
Rijndael算法描述
? Rijndael是 分组和密钥都可变的迭代分组加密算法，
分组和密钥长度可分别为 128,192,256位；
? 加密之前，首先把数据块写成字的形式，其次把字
记为列的形式。算法中间的结果也需要分组，称之
为状态。状态可以用以字节为元素的矩阵阵列表示
，该阵列有 4行，列数 Nb为分组长度除 32；
? 种子密钥类似地以字节为元素的矩阵阵列表示，阵
列为 4行，列数 Nk为密钥长度除 32；
? 算法轮数 Nr由 Nb和 Nk共同决定
2012-3-19 41
Nb=6和 Nk=4的状态密钥阵列
按此顺序放入和读出 按此顺序放入 按此顺序放入和读出 按此顺序放入按此顺序放入和读出 按此顺序放入
2012-3-19 42
分组和阵列中元素对应关系
? 分组下标 n
? 阵列位置 (i,j)
– i=n mod 4,j=[n/4];n=i+4j
? 轮数 Nr与 Nb和 Nk对应关系
Nb=4 Nb=6 Nb=8
Nk=4 10 12 14
Nk=6 12 12 14
Nk=8 14 14 14
2012-3-19 43
Rijndael
加密过程
E
E
E 1
密 文
K 0
K 1
K N r - 1
K N r
明 文 M
第 一 轮
最 后 一 轮
字 节 代 换
行 移 变 换
字 节 代 换
列 变 换
行 移 变 换
2012-3-19 44
字节代换
? 非线性代换，独立地对状态的每个字节
进行，并且代换 表 (S盒 )可逆，记为
ByteSub (State),分两步,
– 将字节作为 GF(28)上的元素映射到自己的
逆元
– 将字节做如下的 GF(2)上变换
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
1
0
0
0
1
1
11111000
01111100
00111110
00011111
10001111
11000111
11100011
11110001
7
6
5
4
3
2
1
0
7
6
5
4
3
2
1
0
x
x
x
x
x
x
x
x
y
y
y
y
y
y
y
y
2012-3-19 45
行移变换
? 将状态阵列的各行进行循环移位，记为
ShiftRow(State)。不同行的移位量不
同,
– 0行：不动
– 1行：循环左移 C1字节
– 2行：循环左移 C2字节
– 3行：循环左移 C3字节
移位量与分组长度的关系
Nb C1 C2 C3
4 1 2 3
6 1 2 3
8 1 3 4
2012-3-19 46
列混合变换
? 列混合变换表示为 MixColumn(State)
? 将每列视为 GF(28)上多项式，与固定的
多项式 c(x)进行模 x4+1乘法,要求 c(x)
模 x4+1可逆。
'02''01''01''03')( 23 ???? xxxxc
2012-3-19 47
密钥加
? 密钥加表示为 AddRoundKey(State)
? 轮密钥与状态进行逐比特异或。
? 轮密钥由种子密钥通过密钥编排算法得
到
? 轮密钥长度与分组密钥长度相同
2012-3-19 48
轮密钥生成
? 从种子密钥到轮密钥由密钥扩展和轮密钥选取两部
分组成。基本原则如下,
– 轮密钥的比特数等于分组长度乘以轮数加 1；
– 种子密钥被扩展成为扩展密钥。其中根据 Nk >6
和 Nk <=6两种不同的情况，采取不同的主密钥
扩展方式；
– 从扩展密钥中选取轮密钥。第 i个轮密钥由轮密
钥缓冲字 W[Nb*i] 到 W[Nb*（ i+1） ]给出。如图
所示
W 0 W 9W 8W 7W 6W 5W 4W 3W 2W 1 W 1 0 W 1 4W 1 3W 1 2W 1 1
轮 密 钥 1轮 密 钥 0
N b = 6 且 N k = 4 时 的 密 钥 扩 展 和 轮 密 钥 选 取
2012-3-19 49
Rijndael的解密
Rijndael解密算法的结构和加密算法
的结构相同，其中的变换为加密算法变换
的逆变换，使用了一个稍有改变的密钥编
制
2012-3-19 50
Rijndael算法的安全性
? 对密钥的选取没有任何限制
– 每轮常数的不同消除了密钥的对称性；
– 密钥扩展的非线性消除了相同密钥的可能性；
– 加解密使用不同的变换，消除了在 DES里出现的
弱密钥和半弱密钥存在的可能性。
? 能有效地抵抗密钥已知的攻击方法的攻击，
目前最有效的攻击还是穷尽密钥搜索攻击
2012-3-19 51
四、分组密码分析方法 *
2012-3-19 52
分组密码分析方法
? 对分组密码的分析方法主要有以下几种
类型,
– 穷尽密钥搜索（强力攻击）；
– 差分密码分析；
– 线性密码分析；
– 相关密钥密码分析；
– 中间相遇攻击。
2012-3-19 53
差分密码分析
? 1991年 Biham和 Shamir公开发表了差分密码分析法
才使对 DES一类分组密码的分析工作向前推进了一
大步 。
? 差分分析是迄今已知的攻击迭代密码最有效的方法
之一, 基本思想是通过分析明文队的差值对密文队
的差值的影响来恢复某些密钥比特 。
? 它对多种分组密码和 Hash 函数都相当有效, 相继
攻破了 FEAL,LOKI,LUCIFER等密码 。
2012-3-19 54
差分密码分析
? 它不是直接分析密文或密钥的统计相关性, 而是分
析明文差分和密文差分之间的统计相关性；
? 给定分组长度为 n的 r轮迭代密码, 两个 n 比特串 Y和
Y*,定义其差分为 ?Y=Y?(Y*)-1 。 其中, ?表示 n-
bits串集上的定义的特定群运算, (Y*)-1为 Y*在群中
的逆元 。
? 由加密对可得差分序列, 其中 和
是明文对, 和 是第 i轮的输出, 他们同
时也是第 i+1轮的输入 。 第 i轮的子密钥记为, 且有
,
01,,,rY Y Y? ? ? 0Y *0Y
* ( 1 )iY i r??iY
1(,)i i iY F Y K??
iK
2012-3-19 55
差分密码分析
? 定义一,r-轮特征 是一个差分序列,
其中 是明文对 和 的差分,是第 i轮输出
和 的差分。
? 定义二,r-轮特征的概率 是在明文 和
子密钥 独立、均匀随机时，明文对 和
的差分为 的条件下，第 轮输出 和 的差
分为 的概率；
? 定义三,在 r-轮特征 中定义,
即 表示在输入差分为 的条件下，轮函数 F的输出
差分为 的概率
? 01,,,r? ? ?
0Y *0Y (1 )i ir? ? ?
01,,,r? ? ? ? ?
01,,,rK K K
0?
iY *iY
0Y
0Y *0Y
0? iY *iY(1 )i i r??
i?
01,,,r? ? ? ? ?
1( ( ) )i i ip P F Y Y? ?? ? ? ? ?
ip? 1i??
i?
2012-3-19 56
差分密码分析
? r-轮迭代密码的差分分析过程可以综述为如下步
骤,
1,找出一个（ r-1）轮特征,使得他
的概率达到最大或几乎最大；
2,均匀随机地选择明文 并计算,使得 和 的差分
为,找出 和 在实际密钥加密下所得的密文 和
，若最后一轮的子密钥 或其部分比特有 2m个可能
值,设置相应的 2m个计数器,用每
个 解密密文 和,得到 和,如果 和
的差分是,则给相应的计数器 加 1；
3,重复步骤 2，直到 1个或几个计数器的值明显高于
其他计数器的值，输出他们所对应的子密钥（或部
分比特）
01( 1 ),,,irr ?? ? ? ? ? ?
0Y *0Y
0? rY
*rY rK
jrK j?
1rY? *1rY?
1r??
0Y *
0Y
0Y *0Y
(1 2 )mj??
jrK
j?
*rYrY 1rY?
*1rY?
2012-3-19 57
差分密码分析的复杂度
? 一种攻击的复杂度可以分为两部分：数据复
杂度和处理复杂度。
– 数据复杂度是实施该攻击所需输入的数据量；
– 处理复杂度是处理这些数据所需的计算量；
? 差分密码分析的数据复杂度是成对加密所需
的选择明文对个数的两倍，处理复杂度是从
找出子密钥或其部分比特的计算量，实际上
和 r无关。而且由于轮函数是弱的，所以此计
算量在大多数情况下相对较小。因此，差分
密码分析的复杂度取决于它的数据复杂度。
2012-3-19 58
线性密码分析
? 线性密码分析是对迭代密码的一种已知明文攻击 。 是
通过寻找一个给定密码算法的有效的线性近似表达式
来破译密码系统；
? 线形密码分析的目标是找出以下形式的有效的线性方
程,
其中, 。
– 是明文分组；
– 是密文分组；
– 是密钥分组；
– 定义
1 2 1 2 1 2[,,,] [,,,] [,,,]a b cP i i i C j j j K k k k??
1,a b n?? 1 cm??
[ 1 ],[ 2 ],,[ ]P P P n
[ 1 ],[ 2 ],,[ ]C C C n
[ 1 ],[ 2 ],,[ ]K K K m
[,,,] [ ] [ ] [ ]A i j k A i A j A k? ? ? ?
2012-3-19 59
线性密码分析
? 如果方程成立的概率,则称该方程是有
效的线性逼近 ;
? 如果 是最大的，则称该方程是最有效的
线性逼近。
? 设 N表示明文数,T是使方程左边为 0的明文数,
– 如果 T>N/2，则令,
– 如果 T<N/2，则令,
12
10,( )
2[,,,]
11,( )
2
c
p
K k k k
p
? ?
?
? ?
??
?
12
10,( )
2[,,,]
11,( )
2
c
p
K k k k
p
? ?
?
? ?
???
1
2
p ?
1
2
p ?
2012-3-19 60
线性密码分析
? 从而可得关于密钥比特的一个线性方程，对不同的
明密文对重复以上过程可得关于密钥的一组线性方
程，从而确定出密钥比特
? 研究表明，当 充分小时，攻击成功的概率是,
这一概率只依赖于,并随着 或 的增
加而增加
1
2p ?
2
2
1
2
2
1
2
x
Np
e d x
?
? ?
???
1
2Np?
N 1
2p ?
2012-3-19 61
当前研究热点
如何对差分密码分析和线性密码
分析进行改进，降低它们的复杂度
仍是现在理论研究的热点。
2012-3-19 62
五、分组码的工作模式
2012-3-19 63
主要工作模式
? 分组密码可以按不同的模式工作，实际
应用的环境不同应采用不同的工作模式
– 电码本 (ECB)模式
– 密码分组链接 (CBC)模式
– 密码反馈 (CFB)模式
– 输出反馈 (OFB)模式
– 计数器 (CTR)模式
2012-3-19 64
电码本（ ECB） 模式
? 最简单的运行模式, 一次对一个 64bit长的
明文分组加密, 且每次加密密钥都相同 。
x
k
y x
k
y
1D E S ?D E S
2012-3-19 65
电码本（ ECB） 模式
? 在用于短数据 （ 如加密密钥 ） 时非常理想,
是安全传递 DES密钥的最合适的模式
? 在给定的密钥下同一明文组总产生同样的密
文组 。 这会暴露明文数据的格式和统计特征
。
? 明文数据都有固定的格式, 需要以协议的形
式定义, 重要的数据常常在同一位置上出现
,使密码分析者可以对其进行统计分析, 重
传和代换攻击
2012-3-19 66
密码分组链接（ CBC） 模式
? 一次对一个明文分组加密，每次加密使用同一密钥
，加密算法的输入是当前明文分组和前一次密文分
组的异或（在产生第 1个密文分组时，需要有一个初
始向量 IV与第一个明文分组异或）；
D E S
?
D E S
?第 1 次 P 1
I V
K
C 1
第 2 次 P 2
C 2
D E S
?第 N 次 P N
C N
K
K
C N - 1
2012-3-19 67
密码分组链接（ CBC）模式
? 解密时，每一个密文分组被解密后，再与前一个密
文分组异或（第一个密文分组解密后和初始向量 IV
异或恢复出第一个明文分组）。
D E S? ? ?
D E S D E S
K K K
C 1 C 2 C N
I V
P 1
P 2
P N
C N - 1
2012-3-19 68
密码分组链接（ CBC）模式
? 为使安全性最高,IV应像密钥一样被保护。可使用 ECB
加密模式来发送 IV；
? 保护 IV原因是：如果敌手能欺骗接受方使用不同的 IV，
敌手就能够在明文的第一个分组中插入自己选择的比特
值；
? IV的完整性要比其保密性更为重要。在 CBC模式下，最
好是每发一个消息，都改变 IV,比如将其值加一；
? 由于 CBC模式的链接机制，该模式对于加密长于 64bit的
消息非常合适；
? CBC模式除能获得保密性外，还能用于认证。
2012-3-19 69
密码反馈 （ CFB） 模式
? 加密算法的输入是 64bit移位寄存器，其初始值为某个初
始向量 IV，加密算法输出的最左（最高有效位） j bit与
明文的第一个单元进行异或，产生第一个密文单元 并
传送该单元。然后将移位寄存器的内容左移 j位并将 送
入移位寄存器最右边（最低有效位） j位。这一过程持续
到明文的所有单元都被加密为止
1C
1C
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 1
j
j
j
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 2
j
j
j
C 1
C 2
I V 移 位 寄 存 器
两 轮 C F B 模 式 加 密 示 意 图
2012-3-19 70
密码反馈 （ CFB） 模式
? 解密时，
将收到的
密文单元
与加密函
数的输出
进行异或
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 1
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 2
C 1
C 2
I V 移 位 寄 存 器
两 轮 C F B 模 式 解 密 示 意 图
? 为什么此时仍然使用加密算法而不
是解密算法？
2012-3-19 71
密码反馈 （ CFB） 模式
? 利用 CFB模式或者 OFB模式可将 DES转换为
流密码；
? 流密码不需要对消息进行填充，而且运
行是实时的，因此如果传送字母流，可
使用流密码对每个字母直接加密进行传
送；
? CFB模式除了获得保密性外，还能用于认
证。
2012-3-19 72
输出反馈 (OFB)模式
? OFB模式的结构类似于 CFB,不同之处在于,OFB
模式将加密算法的输出反馈到移位寄存器, 而 CFB
模式中是将密文单元反馈到移位寄存器
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
K
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
K
P 2
C 1
C 2
I V 移 位 寄 存 器
两 轮 O F B 模 式 加 密 示 意 图
2012-3-19 73
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
K
P 1
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 2
C 1
C 2
I V 移 位 寄 存 器
两 轮 O F B 模 式 解 密 示 意 图
2012-3-19 74
输出反馈 (OFB)模式
? 克服了 CFB的错误传播所带来的问题 。
? 比 CFB模式更易受到对消息流的篡改攻击,
使得敌手有可能通过对消息校验部分的篡改
和对数据部分的篡改, 而以纠错码不能检测
的方式篡改密文 。
2012-3-19 75
计数器 (CRT)模式
? CTR可以把分组密码转换为流密码
? 和 OFB类似，但是加密计数器值，而不是密
文反馈值
? 必须对每一个明文使用一个不同的密钥和计
数值
iiCP? xor iO
1 ()iKO D E S i?
2012-3-19 76
?加 密K C o u n t e r
C 1
P 1
?加 密K?加 密K C o u n t e r + 1 C o u n t e r + N - 1
P 2
P N
C 2
C N
C T R 模 式 加 密 示 意 图
?解 密K C o u n t e r 1
C 1
P 1
?解 密K?解 密K C o u n t e r 2 C o u n t e r N
P 2
P N
C 2
C N
C T R 模 式 解 密 示 意 图
2012-3-19 77
计数器 (CRT)模式
? 该模式优点是安全、高效、可并行、适合
任意长度的数据,的计算可以预处理，
适用于高速网络。加解密过程仅涉及加密
运算，不涉及解密算法，因此不用实现解
密算法。
? 缺点是没有错误传播，因此不易确保数据
完整性。信息快可被替换，重放，对明文
的主动攻击时可能的。
iO
2012-3-19 78
比较和选用
? ECB模式, 简单, 高速, 但最弱, 易受重发攻击
,一般不推荐 。
? CBC适用于文件加密, 但较 ECB慢 。 安全性加强
。 当有少量错误时, 也不会造成同步错误 。
? OFB和 CFB较 CBC慢许多 。 每次迭代只有少数 bit
完成加密 。 若可以容忍少量错误扩展, 则可换来
恢复同步能力, 此时用 CFB。 在字符为单元的流
密码中多选 CFB模式 。
? OFB用于高速同步系统, 不容忍差错传播 。
2012-3-19 79
习题
1,证明可以通过颠倒密钥方案用 DES加密算法加密密
文实现 DES解密。
2,在 DES数据加密标准中,
明文 m=0011 1000 1101 0101 1011 1000 0100
0010 1101 0101 0011 1001 1001 0101 1110
0111
密钥 K=1010 1011 0011 0100 1000 0110 1001
0100 1101 1001 0111 0011 1010 0010 1101
0011
试求 L1和 R1。
3,假设我们有 128bit的 AES密钥，用 16进制表示为,
2012-3-19 80
2B7E151628AED2A6ABF7158809CF4F3C
由该种子密钥构造一个完整的密钥编排方案。
4,使用上题中的 128bit密钥，在 10轮 AES下计算下列
明文（以 16进制表示）的加密结果：
3243F6A8885A308D313198A2E0370734。
5,在 IDEA的模乘运算中，为什么将模数取为 216+1而
不是 216？在其模加运算中，为什么模数取为 216而
不是 216+1？
6,已知 IDEA密码算法中,
明文 m=01011100 10001101 10101001 11011110
10101101 00110101 00010011 10010011;
2012-3-19 81
密钥 K=00101001 10100011 11011000 11100111 10100101
01010011 10100010 01011001 00100100 01011001
11001010 11100111 10100010 00101010 11010101
00110101，求第一轮的输出和第二轮的输出。
7,在 DES的 ECB模式中，如果在密文分组中有一个错误，解密后
仅相应的明文分组受到影响，然而在 CBC模式中，将有错误
传播（见 PPT相应的图中 C1的一个错误明显地影响 P1和 P2的结
果）。
（ 1） P2后的结果是否受到影响？
（ 2）设加密前的明文分组 P1中有 1bit的错误，问这一错误将
在多少个密文分组中传播？对接收者有什么影响？
2012-3-19 82
谢谢大家！
欢迎指正！
第三章 分组密码
一、分组密码的一般模型
二,DES与 IDEA
三,AES 算法 —— Rijndael
四、分组密码分析方法 *
五、分组密码工作模式
2012-3-19 2
一,分组密码的一般模型
2012-3-19 3
分组密码概述
? 分组密码,
将消息编码表示后的数字（通常是 0和 1）序列 x1,
x2,…,xi,… 划分为长为 n的组,各
组（长为 n的矢量）分别在密钥 的
控制下变换成等长的输出数字序列
（长为 m的矢量）。
? ?0 1 1,,,nx x x x ??
? ?0 1 1,,,tk k k k ??
? ?0 1 1,,,my y y y ??
加 密 算 法 解 密 算 法
明 文
? ?0 1 1,,,nx x x x ??
密 文
密 钥 密 钥
明 文
? ?0 1 1,,,tk k k k ??
? ?0 1 1,,,my y y y ?? ? ?0 1 1,,,nx x x x ??
? ?0 1 1,,,tk k k k ??
分 组 密 码 框 图
2012-3-19 4
? 分组密码是一种满足下列条件的映射 E,
? 对每个, 是从 到 的置换
?,密钥为 时的加密函数
?,密钥为 时的解密函数
? 密钥规模,bit
? 密钥长度等于密钥规模当且仅当,
Eg:DES真正的密钥规模 =56bit,且 也就是密钥长度
22mmkF S F??
? ?,Ek? 2mF 2mF
? ?,Ek?
kkS?
k
? ?,Dk? k
2l o g klS?
2tkSF?
ll
2012-3-19 5
分组密码设计问题
分组密码的设计问题在于找到一
种算法, 能在密钥控制下从一个足
够大且足够好的置换子集中, 简单
而迅速地选出一个置换, 用来对当
前输入的明文的数字组进行加密变
换 。
2012-3-19 6
分组密码算法应满足的要求
? 分组长度 n要足够大,
防止明文穷举攻击法奏效 。
? 密钥量要足够大,
尽可能消除弱密钥并使所有密钥同等地好, 以防止密钥穷
举攻击奏效 。
? 由密钥确定置换的算法要足够复杂,
充分实现明文与密钥的扩散和混淆，没有简单的关系可循
,要能抗击各种已知的攻击
2012-3-19 7
分组密码算法应满足的要求
? 加密和解密运算简单,
易于软件和硬件高速实现 。
? 数据扩展,
一般无数据扩展, 在采用同态置换和随机化加密技术时
可引入数据扩展 。
? 差错传播尽可能地小
2012-3-19 8
二,DES与 IDEA
2012-3-19 9
数据加密标准 （ DES）
? DES的历史
– 1971年 IBM,由 Horst Feistel领导的密码研究项目
组研究出 LUCIFER算法, 并应用于商业领域 ;
– 1973年,美国标准局征求标准, IBM提交结果 ;
– 1977年, 被选为数据加密标准 ;
– 虽然 DES已有替代的数据加密标准算法, 但它仍
是迄今为止得到最广泛应用的一种算法, 也是一
种最有代表性的分组加密体制 。
2012-3-19 10
DES加密过程
? DES利用 56bit长度的密
钥 K来加密长度为 64bit
的明文，得到长度为
64bit的密文
? 该算法分 三个阶段 实现
? IP和 IP-1在密码意义上
作用不大，它们的作用
在于打乱原来输入 x的
ASCII码字划分的关系
，并将原来明文的校验
位 x8,x16,?,x64变成为 IP
输出的一个字节。
逆初始置换
乘积变换
（ ） 16轮迭代
6 4 b i t 密文数据
6 4 b i t 明文数据
初始置换
输入
输出
将 6 4 b i t 明 文 位 置 进 行 置
换 得 到 一 个 乱 序 的 6 4
b i t 明 文 组 而 后 平 分 成
左 右 两 段 I P 中 各 列 元 素 位 号 数
相 差 为 8 相 当 于 将 原 明 文 各 字
节 按 列 写 出 各 列 比 特 经 过
奇 偶 采 样 置 换 后 再 对 各
行 进 行 逆 序 将 阵 中 元
素 按 行 读 出 构 成
置 换 输 出
将 1 6 轮 迭 代 后 给 出 的 6 4
b i t 组 进 行 置 换 得 到 输 出
的 密 文 组 输 出 为 阵 中
的 元 素 按 行 读 得
的 结 果
2012-3-19 11
一轮加密的简图
?
Li-1 Ri-1
F
+
Li Ri
Ki
A=R(32 bits) J=K(48 bits)
E
E(A)为 48 bits +
B1 B2 B3 B4 B5 B6 B7 B8
S1 S2 S3 S4 S5 S6 S7 S8
C1 C2 C3 C4 C5 C6 C7 C8
P
32 bits F(A,J)
B 写成 8个 6比特串
2012-3-19 12
? 对 F函数的说明,F（ Ri-1,Ki） 函数 F以 长
度为 32的比特串 A=R（ 32bits） 作第一个
输入，以长度为 48的比特串变元
J=K(48bits)作为第二个输入。产生的输
出为长度为 32的位串。
– 对第一个变元 A,由给定的扩展函数 E,将其
扩展成 48位串 E（ A） ；
– 计算 E(A)+J,并把结果写成连续的 8个 6位串,
B=b1b2b3b4b5b6b7b8
2012-3-19 13
– 使用 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)。
– 最后, P为一个固定置换 。
2012-3-19 14
选择压缩运算 S
4 8 b i t 寄存器
S1
3 2 b i t 寄存器
S3S2 S5 S6 S7 S8S4
6bit
4bit
2012-3-19 15
子密钥的生成
? 从密钥 K计算子密钥,实际上,K是长
度为 64的位串，其中 56位是密钥,8位是奇偶
校验位（为了检错），在密钥编排的计算中
，这些校验位可略去。
– 给定 64位的密钥 K,放弃奇偶校验位 （ 8,16，
…, 64） 并根据固定置换 PC-1来排列 K中剩下的
位 。 PC-1(K)=C0D0 。 其中 C0由 PC-1（ K） 的前 28
位组成； D0由后 28位组成 。
– 对 1<=i<=16,计算 Ci=LSi(Ci-1) Di=LSi(Di-1)
LSi表示循环左移 2或 1个位置, 取决于 i的 的值 。
2012-3-19 16
子密钥的生成
i=1,2,9和 16 时移 1个位置，否则移 2位置。
Ki=PC-2(CiDi),PC-2为固定置换 。
一共 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
2012-3-19 17
子密钥的生成
K(64bit)
PC-1
C0 D0
LS1 LS1
C1 D1
LS2 LS2
LS16 LS16
C16 D16
PC-2
PC-2
K1
K16
…
除去第 8,16,?,64位 (8个校验位 )
28bit
2012-3-19 18
DES加密的一个例子
? 取 16进制明文 X,0123456789ABCDEF
密钥 K为,133457799BBCDFF1
去掉奇偶校验位以二进制形式表示的密钥是
0001001001101001010110111100100110110111
1011011111111000
应用 IP，我们得到,
L0=11001100000000001100110011111111
L1=R0=11110000101010101111000010101010
然后进行 16轮加密。
最后对 L16,R16使用 IP-1得到密文：
85E813540F0AB405
DES解密和加密使用同一算法，但子密钥
使用的顺序相反
2012-3-19 19
DES的安全性
? 互补性, DES算法具有下述性质。若明文组 x逐位
取补，密钥 k逐位取补，即 y=DESk(x),则有
?这种互补性会使 DES在选择明文破译下所需
的工作量减半 。
?绝大多数消息并无明文补分组 。
? 弱密钥和半弱密钥,DES算法在每次迭代时都
有一个子密钥供加密用 。 如果给定初始密钥 k,各
轮的子密钥都相同, 即有 k1=k2= … =k16,就称给定
密钥 k为弱密钥 (Weak key)。
)( xD E Sy K?
2012-3-19 20
DES的安全性
若 k为弱密钥，则有,
DESk(DESk(x))=x DESk-1(DESk-1(x))=x
即以 k对 x加密两次或解密两次都可恢复出
明文 。 其加密运算和解密运算没有区别 。
?弱密钥下使 DES在选择明文攻击下的搜索量减
半
? 如果随机地选择密钥, 弱密钥所占比例极小,
而且稍加注意就不难避开 。 因此, 弱密钥的存
在不会危及 DES的安全性 。
2012-3-19 21
DES的安全性
? DES的密钥长度可能太小
? DES的迭代次数可能太少
? S盒中可能有不安全因素
? DES的关键部分不应当保密
2012-3-19 22
三重 DES
1.两重 DES加密的强度一定等
价于 112 bit 密钥的密码的强
度吗？考虑对任意密钥 k1和
k2,能够找出另一密钥 k3，使
Ek2[Ek1[P]] = Ek3[P],这种假设
成立吗？
2.若有明文密文对 (P,C)满足 yi=Ek2[Ek1[P]]，则
可得 z=Ek1[P]=Dk2[C]。考虑这种攻击的情
况。
3.使用三个不同的密钥做三次加密就能抵抗中
途相遇攻击吗？
2012-3-19 23
三重 DES
? 使用两个密钥做三次加密，实现方法为加密
— 解密 — 加密,简记 EDE(encrypt-decrypt-
encrypt)。
E ED
P
A
B
C
K 1
K 2 K 1
加 密
D DE
C
B
A
P
K 1
K 2
K 1
解 密
2012-3-19 24
三重 DES
? 加密,y=Ek1[Dk2[Ek1 [x]]]
? 解密,x=Dk1[Ek2[Dk1[y]]]
? 破译它的穷举密钥搜索量为 2112?5× 1035量级，而用
差分分析破译也要超过 1052量级。此方案仍有足够的
安全性。
? 没有针对三重 DES的攻击方法，它是一种较受欢迎的
DES替代方案 。
? 此方案已在 ANSI X9.17和 ISO 8732标准中采用，并
在保密增强邮递 (PEM)系统中得到利用。
2012-3-19 25
IDEA算法
? IDEA的历史
– 1990年, 瑞士的来学嘉 （ Xuejia Lai） 和
James Massey于 1990年公布了 IDEA密码算
法第一版, 称为 PES (Proposed Encryption
Standard)；
– 1991年, 为抗击差分密码攻击, 他们增强了
算法的强度, 称 IPES（ Improved PES)；
– 1992年, 改名为 IDEA（ International Data
Encryption Algorithm） 。
2012-3-19 26
IDEA加密过程
? IDEA是一个分组长度为
64bit的分组密码算法
，密钥长度为 128bit（
抗强力攻击能力比 DES
强），同一算法既可加
密也可解密。
? IDEA的“混淆”和“扩
散”设计原则来自三种
运算，它们易于软、硬
件实现（加密速度快）
,
Z6
F2 F1
Z5
G1 G2
异
或
运
算
模
2
^
1
6
加
模
(
2
^
1
6
)
+
1
2012-3-19 27
1.在 IDEA的模乘
运算中，为什
么将模数取为
216+1，而不是
216？
1.在其模加运算中，为什么模数取为
216而不是 216+1？
2012-3-19 28
IDEA加密的总体方案图
循环 2
循环 8
循环 1
输出变换
64位密文
64位明文
Z1
Z6
Z7
Z12
Z43
Z48
Z49
Z52
子密钥生成器
128bit密钥
Z1 Z52
16
2012-3-19 29
IDEA加密的单个循环图
X1 X2 X3 X4
Z1
Z2
Z3
Z4
Z5
Z6
W11 W12 W13 W14
2012-3-19 30
IDEA的密钥生成
? 56个 16bit的子密钥从 128bit的密钥中生
成前 8个子密钥直接从密钥中取出；
? 对密钥进行 25bit的循环左移，接下来的
密钥就从中取出；
? 重复进行直到 52个子密钥都产生出来。
2012-3-19 31
IDEA的解密
? 加密解密实质相同，但使用不同的密钥；
? 解密密钥以如下方法从加密子密钥中导出,
– 解密循环 I的头 4个子密钥从加密循环 10－ I的头
4个子密钥中导出；解密密钥第 1,4个子密钥
对应于 1,4加密子密钥的乘法逆元； 2,3对应
2,3的加法逆元；
– 对前 8个循环来说，循环 I的最后两个子密钥等
于加密循环 9－ I的最后两个子密钥；
2012-3-19 32
IDEA简介 (Cont.)
? 实现上的考虑
–使用子分组,16bit的子分组；
–使用简单操作（易于加法、移位等操
作实现） ；
–加密解密过程类似；
–规则的结构（便于 VLSI实现）。
2012-3-19 33
IDEA的安全性
? IDEA能抗差分分析和相关分析；
? IDEA似乎没有 DES意义下的弱密钥；
? IDEA是 PGP的一部分；
? Bruce Schneier 认为 IDEA是 DES的最好
替代，但问题是 IDEA太新，许多问题没
解决。
2012-3-19 34
三,AES算法 -Rijindael
2012-3-19 35
AES的历史
? 1997年 1月, 美国 NIST向全世界密码学界发出征集 21
世纪高级加密标准 （ AES—— Advanced Encryption
Standard） 算法的公告, 并成立了 AES标准工作研究
室, 稍后 制定了对 AES的评估标准 ；
? 1998年 8月, 在首届 AES候选会议上公布了 AES的 15个
候选算法, 任由全世界各机构和个人攻击和评论；
? 2000年 4月, 召开了第三届 AES候选会议, 继续对最后
的五个候选算法进行讨论；
? 2000年 10月, NIST宣布 Rijndael作为新的 AES,至此
,经过三年多的讨论, Rijndael终于脱颖而出 。
2012-3-19 36
AES的评估准则
? AES是公开的；
? AES为单钥体制分组密码；
? AES的密钥长度 128/192/256bit;
? AES适于用软件和硬件实现；
? AES可以自由地使用，或按符合美国国
家标准 （ ANST） 策略的条件使用；
2012-3-19 37
AES的评估准则
? 满足以上要求的 AES算法，需按下述条
件判断优劣
– 安全性
– 代价：各种实现的计算效率（速度和存储
需求），包括软件实现、硬件实现和智能
卡实现等；
– 算法和实现特性：包括算法的灵活性、简
洁性及其它因素。
2012-3-19 38
Rijndael算法设计原理
? Rijndeal密码的设计力求满足以下标准,
– 抵抗所有的已知攻击
– 在多个平台上速度快，编码紧凑
– 设计简单
– Rijndael没有采用 Feistel结构，轮函数由 3
个不同的可逆均匀变换构成的，称为 3个
层
– 均匀变换是指状态的每个 bit都用类似的方
法处理
2012-3-19 39
宽轨迹策略
?, 宽轨迹策略, 是针对抗差分分析和线性分析提出
的；
? 优点：可以给出算法的最佳差分特征的概率即最佳
线性逼近的偏差边界，由此可以分析算法抵抗差分
密码及线性密码分析的能力；
? 实现方法：轮函数 3层中的每层都有它自己的功能,
– 线性混合层：确保多轮之上的高度扩散；
– 非线性层：将具有最优的“最坏情况非线性特性”的
S盒并行使用；
– 密钥加层：单轮子密钥简单的异或到中间状态上，实
现一次性掩盖。
2012-3-19 40
Rijndael算法描述
? Rijndael是 分组和密钥都可变的迭代分组加密算法，
分组和密钥长度可分别为 128,192,256位；
? 加密之前，首先把数据块写成字的形式，其次把字
记为列的形式。算法中间的结果也需要分组，称之
为状态。状态可以用以字节为元素的矩阵阵列表示
，该阵列有 4行，列数 Nb为分组长度除 32；
? 种子密钥类似地以字节为元素的矩阵阵列表示，阵
列为 4行，列数 Nk为密钥长度除 32；
? 算法轮数 Nr由 Nb和 Nk共同决定
2012-3-19 41
Nb=6和 Nk=4的状态密钥阵列
按此顺序放入和读出 按此顺序放入 按此顺序放入和读出 按此顺序放入按此顺序放入和读出 按此顺序放入
2012-3-19 42
分组和阵列中元素对应关系
? 分组下标 n
? 阵列位置 (i,j)
– i=n mod 4,j=[n/4];n=i+4j
? 轮数 Nr与 Nb和 Nk对应关系
Nb=4 Nb=6 Nb=8
Nk=4 10 12 14
Nk=6 12 12 14
Nk=8 14 14 14
2012-3-19 43
Rijndael
加密过程
E
E
E 1
密 文
K 0
K 1
K N r - 1
K N r
明 文 M
第 一 轮
最 后 一 轮
字 节 代 换
行 移 变 换
字 节 代 换
列 变 换
行 移 变 换
2012-3-19 44
字节代换
? 非线性代换，独立地对状态的每个字节
进行，并且代换 表 (S盒 )可逆，记为
ByteSub (State),分两步,
– 将字节作为 GF(28)上的元素映射到自己的
逆元
– 将字节做如下的 GF(2)上变换
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
1
0
0
0
1
1
11111000
01111100
00111110
00011111
10001111
11000111
11100011
11110001
7
6
5
4
3
2
1
0
7
6
5
4
3
2
1
0
x
x
x
x
x
x
x
x
y
y
y
y
y
y
y
y
2012-3-19 45
行移变换
? 将状态阵列的各行进行循环移位，记为
ShiftRow(State)。不同行的移位量不
同,
– 0行：不动
– 1行：循环左移 C1字节
– 2行：循环左移 C2字节
– 3行：循环左移 C3字节
移位量与分组长度的关系
Nb C1 C2 C3
4 1 2 3
6 1 2 3
8 1 3 4
2012-3-19 46
列混合变换
? 列混合变换表示为 MixColumn(State)
? 将每列视为 GF(28)上多项式，与固定的
多项式 c(x)进行模 x4+1乘法,要求 c(x)
模 x4+1可逆。
'02''01''01''03')( 23 ???? xxxxc
2012-3-19 47
密钥加
? 密钥加表示为 AddRoundKey(State)
? 轮密钥与状态进行逐比特异或。
? 轮密钥由种子密钥通过密钥编排算法得
到
? 轮密钥长度与分组密钥长度相同
2012-3-19 48
轮密钥生成
? 从种子密钥到轮密钥由密钥扩展和轮密钥选取两部
分组成。基本原则如下,
– 轮密钥的比特数等于分组长度乘以轮数加 1；
– 种子密钥被扩展成为扩展密钥。其中根据 Nk >6
和 Nk <=6两种不同的情况，采取不同的主密钥
扩展方式；
– 从扩展密钥中选取轮密钥。第 i个轮密钥由轮密
钥缓冲字 W[Nb*i] 到 W[Nb*（ i+1） ]给出。如图
所示
W 0 W 9W 8W 7W 6W 5W 4W 3W 2W 1 W 1 0 W 1 4W 1 3W 1 2W 1 1
轮 密 钥 1轮 密 钥 0
N b = 6 且 N k = 4 时 的 密 钥 扩 展 和 轮 密 钥 选 取
2012-3-19 49
Rijndael的解密
Rijndael解密算法的结构和加密算法
的结构相同，其中的变换为加密算法变换
的逆变换，使用了一个稍有改变的密钥编
制
2012-3-19 50
Rijndael算法的安全性
? 对密钥的选取没有任何限制
– 每轮常数的不同消除了密钥的对称性；
– 密钥扩展的非线性消除了相同密钥的可能性；
– 加解密使用不同的变换，消除了在 DES里出现的
弱密钥和半弱密钥存在的可能性。
? 能有效地抵抗密钥已知的攻击方法的攻击，
目前最有效的攻击还是穷尽密钥搜索攻击
2012-3-19 51
四、分组密码分析方法 *
2012-3-19 52
分组密码分析方法
? 对分组密码的分析方法主要有以下几种
类型,
– 穷尽密钥搜索（强力攻击）；
– 差分密码分析；
– 线性密码分析；
– 相关密钥密码分析；
– 中间相遇攻击。
2012-3-19 53
差分密码分析
? 1991年 Biham和 Shamir公开发表了差分密码分析法
才使对 DES一类分组密码的分析工作向前推进了一
大步 。
? 差分分析是迄今已知的攻击迭代密码最有效的方法
之一, 基本思想是通过分析明文队的差值对密文队
的差值的影响来恢复某些密钥比特 。
? 它对多种分组密码和 Hash 函数都相当有效, 相继
攻破了 FEAL,LOKI,LUCIFER等密码 。
2012-3-19 54
差分密码分析
? 它不是直接分析密文或密钥的统计相关性, 而是分
析明文差分和密文差分之间的统计相关性；
? 给定分组长度为 n的 r轮迭代密码, 两个 n 比特串 Y和
Y*,定义其差分为 ?Y=Y?(Y*)-1 。 其中, ?表示 n-
bits串集上的定义的特定群运算, (Y*)-1为 Y*在群中
的逆元 。
? 由加密对可得差分序列, 其中 和
是明文对, 和 是第 i轮的输出, 他们同
时也是第 i+1轮的输入 。 第 i轮的子密钥记为, 且有
,
01,,,rY Y Y? ? ? 0Y *0Y
* ( 1 )iY i r??iY
1(,)i i iY F Y K??
iK
2012-3-19 55
差分密码分析
? 定义一,r-轮特征 是一个差分序列,
其中 是明文对 和 的差分,是第 i轮输出
和 的差分。
? 定义二,r-轮特征的概率 是在明文 和
子密钥 独立、均匀随机时，明文对 和
的差分为 的条件下，第 轮输出 和 的差
分为 的概率；
? 定义三,在 r-轮特征 中定义,
即 表示在输入差分为 的条件下，轮函数 F的输出
差分为 的概率
? 01,,,r? ? ?
0Y *0Y (1 )i ir? ? ?
01,,,r? ? ? ? ?
01,,,rK K K
0?
iY *iY
0Y
0Y *0Y
0? iY *iY(1 )i i r??
i?
01,,,r? ? ? ? ?
1( ( ) )i i ip P F Y Y? ?? ? ? ? ?
ip? 1i??
i?
2012-3-19 56
差分密码分析
? r-轮迭代密码的差分分析过程可以综述为如下步
骤,
1,找出一个（ r-1）轮特征,使得他
的概率达到最大或几乎最大；
2,均匀随机地选择明文 并计算,使得 和 的差分
为,找出 和 在实际密钥加密下所得的密文 和
，若最后一轮的子密钥 或其部分比特有 2m个可能
值,设置相应的 2m个计数器,用每
个 解密密文 和,得到 和,如果 和
的差分是,则给相应的计数器 加 1；
3,重复步骤 2，直到 1个或几个计数器的值明显高于
其他计数器的值，输出他们所对应的子密钥（或部
分比特）
01( 1 ),,,irr ?? ? ? ? ? ?
0Y *0Y
0? rY
*rY rK
jrK j?
1rY? *1rY?
1r??
0Y *
0Y
0Y *0Y
(1 2 )mj??
jrK
j?
*rYrY 1rY?
*1rY?
2012-3-19 57
差分密码分析的复杂度
? 一种攻击的复杂度可以分为两部分：数据复
杂度和处理复杂度。
– 数据复杂度是实施该攻击所需输入的数据量；
– 处理复杂度是处理这些数据所需的计算量；
? 差分密码分析的数据复杂度是成对加密所需
的选择明文对个数的两倍，处理复杂度是从
找出子密钥或其部分比特的计算量，实际上
和 r无关。而且由于轮函数是弱的，所以此计
算量在大多数情况下相对较小。因此，差分
密码分析的复杂度取决于它的数据复杂度。
2012-3-19 58
线性密码分析
? 线性密码分析是对迭代密码的一种已知明文攻击 。 是
通过寻找一个给定密码算法的有效的线性近似表达式
来破译密码系统；
? 线形密码分析的目标是找出以下形式的有效的线性方
程,
其中, 。
– 是明文分组；
– 是密文分组；
– 是密钥分组；
– 定义
1 2 1 2 1 2[,,,] [,,,] [,,,]a b cP i i i C j j j K k k k??
1,a b n?? 1 cm??
[ 1 ],[ 2 ],,[ ]P P P n
[ 1 ],[ 2 ],,[ ]C C C n
[ 1 ],[ 2 ],,[ ]K K K m
[,,,] [ ] [ ] [ ]A i j k A i A j A k? ? ? ?
2012-3-19 59
线性密码分析
? 如果方程成立的概率,则称该方程是有
效的线性逼近 ;
? 如果 是最大的，则称该方程是最有效的
线性逼近。
? 设 N表示明文数,T是使方程左边为 0的明文数,
– 如果 T>N/2，则令,
– 如果 T<N/2，则令,
12
10,( )
2[,,,]
11,( )
2
c
p
K k k k
p
? ?
?
? ?
??
?
12
10,( )
2[,,,]
11,( )
2
c
p
K k k k
p
? ?
?
? ?
???
1
2
p ?
1
2
p ?
2012-3-19 60
线性密码分析
? 从而可得关于密钥比特的一个线性方程，对不同的
明密文对重复以上过程可得关于密钥的一组线性方
程，从而确定出密钥比特
? 研究表明，当 充分小时，攻击成功的概率是,
这一概率只依赖于,并随着 或 的增
加而增加
1
2p ?
2
2
1
2
2
1
2
x
Np
e d x
?
? ?
???
1
2Np?
N 1
2p ?
2012-3-19 61
当前研究热点
如何对差分密码分析和线性密码
分析进行改进，降低它们的复杂度
仍是现在理论研究的热点。
2012-3-19 62
五、分组码的工作模式
2012-3-19 63
主要工作模式
? 分组密码可以按不同的模式工作，实际
应用的环境不同应采用不同的工作模式
– 电码本 (ECB)模式
– 密码分组链接 (CBC)模式
– 密码反馈 (CFB)模式
– 输出反馈 (OFB)模式
– 计数器 (CTR)模式
2012-3-19 64
电码本（ ECB） 模式
? 最简单的运行模式, 一次对一个 64bit长的
明文分组加密, 且每次加密密钥都相同 。
x
k
y x
k
y
1D E S ?D E S
2012-3-19 65
电码本（ ECB） 模式
? 在用于短数据 （ 如加密密钥 ） 时非常理想,
是安全传递 DES密钥的最合适的模式
? 在给定的密钥下同一明文组总产生同样的密
文组 。 这会暴露明文数据的格式和统计特征
。
? 明文数据都有固定的格式, 需要以协议的形
式定义, 重要的数据常常在同一位置上出现
,使密码分析者可以对其进行统计分析, 重
传和代换攻击
2012-3-19 66
密码分组链接（ CBC） 模式
? 一次对一个明文分组加密，每次加密使用同一密钥
，加密算法的输入是当前明文分组和前一次密文分
组的异或（在产生第 1个密文分组时，需要有一个初
始向量 IV与第一个明文分组异或）；
D E S
?
D E S
?第 1 次 P 1
I V
K
C 1
第 2 次 P 2
C 2
D E S
?第 N 次 P N
C N
K
K
C N - 1
2012-3-19 67
密码分组链接（ CBC）模式
? 解密时，每一个密文分组被解密后，再与前一个密
文分组异或（第一个密文分组解密后和初始向量 IV
异或恢复出第一个明文分组）。
D E S? ? ?
D E S D E S
K K K
C 1 C 2 C N
I V
P 1
P 2
P N
C N - 1
2012-3-19 68
密码分组链接（ CBC）模式
? 为使安全性最高,IV应像密钥一样被保护。可使用 ECB
加密模式来发送 IV；
? 保护 IV原因是：如果敌手能欺骗接受方使用不同的 IV，
敌手就能够在明文的第一个分组中插入自己选择的比特
值；
? IV的完整性要比其保密性更为重要。在 CBC模式下，最
好是每发一个消息，都改变 IV,比如将其值加一；
? 由于 CBC模式的链接机制，该模式对于加密长于 64bit的
消息非常合适；
? CBC模式除能获得保密性外，还能用于认证。
2012-3-19 69
密码反馈 （ CFB） 模式
? 加密算法的输入是 64bit移位寄存器，其初始值为某个初
始向量 IV，加密算法输出的最左（最高有效位） j bit与
明文的第一个单元进行异或，产生第一个密文单元 并
传送该单元。然后将移位寄存器的内容左移 j位并将 送
入移位寄存器最右边（最低有效位） j位。这一过程持续
到明文的所有单元都被加密为止
1C
1C
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 1
j
j
j
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 2
j
j
j
C 1
C 2
I V 移 位 寄 存 器
两 轮 C F B 模 式 加 密 示 意 图
2012-3-19 70
密码反馈 （ CFB） 模式
? 解密时，
将收到的
密文单元
与加密函
数的输出
进行异或
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 1
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 2
C 1
C 2
I V 移 位 寄 存 器
两 轮 C F B 模 式 解 密 示 意 图
? 为什么此时仍然使用加密算法而不
是解密算法？
2012-3-19 71
密码反馈 （ CFB） 模式
? 利用 CFB模式或者 OFB模式可将 DES转换为
流密码；
? 流密码不需要对消息进行填充，而且运
行是实时的，因此如果传送字母流，可
使用流密码对每个字母直接加密进行传
送；
? CFB模式除了获得保密性外，还能用于认
证。
2012-3-19 72
输出反馈 (OFB)模式
? OFB模式的结构类似于 CFB,不同之处在于,OFB
模式将加密算法的输出反馈到移位寄存器, 而 CFB
模式中是将密文单元反馈到移位寄存器
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
K
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
K
P 2
C 1
C 2
I V 移 位 寄 存 器
两 轮 O F B 模 式 加 密 示 意 图
2012-3-19 73
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
K
P 1
6 4 - j b i t j b i t
D E S 加 密
丢 弃 6 4 - j b i t选 j b i t?
6 4
6 4
K
P 2
C 1
C 2
I V 移 位 寄 存 器
两 轮 O F B 模 式 解 密 示 意 图
2012-3-19 74
输出反馈 (OFB)模式
? 克服了 CFB的错误传播所带来的问题 。
? 比 CFB模式更易受到对消息流的篡改攻击,
使得敌手有可能通过对消息校验部分的篡改
和对数据部分的篡改, 而以纠错码不能检测
的方式篡改密文 。
2012-3-19 75
计数器 (CRT)模式
? CTR可以把分组密码转换为流密码
? 和 OFB类似，但是加密计数器值，而不是密
文反馈值
? 必须对每一个明文使用一个不同的密钥和计
数值
iiCP? xor iO
1 ()iKO D E S i?
2012-3-19 76
?加 密K C o u n t e r
C 1
P 1
?加 密K?加 密K C o u n t e r + 1 C o u n t e r + N - 1
P 2
P N
C 2
C N
C T R 模 式 加 密 示 意 图
?解 密K C o u n t e r 1
C 1
P 1
?解 密K?解 密K C o u n t e r 2 C o u n t e r N
P 2
P N
C 2
C N
C T R 模 式 解 密 示 意 图
2012-3-19 77
计数器 (CRT)模式
? 该模式优点是安全、高效、可并行、适合
任意长度的数据,的计算可以预处理，
适用于高速网络。加解密过程仅涉及加密
运算，不涉及解密算法，因此不用实现解
密算法。
? 缺点是没有错误传播，因此不易确保数据
完整性。信息快可被替换，重放，对明文
的主动攻击时可能的。
iO
2012-3-19 78
比较和选用
? ECB模式, 简单, 高速, 但最弱, 易受重发攻击
,一般不推荐 。
? CBC适用于文件加密, 但较 ECB慢 。 安全性加强
。 当有少量错误时, 也不会造成同步错误 。
? OFB和 CFB较 CBC慢许多 。 每次迭代只有少数 bit
完成加密 。 若可以容忍少量错误扩展, 则可换来
恢复同步能力, 此时用 CFB。 在字符为单元的流
密码中多选 CFB模式 。
? OFB用于高速同步系统, 不容忍差错传播 。
2012-3-19 79
习题
1,证明可以通过颠倒密钥方案用 DES加密算法加密密
文实现 DES解密。
2,在 DES数据加密标准中,
明文 m=0011 1000 1101 0101 1011 1000 0100
0010 1101 0101 0011 1001 1001 0101 1110
0111
密钥 K=1010 1011 0011 0100 1000 0110 1001
0100 1101 1001 0111 0011 1010 0010 1101
0011
试求 L1和 R1。
3,假设我们有 128bit的 AES密钥，用 16进制表示为,
2012-3-19 80
2B7E151628AED2A6ABF7158809CF4F3C
由该种子密钥构造一个完整的密钥编排方案。
4,使用上题中的 128bit密钥，在 10轮 AES下计算下列
明文（以 16进制表示）的加密结果：
3243F6A8885A308D313198A2E0370734。
5,在 IDEA的模乘运算中，为什么将模数取为 216+1而
不是 216？在其模加运算中，为什么模数取为 216而
不是 216+1？
6,已知 IDEA密码算法中,
明文 m=01011100 10001101 10101001 11011110
10101101 00110101 00010011 10010011;
2012-3-19 81
密钥 K=00101001 10100011 11011000 11100111 10100101
01010011 10100010 01011001 00100100 01011001
11001010 11100111 10100010 00101010 11010101
00110101，求第一轮的输出和第二轮的输出。
7,在 DES的 ECB模式中，如果在密文分组中有一个错误，解密后
仅相应的明文分组受到影响，然而在 CBC模式中，将有错误
传播（见 PPT相应的图中 C1的一个错误明显地影响 P1和 P2的结
果）。
（ 1） P2后的结果是否受到影响？
（ 2）设加密前的明文分组 P1中有 1bit的错误，问这一错误将
在多少个密文分组中传播？对接收者有什么影响？
2012-3-19 82
谢谢大家！
欢迎指正！
