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

时间:2021-04-08 19:03:07

DES背景

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

DES算法概述

基本流程

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

初始置换和逆初始置换

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

圈函数

初始置换之后的输出要进行16圈迭代。
圈函数使用的是Feistel模型,它的数学描述如下:
[密码学]DES算法过程描述
第1,2.。。。15圈的圈加密结构图如下
[密码学]DES算法过程描述
每一圈迭代过程中:
  • 输出的左32位就是输入的右32位
  • 输出的右32位是输入的右32位和圈密钥k进行f函数运算后和输入左32位异或运算得到。

圈函数

f函数

f函数的数学表达式如下
[密码学]DES算法过程描述
f函数的运算流程如下图所示:
[密码学]DES算法过程描述

  • 先对右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 .... 以此类推)。
[密码学]DES算法过程描述

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

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

P盒置换——移位变换

P盒置换是对S盒变换后的32比特数据进行比特置换,置换后得到的32比特数据即为f函数的输出。
P盒置换的方式和初始置换相同,如c1c2c3c4 = m16m7m20m21 .... 如下图所示,以此类推。
[密码学]DES算法过程描述

圈密钥生成算法

64位的密钥首先进行置换选择1,得到56位的有效密钥,置换选择1如下图所示,进行方式同初始置换,c1c2c3c4c5c6c7 = m57m49m41m33m25m17m9,以此类推。
[密码学]DES算法过程描述
之后每一圈的48位圈密钥生成过程如下图所示:
[密码学]DES算法过程描述
把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算法过程描述

脱密过程

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

PS

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