分组密码 41分组密码设计原则和设计方法

1、密码学第四章 分组密码主要内容：主要内容：分组密码的基本概念，分组密码的基本分组密码的基本概念，分组密码的基本设计原则和设计方法，典型的分组密码算法，常见设计原则和设计方法，典型的分组密码算法，常见的分组密码攻击方法，以及分组密码的工作模式等。的分组密码攻击方法，以及分组密码的工作模式等。重点：重点：数据加密标准数据加密标准(DES)、高级加密标准、高级加密标准(AES)。 希望希望大家能理解分组密码设计的原理与方法，大家能理解分组密码设计的原理与方法，掌握掌握DES、AES等分组密码算法，了解常见的分组等分组密码算法，了解常见的分组密码安全性分析方法。密码安全性分析方法。第四章 分组密码4.

2、1 分组密码设计原则和设计方法 分组密码概述分组密码概述分组密码设计原则分组密码设计原则 分组密码设计方法分组密码设计方法4.1 分组密码设计原则和设计方法 分组密码分组密码是将明文数据序列按固定长度是将明文数据序列按固定长度进行分组，然后在同一密钥控制下用同一算进行分组，然后在同一密钥控制下用同一算法逐组进行加密，从而将各个明文分组变换法逐组进行加密，从而将各个明文分组变换成一个长度固定的密文分组的密码。成一个长度固定的密文分组的密码。一、分组密码概述一、分组密码概述 二进制明文的分组长度称为该分组密码二进制明文的分组长度称为该分组密码的的分组长度分组长度或或分组规模分组规模。同样，二进制密

3、钥。同样，二进制密钥的长度称为分组密码的的长度称为分组密码的密钥长度密钥长度或或密钥规模密钥规模。主要特点：主要特点：同一密钥，同一加密算法，同一密钥，同一加密算法， 分组加密，分组长度固定。分组加密，分组长度固定。 1212122nnnnmmx xx xxx 加加密密算算法法k加加密密算算法法k 1212122ccssssy yy yyy 明文明文密文密文加密加密：(),1,2,ikicEmi12,cc c12mm m一、分组密码概述一、分组密码概述 明文分组长度为明文分组长度为n，密文分组长度为，密文分组长度为s，若若n s，则称其为有数据，则称其为有数据压缩压缩的分组密码；的分组密码；若

4、若n s，则称其为有数据，则称其为有数据扩展扩展的分组密码。的分组密码。本章我们都取本章我们都取 n = s例例1 移位密码中的电文倒置法移位密码中的电文倒置法明文为：明文为： 2346 3498密文为：密文为： 6432 8943密钥（密钥（4321）一、分组密码概述一、分组密码概述例例2 代替密码代替密码 明文为：明文为： 2346 3498密文为：密文为： 4560 5628一、分组密码概述一、分组密码概述 安全原则安全原则 实现原则实现原则二、分组密码基本设计原则二、分组密码基本设计原则 安全原则安全原则二、分组密码基本设计原则二、分组密码基本设计原则 安全性安全性是分组密码设计时应考

5、虑的最重要因是分组密码设计时应考虑的最重要因素。人们一般将素。人们一般将Shannon提出的提出的混乱原则混乱原则和和扩散扩散原则原则作为保证分组密码安全性的两个基本设计原作为保证分组密码安全性的两个基本设计原则。则。混乱原则混乱原则1.安全原则安全原则扩散原则扩散原则二、分组密码基本设计原则二、分组密码基本设计原则 混乱原则混乱原则就是将就是将密文、明文、密钥密文、明文、密钥三者之三者之间间的统计关系和的统计关系和代数关系代数关系变得尽可能复杂，保变得尽可能复杂，保证密钥和明文的任何信息既不能由密文利用统证密钥和明文的任何信息既不能由密文利用统计关系确定出来，又不能由密文利用代数方法计关系确

6、定出来，又不能由密文利用代数方法确定出来。确定出来。( )( ,)kcE mf k m二、分组密码基本设计原则二、分组密码基本设计原则 可进一步理解为：可进一步理解为：（1 1）当前明文不能由已知的明文、密文及）当前明文不能由已知的明文、密文及少许密钥比特代数地表示出来。少许密钥比特代数地表示出来。（2 2）当前）当前密钥不能由已知的明文、密文及密钥不能由已知的明文、密文及少许密钥比特统计地表示出来。少许密钥比特统计地表示出来。 混乱原则使得分组密码算法有足够的混乱原则使得分组密码算法有足够的“非线性非线性”因素。因素。二、分组密码基本设计原则二、分组密码基本设计原则 扩散原则要求人们设计的密

