对称密码学之现代密码学-DES算法分析
DES算法分析
1.DES加密机制
下图1表示了DES加密的整个机制。对于任意加密方案：总有两个输入：明文和**。DES的明文长为64位，**长为56位（实际上该密码函数希望采用64位的**，然而却仅仅采用了56位，其余8位可以用作奇偶校验或随意设置）。
从图1左半部分，可见明文的处理经过了3个阶段。首先，64位的明文经过初始置换IP而被从新排列。然后进行16轮相同函数的作用。每轮作用都有置换和代替。最后一轮迭代的输出有64位，它是输入明文和**的函数。其左半部分和右半部分互换产生预输出。最后预输出再与初始置换IP互逆的置换IP-1作用产生64位的明文。
图1的右半部分给出了56位**产生的过程。首先**经过一个置换后，在经过循环左移和一个置换分别得到各轮的子**Ki用于各轮的迭代。每轮的置换函数都一样，但是由于**的循环移位是的各轮的子**互不相同。
2.DES基本结构
DES基本结构如图2所示，具体过程下面进行一一详解。
2.1 子**的产生
首先由于DES是16轮循环，所以需要由64bit的随机**Key生成16个子**Ki（i从0~15），Key共64bit，但是其每个字节的最后一位都用不到（即第8、16、24、32、40、48、56、64位共8位），所以先通过初始置换将64bit的**转换为56bit。而转换是根据**转换表，如表1所示：
该表共有56个元素（可以看到不包含8、16、24、32、40、48、56、64），代表了转换后的56bit的位置。而对应位置的数字x，表示转换前64bit**的下标+1。比如：第1位（下标为0，位置为1）的值为57;获取原来的第57位的bit值（0或1），作为置换后的第1位的bit值。依次类推（表的读取方式为从左到右，从上到下，如：第3行第5个为置换后的第2*14+5=33位）。
经过置换的key变为56bit，该56bit分为左右两半部分：left_key和right_key，各28bit，然后左右两部分分别循环左移一定位数n。n的大小根据子**Ki的下标决定（i从0~15），如表2所示（最多循环左移两位，最少一位）：
经过移位的左右两部分合并为56bit，然后经过压缩置换将56bit压缩为48bit，则产生一个子**Ki，经过16轮循环产生16个子**（对应DES结构图）。而压缩置换的压缩表如表3所示：
2.2 初始置换与扩展置换
64bit的明文分组，首先经过明文初始置换表（64bit->64bit的置换），打乱原有明文bit顺序。明文初始置换表如表4所示：
经过初始置换，将64bit明文分组分为左右两部分，各32bit。下一轮的左半部分是本轮的右半部分；下一轮的右半部分：是本轮的右半部分和子**Ki经过F函数运算的结果，再和本轮的左半部分进行异或得到的，即：
而F函数中第一步是进行扩展置换，将32bit的rdata扩展成为48bit的exp_data，扩展置换表如表5所示：
经过扩展置换的明文rdata和经过压缩置换的子**Ki均为48bit，二者进行异或以后进入下一步操作：S盒置换。
2.3 S盒置换、P盒置换与末置换
由于上一步的异或结果是48bit，我们要将异或结果重新压缩到32bit并经过P盒置换（32bit->32bit）后，与原有左半部分32bit异或得到下轮的右半部分。而48bit压缩到32bit不是用一张长度为32的置换表从48bit信息中选取32位进行置换。而是通过8个S盒进行8组6bit->4bit的置换（8*4=32bit）：即将48bit按顺序分为8组，每组6bit。然后将每一组的6bit信息输入对应的S盒，输出4bit的信息，8组输出合并为32bit的压缩结果。8个S盒的内容均不一样，但是使用方式都是一样的，S盒如下图3所示：
使用方式为输入6bit为B1B2B3B4B5B6，B1B6两比特（00-11，0-3）定位S盒的行，B2B3B4B5（0000-1111,0-15）定位S盒的列，行和列的组合定位到S盒中的具体的元素（元素值均为0-15，即0000-1111四比特）。该值的4bit 信息作为输出的4bit。如：S1盒的输入为101011，则行为11 = 3，列为0101 = 5，即（3,5）= 9 = 1001，则输出为1001。
经过8组6bit到4bit的转换之后，将合并的32bit经过P盒置换提高混乱度，P盒置换表如表7所示：
在十六轮运算完毕之后，需要进行左右两部分置换（其实是：最后一轮不用左右置换，但是16轮循环中为一种模式，即均置换。所以再左右置换一次相当于最后一轮没置换）。然后将结果做末置换（类似于初始置换），最终的结果就是明文分组的DES加密结果，末置换表如表8所示：
这就是DES整个算法的分析过程。