[密码学]DES算法过程描述

DES背景

DES算法是第一个公开的密码算法，它是一个迭代型分组密码算法，分组长度64比特，密钥长度64比特，有效密钥长度56比特，迭代圈数16圈，圈密钥长度48比特。

DES算法概述

基本流程

DES算法的基本流程如下图所示，对于一个64位的分组（用m1,m2...m64分别表示第1到第64个比特），首先对它进行初始置换，然后进行16圈的迭代，迭代中每一圈的密钥不同，分别是k1，k2。。。k16。之后对结果进行逆初始置换，得到密文c1,c2...c64。如下图所示（来自老师上课课件）：

初始置换和逆初始置换

对于明文M = m1m2...m64，按照下图所示的初始置换IP指示的顺序从输出中取出指定的位放在这一位上，得到输出，比如c1 = c58，c2=c50.。。。以此类推
逆初始置换是初始置换的逆变换，用表格表示如下图，
设输入为m1m2...m64，输出为c1c2...c64，则 c1c2c3c4c5c6c7c8 = m40m8m48m16m56m24m64m32 ... 它的效果和初始置换刚好互逆，即如果把初始置换的输出作为它的输入，则输出为初始置换的输入。

圈函数

初始置换之后的输出要进行16圈迭代。 圈函数使用的是Feistel模型，它的数学描述如下：
第1,2.。。。15圈的圈加密结构图如下
每一圈迭代过程中：

• 输出的左32位就是输入的右32位
• 输出的右32位是输入的右32位和圈密钥k进行f函数运算后和输入左32位异或运算得到。

圈函数

f函数

f函数的数学表达式如下
f函数的运算流程如下图所示：

• 先对右32位输入进行E盒运算得到48位输出
• 再把运算结果和48位的圈密钥进行异或之后输入到s1,s2...s8盒中
• 每个S盒都是6进4出（输入为6比特，输出4比特），综合得到32位输出
• 把结果输入到P盒中，进行P盒置换，最后得到32位输出。

E盒扩展

E盒扩展的作用是把32比特的输入扩展成48比特，扩展的方式如下图所示，把输入的32比特从左到右编号为1,2,3.。。。32，并把 这32比特写成每行4个，共8行的形式。然后把第i-1行最右比特和第i+1行最左比特添加到第i行的左边和右边，这样就得到了48bit的输出。（即c1c2c3c4c5c6 = m32m1m2m3m4m5 .... 以此类推)。

S盒代替——压缩替代变换

S盒的作用是将输入的48比特数据压缩为32比特。
8个6进4出的S盒如下图所示，每个S盒有4行，记为第0,1,2,3行，有16列，记为第0,1,2,3.。。。，15列。
以s6为例解释s盒的使用方法： 对于6位输入b1b2b3b4b5b6，用b1b6组成的二进制数表示行标，b2b3b4b5组成的二进制数表示列标，查s盒的表，表中的十进制数字转为4位二进制即为输出

P盒置换——移位变换

P盒置换是对S盒变换后的32比特数据进行比特置换，置换后得到的32比特数据即为f函数的输出。 P盒置换的方式和初始置换相同，如c1c2c3c4 = m16m7m20m21 .... 如下图所示，以此类推。

圈密钥生成算法

64位的密钥首先进行置换选择1，得到56位的有效密钥，置换选择1如下图所示，进行方式同初始置换，c1c2c3c4c5c6c7 = m57m49m41m33m25m17m9，以此类推。
之后每一圈的48位圈密钥生成过程如下图所示：
把56位有效密钥分成左28位Ci和右28位Di，经过移位变换后得到Ci+1, Di+1，其中得到C/D1,C/D2,C/D9,C/D16前面的移位是循环左移两位，其余的为循环左移1位。 Ci和Di作为输入进行选择置换2，得到48位的输出为Ki。选择置换2如下图所示：

再次回顾DES算法加密的框图，我们已经掌握了算法流程中的每一个细节: )

脱密过程

DES的脱密框图如下图所示，DES的脱密运算和加密运算用的是同一个算法，二者的不同之处是圈密钥的使用次序相反，即脱密过程中第i圈（i=1,2,...,16)的圈密钥是加密过程中第17-i圈的圈密钥K17-i。证明过程在网上和教材中容易找到。

PS

DES算法中有许多张表，如初始置换表，置换选择表，S盒等，这些表都有非常深刻的设计思想，稍微变动一点点都会使算法的保密性变弱，关于DES算法的设计思想和安全性分析，有兴趣的读者可以自行参看密码学的教材和相关文献。