DES详解(Java实现)

2019-01-16 05:50:55来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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)

  

解密结构

  Li-1 = R⊕ f ( L, k)

  Ri-1 = Li

  

影响因素

  影响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的矩阵如下:

  

(2)循环左移

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

  循环左移位数表如下:

  

(3)置换选择2

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

  置换选择2的矩阵如下:

  

初始置换IP

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

  初始置换IP的矩阵如下:

  

轮函数

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

(1)选择运算E

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

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

  选择运算E的矩阵如下:

  

(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盒的代替矩阵如下:

  

  

  

  

  

  

  

  

(4)置换运算P

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

  置换运算P的矩阵如下:

  

逆初始置换IP-1

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

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

  


 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

运行结果

  


参考文献

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


原文链接:https://www.cnblogs.com/mx-lqk/p/10255149.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:深入剖析Tomcat(2)

下一篇:数据结构 -- 红黑树精解