现代密码学第4章1：概述

1、1分组密码分组密码现代密码学现代密码学第第4章章(1)2本章主要内容本章主要内容n1 1、分组密码概述、分组密码概述n2 2、数据加密标准、数据加密标准DESDES算法算法n3 3、分组密码的运行模式、分组密码的运行模式n4 4、差分密码分析与线性密码分析、差分密码分析与线性密码分析n5 5、IDEAIDEA算法算法n6 6、AESAES算法算法RijndaelRijndael3 在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码（MAC）和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心

2、组成部分。第第1 1节：分组密码概述节：分组密码概述4n 实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择。1 分组密码概述分组密码概述5n是一种单钥或对称算法n通信实体双方使用相同的密钥加密和解密 n现代分组密码（由乘积密码构成）包括DES, Blowfish, IDEA, LOKI, RC5, Rijndael (AES) 及其它一些算法1 分组密码概述分组密码概述6n在分组密码中，消息被分成许多块，每块都要被加密n类似于许

3、多字符被替换-（64-bits or more ）n许多现代分组密码具有下列形式：1 分组密码概述分组密码概述71 分组密码概述分组密码概述8分组密码理论基础分组密码理论基础n理想的方法是使用尽可能大的替换模块，但不实际，因为对每个64bit的模块，将需要264 个实体的替换表，因此使用一些小的模块代替。n使用乘积密码的思想 n这种概念由 Shannon and Feistel 提出9分组密码的设计原理分组密码的设计原理n可变密钥长度可变密钥长度n混合操作混合操作n依赖数据的循环移位依赖数据的循环移位n依赖于密钥的循环移位依赖于密钥的循环移位n依赖密钥的依赖密钥的S盒子盒子n冗长的密钥调度算法

4、冗长的密钥调度算法n可变的可变的F函数和可变的明文函数和可变的明文/密文长度密文长度n可变的循环次数可变的循环次数n在每次循环中都对两半数据进行操作在每次循环中都对两半数据进行操作10Shannons 保密系统理论保密系统理论 nClaude Shannon 对现代密码的重要工作：nC E Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, Vol 28, Oct 1949, pp 656-715 nC E Shannon, Prediction and Entropy of prin

5、ted English, Bell System Technical Journal, Vol 30, Jan 1951, pp 50-64 n在上述文章中，提出了下列概念: n“熵”的概念n语言冗余度n破译密码需要多少信息量n定义了”计算安全”与”无条件安全”11n即如果通过填加一些英语字母加密英文内容，是不安全的。n因为英语有80%的冗余度，英语密文如果有60%的冗余度，就可以破解。Shannons 保密系统理论保密系统理论 12 分组密码是将明文消息编码表示后的数字序列x0,x1,xi,划分成长为n的组x=(x0,x1,xn-1)，各组（长为n的矢量）分别在密钥k=(k0,k1,kt-1

6、)控制下变换成等长的输出数字序列y=(y0,y1,ym-1)（长为m的矢量），其加密函数E：VnKVm，Vn和Vm分别是n维和m维矢量空间，K为密钥空间，如图1所示。1 1 分组密码概述分组密码概述13 明文序列明文序列 x1, x2, xi, 加密函数加密函数E: VnKVn 这种密码实质上是字长为这种密码实质上是字长为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)图1 分组密码框图

7、1 1 分组密码概述分组密码概述14n 它与流密码不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。n 在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为n的数字序列的代换密码。1 1 分组密码概述分组密码概述15 通常取m=n。若mn，则为有数据扩展的分组密码；若mn，则为有数据压缩的分组密码。 在二元情况下，x和y均为二元数字序列，它们的每个分量xi，yiGF(2)。本节将主要讨论二元情况。设计的算法应满足下述要求：1 1 分组密码概述分组密码概述16n分组密码是许多系