7、码应使得每个扩散原则要求人们设计的密码应使得每个明文明文比特和比特和密钥密钥比特影响尽可能多的比特影响尽可能多的密文密文比特。比特。 扩散原则应将明文的统计规律和结构规律扩散原则应将明文的统计规律和结构规律散射到相当长的一段统计中去。散射到相当长的一段统计中去。二、分组密码基本设计原则二、分组密码基本设计原则 （1 1）明文和密钥中的每一位影响密文中的）明文和密钥中的每一位影响密文中的尽可能多的位；尽可能多的位； （2 2）密文中的每一位都受到明文和密钥中）密文中的每一位都受到明文和密钥中的尽可能多位的影响。的尽可能多位的影响。 扩散原则使得扩散原则使得每个明文比特和密钥比特均每个明文比特和密

8、钥比特均应影响密文的所有比特应影响密文的所有比特。二、分组密码基本设计原则二、分组密码基本设计原则 实现原则实现原则二、分组密码基本设计原则二、分组密码基本设计原则 硬件硬件实现原则实现原则2.实现原则实现原则 软件软件实现原则实现原则二、分组密码基本设计原则二、分组密码基本设计原则硬件实现原则硬件实现原则 硬件实现分组密码，通常是硬件实现分组密码，通常是将密码算法做将密码算法做成一个专用的超大规模集成电路芯片成一个专用的超大规模集成电路芯片。这可使。这可使加、脱密运算高速完成，但需大批量生产方可加、脱密运算高速完成，但需大批量生产方可降低成本。因此，硬件实现适合对信息快速、降低成本。因此，硬

9、件实现适合对信息快速、实时进行处理的系统，以及可大规模生产的时实时进行处理的系统，以及可大规模生产的时候。候。二、分组密码基本设计原则二、分组密码基本设计原则硬件实现原则硬件实现原则 用硬件实现的分组密码应遵循下述原则：用硬件实现的分组密码应遵循下述原则：(1) (1) 加、脱密算法结构相同；加、脱密算法结构相同；(2) (2) 结构的规则性；结构的规则性；(3) (3) 设计成迭代型；设计成迭代型；(4) (4) 选择易于硬件实现的编码环节，避免硬件选择易于硬件实现的编码环节，避免硬件难于实现的编码环节。难于实现的编码环节。二、分组密码基本设计原则二、分组密码基本设计原则软件实现原则软件实现

10、原则 软件实现分组密码，软件实现分组密码，成本较低且可以灵活地成本较低且可以灵活地编程编程，但其速度一般没有硬件实现快。，但其速度一般没有硬件实现快。 用软件实现的分组密码应遵循下述原则：用软件实现的分组密码应遵循下述原则：(1) (1) 加、脱密加、脱密算法结构算法结构的相似性；的相似性；(2) (2) 使用子块；使用子块；(3) (3) 设计成迭代型；设计成迭代型；(4) (4) 使用既简单又易于软件实现的运算。使用既简单又易于软件实现的运算。二、分组密码基本设计原则二、分组密码基本设计原则 对一个分组密码，对一个分组密码，安全原则安全原则要求其实现足够要求其实现足够的的混乱混乱和和扩散扩

11、散，实现原则实现原则要求其要求其易于软件和易于软件和(或或)硬件实现硬件实现。 Shannon提出提出乘积密码乘积密码的思想。的思想。乘积密码的乘积密码的基本思想基本思想是通过将一个是通过将一个易于实现的易于实现的具有一定混乱具有一定混乱和扩散结构的和扩散结构的较弱的密码函数较弱的密码函数进行进行多次迭代多次迭代来来产产生一个强的密码函数生一个强的密码函数。 三、分组密码设计方法三、分组密码设计方法（一）（一）乘积密码乘积密码 Shannon在在1949提出，其主要思想就是通过提出，其主要思想就是通过简单密码的乘积来组合密码体制。简单密码的乘积来组合密码体制。 1111(, ,)SM C K

12、E D2222(, ,)SM C KE D假设假设 M= C S1和和 S2的乘积密码体制的乘积密码体制 S1S2定义为定义为：1212(,)SSM C KKE D密钥形式为：密钥形式为：K= ( K1，K2 ) 三、分组密码设计方法三、分组密码设计方法加密和解密规则定义如下加密和解密规则定义如下： 1221(,)( )( )( )KK KKKExExEExy1212(,)( )( )( )KK KKKDyDyDDyx注意：注意：解密次序与加密次序相反解密次序与加密次序相反 12122111(,)( )( )( )K KKKKKKKDyDDEExDExx三、分组密码设计方法三、分组密码设计方法

