2.1 DES算法

DES算法基于Feistel结构（由密码学家Horst Feistel提出的分组密码结构），是基于硬件的可以快速实现的对称密码算法。从历史的视角看，DES算法在一定程度上推动了Feistel结构的广泛应用。标准的Feistel结构如图2-1所示。

在图2-1所示的Feistel结构中，输入数据Di－1分为左、右两部分，分别记为Li－1和Ri－1，输出数据Di也分为左、右两部分，分别记为Li和Ri。在DES中，每个Di的长度为64位，Li和Ri的长度均为32位。

图2-1实现了如式（2-1）和式（2-2）所示的运算。式（2-2）中的函数f可取任意输出为32位的函数（包括不可逆函数）。函数f具有两个输入参数，即ki和Ri－1，这里的ki为48位长的随机数序列，由密钥产生。

图2-1所示的Feistel结构将输入Di－1变换为Di，实现了以下3个原则。

（1）在密钥的作用下（体现为ki的参与），将输入Di－1变换为Di。

（2）Feistel结构是可逆的，由Di变换为Di－1的运算如式（2-3）和式（2-4）所示。

（3）Feistel结构是明文关联的，即如果伪随机序列ki是相同的，微小变化的Di－1（实际上是微小变化的Ri－1）将使得Di发生显著变化（实际上是Ri发生显著的变化）。

上述3个原则是设计密码系统的核心原则，即借助密码和加密算法将明文加密为密文，密文受到密钥的控制；加密算法是可逆的，解密算法是加密算法的逆过程；加密算法和解密算法都是明文关联的，即当密钥保持不变时，微小变化的明文将产生具有显著差异的密文，同时，微小变化的密文还原后的图像具有显著的差异，可以有效地对抗差分攻击。

由图2-1可知，这里的Di分为Li和Ri采取了等长分割，事实上，也可以采取不等长分割方法，如图2-2所示。

图2-2为Feistel结构的变种形式I，由于对Di采取了不等长分割，所以在相邻的两级中，函数fi与fi＋1是不同的（至少其函数的输出值的位数不同）。此时，运算公式如式（2-5）和式（2-6）所示，其中，每一级中的fi都不尽相同。

显然，图2-2所示Feistel结构的变种I是可逆的，其逆运算如式（2-7）和式（2-8）所示。

在图2-2中，Di的分割位置是固定的。事实上，在每一级中可以随意选定分割的位置，这样可得到Feistel结构的变种II，如图2-3所示。

在图2-3所示的Feistel结构的变种II中，每一级中的输入数据先进行循环左移操作，循环左移操作属于非线性运算，广泛应用于密码学中，然后，将输入数据分割为左、右两部分。其中，循环左移的位数和分割的位置由密钥决定。对于第i级而言，循环左移的位数di－1和分割的位置pi－1由密钥ki决定，即{di－1，pi－1}＝gi（ki），这里，函数gi为非线性函数。此时，第i级的运算仍然与式（2-5）和式（2-6）相同。显然，图2-3所示Feistel结构的变种形式II是可逆的，在逆运算中，首先由密钥ki和函数gi生成循环右移的位数di－1和分割的位置pi－1，然后，由式（2-7）和式（2-8）计算Li－1和Ri－1，最后，循环右移di－1位还原出Di－1。

思考：Feistel结构需要多少级才能达到满意的加密效果呢？在图2-1所示标准的Feistel结构中，假设每一级中Ri都充分体现了Li－1、Ri－1和ki的共同作用，试着说明标准Feistel结构的最佳级数。同样，对于图2-2和图2-3中的两种变种形式，试着说明Feistel变种形式的最佳级数，并试着分析数据分割位置与加密效果的关系，当级数固定时，存在最佳的分割位置吗？在DES算法中，使用了16级Feistel结构，分割方式为中间位置等分，要求输入数据的长度必须为偶数位，DES算法的输入数据位数为64位。

2.1.1 DES加密算法

本小节内容参考了NIST FIPS PUB46-3标准。DES加密算法使用了16级Feistel结构，密钥长度为56位，输入明文长度为64位，输出密文长度与明文长度相同，也是64位。DES加密算法如图2-4所示，首先将输入的明文x进行位置乱处理，然后经过16级Feistel结构的运算处理，最后一级Feistel结构的输出还要经过一次位置乱处理（这次的位置乱处理是输入明文的位置乱的逆运算），最后将得到密文y。这里的每级Feistel结构如图2-1所示，Li和Ri的长度均为32位，i＝0，1，2，…，16。

在图2-4中，输入长度为64位的明文x和长度为64位的密钥key，将得到长度为64位的密文y，即y＝DES（key，x）。

如图2-4所示，DES加密算法的步骤如下所示。

Step 1.明文x经过初始置乱IP后得到D0。初始置乱IP见表2-1。表2-1的含义为：x中第58位的位数据作为D0的第1位，x中第50位的位数据作为D0的第2位，以此类推，x中第8位的位数据作为D0的第64位。

Step 2.令i＝0。

Step 3.将Di平分为左、右两部分，分别记为Li和Ri。

Step 4.计算

得到Di＋1，即Li＋1为Di＋1的左32位，Ri＋1为Di＋1的右32位。其中，函数f的结构和子密钥Ki＋1的产生方法将在下文介绍。

Step 5.i＝i＋1。如果i＝16，则继续到Step 6；否则跳转到Step 3。

Step 6.将L16和R16互换位置得到新的D16。

Step 7.将新的D16进行逆初始置乱IP－1，得到密文y，即y＝IP－1（D16）。其中，逆初始置乱IP－1见表2-2，IP－1是IP的逆变换。

图2-4中，函数f的结构如图2-5所示。

在图2-5中，输入32位的Ri和48位的子密钥Ki＋1，输出为f（Ki＋1，Ri），具体实现步骤如下。