8、统安全的一个重要组分组密码是许多系统安全的一个重要组成部分。可用于构造成部分。可用于构造n拟随机数生成器拟随机数生成器n流密码流密码n消息认证码消息认证码(MAC)(MAC)和杂凑函数和杂凑函数n消息认证技术、数据完整性机构、实体认证消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分协议以及单钥数字签字体制的核心组成部分。分组密码概述分组密码概述17分组密码与序列密码比较，主要区别是在加密方式上：序列密码序列密码：kKGk=k0k1k2012mmm)()(001122kmkmkm分组密码概述分组密码概述18大多数实用分组密码的明文信号取自于F2、且满足：n=n（即明文

9、没有被扩展）。考察的一个分组密码体制，设 为密 钥空间，n为分组长度，那么加密变换空间为： =Ek|Ek: 是一一映射,k 。若将 中点 与其所对应的二进制数 不加区别，则每个k(k )可等同一个2n-置换。nnFF22),(110nxxxXnF22110)(nxxxX分组密码概述分组密码概述19线性部分nS2记 为由所有2n-置换构成的所谓2n次对称群，那么一个好的分组密码的加密变换空间在 中的位置应如下图所示：nS2nS2分组密码概述分组密码概述20应用中对于分组码的要求应用中对于分组码的要求n安全性安全性n运行速度运行速度n存储量存储量( (程序的长度、数据分组长度、高速缓存大程序的长度

10、、数据分组长度、高速缓存大小小) )n实现平台实现平台( (硬、软件、芯片硬、软件、芯片) )n运行模式运行模式21分组密码设计问题分组密码设计问题 分组密码的设计问题在于找到一种算分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数一个置换，用来对当前输入的明文的数字组进行加密变换。字组进行加密变换。22 分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和LOKI等分组密码都采用n=

11、64，在生日攻击下用232组密文成功概率为1/2，同时要求23264b=215MB存贮，故采用穷举攻击是不现实的。1 1 分组密码算法设计要求分组密码算法设计要求23 密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。DES采用56比特密钥，看来太短了，IDEA采用128比特密钥，据估计，在今后3040年内采用80 比特密钥是足够安全的。1 1 分组密码算法设计要求分组密码算法设计要求24 由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻

12、击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。1 1 分组密码算法设计要求分组密码算法设计要求25 加密和解密运算简单，易于软件和硬件高速实现。如将分组n化分为子段，每段长为8、16或者32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。1 1 分组密码算法设计要求分组密码算法设计要求26n 为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代

13、等，以便于软件和VLSI快速实现。此外，差错传播和数据扩展要尽可能地小。1 1 分组密码算法设计要求分组密码算法设计要求27 数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。 差错传播尽可能地小。1 1 分组密码算法设计要求分组密码算法设计要求28l软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，比如8、16或32比特等； 在软件实现中，按比特操作（如置换）是难于实现的，因此应该尽量避免它。子块上所进行的密码运算应该是一些易于软件实现的运算，最好是用一些标准处理器所具有的那些基本指令，比如加法、乘法和移位等。1 1

14、分组密码软件设计原则分组密码软件设计原则29加密和解密应具有相似性（最好只是在密钥的使用方式上存在不同，其余皆同）以便可以用同样的器件来实现。 尽量使用规则结构，且应符合国际的统一标准，以便适合于用超大规模集成电路来实现。：分组密码常常以乘积密码的方式来设计。由合理选择的许多子密码（相继使用）构成的乘积密码既可实现良好的混乱、又可实现良好的扩散。1 1 分组密码硬件设计原则分组密码硬件设计原则30 要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法，而后进行严格的安全性检验，并且要易于实现。 下面介绍设计分组密码时的一些常用方法。1 1 分组密码算法设计要求分组密码算法设计要

15、求31 如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。（1）代换）代换1 1 分组密码算法设计方法分组密码算法设计方法32 图2表示n=4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。 加密映射和解密映射可由代换表来定义，如表3.1所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任

16、何可逆映射。（见33页表3.1）（1）代换）代换33n在Shannon 1949 的文章中，介绍了替换-置换网络的思想 (S-P) networks n这种思想形成了现代密码的基础nS-P network 替换-置换乘积密码的现代形式nS-P networks 是基于下列两种最基本的密码运算（前面介绍过）：n替换（ Substitution ）n置换（ Permutation ）（1）代换）代换34图2 代换结构（1）代换）代换35 但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小，如n=4，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。这个弱点不是代换结构固有的，只

17、是因为分组长度太小。如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。（1）代换）代换36 然而，从实现的角度来看，分组长度很大的可逆代换结构是不实际的。仍以表3.1为例，该表定义了n=4时从明文到密文的一个可逆映射，其中第2列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。 因此从本质上来说，第2列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥需要64比特。一般地，对n比特的代换结构，密钥的大小是n2n比特。如对64比特的分组，密钥大小应是64264=2701021比特，因此难以处理。（1）代换）代换37 实际中

18、常将n分成较小的段，例如可选n=rn0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般n0都不太大，称每个子代换为代换盒，简称为S盒。例如DES中将输入为48比特、输出为32比特的代换用8个S盒来实现，每个S盒的输入端数仅为6比特，输出端数仅为4比特。（1）代换）代换38代换网络代换网络n 代换代换是输入集是输入集A到输出到输出A上的双射变上的双射变换换： fk：AA 式中，式中，k是控制输入变量，在密码学是控制输入变量，在密码学中则为密钥中则为密钥。n 实现代换实现代换fk的网络称作代换网络。双的网络称作代换网络。双射条件保证在给定

19、射条件保证在给定k下可从密文惟一地恢下可从密文惟一地恢复出原明文复出原明文。39n代换代换fk的集合：的集合： S=fk k KnK是密钥空间。如果网络可以实现所有可是密钥空间。如果网络可以实现所有可能的能的2n!个代换，则称其为全代换网络。个代换，则称其为全代换网络。n全代换网络密钥个数必须满足条件：全代换网络密钥个数必须满足条件： k 2n! 代换网络代换网络40n 密码设计中需要先定义代换集密码设计中需要先定义代换集S，而后还，而后还需定义解密变换集，即逆代换网络需定义解密变换集，即逆代换网络S-1，它以，它以密文密文y作为输入矢量，其输出为恢复的明文矢作为输入矢量，其输出为恢复的明文矢

20、量量x。n 要实现全代换网络并不容易。因此实用中要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密码较复杂的、元素个数较多的代换集。实用密码体制的集合体制的集合S中的元素个数都远小于中的元素个数都远小于2n!。代换网络代换网络41例例:n=4 代换结构代换结构0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1542明文 密文明文 密文0000 11010001 01010010 00010011

21、01100100 10010101 11110110 00100111 00111000 10101001 10001010 10111011 11101100 01111101 01001110 11001111 0000密文 明文密文 明文0000 11110001 00100010 01100011 01110100 11010101 00010110 00110111 11001000 10011001 01001010 10001011 10101100 11101101 00001110 10111111 0101正向代换反向代换43 在二元域上，如果明文和密文在二元域上，如果明文

22、和密文的长度都为的长度都为n则共有多少个可逆代换？则共有多少个可逆代换？课堂思考：课堂思考：44 在密码设计中，可选在密码设计中，可选n=r n0，其中，其中r和和n0都为正整都为正整数，将设计数，将设计n个变量的代换网络化为设计个变量的代换网络化为设计r个较小的子个较小的子代换网络，而每个子代换网络只有代换网络，而每个子代换网络只有n0个输入变量。称个输入变量。称每个子代换网络为代换盒每个子代换网络为代换盒(Substitution Box) S盒 x5 x4 x3 x2 x1 x0 y3 y2 y1 y0DES的S盒代换盒代换盒(S(S盒盒) )45DESDES的的S S1 1- -盒的输

23、入和输出关系盒的输入和输出关系nx5 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)46 迄今为止，

