DES详解_p置换

1.DES算法简介

　　DES算法为密码体制中的对称密码体制，又被称为美国数据加密标准。

　　DES是一个分组加密算法，典型的DES以64位为分组对数据加密，加密和解密用的是同一个算法。

　　密钥长64位，密钥事实上是56位参与DES运算（第8、16、24、32、40、48、56、64位是校验位，使得每个密钥都有奇数个1），分组后的明文组和56位的密钥按位替代或交换的方法形成密文组。

　　DES算法的主要流程如下图所示，本文按照流程依次介绍每个模块。

2.IP置换

　　IP置换目的是将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位。

　　置换规则如下表所示：

　　表中的数字代表原数据中此位置的数据在新数据中的位置，即原数据块的第1位放到新数据的第58位，第2位放到第50位，……依此类推，第64位放到第7位。置换后的数据分为L0和R0两部分，L0为新数据的左32位，R0为新数据的右32位。

　　设转换前的数据位D1D2D3…D64，则IP置换后的结果为L0=D58D50…D8，R0=D57D49…D7。0x0000 0080 0000 0002转换后的结果为0x0002 0000 0000 0001，且L0=0x0002 0000，R0=0x0000 0001。置换步骤如下：

　　原数据第33位为1，置换表第33位为64，因此将1放到新数据的第64位；原数据第63位为1，置换表第63位为7，因此将1放到新数据的第7位；其余值为0的位按此置换。要注意一点，位数是从左边开始数的，即最0x0000 0080 0000 0002最左边的位为1，最右边的位为64。

3.密钥置换

　　不考虑每个字节的第8位，DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。产生的56位密钥由下表生成（注意表中没有8,16,24，32,40,48,56和64这8位）：

　　在DES的每一轮中，从56位密钥产生出不同的48位子密钥，确定这些子密钥的方式如下：

　　1).将56位的密钥分成两部分，每部分28位。

　　2).根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数如下表：

　　移动后，从56位中选出48位。这个过程中，既置换了每位的顺序，又选择了子密钥，因此称为压缩置换。压缩置换规则如下表（注意表中没有9，18，22，25，35，38，43和54这8位）：

         置换方法同上，此处省略。

4.E扩展置换

　　扩展置置换目标是IP置换后获得的右半部分R0，将32位输入扩展为48位(分为4位×8组)输出。

　　扩展置换目的有两个：生成与密钥相同长度的数据以进行异或运算；提供更长的结果，在后续的替代运算中可以进行压缩。

　　扩展置换原理如下表：

　　表中的数字代表位，两列黄色数据是扩展的数据，可以看出，扩展的数据是从相邻两组分别取靠近的一位，4位变为6位。靠近32位的位为1，靠近1位的位为32。表中第二行的4取自上组中的末位，9取自下组中的首位。

　　我们举个例子看一下(虽然扩展置换针对的是上步IP置换中的R0，但为便于观察扩展，这里不取R0举例)：

　　输入数据0x1081 1001，转换为二进制就是0001 0000 1000 0001B，按照上表扩展得下表

　　表中的黄色数据是从临近的上下组取得的，二进制为1000 1010 0001 0100 0000 0010 1000 1010 0000 0000 0000 0010B，转换为十六进制0x8A14 028A 0002。

       扩展置换之后，右半部分数据R0变为48位，与密钥置换得到的轮密钥进行异或。

5.S盒代替

　　压缩后的密钥与扩展分组异或以后得到48位的数据，将这个数据送人S盒，进行替代运算。替代由8个不同的S盒完成，每个S盒有6位输入4位输出。48位输入分为8个6位的分组，一个分组对应一个S盒，对应的S盒对各组进行代替操作。

　　一个S盒就是一个4行16列的表，盒中的每一项都是一个4位的数。S盒的6个输入确定了其对应的输出在哪一行哪一列，输入的高低两位做为行数H，中间四位做为列数L，在S-BOX中查找第H行L列对应的数据(<32)。

　　8个S盒如下：

　　S盒1

　　S盒2

　　S盒3

　　S盒4

　　S盒5

　　S盒6

　　S盒7

　　S盒8

 

