欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

DES详解(Java实现)

程序员文章站 2022-04-18 15:33:52
GitHub DES 数据加密标准(Data Encryption Standard),简称DES,是由IBM公司提交,美国*于1977年1月5日颁布的一种加密算法。 DES的设计目标是,用于加密保护静态存储和传输信道中的数据,安全使用10~15年。 DES综合运用了置换、代替、代数等多种密码技术 ......

github


des

  数据加密标准(data encryption standard),简称des,是由ibm公司提交,美国*于1977年1月5日颁布的一种加密算法。

  des的设计目标是,用于加密保护静态存储和传输信道中的数据,安全使用10~15年。

  des综合运用了置换、代替、代数等多种密码技术。它设计精巧、实现容易、使用方便,堪称是适应计算机环境的近代分组密码的一个典范。des的设计充分体现了shannon所阐述的设计密码的思想,标志着密码的设计与分析达到了新的水平。

  des是一种分组密码。明文、密文和密钥的分组长度都是64位。

  des是面向二进制的密码算法。因而能够加解密任何形式的计算机数据。

  des是对合运算,因而加密和解密共用同一算法,从而使工程实现的工作量减半。

  des的密码结构属于feistel结构。


feistel结构

  feistel结构是ibm的密码专家horst feistel最早提出的。由于它是对称的密码结构,所以对信息加密和解密的过程就极为相似,甚至完全一样。这就使得在实施的过程中,对编码量和线路传输的要求就减少了几乎一半。

加密结构

  l= ri-1

  ri = li-1 ⊕ f ( ri-1 , k)

  DES详解(Java实现)

解密结构

  li-1 = r⊕ f ( l, k)

  ri-1 = li

  DES详解(Java实现)

影响因素

  影响feistel结构的因素有以下5个:

  1.块的大小:大的块会提高加密的安全性,但是会降低加密、解密的速度;

  2.密钥的大小:大的密钥也会提高加密的安全性,但是也会降低加密、解密的速度;

  3.轮次数:每多进行一轮循环,安全性就会有所提高;

  4.子密钥的生成算法:生成算法越复杂,则会使得密文被破译的难度增强,即信息会越安全;

  5.轮函数的复杂度:轮函数越复杂,则安全性会越高。


des算法细节

子密钥的产生

  64位密钥经过置换选择1、循环左移、置换选择2等变换,产生出16个48位长的子密钥。

(1)置换选择1

  64位密钥分为8个字节。每个字节的前7位是真正的密钥位,第8位是奇偶校验位。奇偶校验位可以从前7位密钥位计算得出,不是随机的,因而不起密钥的作用。因此,des真正的密钥只有56位。

  置换选择1的作用有两个:一是从64位密钥中去掉8个奇偶校验位;二是把其余56位密钥位打乱重排,且将前28位作为c0,后28位作为d0

  置换选择1的矩阵如下:

  DES详解(Java实现)

(2)循环左移

  每一次迭代,将ci-1和di-1按照一定的位数循环左移分别得到ci和di

  循环左移位数表如下:

  DES详解(Java实现)

(3)置换选择2

  将ci和di合并成一个56位的中间数据,置换选择2从中选择出一个48位的子密钥ki

  置换选择2的矩阵如下:

  DES详解(Java实现)

初始置换ip

  初始置换ip(initial permutation)的作用在于将64位数据打乱重排,并分成左右两半,供后面的迭代使用。

  初始置换ip的矩阵如下:

  DES详解(Java实现)

轮函数

  轮函数是des的核心部分。在迭代中将32位的数据组a进行选择运算e、模2相加、代替函数组s、置换运算p等运算,得到32位输出结果。根据shannon用混淆和扩散设计密码的理论,des的s盒用来提供混淆,而p置换用来提供扩散。

(1)选择运算e

  选择运算e对32位的数据组a的各位进行选择和排列,产生一个48位的结果。

  选择运算e是一种扩展运算,通过重复选择某些数据位来达到数据扩展的目的。

  选择运算e的矩阵如下:

  DES详解(Java实现)