24、有关方面未曾完全公开有关迄今为止，有关方面未曾完全公开有关DES的的S盒盒的设计准则。的设计准则。Branstead等曾披露过下述准则：等曾披露过下述准则：nP1 S盒的输出都不是其输入的线性或仿射函数。盒的输出都不是其输入的线性或仿射函数。nP2 改变改变S盒的一个输入比特，其输出至少有两比特盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。产生变化，即近一半产生变化。nP3 当当S盒的任一输入位保持不变，其它盒的任一输入位保持不变，其它5位输入变位输入变化时化时(共有共有25 =32种情况种情况)，输出数字中的，输出数字中的0和和1的总的总数近于相等。数近于相等。 这三点使这

25、三点使DES的的S盒能够实现较好的混淆。盒能够实现较好的混淆。S S盒的设计准则盒的设计准则47 问题问题: 如何将几个如何将几个S盒组合起来构成一个盒组合起来构成一个n值较大的组。值较大的组。 将几个将几个S S盒的输入端并行，并通过坐标置换盒的输入端并行，并通过坐标置换(P-(P-盒盒) )将各将各S S盒输出比特次序打乱，再送到下一级盒输出比特次序打乱，再送到下一级各各S S盒的输入端，起到了盒的输入端，起到了ShannonShannon所谓的所谓的“扩散扩散”作用。作用。S S盒提供非线性变换，将来自上一级不同的盒提供非线性变换，将来自上一级不同的S S盒的输出进行盒的输出进行“混淆混

