首页 > > 程序设计 > Java技术 >

DES详解（Java实现）

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

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_i= R_i-1

　　R_i = L_i-1⊕ f ( R_i-1, k_i)

解密结构

　　L_i-1= R_i⊕ f ( L_i, k_i)

　　R_i-1= L_i

影响因素

　　影响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位作为C₀，后28位作为D₀。

　　置换选择1的矩阵如下：

（2）循环左移

　　每一次迭代，将C_i-1和D_i-1按照一定的位数循环左移分别得到C_i和D_i。

　　循环左移位数表如下：

（3）置换选择2

　　将C_i和D_i合并成一个56位的中间数据，置换选择2从中选择出一个48位的子密钥K_i。

　　置换选择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(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位输入b₁b₂b₃b₄b₅b₆中的第1位和第6位数字b₁b₆组成的二进制数代表选中的行号，其余4位数字b₂b₃b₄b₅组成的二进制数代表选中的列号，将处在行号和列号所代表的位置的数字以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位子密钥：K₁,K₂,...,K₁₆，分别供第1次，第2次，...，第16次加密迭代使用。

　　2.64位明文首先经过初始置换IP，将数据打乱重新排列并分成左右两半，左边32位构成L₀，右边32位构成R₀。

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

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

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

DES的解密过程

　　1.64位密钥经子密钥产生算法产生出16个48位子密钥：K₁,K₂,...,K₁₆，分别供第1次，第2次，...，第16次解密迭代使用。

　　2.64位密文首先经过初始置换IP，将数据打乱重新排列并分成左右两半，左边32位构成R₁₆，右边32位构成L₁₆。

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

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

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

DES的安全性

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

DES的安全弱点

密钥较短

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

存在弱密钥和半弱密钥

　　弱密钥和半弱密钥的存在无疑是DES的一个不足。但由于弱密钥和半弱密钥的数量与密钥的总数2⁵⁶相比仍是微不足道的，所以这并不对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 }