现代密码学课件第5讲-分组密码.ppt

1、2023-5-141 第四章第四章 分组密码分组密码一、分组密码概述一、分组密码概述二、分组密码运行模式二、分组密码运行模式三、三、DESDES四、四、AESAES五、分组密码的分析五、分组密码的分析2023-5-142一、分组密码概述一、分组密码概述2023-5-143分组密码概述分组密码概述n分组密码是许多系统安全的一个重要组成部分。分组密码是许多系统安全的一个重要组成部分。可用于构造可用于构造n拟随机数生成器拟随机数生成器n流密码流密码n消息认证码消息认证码(MAC)MAC)和杂凑函数和杂凑函数n消息认证技术、数据完整性机构、实体认证协议以消息认证技术、数据完整性机构、实体认证协议以及单

2、钥数字签字体制的核心组成部分及单钥数字签字体制的核心组成部分。2023-5-144应用中对于分组码的要求应用中对于分组码的要求n安全性安全性n运行速度运行速度n存储量存储量(程序的长度、数据分组长度、高速缓程序的长度、数据分组长度、高速缓存大小存大小)n实现平台实现平台(硬、软件、芯片硬、软件、芯片)n运行模式运行模式2023-5-145分组密码概述分组密码概述 明文序列明文序列 x1,x2,xi,加密函数加密函数E:VnKVn 这种密码实质上是字长为这种密码实质上是字长为m的数字序列的代换密码的数字序列的代换密码。解密算法加密算法密钥k=(k0,k1,kt-1)密钥k=(k0,k1,kt-1

3、)明文明文x=(x0,x1,xm-1)明文明文x=(x0,x1,xm-1)密文密文x=(y0,y1,ym-1)2023-5-146分组密码概述分组密码概述n通常取通常取n=m。n若若nm，则为有数据扩展的分组密码。则为有数据扩展的分组密码。n若若nm，则为有数据压缩的分组密码。则为有数据压缩的分组密码。2023-5-147分组密码设计问题分组密码设计问题 分组密码的设计问题在于找到一种算法，能分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当集中，简单而迅速地选出一个置换，用来对当前输入

4、的明文的数字组进行加密变换。前输入的明文的数字组进行加密变换。2023-5-148分组密码算法应满足的要求分组密码算法应满足的要求n分组长度分组长度n要足够大：要足够大：防止明文穷举攻击法奏效。防止明文穷举攻击法奏效。n密钥量要足够大：密钥量要足够大：尽可能消除弱密钥并使所有密钥同等地好，以防止尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效密钥穷举攻击奏效。n由密钥确定置换的算法要足够复杂：由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关充分实现明文与密钥的扩散和混淆，没有简单的关系可循系可循，要能抗击各种已知的攻击。要能抗击各种已知的攻击。2023-

5、5-149分组密码算法应满足的要求分组密码算法应满足的要求n加密和解密运算简单加密和解密运算简单：易于软件和硬件高速实现易于软件和硬件高速实现。n数据扩展：数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展可引入数据扩展。n差错传播尽可能地小差错传播尽可能地小。2023-5-1410代换网络代换网络n代换代换是输入集是输入集A到输出到输出A上的双射变换上的双射变换：fk：AA 式中，式中，k是控制输入变量，在密码学中则为密是控制输入变量，在密码学中则为密钥钥。n实现代换实现代换fk的网络称作代换网络。双射条件保的网络称作代换

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

7、其输出为恢复的明文作为输入矢量，其输出为恢复的明文矢量矢量x。n要实现全代换网络并不容易。因此实用中要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实现较复杂的、元素个数较多的代换集。实用密码体制的集合实用密码体制的集合S中的元素个数都远小中的元素个数都远小于于2n!。2023-5-1413 代换盒代换盒(S盒盒)在密码设计中，可选在密码设计中，可选n=r n0，其中其中r和和n0都为正整数，都为正整数，将设计将设计n个变量的代换网络化为设计个变量的代换网络化为设计r个较小的子代换个较小的子代换网络

8、，而每个子代换网络只有网络，而每个子代换网络只有n0个输入变量。称每个子个输入变量。称每个子代换网络为代换盒代换网络为代换盒(Substitution Box)S盒 x5 x4 x3 x2 x1 x0 y3 y2 y1 y0DES的S盒2023-5-1414DES的的S1-盒的输入和输出关系盒的输入和输出关系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

9、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)2023-5-1415扩散和混淆扩散和混淆n扩散将明文的统计特性散布到密文中。扩散将明文的统计特性散布到密文中。实现的方式是使明文的每一位影响密文实现的方式是使明文的每一位影响密文中多位的值。中多位的值。2023-5-1416 S S盒的设计准则盒的设计准则 迄今为止，有关方面未曾完全公开有关迄今为止，有关方面未曾完全公开有关DES的的S盒的设

10、计准盒的设计准则。则。Branstead等曾披露过下述准则：等曾披露过下述准则：nP1 S盒的输出都不是其输入的线性或仿射函数。盒的输出都不是其输入的线性或仿射函数。nP2 改变改变S盒的一个输入比特，其输出至少有两比特产生变盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。化，即近一半产生变化。nP3 当当S盒的任一输入位保持不变，其它盒的任一输入位保持不变，其它5位输入变化时位输入变化时(共共有有25=32种情况种情况)，输出数字中的，输出数字中的0和和1的总数近于相等。的总数近于相等。这三点使这三点使DES的的S盒能够实现较好的混淆。盒能够实现较好的混淆。2023-5-14

