【文章标题】: 密码学入门系列(五) 之 DES(现代)
【文章作者】: jackozoo
【作者邮箱】: jackozoo@163.com
【作者声明】: 只是感兴趣,没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
  系列声明:见一.
  
  DES简介: DES全称: Data Encryption Standard .  其前身为IBM公司的Hors t Feistel领导研制的LUCIFER算法. 其设计思想充分体现了香农提出的混淆和扩散原则.DES为分组密码, 其分组长度为64bit, 秘匙长度为64bit(包含8位奇校验位).
  
  DES算法描述:
  
  DES的分组长度为64it, 加密后的密文分组也为64bit, 因此不存在数据扩展. 秘匙长度为64位, 其中的第8,16,24,32,40,48,56,64位为奇检验位.
  (什么是奇校验:使得当前字节的8个bit中1的个数为奇数) , 因此, 实际有效的秘匙长度为56位.
  DES对每个64bit的分组的处理过程如下:
  1) 首先对64bit的明文进行初始置换IP(Initial Permute)
  2) 将分组分为长度相等的两部分L和R.
  3) 进行16轮完全相同的运算.(我们称之为f函数, 其中每一轮都会用到由初始秘匙产生的子秘匙)
  4) L16,R16合在一起进行末置换(或叫逆初始置换).
  5) over,得密文 :)
  
  DES环节各个击破:
  由于DES操作比较复杂, 我们现在开始对DES的各个部分进行各个击破战术, 这样讲解比较清晰.
  
  1) DES中的几处置换:
     在DES中, 我们会用到很多的置换表对数据分组进行置换操作. DES中的置换有无规律的置换,也有有规律的置换. 不过, 在对置换表的处理过程中, 我们大多数直接将其看作无规律置换来处理. 
     
     a.初始置换(IP): DES第一步进行
     
    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
  
     这个表怎么用? 这个表用于对一个64位的分组进行bit的打乱: 将原分组的第58位移至第1位, 第50位移至第二位, 第42位移至第三位,依次类推  ... 
     其中要注意, 经过IP后, 分组依然为64位的, 长度没变, 后面我们会遇到变长置换, 也即置换后分组的长度变长了或缩短了.
  
     b.末置换(IP^-1):16次轮转之后进行          
    40, 8, 48, 16, 56, 24, 64, 32,
    39, 7, 47, 15, 55, 23, 63, 31,
    38, 6, 46, 14, 54, 22, 62, 30,
    37, 5, 45, 13, 53, 21, 61, 29,
    36, 4, 44, 12, 52, 20, 60, 28,
    35, 3, 43, 11, 51, 19, 59, 27,
    34, 2, 42, 10, 50, 18, 58, 26,
    33, 1, 41,   9, 49, 17, 57, 25
  
     c. P置换(P): 出S盒之后进行.          
    16,   7, 20, 21, 
    29, 12, 28, 17,
    1, 15, 23, 26,
    5, 18, 31, 10,
    2,   8, 24, 14,
    32, 27,   3,   9,
    19, 13, 30,   6,
    22, 11,   4, 25
  
     d. 扩展置换E(Expansion) : R(i-1)经过扩展置换E后由32bit变48bit与子秘匙异或, 然后进S盒.
    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. 置换选择1(PC1, Permuted Choice 1 ) : 64位的子秘匙经由PC1去掉奇检验位, 得到56位的子秘匙.
    57, 49, 41, 33, 25, 17,   9,
    1, 58, 50, 42, 34, 26, 18,
    10,   2, 59, 51, 43, 35, 27,
    19, 11,   3, 60, 52, 44, 36,
    63, 55, 47, 39, 31, 23, 15,
    7, 62, 54, 46, 38, 30, 22,
    14,   6, 61, 53, 45, 37, 29, 
    21, 13,   5, 28, 20, 12,   4  
  
     f. 置换选择2(PC2) : 56位的有效秘匙经由PC2后得到48bit的秘匙, 然后与经由E后的48位明文异或.
    14, 17, 11, 24,   1,   5,
    3, 28, 15,   6, 21, 10,
    23, 19, 12,   4, 26,   8,
    16,   7, 27, 20, 13,   2,
    41, 52, 31, 37, 47, 55,
    30, 40, 51, 45, 33, 48,
    44, 49, 39, 56, 34, 53,
    46, 42, 50, 36, 29, 32
  
     g. S盒( S - Box) : 这个待会再讲. 
  
  
  2) 算法流程图
    http://bbs.pediy.com/picture.php?albumid=7&pictureid=132
     
     由图可知, DES对64位的分组先分为各32位的两个部分L0和R0, 然后经过16的轮回计算, 最终得到了密文. 其中有这么几个地方是关键点:
     a. f函数.
     b. 子秘匙的生成.
  
     子秘匙的生成:
     子秘匙经由置换选择1(PC1)后得到56bit数据, 然后将其分为C0, D0两部分, 然后对C0,D0 这各28bit的数据各自循环左移一定的位数, 然后经由PC2得到48bit的秘匙. 其中上次的循环左移会有累计效应 .  
     循环左移也有个左移表, 如下:
       1, 1, 2, 2, 2, 2, 2, 2,
    1, 2, 2, 2, 2, 2, 2, 1
     共有16个元素代表的是16次轮回迭代. 其中第1,2,4,16次迭代时分别左移1位, 其他次迭代则左移2位 .概括起来, 即为: IPC1会执行一次, 然后每次的循环左移都有累计效应. 在每次迭代使用秘匙的时候都会执行依次IPC2, 因此IPC2会执行16次. 事实上, 在我们编写程序的时候可以先把子秘匙先生成好, 然后在迭代中直接使用,免得在迭代的过程中去计算子秘匙.
  
     f函数:     f函数一共干了这么几件事:
     (i).   将明文分组的右边Ri(i=0,1,2 ... 15) 经过E置换变为48位.
     (ii).  得到当次迭代的子秘匙(经由PC2后也为48bit).
     (iii)  以上两者异或. (得48bit结果)
     (iv)   送入S-box, 得32bit结果.
     (v)    将32bit数据送入P置换.
     (vi)   将上步32bit结果与L(i-1)进行异或.(得到Ri) [这个时候Li = R(i-1)].
  
  以上这么几步便是f函数的所作所为.
  
     其中, S-Box是我们目前还没讲到的, 下面来具体看看S-Box.
  
     S-Box 一共有8各子Box , 分别为S1,S2,S3,S4,S5,S6,S7,S8 . 如下图所示:
    http://bbs.pediy.com/picture.php?albumid=7&pictureid=133
  
     对于S-Box,我们要保证48bit进, 32bit出. 这个是这样实现的:
     将48bit数据分成8组, 每组6bit,我们让每组的6bit分别对应送入S-Box的子Box, 实现6进4出.
     8个Box的数据如下(都是4行16列).