(2)模2相加

  将选择运算e得到的结果与48位子密钥k进行模2相加,即逐位异或,得到一个48位的结果。

(3)代替函数组s

  代替函数组s由8个代替函数(s盒)组成。代替函数组s的输入是一个48位的数据,从第1位到第48位依次加到8个s盒的输入端,即第i位到第8i位加到s(i = 1,2,3,4,5,6,7,8)的输入端。

  每个s盒有一个代替矩阵,规定了其输出与输入的代替规则。代替矩阵有4行(0~3)16列(0~15),64个位置都是0~15这16个数字。每个s盒有6位输入,产生4位输出。s盒运算的结果是用输出数据代替了输入数据,所以称其为代替函数。

  s盒的代替规则是:s盒的6位输入b1b2b3b4b5b6中的第1位和第6位数字b1b6组成的二进制数代表选中的行号,其余4位数字b2b3b4b5组成的二进制数代表选中的列号,将处在行号和列号所代表的位置的数字以4位二进制形式输出作为s盒的输出。

  s盒至少应满足以下准则:

  1.输出不是输入的线性和仿射函数;

  2.任意改变输入中的1位,输出至少有2位发生变化;

  3.对于任何s盒和任何输入x,s(x)和s(x⊕001100)至少有2位不同;

  4.对于任何s盒和任何输入x,以及y,z∈gf(2),s(x) ≠ s(x⊕11yz00);

  5.保持输入中的1位不变,其余5位变化,输出中的0和1的个数接近相等。

  代替函数组s中8个s盒的代替矩阵如下:

  DES详解(Java实现)

  DES详解(Java实现)

  DES详解(Java实现)

  DES详解(Java实现)

  DES详解(Java实现)

  DES详解(Java实现)

  DES详解(Java实现)

  DES详解(Java实现)

(4)置换运算p

  置换运算p把s盒输出的32位数据打乱重排,得到32位轮函数输出。

  置换运算p的矩阵如下:

  DES详解(Java实现)

逆初始置换ip-1

  逆初始置换ip-1是初始置换ip的逆置换。它把迭代的结果打乱重排,形成64位结果。

  逆初始置换ip-1的矩阵如下:

  DES详解(Java实现)


 des的加密过程

  1.64位密钥经子密钥产生算法产生出16个48位子密钥:k1,k2,...,k16,分别供第1次,第2次,...,第16次加密迭代使用。

  2.64位明文首先经过初始置换ip,将数据打乱重新排列并分成左右两半,左边32位构成l0,右边32位构成r0

  3.第i次加密迭代:由轮函数f实现子密钥ki对ri-1的加密,结果为32位的数据组f ( ri-1 , ki )。f ( ri-1 , ki )再与li-1模2相加,又得到一个32位的数据组li-1 ⊕ f ( ri-1 , ki )。以li ⊕ f ( ri-1 , ki )作为下一次加密迭代的ri,以ri-1作为下一次加密迭代的li ( i = 1,2,...,16)。

  4.按照上一步的规则进行16次加密迭代。

  5.第16次加密迭代结束后,以r16为左,l16为右,合并产生一个64位的数据组。再经过逆初始置换ip-1,将数据重新排列,便得到64位密文。


des的解密过程

  1.64位密钥经子密钥产生算法产生出16个48位子密钥:k1,k2,...,k16,分别供第1次,第2次,...,第16次解密迭代使用。

  2.64位密文首先经过初始置换ip,将数据打乱重新排列并分成左右两半,左边32位构成r16,右边32位构成l16

  3.第17-i次解密迭代:由轮函数f实现子密钥ki对li的解密,结果为32位的数据组f ( li , ki )。f ( li , ki )再与ri模2相加,又得到一个32位的数据组ri ⊕ f ( li , ki )。以ri ⊕ f ( li , ki )作为下一次解密迭代的li-1,以li作为下一次解密迭代的li-1 ( i = 16,15,...,1)。

  4.按照上一步的规则进行16次解密迭代。

  5.第16次解密迭代结束后,以l0为左,r0为右,合并产生一个64位的数据组。再经过逆初始置换ip-1,将数据重新排列,便得到64位明文。