11、17S S盒的组合盒的组合问题问题:如何将几个如何将几个S盒组合起来构成一个盒组合起来构成一个n值较值较大的组。大的组。将几个将几个S S盒的输入端并行，并通过坐标置换盒的输入端并行，并通过坐标置换(P-P-盒盒)将各将各S S盒输出比特次序打乱，再送到下一级各盒输出比特次序打乱，再送到下一级各S S盒的输入端，起到盒的输入端，起到了了ShannonShannon所谓的所谓的“扩散扩散”作用。作用。S S盒提供非线性变换，将盒提供非线性变换，将来自上一级不同的来自上一级不同的S S盒的输出进行盒的输出进行“混淆混淆”。经过。经过P P-盒的扩盒的扩散作用使散作用使1 1均匀地分散到整个输出矢量

12、中，从而保证了输出均匀地分散到整个输出矢量中，从而保证了输出密文统计上的均匀性，这就是密文统计上的均匀性，这就是ShannonShannon的乘积密码的作用。的乘积密码的作用。2023-5-1418Feistel网络网络 将将n bit明文分成为左右各半、长为明文分成为左右各半、长为n/2 bit的段，以的段，以L和和R表表示。然后进行多轮迭代，其第示。然后进行多轮迭代，其第i轮迭代的输出为前轮输出的轮迭代的输出为前轮输出的函数函数 Li=Ri-1 Ri=Li-1 f(Ri-1,Ki)式中，式中，Ki是第是第i轮用的子密钥，轮用的子密钥，f是任意密码轮函数。称这种是任意密码轮函数。称这种分组密

13、码算法为分组密码算法为Feistel网络（网络（Feistel Network），它保证加，它保证加密和解密可采用同一算法实施密和解密可采用同一算法实施2023-5-1419迭代分组密码迭代分组密码n若以一个简单函数若以一个简单函数f，进行多次迭代，就称其为迭代密码。进行多次迭代，就称其为迭代密码。n每次迭代称作一轮每次迭代称作一轮(Round)。相应函数相应函数f称作轮函数称作轮函数。n每一轮输出都是前一轮输出的函数，即每一轮输出都是前一轮输出的函数，即y(i)=fy(i-1),k(i)，其其中中k(i)是第是第i轮迭代用的子密钥，由秘密密钥轮迭代用的子密钥，由秘密密钥k通过密钥生成通过密钥

14、生成算法产生。算法产生。子 密 钥 产 生 器kk(1)k(2)k(r)y(0)=xy(1)y(2)y(r-1)y(r)=y2023-5-1420对合密码对合密码(Involution Cipher)加密函数加密函数f(x,k)，实现实现F F2n F F2t F F2n的映射。其中，的映射。其中，n是分是分组长，组长，t是密钥长。若对每个密钥取值都有是密钥长。若对每个密钥取值都有ff(x,k)，k=x，即即f(x,k)2=I(恒等置换恒等置换)则称其为对合密码，以则称其为对合密码，以fI表示。表示。2023-5-1421I型迭代分组密码型迭代分组密码n以对合密码函数构造的多轮迭代分组密码以对

15、合密码函数构造的多轮迭代分组密码。Ex,k=fIfI fI fIx,k(1)，k(2)，k(r-1)，k(r)Dy,k=fI fI fIfIy,k(r)，k(r-1)，k(2)，k(1)n 缺点：对任意偶数轮变换，若对所有缺点：对任意偶数轮变换，若对所有i选择选择k(2i-1)=k(2i)，则加密的变换等价于恒等变换，在实用中需要避免这则加密的变换等价于恒等变换，在实用中需要避免这类密钥选择。类密钥选择。2023-5-1422对合置换和对合置换和II型迭代分组密码型迭代分组密码n对合置换对合置换 令令P是对是对x的置换，即的置换，即P：F F2n F F2n，若对所有若对所有x GF(2n)，

16、有有PPx=x，即即PP=I(恒等置换恒等置换)，以，以PI表示。表示。nII型迭代分组密码型迭代分组密码 每轮采用对合密码函数和对合置换级连，即每轮采用对合密码函数和对合置换级连，即 Fx,kPI fI x,k 并选解密子密钥与加密子密钥逆序，则加密解密可用同一器并选解密子密钥与加密子密钥逆序，则加密解密可用同一器件完成。件完成。DES、FEAL和和LOKI等都属此类。等都属此类。2023-5-1423 III型迭代分组密码型迭代分组密码群密码群密码：若密钥与明文、密文取自同一空间：若密钥与明文、密文取自同一空间GF(2 n)，且且y=x k式中，式中，是是群运算群运算，则称其为群密码。显然

17、，则称其为群密码。显然x可通过可通过k的逆元的逆元求得求得 x=y k-1 令令x k为一群密码，令为一群密码，令fI(x,kB)为一对合密码，以为一对合密码，以Fx,kfI(x kA,kB)为迭代函数，可以为迭代函数，可以III型多轮迭代分组密码。在最后一轮型多轮迭代分组密码。在最后一轮中，另外加了一次群密码运算，用以保证整个加、解密中，另外加了一次群密码运算，用以保证整个加、解密的对合性。的对合性。2023-5-1424III型迭代分组密码型迭代分组密码 轮函数轮函数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

18、 y fI fI x (b)解密解密 kA(r+1)-1 kB(r)(kA(r)-1 kB(1)(kA)-1 2023-5-1425IV型迭代分组密码型迭代分组密码 在在III型密码的轮函数基础上，再增加一个对型密码的轮函数基础上，再增加一个对合置换合置换PI，构成构成IV型迭代分组密码的轮函数型迭代分组密码的轮函数 Fx,kPIfI x kA,kB2023-5-1426IV型迭代分组密码型迭代分组密码 轮函数轮函数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)PIkA(r)-1 PIkA(2)-1 kB(1)(kA(1)-1