第3章密码学基础分组密码体制祥解.ppt

第3章 分组密码体制 3.1 分组密码概述（▲Feistel密码结构，扩散和混淆） 3.2 数据加密标准▲ 3.3 差分密码分析与线性密码分析 * （中途相遇攻击原理） 3.4 分组密码的运行模式▲ 3.5 IDEA 3.6 AES算法——Rijndael ▲ 习题 3.1分组密码概述 在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码（MAC）和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择。 明文x0,x1,…,xi,… 明文分组 x=(x0, x1,…, xn-1)， 密钥 k=(k0, k1,…, kt-1) 密文分组 y=(y0,y1,…,ym-1 加密函数 E：Vn×K→Vm 图3.1 分组密码框图 通常取m=n。 若mn，则为有数据扩展的分组密码； 若mn，则为有数据压缩的分组密码。 设计的算法应满足下述要求： ① 分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。 DES、IDEA、FEAL和LOKI等分组密码都采用n=64，在生日攻击下用232组密文成功概率为1/2，同时要求232×64b=215MB存贮，故采用穷举攻击是不现实的。 ② 密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。 但密钥又不能过长，以便于密钥的管理。 DES采用56比特密钥，太短了，IDEA采用128比特密钥，据估计，在今后30～40年内采用80 比特密钥是足够安全的。 ③ 由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。 ④ 加密和解密运算简单，易于软件和硬件高速实现。如将分组n化分为子段，每段长为8、16或者32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现。此外，差错传播和数据扩展要尽可能地小。 ⑤ 数据扩展尽可能地小。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。 ⑥ 差错传播尽可能地小。 3.1.1 代换 如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的， 称明文分组到密文分组的可逆变换为代换。 明文到密文，或密文到明文，可由代换表完成表示，代换表是可逆的、一对一的映射表。见教材P36，表3-1。 不同可逆变换的个数有2n!个。 图3.2表示n=4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。加密映射和解密映射可由代换表来定义，如表3.1所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。（见33页表3.1） 图3.2 代换结构 如果分组长度太小，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。 从实现的角度来看，分组长度很大的可逆代换结构是不实际的。 仍以表3.1为例，该表定义了n=4时从明文到密文的一个可逆映射，其中第2列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第2列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥需要64比特。一般地，对n比特的代换结构，密钥的大小是n×2n比特。如对64比特的分组，密钥大小应是64×264=270≈1021比特，因此难以处理。 实际中常将n分成较小的段，例如可选n=r· n0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般n0都不太大， 称每个子代换为代换盒，简称为S盒。 例如DES中将输入为48比特、输出为32比特的代换用8个S盒来实