DES详解(Java实现)
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最早提出的。由于它是对称的密码结构,所以对信息加密和解密的过程就极为相似,甚至完全一样。这就使得在实施的过程中,对编码量和线路传输的要求就减少了几乎一半。
加密结构
li = ri-1
ri = li-1 ⊕ f ( ri-1 , ki )
解密结构
li-1 = ri ⊕ f ( li , ki )
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位加到si (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年