13、例例3: (乘法密码乘法密码) )设设 M=C=Z261)26,gcd(:26aZaK对于对于 ，明文明文 x，密文密文 y，定义定义：aK( )(mod26)aExax1( )(mod26)aDya y例例4: (移位密码移位密码) )设设 M=C=K=Z26对于对于 ，明文，明文 x，密文，密文 y，定义，定义：kK( )()(mod26)kExxk( )()(mod26)kDyyk三、分组密码设计方法三、分组密码设计方法 假设假设 S1 是乘法密码，是乘法密码， S2 是移位密码，很容是移位密码，很容易看出易看出 S1 S2 是仿射密码是仿射密码。对于对于S1 S2 ，其密钥形式为，其密

14、钥形式为（a, k） ( , )( )()(mod26)a kExaxk对于对于S2 S1 ，其密钥形式为，其密钥形式为（k, a） ( , )( )()(mod26)()(mod26)k aExa xkaxak三、分组密码设计方法三、分组密码设计方法 如果将密码体制如果将密码体制 S 和自己做乘积，得到密码和自己做乘积，得到密码体制体制 SS，记为，记为S 2。如果做。如果做 n 重乘积，得到的密重乘积，得到的密码体制记为码体制记为S n。 如果如果S 2= S，称该密码体制是幂等的。，称该密码体制是幂等的。 如果密码体制是幂等的，使用乘积系统就毫如果密码体制是幂等的，使用乘积系统就毫无意义

15、，这是因为使用多余的密钥，但并不能提无意义，这是因为使用多余的密钥，但并不能提高更多的安全性。高更多的安全性。 如果密码体制不是幂等的，多次乘积就有可如果密码体制不是幂等的，多次乘积就有可能提高安全性。通常是将能提高安全性。通常是将代替密码代替密码和和置换密码置换密码做做乘积。乘积。三、分组密码设计方法三、分组密码设计方法（二）（二）迭代密码迭代密码 当今大多数分组密码都是乘积密码，乘积密当今大多数分组密码都是乘积密码，乘积密码通常伴随一系列置换与代替操作，常见的乘积码通常伴随一系列置换与代替操作，常见的乘积密码是迭代密码。密码是迭代密码。 迭代密码通过将一个弱的密码函数迭代密码通过将一个弱的

16、密码函数(称为圈函称为圈函数、轮函数等数、轮函数等)迭代若干次，产生一个强的密码函迭代若干次，产生一个强的密码函数，既能快速、有效地实现，又能使明文和密钥数，既能快速、有效地实现，又能使明文和密钥得到必要的混乱和扩散。得到必要的混乱和扩散。三、分组密码设计方法三、分组密码设计方法1kF2krkFFF 称为圈变换、圈函数或轮称为圈变换、圈函数或轮函数，函数，r 称为迭代次数、圈称为迭代次数、圈数或轮数。数或轮数。12,rk kk是是 r 个圈子密钥个圈子密钥三、分组密码设计方法三、分组密码设计方法 在设计圈函数时，要充分在设计圈函数时，要充分利用利用代替密码代替密码( (实现混乱实现混乱) )和

17、和移移位密码位密码( (实现扩散实现扩散) )各自的优点，各自的优点，抵消各自的缺点，保证通过多抵消各自的缺点，保证通过多次迭代，形成一个强的分组密次迭代，形成一个强的分组密码算法。码算法。 对于一个给定的密钥编排方案，圈函数对于一个给定的密钥编排方案，圈函数 F的输入为圈密钥的输入为圈密钥kr和当前状态和当前状态wr-1，下一个状态，下一个状态定义为：定义为：wr=F(wr-1,kr)。初态。初态 w0定义为明文定义为明文 x，密文密文y定义为经过定义为经过 r 轮后的状态。轮后的状态。w0 xw1F(w0,k1)w2F(w1,k2)wr-1F(wr-2,kr-1)wrF(wr-1,kr)y

18、wr加密过程：加密过程： 解密过程：解密过程： wrywr-1F-1(wr,kr)wr-2F-1 (wr-1,kr-1)w1F-1 (w2,k2)w0F-1 (w1,k1)xw0 三、分组密码设计方法三、分组密码设计方法 迭代密码迭代密码的常见模型有的常见模型有S-P网络网络(代代替替-置换网络置换网络)、 Feistel网络网络等。等。 三、分组密码设计方法三、分组密码设计方法（三）（三）代替置换网络代替置换网络（S-PN） 一个一个S-PN就是一类特殊的迭代密码。设就是一类特殊的迭代密码。设l和和m都是正整数，明密文都是长为都是正整数，明密文都是长为lm的二元向量，一的二元向量，一个个S-PN包含两个变换，分别记为包含两个变换，分别记为s和和p。:0,10,1lls实现实现 l 比特的代替，即比