代码:
const static char S_Box_1[4][16]={
// Sbox1
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
};



const static char S_Box_2[4][16]={
// S2
15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
};

const static char S_Box_3[4][16]={
// S3
10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
};

const static char S_Box_4[4][16]={
// S4
7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
};

const static char S_Box_5[4][16]={
// S5
2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3

};

const static char S_Box_6[4][16]={
// S6
12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
};

const static char S_Box_7[4][16]={
// S7
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
};

const static char S_Box_8[4][16]={
// S8
13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
};
     如, 第一组数据中的6bit为101011 , 我们取其第一位和第六位分别为1和1, 组成二进制数11, 即为3.再取中间4位bit为0101, 即为5. 
     这样我们就去可以去查Box了: 
     第一组就在S1中查, 3即代表行数为4(因为从0开始). 5代表列数为6. 我们查得结果为:9. 也即二进制的1001. 这里的1001即为输出的4bit, 这样依次类推. 最终便会得到32bit的数据.
     呵呵, 怎么样? S-Box也很简单吧?
  
  3) DES的解密
   
     谈了加密, 就不得不说解密了, DES的解密是很特别的. 因为DES的解密算法和加密算法是一样的. 唯一的不同既是: 16个子秘匙要倒过来使用, 也即在解密时, 第一轮迭代使用第16个子秘匙, 第二轮迭代使用第15个子秘匙 ... ...
     可以用数学表达式表示为:
      / R(i-1) = Li.
     |
     |
      \ L(i-1) = Ri Xor f(Li,Ki) .   其中, i = 16,15, ... 1.
     
     DES算法的这个特性也很好证明, 非常简单. 利用的是这个公式:[ a  = (a xor b) xor b ], 异或的特性. 明眼人一眼都能看出来.
  
  
  4) DES加解密程序的编写.
  
     我们要注意几个问题:
     a. 一定要思路清晰, 流程模块化.
     b. 正确的设计模型.
     c. 高效正确的编写代码.
     d. 不足64bit的处理方式.
  
     
     由于DES中的位操作实在是多, 非常麻烦, 有些还是28bit的循环左移, 虽说实现起来也能实现, 但是相当的麻烦. 我刚开始就是用C语言中的位操作来编写DES的,我们直接将分组的64bit数据,以及秘匙放到两个DWORD中去,然后通过位操作来完成算法, 写了很久, 我知道我可以最终写出来, 但是编写起来实在是太麻烦了, 所以最终我放弃了 . 我参考了其他人的一些优秀思想, 使用了另外的模式.
     也即用字节代替bit, 用数组代替分组. 比如对于一个64bit的分组, 如果用DWORD[2]表示, 那么取bit和设置bit是很麻烦的. 相反, 如果我们用char[64]来表示的话, 则取bit和设置bit非常方便. 我们只需要在最后形成结果的时候将char[64]转换为8个byte即可. 我认为这是一个针对此类问题的很好的策略.
     
     如果明文最后一个分组不足8个byte. 则我们填充00 使其到达64bit. 然后加密. 最后在密文尾部附上8个字节, 这8个字节的值为初始明文的长度, 这样解密者解密后, 就可以知道该截取多少长度的字节了. 最后8字节的长度其实也可以放到明文序列中一起加密, 解密的时候一起解密, 两种方式都行. 另外, 8个字节可以表示16Eb的大小, 大的令人恐怖了.
  
  5) 附件中为附带DES学习软件及源码.(由于时间仓促, 代码组织比较混乱, 还请各位见谅)
  
     DES Cipher 1.0 功能:
     对字节序列进行加解密; 对文件进行加解密;
     希望大家可以参照此贴写出自己的DES辅助软件.
  
  
  
  
  
  
  
  
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2009年05月31日 AM 11:41:14
上传的附件 DES_bin.rar
DES_src.rar