第二章 分 组 密 码,分组密码概述分组密码是将明文消息序列m1， m2， m1k, 分成等长的消息组(m1， m2， mn)，(mn+1， mn+2， m2n), 在密钥控制下，按固定的算法Ek一组一组进行加密。加密 后输出等长密文组（y1， ，ym ), (ym+1， ，y2m) ,第二章 分 组 密 码,加 密 算 法,密 钥 k,明文(x1， x2， xn),密文(y1， y2， yn),加密一组明文的过程,第二章 分 组 密 码,分组密码设计原则 一般设计原则 混乱 扩散 实现的设计原则 软件 硬件,第二章 分 组 密 码,分组密码的结构; 分组密码原则“复杂” 难于分解“简单” 易于实现 选代密码：,X = Y(0),F,F,F,密钥K,Y(2),Y(r-1),Y(1),Y(r),Z(2),Z(1),Z(r),第二章 分 组 密 码,分组密码两种类型的总体结构： Feistal网络：只改变输入分组的一半 SP网络: 改变整个数据分组,典型的分组密码算法 DES数据加密标准DES （Data Encryption Standard )DES密码体制 最有名的密码算法 第一个被公开的现代密码 由IBM于1971年至1972年研制成功 分组长度：64比特 密钥长度：56比特,第二章 分 组 密 码,DES是一个对称算法：加密和解密用的是同一算法。 目前DES已被视为不安全，普遍使用的是变种triple DES，即对64比特分组加密三次，每次用不同的密钥，密钥长度总共168比特。,第二章 分 组 密 码,第二章 分 组 密 码,比较著名的对称加密算法,2. DES算法描述1) DES算法规定DES密钥长度规定为64位，但实际只使用56位，其余的八位用作奇偶校验位。具体地说，在64位密钥中8的倍数位是校验位，即第8，16，24，32，40，48，56和64位是校验位，剩下的56位则作为真正的密钥。,第二章 分 组 密 码,DES是一个分组密码。它的入口参数有三个，分别是Key、Data和Mode。其中Key为64位，是 DES算法的工作密钥；Data为64位，是要被加密或被解密的数据；Mode为DES的工作方式，分加密或解密两种。,第二章 分 组 密 码,在通信网络的两端，双方约定一致的Key，在通信的源点用Key对明文数据进行DES加密，然后以密文形式在公共通信网(如电话网)中传输到通信网络的终点，密文数据到达目的地后，用同样的Key对密文数据进行解密，便恢复了明文数据。,第二章 分 组 密 码,2) DES加密过程DES算法加密的过程大致可以分为三部分：初始置换、16次迭代过程和逆置换，其中在16次迭代过程中还必须从密钥中提取子密钥，将32位的右半部分扩展为48位。具体算法过程如下所示。,第二章 分 组 密 码,第二章 分 组 密 码,DES加密过程,初始置换, , , , ,密钥（1）,密钥（2）,密钥（3）,密钥（16）,64位明文,逆初始置换,第二章 分 组 密 码,DES算法加密过程:,初始置换：密钥置换：密钥 64位 56 48 扩展置换：Ri 从 32 48S 盒代替：48 32P 盒置换：末置换：,第二章 分 组 密 码,第二章 分 组 密 码,(1) 初始置换：在表2-3中的IP的置换中将明文的第58位移到第一位，将第50位移到第二位，将第42位移到第三位依次类推。而在表2-3中的IP的逆置换中，将第一位拉回到第58位，第二位拉回到第50位，第三位拉回到第42位，考察其他的位，也可以得到同IP初始置换相对应的位。所以，称IP是IP的逆置换。因而，DES算法既可以用于加密，又可以用于解密。,表2-2 初始置换IP,第二章 分 组 密 码,表2-3 逆初始置换IP-1,第二章 分 组 密 码,(2) 迭代过程T。在DES算法中，一共要作16次迭代过程，顺序记为Ti 设第i次迭代T的输入为，其中、R分别是左半部分32位和右半部分32位，则第i次迭代的输出为Li = Ri-1 Ri = Li-1 + f (Ri-1, Ki ) 第i次迭代的输出作为第i+1次迭代的输入，进行下一次迭代。,第二章 分 组 密 码,第三章 分 组 密 码,f,f是将一个32位的符号串转换为另一个32位的符号串的运算函数，其流程如图2-4 所示。功能的第一步是将32位的输入转换为48位，并与迭代密钥按位异或，再把得到的48位分为八组，每组六位，分别通过S1，S2，S8输出，每组只输出四位，组合成32位，这32位最后通过置换输出。在计算时，需要计算出。,第三章 分 组 密 码,图2-4 f(Ri-1,ki)的计算过程,第三章 分 组 密 码,第三章 分 组 密 码,图9-4中扩增排列的选位表描述了如何将32位转换为48位的方法，总共八行六列。如果，则E(Ri-1)=r32r1r2r3r32 r1，如表2-5所示。,表2-5 扩增排列E(R),数据在S盒中执行混淆动作。八个S盒中的每一个S盒都是将六位的输入映射为四位的输出。以S1盒为例，盒中的数据排列如表所示。,第三章 分 组 密 码,S盒的工作原理是这样的：若输入为101101 ，其中首尾(11)两位二进制数转换为十进制数(3)作为行，中间四位(0110)二进制数转换为十进制数(6)作为列。假设从表2-6中查得的数为m，0m15，m换为四位二进制数，则就是输入的四位输出。,第三章 分 组 密 码,例如，Sl盒的输入为101101，在盒中的第三行第六列上的数字是1，用二进制数表示为0001，则4位输出为0001。 注意：S盒的行和列序号都是从0开始的。,第三章 分 组 密 码,单纯置换是对输入的32位进行置换，产生32位输出。如果输入为Hi=r1r2r32，则P(Hi)=h16h7h4h25，如表2-6所示。,表2-6 单纯置换P(H),第三章 分 组 密 码,(3) Ki是由56位的密钥K确定的48位密钥，每一次迭代使用不同的48位密钥。密钥Ki的生成过程如图所示。,第二章 分 组 密 码,密 钥 的 产 生 过 程,初始密钥 K ( 64 bit ),PC - 1,LS1,C0(28 bit ) D0(28 bit ),LS1,C1 D1,LS2,LS2,LS16,LS16,C16 D16,PC - 2,K1,PC - 2,K16,第三章 分 组 密 码,子密钥的初始值为64位。DES算法规定其中的第8、16、24、32、40、48、56、64位(共8位)为奇偶校验位，不参与DES运算。因此，子密钥的实际可用位数为56位。即经过缩小选择换位1之后，由64位变成56位。,第三章 分 组 密 码,将56位密钥分成两部分的28位密钥，然后这两部分分别循环左移一位或两位，由圈数决定。移位后，再从56位中选出48位。由于每次都移位，因此每次产生的子密钥都不同。,第二章 分 组 密 码,缩小选择换位表为八行七列，共56个元素，分为两个部分：上面四行为L0，下面四行为R0，每部分都是28位。若密钥k=d1d2d64，则L0=d57d49d36，R0=d63d55d4。其中缩小选择换位1如表2-7所示。然后分别进行第一次循环左移，得到L1、R1。将28位的L1、28位的R1合并得到56位。经过缩小选择换位2如表2-8所示，得到48位的密钥K1。同样方法可以得到密钥K2，K3，K16。,第二章 分 组 密 码,表2-7 缩小选择换位1(PC-1),第二章 分 组 密 码,表2-8 缩小选择换位2,DES解密加密和解密使用相同算法不同之处是密钥的次序相反 归纳如下：R16L16=IP(64 bit密文)Ri-1=Li，Li-1=Rif(Ri-1，ki)，i=1, 2, ，6464 bit明文=IP-1(L0R0),第二章 分 组 密 码,第三章 分 组 密 码,DES 的工作模式（P28） 电码本模式（ECB） 密码分组链接模式（CBC） 密文反馈方式（CFB） 输出反馈模式（OFB）,电码本模式（ECB）,电码本模式（ECB）,密码分组链接模式（CBC）,密码分组链接模式（CBC）,密文反馈方式（CFB）,密文反馈方式（CFB）,输出反馈模式（OFB）,输出反馈模式（OFB）,二重DES 及其问题,二重DES 及其问题,明 文,三重DES密文,DES加密 密钥 = K1,DES解密 密钥 = K2,DES加密 密钥 = K1 / K3,三重DES (P30),第三章 分 组 密 码,第三章 分 组 密 码,差分分析法： 基本思想：通过分析 特定明文差分对相应密文差分影响来获取可能性最大的密钥。 定义 差分分析实例,第三章 分 组 密 码,线性密码分析： 基本思想 攻击方法,第三章 分 组 密 码,其它分组密码国际数据加密算法（International Data Encryption Algorithm IDEA )IDEA是使用一个密钥对64位数据块进行加密的常规共享密钥加密算法。IDEA使用128位密钥进行操作。与DES不同的是IDEA不使用置换。,第三章 分 组 密 码,第三章 分 组 密 码,IDEA 算法1. 混淆特性：三个运算 （1） 异或 （2） 模216加 （3） 模216+1 乘 扩散特性：MA运算结构2. 加密过程3. 解密过程,第三章 分 组 密 码,高级数据加密标准 ( AES Rijndael ) AES的设计思想和功能 算法说明 加密流程：,第三章 分 组 密 码,其他算法： Blowfish Gost RC5,第三章 分 组 密 码,第三章 分 组 密 码,第三章 分 组 密 码,