26、淆”。经过。经过P P- -盒的扩散作用使盒的扩散作用使1 1均匀地分散到整个输出矢量中，从而保证了输出均匀地分散到整个输出矢量中，从而保证了输出密文统计上的均匀性，这就是密文统计上的均匀性，这就是ShannonShannon的乘积密码的乘积密码的作用。的作用。S S盒的组合盒的组合48 扩散和混淆是由Shannon提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。

27、（2 2）扩散和混淆）扩散和混淆49n 在Shannon称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。图2讨论的代换密码就是这样的一个密码系统，然而它是不实用的。（2）扩散和混淆）扩散和混淆50 所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。 例如对英文消息M=m1m2m3的加密操作 其中ord(mi)是求字母mi对应的序号，chr(i)是求序号i对应的字母。1mod26knn iiychrord m（2）扩散和混淆）扩散和混淆51n 这时明文的统计特性将被散布到密文中，因而每一字母在密

28、文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。n 在二元分组密码中，可对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。（2）扩散和混淆）扩散和混淆52 分组密码在将明文分组依靠密钥变换到密文分组时： 扩散的目的是使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥； 混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。（2）扩散和混淆）扩散和混淆53n 因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥。使用复杂的代换算法可以得到预期的混淆效果，而简单的线性代换函数得到

29、的混淆效果则不够理想。n 扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。（2）扩散和混淆）扩散和混淆54代换运算代换运算55n二进制字次序被打乱 n重新排序的方法构成密钥 n叫这种变换为 P-boxes 代换运算代换运算56P-Box57Substitution-Permutation Network nShannon 把这两种运算组合在一起 n一些 S-boxes 由 P-box 连接n这种变换叫做混合变换n（mixing transformations）58替换替换-置换网络置换网络59实际使用的替换实际使用的替换-置换网络置换网络n实际中，我们需要加密，也需要

30、解密n因此，有两种方法：n1.定义每个替换、置换的逆，这样增加了复杂度2. 定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密60nHorst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，设计了这样的结构，我们现在叫做feistel cipher n思想是把输入块分成左右两部分 L(i-1) 和R(i-1), 变换是在密码的第I轮只使用R(i-1) n函数 g incorporates one stage of the S-P network的每个阶段有g 工作，由第i 个密钥控制（叫子密钥）。F

31、eistel 密码结构密码结构61 很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。 Feistel提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果，Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。Feistel 密码结构密码结构62 图3是Feistel网络示意图，加密算法的输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的

32、输入为前一轮输出的函数： 其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。111,iiiiiiLRRLF RK1.Feistel1.Feistel加密结构加密结构63图3 Feistel网络示意图64 Feistel网络中每轮结构都相同，每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。每轮的轮函数的结构都相同，但以不同的子密钥Ki作为参数。 代换过程完成后，再交换左、右两半数据，这一过程称为置换。这种结构是Shannon提出的代换置换网络（substitution-permutation network, SPN）

33、的特有形式。1.Feistel1.Feistel加密结构加密结构65 Feistel网络的实现与以下参数和特性有关： 分组大小分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比特。 密钥大小密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。1.1.Feistel 网络的实现网络的实现66n 轮数单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。n 子密钥产生算法该算法的复杂性越大，则密码分析的困难性就越大。n 轮函数轮函数的复杂性越大，密码分析的困难性也越大。1.

34、Feistel 网络的实现网络的实现67 在设计Feistel网络时，还有以下两个方面需要考虑： 快速的软件实现在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。 算法容易分析如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。1.1.Feistel 网络的设计网络的设计68 Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。2.2.Feistel 解密结构解密结构