des的安全性

  des算法中除了s盒是非线性变换外,其余变换均为线性变换,所以des安全的关键是s盒。因为算法中使用了16次迭代,从而使得改变输入明文或密钥中的1位,密文都会发生大约32位的变化,具有良好的雪崩效应,大大提高了保密性。s盒用来提供混淆,使明文、密钥、密文之间的关系错综复杂,而p置换用来提供扩散,把s盒提供的混淆作用充分扩散开来。这样,s盒和p置换互相配合,形成了很强的抗差分攻击和抗线性攻击能力,其中抗差分攻击能力更强些。


des的安全弱点

密钥较短

  面对计算能力高速发展的形式,des采用56位密钥,显然短了一些。如果密钥的长度再长一些,将会更安全。

存在弱密钥和半弱密钥

  弱密钥和半弱密钥的存在无疑是des的一个不足。但由于弱密钥和半弱密钥的数量与密钥的总数256相比仍是微不足道的,所以这并不对des构成太大威胁,只要注意在实际应用中不使用这些弱密钥和半弱密钥即可。

存在互补对称性

  互补对称性使des在选择明文攻击下所需的工作量减半。产生互补对称性的原因在于des中两次异或运算的配置,一次在轮函数中s盒之前,另一次在轮函数输出之后。攻击者任取一个明文m,并可得到密文c = des ( m , k ),攻击者只要简单地对c取非,便得到另一明文m'(m取非)在密钥k'(k取非)加密下的密文c' = des ( m' , k' )。因此攻击者只要做一次实验便可知道k和k'是否是所求的密钥。


java实现

子密钥产生

 1 //置换选择1矩阵
 2 static int[] replace1c = {
 3         57, 49, 41, 33, 25, 17,  9, 
 4          1, 58, 50, 42, 34, 26, 18, 
 5         10,  2, 59, 51, 43, 35, 27, 
 6         19, 11,  3, 60, 52, 44, 36
 7 };
 8 static int[] replace1d = {
 9         63, 55, 47, 39, 31, 23, 15, 
10          7, 62, 54, 46, 38, 30, 22, 
11         14,  6, 61, 53, 45, 37, 29, 
12         21, 13,  5, 28, 20, 12,  4
13 };
14 
15 //循环左移位数表
16 static int[] movenum = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
17 
18 //置换选择2矩阵
19 static int[] replace2 = {
20     14, 17, 11, 24,  1,  5, 
21      3, 28, 15,  6, 21, 10, 
22     23, 19, 12,  4, 26,  8, 
23     16,  7, 27, 20, 13,  2, 
24     41, 52, 31, 37, 47, 55, 
25     30, 40, 51, 45, 33, 48, 
26     44, 49, 39, 56, 34, 53, 
27     46, 42, 50, 36, 29, 32
28 };
 1 /**
 2  * 子密钥的产生
 3  * @param skey  64位密钥
 4  * @return      16个48位子密钥
 5  */
 6 static byte[][] generatekeys(byte[] skey) {
 7     byte[] c = new byte[28];
 8     byte[] d = new byte[28];
 9     byte[][] keys = new byte[16][48];
10     //置换选择1
11     for (int i = 0; i < 28; i++) {
12         c[i] = skey[replace1c[i] - 1];
13         d[i] = skey[replace1d[i] - 1];
14     }
15     for (int i = 0; i < 16; i++) {
16         //循环左移
17         c = rshr(c, movenum[i]);
18         d = rshr(d, movenum[i]);
19         //置换选择2
20         for (int j = 0; j < 48; j++) {
21             if (replace2[j] <= 28) keys[i][j] = c[replace2[j] - 1];
22             else keys[i][j] = d[replace2[j] - 28];
23         }
24     }
25     return keys;
26 }
 1 /**
 2  * 循环左移
 3  * @param b  数组
 4  * @param n  位数
 5  * @return
 6  */
 7 static byte[] rshr(byte[] b, int n) {
 8     string s = new string(b);
 9     s = (s + s.substring(0, n)).substring(n);
10     return s.getbytes();
11 }

