DES加密算法.doc

数据加密标准DES(data encryption standard)算法是由美国IBM公司研制的一种分组密码算法，是一个迭代分组密码。DES是一个使用最为广泛的加密算法，虽然从DES出现后又产生了许多常规加密算法，但DES仍是此类算法中最重要的一个。在正式讨论DES算法之前，为了更好的理解算法的实际工作过程，我们先来看一个简化的DES算法，以此加深对DES算法的理解。图6.9 简单DES的加密过程 一、简单DES简单DES的加密算法是以8bit的明文分组和10bit密钥作为输入，产生8bit密文分组作为输出。1、加密过程简单DES的加密过程如图6.9所示。2、加密算法构成： 简单DES的加密算法包括4个基本函数：一个初始置换函数IP；一个fk函数；一个用来交换数据的SW置换函数；一个逆置换函数IP-1。（1）初始置换函数IP 数据原先所在位置IP置换2 6 3 1 4 8 5 7初始置换IP是将明文M中数据的排列顺序按一定的规则重新排列，而生成新的数据序列的过程。如图6.10所示：图6.10 简单DES的初始置换 设8bit数据K各位分别为K1、K2、K3、K4、K5、K6、K7、K8，则经过IP置换后，各位分别为K2、K6、K3、K1、K4、K8、K5、K7。例：设8bit数据为11110011 ，则初始置换的结果为：经IP置换 1111001110111101 （2）fk函数fk函数是多个置换函数和替代函数的组合函数。fk函数将输入它的8bit数据进行分组，分成左4位和右4位，然后进行如下运算。fk（L,R）=（LF（R，SK），R）L 输入的左边4位分组R 输入的右边4位分组 逐位异或（3）F（R，SK）函数F（R，SK）函数是fk函数的核心函数，其中SK是子密钥。F（R，SK）函数的运算方法如下：E/P4 1 2 3 2 3 4 11）扩展/置换E/P图6.11 简单DES的扩展/置换 扩展/置换是将4bit输入数据经过置换和扩展而产生8bit数据的算法，如图6.11所示。2）与8位子密钥SK逐位异或异或运算如图6.12所示。A B 结果0 1 0 01 01 11010图6.12 异或运算 1 0 3 23 2 1 00 2 1 33 1 3 20 1 2 32 0 1 33 0 1 02 1 0 3 S0 = S1= 图6.13 S盒 图6.14 S盒运算 3）S盒输出简单DES算法使用两个S盒S0和S1。如图6.13所示。其运算方法是将4bit数据输入S盒，第一和第四比特数据作为2比特数值，这个数值用来指定S盒的一行。第二和第三比特数据也作为2比特数值，这个数值用来指定S盒的一列。对应S盒中该行该列的数值用二进制表示，既为S盒的2bit输出。其运算方法如图6.14所示。4）P4置换P42 4 3 1由S0和S1产生的4bit数据经P4置换，产生4bit数据的输出。P4置换的方法如图6.15所示。 图6.15 P4置换 （4）交换函数（SW） ： 交换函数SW是将8bit输入数据的左四位与右四位交换位置之后产生8bit数据的输出。其运算方法如图6.16所示。1 0 1 1 1 1 0 11 1 0 1 1 0 1 1 图6.16 SW运算 （5）逆置换函数IP-1 逆置换函数IP-1是将8bit输入数据置换为8bit数据输出。其运算方法如图6.17所示。IP-14 1 3 5 7 2 8 6 图6.17 逆置换函数IP-1 3、子密钥生成 简单DES密钥是使用一个发送方和接收方共享的10bit密钥。运算中使用的两个8bit子密钥就是从这个10bit密钥生成。输入：10bit密钥输出：两个8bit子密钥图6.18 简单DES的子密钥生成 （1）子密钥生成过程 简单DES的两个8bit子密钥的生成过程如图6.18所示。（2）算法构成： P103 5 2 7 4 10 1 9 8 6P86 3 7 4 8 5 10 9 简单DES的子密钥生成算法主要由置换函数P10和置换函数P8这两个置换函数加上循环左移构成。设10bit数据从左到右依次为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10）则置换方式如图6.19所示。101000001010000 0110000001 110001010010000100 0001101000011子密钥K1子密钥K2图6.19 P10和P8置换 图6.20 子密钥的生成 P10（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10）=（k3,k5,k2,k7,k4,k10,k1,k9,k8,k6,）；P8（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10）=（k6,k3,k7,k4,k8,k5,k10,k9）（3）子密钥生成例：设密钥为1010000010 ，则子密钥的生成过程如图6.20所示。4、加密过程举例 设8bit明文为11110011，使用前例中的子密钥进行加密，其过程如图6.21所示。二、DES加密： 在讨论完简单DES加密的基础上，我们来进一步探讨DES的加密过程。1、加密过程 DES的加密过程如图6.22所示，其中的一轮运算要循环16次，每一次循环都执行相同的过程，其具体过程如图6.23所示。2、加密算法的构成： DES的加密算法和简单DES的加密算法相类似，也是主要包括4个基本函数：一个初始置换函数IP；一个fk函数；一个用来交换数据的SW置换函数；一个逆置换函数IP-1。（1）IP置换图6.22 DES算法的一般过程图6.23 DES算法的一个循环与简单DES不同，DES的IP置换是将64bit的输入，经过置换产生64bit的输出。其置换方法如图6.24所示。58 60 62 64 57 59 61 63 50 52 54 56 49 51 53 55 42 44 46 48 41 43 45 47 34 36 38 40 33 35 37 39 26 28 30 32 25 27 29 31 18 20 22 24 17 19 21 23 10 12 14 16 9 11 13 15 2 4 6 8 1 3 5 7 图6.24 IP置换 （2）扩展置换扩展置换是将32bit的输入通过置换与扩展转化为48bit的输出。扩展置换的方法如图6.25所示。 32 4 8 12 16 20 24 28 1 5 9 13 17 21 25 29 2 6 10 14 18 22 26 30 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32 5 9 13 17 21 25 29 1 图6.25 扩展置换 （3）S盒 DES算法使用8个S盒,每个S盒将一个48bit输入经过替代选择产生32bit的输出。如图6.26所示。 S1 14 0 4 15 4 15 1 12 13 7 14 8 1 4 8 2 2 14 13 4 15 2 6 9 11 13 2 1 8 1 11 7 3 10 15 5 10 6 12 11 6 12 9 3 12 11 7 14 5 9 3 10 9 5 10 0 0 3 5 6 7 8 0 13 S2 15 3 0 13 1 13 14 8 8 4 7 10 14 7 11 1 6 15 10 3 11 2 4 15 3 8 13 4 4 14 1 2 9 12 5 11 7 0 8 6 2 1 12 7 13 10 6 12 12 6 9 0 0 9 3 5 5 11 2 14 10 5 15 9 S3 10 13 13 1 0 7 6 10 9 0 4 13 14 9 9 0 6 3 8 6 3 4 15 9 15 6 3 8 5 10 0 7 1 2 11 4 13 8 1 15 12 5 2 14 7 14 12 3 11 12 5 11 4 11 10 5 2 15 14 2 8 1 7 12 S4 7 13 10 3 13 8 6 15 14 11 9 0 3 5 0 6 0 6 12 10 6 15 11 1 9 0 7 13 10 3 13 8 1 4 15 9 2 7 1 4 8 2 3 5 5 12 14 11 11 1 5 12 12 10 2 7 4 14 8 2 15 9 4 14 S5 2 14 4 11 12 11 2 8 4 2 1 12 1 12 11 7 7 4 10 1 10 7 13 14 11 13 7 2 6 1 8 13 8 5 15 6 5 0 9 15 3 15 12 0 15 10 5 9 13 3 6 10 0 9 3 4 14 8 0 5 9 6 14 3 S6 12 10 9 4 1 15 14 3 10 4 15 2 15 2 5 12 9 7 2 9 2 12 8 5 6 9 12 15 8 5 3 10 0 6 7 11 13 1 0 14 3 13 4 1 4 14 10 7 14 0 1 6 7 11 13 0 5 3 11 8 11 8 6 13 S7 4 13 1 6 11 0 4 11 2 11 11 13 14 7 13 8 15 4 12 1 0 9 3 4 8 1 7 10 13 10 14 7 3 14 10 9 12 3 15 5 9 5 6 0 7 12 8 15 5 2 0 14 10 15 5 2 6 8 9 3 1 6 2 12 S8 13 1 7 2 2 15 11 1 8 13 4 14 4 8 1 7 6 10 9 4 15 3 12 10 11 7 14 8 1 4 2 13 10 12 0 15 9 5 6 12 3 6 10 9 14 11 13 0 5 0 15 3 0 14 3 5 12 9 5 6 7 2 8 11 图6.26 DES算法的S盒 （4）置换函数P置换函数P将DES算法中8个S盒输出的共32bit数据经过置换产生32bit的输出，其置换方法如图6.27所示。16 1 2 19 7 15 8 13 20 23 24 30 21 26 14 6 29 5 32 22 12 18 27 11 28 31 3 4 17 10 9 25 图6.27 P置换 （5）IP-1逆置换逆置换函数IP-1负责产生最后的64bit密文分组。运算方法如图6.28所示。40 39 38 37 36 35 34 33 8 7 6 5 4 3 2 1 48 47 46 45 44 43 42 41 16 15 14 13 12 11 10 9 56 55 54 53 52 51 50 49 24 23 22 21 20 19 18 17 64 63 62 61 60 59 58 57 32 31 30 29 28 27 26 25 图6.28 IP-1逆置换 3、子密钥生成 DES子密钥算法如图6.29所示。其中每次循环的具体运算方法如图6.30所示。算法与简单DES的算法类似，具体置换和循环左移的方法如图6.31-6.33所示。图6.30 子密钥生成的一次循环图6.29 DES的子密钥生成算法 57 1 10 19 63 7 14 21 49 58 2 11 55 62 6 13 41 50 59 3 47 54 61 5 33 42 51 60 39 46 53 28 25 34 43 52 31 38 45 20 17 26 35 44 23 30 37 12 9 18 27 36 15 22 29 4 图6.31 置换选择1(PC-1) 14 15 26 41 51 34 17 6 8 52 45 53 11 21 16 31 33 46 24 10 7 37 48 42 1 23 27 47 44 50 5 19 20 55 49 36 3 12 13 30 39 29 28 4 2 40 56 32 图6.32 置换选择2(PC-2) 循环次数 左移比特数 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1 图6.32 左移调度 4、DES算法举例设明文M和密钥K的取值分别如下：M=0000 0100 1011 0101 1101 1001 1100 1110 1010 1100 1000 0110 1111 1000 0101 0011K=0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10111100 1101 1110 1111（1）IP置换M经过IP置换得L01100 1100 1100 011 0 0011 1011 1000 0110R0= 0111 1110 0101 0010 0101 1100 1010 1000密钥K经过置换选择PC-1得C0D0（56位），其中C01111 0000 1100 1100 1010 1010 0000D01010 1010 1100 1100 1111 0000 0000（2）左移置换左移C0、D0得 C1=1110 0001 1001 1001 0101 0100 0001D1=0101 0101 1001 1001 1110 0000 0001 对C1D1进行置换选择PC-2得子密钥K1K1=0000 1011 0000 0010 0110 01111001 1011 0100 1001 1010 0101（3）扩展置换E(R0)=00