　　例如，假设S盒8的输入为110011，第1位和第6位组合为11，对应于S盒8的第3行；第2位到第5位为1001，对应于S盒8的第9列。S盒8的第3行第9列的数字为12，因此用1100来代替110011。注意，S盒的行列计数都是从0开始。

　　代替过程产生8个4位的分组，组合在一起形成32位数据。

       S盒代替时DES算法的关键步骤，所有的其他的运算都是线性的，易于分析，而S盒是非线性的，相比于其他步骤，提供了更好安全性。

 

6.P盒置换

　　S盒代替运算的32位输出按照P盒进行置换。该置换把输入的每位映射到输出位，任何一位不能被映射两次，也不能被略去，映射规则如下表：

　　表中的数字代表原数据中此位置的数据在新数据中的位置，即原数据块的第16位放到新数据的第1位，第7位放到第2位，……依此类推，第25位放到第32位。

　　例如0x10A1 0001进行P盒置换后变为0x8000 0886。

　　0x10A1 0001表现为表的形式（第一位位于左上角）原来为

　　经P盒变换后为

　　即1000 0000 0000 0000 0000 1000 1000 0110B，十六进制为0x8000 0886。

 

　　最后，P盒置换的结果与最初的64位分组左半部分L0异或，然后左、右半部分交换，接着开始另一轮。

 

7.IP^-1末置换

　　末置换是初始置换的逆过程，DES最后一轮后，左、右两半部分并未进行交换，而是两部分合并形成一个分组做为末置换的输入。末置换规则如下表：

　　置换方法同上，此处省略。

 

　　经过以上步骤，就可以得到密文了。

 以上的内容来自于“http://www.cnblogs.com/songwenlong/p/6528025.html”，博主的文章写的很好，所以特意作为了自己的笔记。

以下，就是自己的一点补充，对整个DES加密的过程的：

首先，将64位的明文讲过p置换：

IP[] = {58, 50, 42, 34, 26, 18, 10, 2,
   60, 52, 44, 36, 28, 20, 12, 4,
   62, 54, 46, 38, 30, 22, 14, 6,
   64, 56, 48, 40, 32, 24, 16, 8,
   57, 49, 41, 33, 25, 17, 9,  1,
   59, 51, 43, 35, 27, 19, 11, 3,
   61, 53, 45, 37, 29, 21, 13, 5,
   63, 55, 47, 39, 31, 23, 15, 7};这个的意思就是将原来的58个换到第一个上。然后，会分出左半部分和右半部分，我们用l[32],r[32]表示，在将r[32]通过E扩展到48位，这样做是为了与48位的轮密钥异或才这样做的，

E={32,  1,  2,  3,  4,  5,
      4,  5,  6,  7,  8,  9,
      8,  9, 10, 11, 12, 13,
     12, 13, 14, 15, 16, 17,
     16, 17, 18, 19, 20, 21,
     20, 21, 22, 23, 24, 25,
     24, 25, 26, 27, 28, 29,
     28, 29, 30, 31, 32,  1};这就是E置换，就是将

就是这个规律，这样得到的48位的r[48]与轮密钥异或。在经过s盒和p盒的处理，再与l[32]异或就得到了下一次的r[32],而下一次的l[32]就是上一次的r[32]，s盒一共有8个，是将6位的二进制转化为4位的输出：我们如何使用s盒那，就是将输入的8位中的最高位和最低位组成的数作为行，中间的4位组成的数作为列，通过这个行列找到s和中所对应的数，输出就是了，p盒是和前面的置换盒是一样的。

而轮换密钥的得到就是，首先将64位的密钥，通过pc置换盒置换，其实就是将64位中的奇偶校验位取出，这样过来的话就是56位了，在分成二部分，每部分就是28位的，这二部分都是要进行循环左移的，左移的位数是根据轮数来决定的，左移后的二部分在合并成一部分，但是这个是56位的，所以通过压缩置换pc2将其变为48位的，这样就形成了轮换密钥，将这二部分再进行循环左移形成下一次的二部分，以此就会得到这些轮密钥。通过这些，我们进行16轮这样的加密迭代。最后输出的还要进行一次置换，p-1置换，置换完后，输出的64位才是密文。