Step 1.将Ri作位扩展运算E扩展为48位。位扩展运算E见表2-3。

表2-3中的阴影部分为Ri的原始位的位位置，共32位，每行都做了头尾扩展，扩展后的表2-3中包含48位。扩展后，原Ri中位于第32位的位成为扩展后向量的第1位，原Ri中位于第1位的位成为扩展后向量的第2位，按表2-3继续下去，最后，原Ri中位于第1位的位成为扩展后向量的第48位。

Step 2.将子密钥Ki＋1按行折叠成8行6列的表格，与Ri作位扩展运算E后得到的48位（其位位置见表2-3）作异或运算，其结果的第1行赋给S1，第2行赋给S2，以此类推，第8行赋给S8，即第i行赋给Si，下一步介绍Si的处理方式，这里将第i行记为ri＝{ri1，ri2，ri3，ri4，ri5，ri6}。

Step 3.每个Si都称作S盒子，是一个4行16列的二维数组，每行的16个元素是0~ 15的一个排列。对于ri而言，将其二进制位ri1和ri6组合成行号，将ri2，ri3，ri4和ri5组合成列号，查Si表得到的值为Si盒子的输出，输出值为4位。8个S盒子见表2-4~表2-11。

以S8盒为例，设r8＝011011b，则行号为01B＝（1）10，列号为1101B＝（13）10，即S8盒中第1行第13列的元素（14）10＝1110B为r8对应的4位输出。

Step 4.8个S盒的输出依次连接成32位长的数据，经过扰乱P后得到输出结果f（Ki＋1，Ri）。这里，扰乱P见表2-12。

表2-12表示，扰乱前的数据的第16位将成为扰乱后的数据的第1位，扰乱前的数据的第7位将成为扰乱后的数据的第2位，以此类推，扰乱前的数据的第25位将成为扰乱后的数据的第32位。

现在回到图2-4，介绍子密钥Ki，i＝1，2，…，16的生成方法。如图2-4的右半部分所示，输入64位长的密钥key，输出16个48位长的子密钥Ki，i＝1，2，…，16。子密钥生成的步骤如下。

Step 1.输入长为64位的密钥key＝{kj}，j＝1，2，…，64。DES算法中，密钥的有效长度为56位，64位key中的k8，k16，k24，k32，k40，k48，k56和k648个位为奇校验位，即k8j，j＝1，2，…，8与各自前面的7个位组成奇校验，例如，k1，k2，k3，k4，k5，k6，k7与k8组成奇校验，k8取值为0还是为1取决于必须保证{k1，k2，k3，k4，k5，k6，k7，k8}中1的个数为奇数个。如果密钥校验是正确的（预防存取或通信中发生错位），则可以直接将k8，k16，k24，k32，k40，k48，k56 和k64舍去。

Step 2.对舍去k8，k16，k24，k32，k40，k48，k56和k64的key中的剩余位按扰乱方式PC-1进行位扰乱。扰乱方式PC-1见表2-13。

表2-13表示扰乱前的key的第57位将成为扰乱后的数据的第1位，扰乱前的key的第49位将成为扰乱后的数据的第2位，按表2-13推理下去，扰乱前的key的第4位将成为扰乱后的数据的第56位。由于key中没有k8，k16，k24，k32，k40，k48，k56和k64这些位，所以表2-13中也没有这些位的位置号，经表2-13扰乱后的数据的前28位赋给A0，其后28位赋给B0。

Step 3.i＝0。

Step 4.如果i＝0，1，8或15，则LSi＝1；否则，LSi＝2。

Step 5.将Ai循环左移LSi位得到Ai＋1，同时，将Bi循环左移LSi位得到Bi＋1。

Step 6.将Ai＋1与Bi＋1连接成56位，各位的位置重新顺序编号，从1至56。然后，经过扰乱方式PC-2的扰乱后，得到子密钥Ki＋1。扰乱方式PC-2见表2-14。

表2-14表示连接Ai＋1与Bi＋1得到的56位长的数据中，第14位作为子密钥Ki＋1的第1位，第17位作为子密钥Ki＋1的第2位，按表2-14推理下去，第32位作为子密钥Ki＋1的第48位。

Step 7.i＝i＋1。如果i＝16，则结束；否则，跳转到Step 4。

2.1.2 DES解密算法

DES解密算法是DES加密算法的逆过程。仔细研究图2-4会发现，图2-4左半部分正向和逆向过程在形式上是相同的。因此，只把子密钥序列逆序输入就可以得到DES解密过程，即先使用子密钥K16，再使用子密钥K15，以此类推，最后使用子密钥K1。所以，可以先执行密钥发生器，由输入密钥key预先准备好全部的16个子密钥，这样，只需要逆序输入各个子密钥就可以实现DES解密过程。

另一种方法是直接逆序产生子密钥。仔细观察图2-4的右半部分，由于16次循环次数LS0＋LS1＋LS2＋…＋LS15＝28，即全部循环结束后的A16＝A0，B16＝B0。因此，可以直接由A0、B0得到A16和B16，然后，再进行相同次数的循环右移就可以得到Ai、Bi，i＝15，14，…，3，2，1，这一过程如图2-6的右半部分所示。

在图2-6中引入了两个循环控制变量i和j，这样使得输入的子密钥的索引号（用i索引）仍然是顺序的（即从1至16），这样编号是为了程序设计的方便。此外，在图2-6右半部分的子密钥发生器中，16次循环体内均使用了向右循环移位，循环移动的位数用RSi（i＝0，1，2，…，15）表示。这里，当i＝0，7和14时，RSi＝1，其余情况下，RSi＝2。仔细对比图2-4和图2-6可知，图2-6是图2-4的逆过程。