35、69 图4的左边表示16轮Feistel网络的加密过程，右边表示解密过程，加密过程由上而下，解密过程由下而上。为清楚起见，加密算法每轮的左右两半用LEi和REi表示，解密算法每轮的左右两半用LDi和RDi表示。 图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值的对应关系，即加密过程第i轮的输出是LEiREi（表示链接），解密过程第16-i轮相应的输入是RDiLDi。2.2.Feistel 解密结构解密结构70明文(2w比特) F1L1R0L0RW比特W比特第1轮 FnLnR1nL1nR第n轮1KnK密文(2w比特)1nL1nR712 Feistel网络解密结构网络解密结构输入（明文）

36、 F1K F1K0LE0RE1RE1LE2RE2LE F15K14RE14LE F16K15LE15RE16RE16LE输出（密文）输入（密文） F16K160RELD 160LERD F15K F2K F1K输出（明文）151LERD 151RELD142RELD 142LERD 214RELD 214LERD 115LERD115RELD 016RELD 016LERD72图4 Feistel加解密过程73 加密过程的最后一轮执行完后，两半输出再经交换，因此密文是RE16LE16。解密过程取以上密文作为同一算法的输入，即第1轮输入是RE16LE16，等于加密过程第16轮两半输出交换后的结果

37、。下面证明解密过程第1轮的输出等于加密过程第16轮输入左右两半的交换值。2.2.Feistel 解密结构解密结构74在加密过程中：在解密过程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLE2.2.Feistel 解密结构解密结构75 所以解密过程第1轮的输出为LE15RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第i轮有因此111,iiiiiiLERERELEF REK111,iiii

38、iiiiiRELELEREF REKREF LEK2.2.Feistel 解密结构解密结构76 以上两式描述了加密过程中第i轮的输入与第i轮输出的函数关系，由此关系可得图4右边显示的LDi和RDi的取值关系。 最后可以看到，解密过程第16轮的输出是RE0LE0，左右两半再经一次交换后即得最初的明文。2.2.Feistel 解密结构解密结构77nShannons 混合变换形成一种特殊的乘积密码，组成部分一起工作: nS-Boxes （S-盒)：提供输入bits混合作用 (confusion) 其目的在于使作用于明文的密钥和密文之间的关系复杂化，使明文和密文之间、密文和密钥之间的统计相关特性极小化

39、，从而使统计分析攻击不能奏效。通常的方法是“替换（Substitution)”（回忆恺撒密码）。2.2.Feistel 结构设计原理结构设计原理78P-BoxesnP-Boxes：提供扩散作用(diffusion) 将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中（将明文冗余度分散到密文中）。产生扩散的最简单方法是通过“换位(Permutation)”（比如：重新排列字符）n这种效果进一步解释为”雪崩”与”完全性” (Avalanche and Completeness )by Webster & Tavares nOn the Design of S-boxes, in Adv

40、ances in Cryptology - Crypto 85, Lecture Notes in Computer Science, No 218, Springer-Verlag, 1985, pp 523-53479雪崩效应雪崩效应(Avalanche effect )n输入改变1bit, 导致近一般的比特发生变化n一个函数F具有好的雪崩特性是指: 对2m个明文 向量, 分为2m-1个向量对xi和xi,每对向量只有一个bit不同, 定义Vi = f(X) XOR f(Xi) ,则近一半的Vi为1.80完备性效应完备性效应(Completeness effect )n每个输出比特是所有输入

41、比特的复杂函数的输出，n www.cs.adfa.oz.au/teaching/studinfo/csc/lectures/ss-less07.html具有好的完备性是指: 对密文输出向量的每一比特j, 0jm, 至少存在一个明文对(xi,xi), 此明文对只在第i比特不同,且F(xi)与F(xi)的第j比特不同.81分组密码设计分组密码设计(Block Cipher Design) n这些设计原理是设计好的分组密码的准这些设计原理是设计好的分组密码的准则。则。 n“雪崩雪崩”保证小的输入变化导致大的输保证小的输入变化导致大的输出变化；出变化；n完全性保证每个输出比特依赖于所有的完全性保证每个

