首页
社区
课程
招聘
[原创]密码学入门系列(五) 之 DES(现代)
发表于: 2009-5-31 11:53 19595

[原创]密码学入门系列(五) 之 DES(现代)

2009-5-31 11:53
19595
【文章标题】: 密码学入门系列(五) 之 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) 算法流程图
   
     
     由图可知, 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 . 如下图所示:
   
  
     对于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

[课程]Linux pwn 探索篇!

上传的附件:
收藏
免费 7
支持
分享
最新回复 (23)
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
2
很不错,期待下一篇
2009-5-31 12:11
0
雪    币: 204
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
很好啊,还附带着源代码,十分感谢LZ
2009-5-31 19:02
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
这样好的原创教程,收藏了
2009-5-31 19:42
0
雪    币: 1491
活跃值: (975)
能力值: (RANK:860 )
在线值:
发帖
回帖
粉丝
5
相当精彩,学习了。。。。
2009-5-31 20:26
0
雪    币: 232
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
多谢楼主啦,学习中~~
2009-6-1 09:48
0
雪    币: 306
活跃值: (153)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
7
有些地方看不懂哦,得看下相关的数学书噢
2009-6-11 15:03
0
雪    币: 193
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
收藏学习!支持!
2009-6-14 20:44
0
雪    币: 164
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
9
你把加密方式一一写了,那我们写点啥子哦。可以看出楼主的基础很好呵呵。
本来想现学现卖写篇浅谈RSA的,估计又得好好蕴量一阵,免得被淹了。
2009-6-14 21:19
0
雪    币: 1450
活跃值: (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
10
呵呵, 加油 . 其实我也都是现学现写的.
期待你的RSA.
2009-6-14 23:17
0
雪    币: 112
活跃值: (48)
能力值: ( LV9,RANK:320 )
在线值:
发帖
回帖
粉丝
11
嗯 好好学习。
2009-6-23 23:59
0
雪    币: 306
活跃值: (153)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
12
呵呵,可是入门了
2009-7-1 19:23
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
哈哈~~~肯定比什么《分享》好多了~~~再分享下去真不如都下载PDF去~~~

顶一下。
2009-7-10 08:26
0
雪    币: 226
活跃值: (85)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
thxs
2009-7-11 16:03
0
雪    币: 253
活跃值: (46)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
15
据我了解,DES加密存在好几种加密模式,ECB等什么的吧,这个原始的实践中基本不适用。
2009-9-3 19:29
0
雪    币: 34
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
原文:
[如, 第一组数据中的6bit为101011 , 我们取其第一位和第六位分别为1和1, 组成二进制数11, 即为3.再取中间4位bit为0101, 即为5.
     这样我们就去查Box: 第一组就在S1中查, 3为行数. 5为列数. 我们查得结果为:13. 也即二进制的1101. 这里的1101即为输出的4bit, 这样依次类推. 最终便会得到32bit的数据.]
下划线的地方,有点没讲清.第3行,第5列应为:9   因为行和列是从0开始数的,二进制2位,4位范围分别从0-3,0-15
2009-10-4 10:40
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
不错的知识 下来认真学习 谢谢楼主
2009-10-16 16:26
0
雪    币: 1450
活跃值: (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
18
[QUOTE=praying;695310]原文:
[如, 第一组数据中的6bit为101011 , 我们取其第一位和第六位分别为1和1, 组成二进制数11, 即为3.再取中间4位bit为0101, 即为5.
     这样我们就去查Box: 第一组就在S1中查, 3为行数. 5为列数. 我们查得结果为:13. 也即二进制的1101. ...[/QUOTE]

是的. 讲到你所说的这里时, 忘了将8个Box的6进4出置换表贴出.  我现在补上去了.
然后3和5对应的应该是第4行和第6列, 这里查表输出应为9(1001).
感谢parying对文中一些错误地方的反馈.
2009-10-22 08:27
0
雪    币: 101
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
19
可是入门了 感谢楼主
2009-10-22 09:06
0
雪    币: 55
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
支持^_^
2009-11-13 20:39
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
21
很好的文章,不过讲得还不够详细,初学者还看不懂~~~~
2012-10-8 14:37
0
雪    币: 50
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
22
弱弱的问一句,DES加密第十六轮操作完成时,得到的左右两个32bits是否还要用Swap函数进行交换?看着书上的好像是要交换,但是也有的资料上显示的是没有进行交换,而直接将这64bits数据进行逆置换后得到了64bits密文。
2012-11-22 20:50
0
雪    币: 5
活跃值: (38)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
23
楼主辛苦,期待AES
2012-11-27 11:28
0
雪    币: 32
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
24
     在用DES加密的第16轮操作完成后,但在进行初始逆置换IP-1之前,是需要将左半部分的L16和右半部分的R16进行交换的,即L17=R16,R17=L16。这也是轮函数F中的最后一步。呵呵。
2013-1-24 09:33
0
游客
登录 | 注册 方可回帖
返回
//