初始置换ip

 1 //初始置换矩阵
 2 static int[] ip = {
 3         58, 50, 42, 34, 26, 18, 10,  2, 
 4         60, 52, 44, 36, 28, 20, 12,  4, 
 5         62, 54, 46, 38, 30, 22, 14,  6, 
 6         64, 56, 48, 40, 32, 24, 16,  8, 
 7         57, 49, 41, 33, 25, 17,  9,  1, 
 8         59, 51, 43, 35, 27, 19, 11,  3, 
 9         61, 53, 45, 37, 29, 21, 13,  5, 
10         63, 55, 47, 39, 31, 23, 15,  7
11 };
 1 /**
 2  * 初始置换ip
 3  * @param text  64位数据
 4  * @return
 5  */
 6 static byte[] ip(byte[] text) {
 7     byte[] newtext = new byte[64];
 8     for (int i = 0; i < 64; i++) 
 9         newtext[i] = text[ip[i] - 1];
10     return newtext;
11 }

轮函数

 1 //选择运算矩阵
 2 static int[] e = {
 3         32,  1,  2,  3,  4,  5, 
 4          4,  5,  6,  7,  8,  9, 
 5          8,  9, 10, 11, 12, 13, 
 6         12, 13, 14, 15, 16, 17, 
 7         16, 17, 18, 19, 20, 21, 
 8         20, 21, 22, 23, 24, 25, 
 9         24, 25, 26, 27, 28, 29, 
10         28, 29, 30, 31, 32,  1
11 };
12 
13 //代替函数组
14 static int[][][] s = {
15         //s1
16         {
17             {14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7}, 
18             { 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8}, 
19             { 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0}, 
20             {15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13}
21         }, 
22         //s2
23         {
24             {15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10}, 
25             { 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5}, 
26             { 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15}, 
27             {13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9}
28         }, 
29         //s3
30         {
31             {10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8}, 
32             {13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1}, 
33             {13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7}, 
34             { 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12}
35         }, 
36         //s4
37         {
38             { 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15}, 
39             {13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9}, 
40             {10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4}, 
41             { 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14}
42         }, 
43         //s5
44         {
45             { 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9}, 
46             {14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6}, 
47             { 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14}, 
48             {11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3}
49         }, 
50         //s6
51         {
52             {12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11}, 
53             {10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8}, 
54             { 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6}, 
55             { 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13}
56         }, 
57         //s7
58         {
59             { 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1}, 
60             {13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6}, 
61             { 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2}, 
62             { 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12}
63         }, 
64         //s8
65         {
66             {13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7}, 
67             { 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2}, 
68             { 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8}, 
69             { 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}
70         }
71 };
72 
73 //置换运算矩阵
74 static int[] p = {
75         16,  7, 20, 21, 
76         29, 12, 28, 17, 
77          1, 15, 23, 26, 
78          5, 18, 31, 10, 
79          2,  8, 24, 14, 
80         32, 27,  3,  9, 
81         19, 13, 30,  6, 
82         22, 11,  4, 25
83 };
 1 /**
 2  * 轮函数
 3  * @param a  32位输入
 4  * @param k  48位子密钥
 5  * @return   32位输出
 6  */
 7 static byte[] f(byte[] a, byte[] k) {
 8     byte[] t = new byte[48];
 9     byte[] r = new byte[32];
10     byte[] result = new byte[32];
11     //选择运算e
12     for (int i = 0; i < 48; i++) 
13         t[i] = a[e[i] - 1];
14     //模2相加
15     for (int i = 0; i < 48; i++) 
16         t[i] = (byte) (t[i] ^ k[i]);
17     //代替函数组s
18     for (int i = 0, a = 0; i < 48; i += 6, a += 4) {
19         int j = t[i] * 2 + t[i + 5];   //b1b6
20         int k = t[i + 1] * 8 + t[i + 2] * 4 + t[i + 3] * 2 + t[i + 4];   //b2b3b4b5
21         byte[] b = integer.tobinarystring(s[i / 6][j][k] + 16).substring(1).getbytes();
22         for (int n = 0; n < 4; n++) 
23             r[a + n] = (byte) (b[n] - '0');
24     }
25     //置换运算p
26     for (int i = 0; i < 32; i++) 
27         result[i] = r[p[i] - 1];
28     return result;
29 }