42、输出比特依赖于所有的输入比特；输入比特；n我们可以看到我们可以看到,古典密码没有这些性质。古典密码没有这些性质。82Feistel Cipher 设计设计n设计密码时,下列参数需要考虑: n分组大小分组大小(block size) 增加分组长度会提高安全性, 但降低了密码运算速度n密钥大小密钥大小(key size) 增加密钥长度,可以提高安全性(使得穷搜索困难),同样,降低了密码速度. 83n轮数轮数 增加轮数可以提高安全性,但降低速度n子密钥生成子密钥生成 子密钥生成越复杂,就越安全,但降低速度n轮函数轮函数 复杂的轮函数能够使的密码分析困难,但降低速度 n(所有问题就是平衡问题)n设计”

43、安全”的密码算法并不难,只要使用足够多的轮数就可以,但降低速度n 得到一个快速安全的算法是困难的Feistel Cipher 设计设计84密码设计密码设计 评价评价 “好的”密码设计具有: 雪崩特性,完备性,不可预料性(avalanche, completeness, unpredictability )n差的密码设计缺乏随机性,具有太大的可预料性n许多密码都被攻破 (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers) n即使密码学专家也会犯这样的错误n最好的办法是测试, 通过

44、实际检验证明它的安全性85n若以一个简单函数若以一个简单函数f，进行多次迭代，就称其为迭代密码。，进行多次迭代，就称其为迭代密码。n每次迭代称作一轮每次迭代称作一轮(Round)。相应函数。相应函数f 称作轮函数。称作轮函数。n每一轮输出都是前一轮输出的函数，即每一轮输出都是前一轮输出的函数，即y(i)=fy(i-1), k(i)，其，其中中k(i)是第是第i轮迭代用的子密钥，由秘密密钥轮迭代用的子密钥，由秘密密钥k通过密钥生成通过密钥生成算法产生。算法产生。 子 密 钥 产 生 器kk(1)k(2)k(r)y(0) = xy(1)y(2)y(r-1)y(r)=y迭代分组密码迭代分组密码86

45、加密函数加密函数f(x, k)，实现，实现F F2n F F2t F F2n的映射。的映射。其中，其中，n是分组长，是分组长，t是密钥长。若对每个密钥取值是密钥长。若对每个密钥取值都有都有 ff(x, k)，k=x，即，即f(x, k)2 =I (恒等置换恒等置换) 则称其为对合密码，以则称其为对合密码，以fI表示。表示。对合密码对合密码( (Involution Cipher) )87I I型迭代分组密码型迭代分组密码n以对合密码函数构造的多轮迭代分组密码以对合密码函数构造的多轮迭代分组密码。Ex, k=fIfI fI fIx, k(1)，k(2) ，k(r-1)，k(r)Dy, k =fI

46、 fI fIfIy, k(r)，k(r-1) ，k(2) ，k(1) n 缺点：对任意偶数轮变换，若对所有缺点：对任意偶数轮变换，若对所有i选择选择k(2i-1) =k(2i)，则，则加密的变换等价于恒等变换，在实用中需要避免这类密钥加密的变换等价于恒等变换，在实用中需要避免这类密钥选择。选择。88n对合置换对合置换 令令P是对是对x的置换，即的置换，即P： F F2n F F2n ，若对所有，若对所有x GF(2n)，有，有PPx=x，即，即PP=I(恒等置换恒等置换)，以，以PI表示。表示。nII型迭代分组密码型迭代分组密码 每轮采用对合密码函数和对合置换级连，即每轮采用对合密码函数和对合置换级连，即 Fx, kPI fI x, k 并选解密子密钥与加密子密钥逆序，则加密解并选解密子密钥与加密子密钥逆序，则加密解密可用同一器件完成。密可用同一器件完成。 DES、FEAL和和LOKI等都属此类。等都属此类。对合置换和对合置换和IIII型迭代分组密码型迭代分组密码89 群密码群密码：若密钥与明文、密文取自同一空间：若密钥与明文、密文取自同一空间GF(2 n)，且，且 y=x k，式中，式中， 是是群运算群运算，则称其为，则称其为群密码。群密码。 显然显然x可通过可通过k的逆元求得的逆元求得 x=y k-1