第三章 分组密码
3.1 3.2 3.3 3.4 3.5 3.6 分组密码概述 数据加密标准 差分密码分析 分组密码的运行模式 IDEA AES算法 算法——Rijndael 算法
1
2010-10-9
3.1 分组密码概述
2010-10-9
2
分组密码概述
分组密码是许多系统安全的一个重要组 成部分。 成部分。可用于构造
2010-10-9 7
分组密码算法应满足的要求
加密和解密运算简单： 加密和解密运算简单： 易于软件和硬件高速实现。 易于软件和硬件高速实现。 加密和解密可用同一器件实现。 加密和解密可用同一器件实现。 数据扩展： 数据扩展： 一般无数据扩展， 一般无数据扩展 ， 在采用同态置换和随 机化加密技术时可引入数据扩展。 机化加密技术时可引入数据扩展。 差错传播尽可能地小。 差错传播尽可能地小。
扩散和混淆—抗统将明文及密钥的影响尽可能迅速地散布到较多 输出的密文中，使比特0 输出的密文中，使比特0、1均匀分布
混淆(confusion) 混淆(confusion)
使明文、 使明文、密钥和密文之间的关系复杂化 分组密码设计思想：扩散、混淆 分组密码设计思想：扩散、 置换和代换方法可实现扩散 扩散、 置换和代换方法可实现扩散、混淆
M34 M36 M38 M40 M33 M35 M37 M39
M26 M28 M30 M32 M25 M27 M29 M31
M18 M20 M22 M24 M17 M19 M21 M23
M10 M2 M12 M4 M14 M6 M16 M8 M9 M1 M11 M3 M13 M5 M15 M7
初始置换IP 初始置换
DES加密算法框图 加密算法框图
M1 M9 M17 M25 M33 M41 M49 M57
M2 M10 M18 M26 M34 M42 M50 M58
M3 M4 M11 M12 M19 M20 M27 M28 M35 M36 M43 M44 M51 M52 M59 M60
M5 M6 M7 M8 M13 M14 M15 M16 M21 M22 M23 M24 M29 M30 M31 M32 M37 M38 M39 M40 M45 M46 M47 M48 M53 M54 M55 M56 M61 M62 M63 M64
2010-10-9
11
3.1.3 Feistel密码结构
乘积密码： 乘积密码： 顺序地执行两个或多个基本密码系统 密码强度高于每个基本密码系统的强度。 密码强度高于每个基本密码系统的强度。 Feistel密码基本思想： 密码基本思想： 密码基本思想 利用乘积密码实现混淆和扩散
2010-10-9
12
Feistel网络参数 网络参数
分组大小。分组越大则安全性越高 越大则安全性越高， ① 分组大小。分组越大则安全性越高，但 加密速度就越慢。 加密速度就越慢。最为普遍使用的分组大 小是64比特 比特。 小是 比特。 密钥大小。密钥越长则安全性越高， ②密钥大小。密钥越长则安全性越高，但 加密速度就越慢。现在普遍认为64比特或 加密速度就越慢。现在普遍认为 比特或 更短的密钥长度是不安全的， 更短的密钥长度是不安全的，通常使用 128比特的密钥长度。 比特的密钥长度。 比特的密钥长度 轮数。单轮结构远不足以保证安全性， ③ 轮数。单轮结构远不足以保证安全性， 多轮结构可提供足够的安全性。典型地， 多轮结构可提供足够的安全性。典型地， 轮数取为16。 轮数取为 。 子密钥产生。算法的复杂性越大， ④ 子密钥产生。算法的复杂性越大，则密 码分析的困难性就越大。 码分析的困难性就越大。 轮函数。轮函数越复杂， ⑤ 轮函数。轮函数越复杂，密码分析的困 难性也越大。 难性也越大。
若n>m，则为有数据压缩的分组密码。 ，则为有数据压缩的分组密码。 若n<m，则为有数据扩展的分组密码。 ，则为有数据扩展的分组密码。
2010-10-9 6
分组密码算法应满足的要求
分组长度n要足够大： 分组长度 要足够大： 要足够大
防止明文穷举攻击法奏效。 防止明文穷举攻击法奏效。
密钥量要足够大： 密钥量要足够大：
2010-10-9
4
分组密码概述
明文序列 x1, x2,…, xi,… 加密函数E: 加密函数 Vn×K→Vm →
密钥k=(k0, k1,…, kt-1 ) 明文 x=(x0, x1,…, xn-1) 加密算法
密钥k=(k0, k1,…, kt-1 ) 明文 x=(x0, x1,…, xn-1) 解密算法
2010-10-9 17
3.2.1 DES描述 描述
明文分组长为64比特，密钥长为 比特 比特。 明文分组长为 比特，密钥长为56比特。 比特 一个初始置换IP，用于重排明文分组的64比特数 一个初始置换 ，用于重排明文分组的 比特数 据。 具有相同功能的16轮变换 轮变换， 具有相同功能的 轮变换，和Feistel密码结构完 密码结构完 全相同。 轮变换的输出左右两半交换次序。 全相同。第16轮变换的输出左右两半交换次序。 轮变换的输出左右两半交换次序 经过一个逆初始置换IP 产生64比特的密文 经过一个逆初始置换 -1产生 比特的密文
消息认证码(MAC)和杂凑函数 消息认证码(MAC)和杂凑函数 单钥数字签字体制的核心组成部分 拟随机数生成器
2010-10-9
3
应用中对于分组码的要求
安全性 运行速度 存储量(程序的长度、数据分组长度、高速缓 存储量(程序的长度、数据分组长度、 存大小) 存大小) 实现平台( 软件、芯片) 实现平台(硬、软件、芯片) 运行模式
Feistel网络中每轮结构都相同 网络中每轮结构都相同 代换substitution：每轮中右半数据 代换 ： 被作用于轮函数F后 被作用于轮函数 后，再与左半数据 进行异或运算。 进行异或运算。 置换permutation ：代换完成后， 代换完成后， 置换 再交换左、 再交换左、右两半数据 Feistel网络结构：Shannon提出的 网络结构： 网络结构 提出的 代换—置换网络 置换网络（ 代换 置换网络（SPN）的特有形式。 ）的特有形式。
Feistel加密结构 加密结构
第i轮迭代的输入为前一轮输 轮迭代的输入为前一轮输 出的函数： 出的函数： 其中Ki是第 轮用的子密钥， 是第i轮用的子密钥 其中 是第 轮用的子密钥， 由加密密钥K得到 得到。 由加密密钥 得到。
Li = Ri 1
Ri = Li 1 ⊕ F ( Ri 1 , K i )
2010-10-9 8
代换Substitution
代换：明文分组到密文分组的可逆变换 代换：明文分组到密文分组的可逆变换 明文和密文的分组长都为n比特 比特， 明文和密文的分组长都为 比特，则明文的每一个分组 都有2n个可能的取值；不同可逆变换的个数有2n!个 都有 个可能的取值；不同可逆变换的个数有 个 实际中常将n分成较小的段 如下： 分成较小的段， 实际中常将 分成较小的段，如下：
相 关 证 明
所以解密过程第1轮的输出等于加密过程第 所以解密过程第 轮的输出等于加密过程第16 轮的输出等于加密过程第 轮输入左右两半交换后的结果。 轮输入左右两半交换后的结果。 可证对应关系在16轮中均成立 可证对应关系在 轮中均成立
3.2 数据加密标准
数据加密标准（ 数据加密标准（data encryption standard, DES）是迄今 ） 为止世界上最为广泛使用和流行的一种分组密码算法. 为止世界上最为广泛使用和流行的一种分组密码算法 DES由IBM研制 分组长度为 比特，密钥长度为 比特 研制,分组长度为 比特， 比特. 由 研制 分组长度为64比特 密钥长度为56比特 1998年5月美国 月美国EFF宣布，他们以一台价值 万美元的计算 宣布， 年 月美国 宣布 他们以一台价值20万美元的计算 机改装成的专用解密机， 小时破译了56 比特密钥的 比特密钥的DES。 机改装成的专用解密机，用56小时破译了 小时破译了 。 美国已决定1998年12月以后将不再使用 月以后将不再使用DES。 美国已决定 年 月以后将不再使用 。 美国国家标准和技术协会征集并进行几轮评估、筛选， 美国国家标准和技术协会征集并进行几轮评估、筛选，产生 了称之为AES(advanced encryption standard) 新加密标准。 新加密标准。 了称之为 尽管如此， 尽管如此，DES对于推动密码理论的发展和应用毕竟起了重 对于推动密码理论的发展和应用毕竟起了重 大作用，对于掌握分组密码的基本理论、 大作用，对于掌握分组密码的基本理论、设计思想和实际应用 仍然有着重要的参考价值。 仍然有着重要的参考价值。
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
尽可能消除弱密钥并使所有密钥同等地好， 尽可能消除弱密钥并使所有密钥同等地好，以防止 密钥穷举攻击奏效。
由密钥确定置换的算法要足够复杂： 由密钥确定置换的算法要足够复杂：
充分实现明文与密钥的扩散和混淆， 充分实现明文与密钥的扩散和混淆，没有简单的关 系可循，要能抗击各种已知的攻击。 系可循，要能抗击各种已知的攻击。
初始置换前后
40 39 38 37 36 35 34 33 8 7 6 5 4 3 2 1 48 47 46 45 44 43 42 41
逆初始置换IP 逆初始置换 -1
16 15 14 13 12 11 10 9 56 55 54 53 52 51 50 49 24 23 22 21 20 19 18 17 64 63 62 61 60 59 58 57 32 31 30 29 28 27 26 25