逆初始置换ip-1

//逆初始置换矩阵
static int[] rip = {
        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
};
 1 /**
 2  * 逆初始置换ip^-1
 3  * @param text  64位数据
 4  * @return
 5  */
 6 static byte[] rip(byte[] text) {
 7     byte[] newtext = new byte[64];
 8     for (int i = 0; i < 64; i++) 
 9         newtext[i] = text[rip[i] - 1];
10     return newtext;
11 }

 加解密过程

 1 /**
 2  * 加密
 3  * @param plaintext  64位明文
 4  * @param skey       64位密钥
 5  * @return           64位密文
 6  */
 7 static byte[] encrypt(byte[] plaintext, byte[] skey) {
 8     byte[][] l = new byte[17][32];
 9     byte[][] r = new byte[17][32];
10     byte[] ciphertext = new byte[64];
11     //子密钥的产生
12     byte[][] k = desutil.generatekeys(skey);
13     //初始置换ip
14     plaintext = desutil.ip(plaintext);
15     //将明文分成左半部分l0和右半部分r0
16     for (int i = 0; i < 32; i++) {
17         l[0][i] = plaintext[i];
18         r[0][i] = plaintext[i + 32];
19     }
20     //加密迭代
21     for (int i = 1; i <= 16; i++) {
22         l[i] = r[i - 1];
23         r[i] = xor(l[i - 1], desutil.f(r[i - 1], k[i - 1]));
24     }
25     //以r16为左半部分,l16为右半部分合并
26     for (int i = 0; i < 32; i++) {
27         ciphertext[i] = r[16][i];
28         ciphertext[i + 32] = l[16][i];
29     }
30     //逆初始置换ip^-1
31     ciphertext = desutil.rip(ciphertext);
32     return ciphertext;
33 }
 1 /**
 2  * 解密
 3  * @param ciphertext  64位密文
 4  * @param skey        64位密钥
 5  * @return            64位明文
 6  */
 7 static byte[] decrypt(byte[] ciphertext, byte[] skey) {
 8     byte[][] l = new byte[17][32];
 9     byte[][] r = new byte[17][32];
10     byte[] plaintext = new byte[64];
11     //子密钥的产生
12     byte[][] k = desutil.generatekeys(skey);
13     //初始置换ip
14     ciphertext = desutil.ip(ciphertext);
15     //将密文分成左半部分r16和右半部分l16
16     for (int i = 0; i < 32; i++) {
17         r[16][i] = ciphertext[i];
18         l[16][i] = ciphertext[i + 32];
19     }
20     //解密迭代
21     for (int i = 16; i >= 1; i--) {
22         l[i - 1] = xor(r[i], desutil.f(l[i], k[i - 1]));
23         r[i - 1] = l[i];
24         r[i] = xor(l[i - 1], desutil.f(r[i - 1], k[i - 1]));
25     }
26     //以l0为左半部分,r0为右半部分合并
27     for (int i = 0; i < 32; i++) {
28         plaintext[i] = l[0][i];
29         plaintext[i + 32] = r[0][i];
30     }
31     //逆初始置换ip^-1
32     plaintext = desutil.rip(plaintext);
33     return plaintext;
34 }
 1 /**
 2  * 两数组异或
 3  * @param a
 4  * @param b
 5  * @return
 6  */
 7 static byte[] xor(byte[] a, byte[] b) {
 8     byte[] c = new byte[a.length];
 9     for (int i = 0; i < a.length; i++) 
10         c[i] = (byte) (a[i] ^ b[i]);
11     return c;
12 }

测试

测试数据

  密钥:00110001 00110010 00110011 00110100 00110101 00110110 00110111 00111000

  明文:00110000 00110001 00110010 00110011 00110100 00110101 00110110 00110111

运行结果

  DES详解(Java实现)


参考文献

  张焕国,唐明.密码学引论(第三版).武汉大学出版社,2015年