背景

    DES加密算法由NBS(美国国家标准局)颁布于1977年, 这套算法由IBM公司研制,并于1998年12月起出于密钥长度的原因, NBS停止使用DES.其后替代以AES为加密标准的新算法.

    该算法的分组长度是64比特，密钥长度为56比特，属于Feistel结构密码 迭代轮数为16轮。Feistel结构密码的一大特点是加解密一致，因此算法实现时占用资源少、效率高。采用DES算法加密时，64比特的明文首先经过一个初始置换然后通过由轮密钥控制的16轮迭代变换，最后再通过初始置换的逆变换进而得到密文。

加密流程

表置换原理

PC-1、PC-2、IP、IP逆以及P表置换原理相同, 例子如下

1
2
3
4
置换表P [3,6,4,1,2,5]  原数据表D[11,22,33,44,55,66,77]

置换后的表N[D[P[0]], D[P[1], D[P[2]], D[P[3]], D[P[4]], D[P[5]]]
N = [44, 77, 55, 22, 33, 66] N的长度与P一致

种子密钥扩展

​ 种子密钥扩展图

  1. 将预先给定的64bit的密钥按PC-1表进行置换, 即将第8, 16, 24, 32, 40, 48, 56, 64位去掉并且打乱密钥的排序 这里DES需要的其实是56bit的密钥,被去掉的位为奇偶校验位,只是为了保证密钥不出错,但为了密钥记录方便,这里直接写入64bit的字符串.

  2. 种子密钥K经过PC-1置换缩小为56bit的新密钥PC-1(K)这里PC-1(K) = C0D0,C0D0为其左右两个部分,各28bit.PC-1表如下:

    image-20220805164141887

    之后按照左移表分别进行循环左移, 左移表如下:

image-20220805163035304

1
2
demo
	[1,2,3,4,5] i=1 对应ti=1(偏移量) ======>  [2,3,4,5,1]
  1. 左移之后将新生成的CiDi复制一份,循环执行2中左移的操作.

​ CiDi接下来继续进行PC-2置换, 生成PC-2(CiDi) = Ki(48bit) PC-2表如下

PC-2置换表

明文加密

image-20220805171610888

  1. 将明文X通过IP置换为IP(x) 此时IP(x) 仍为64bit

  2. 拆分IP(X)为L0, R0两部分,分别占32bit.

  3. 对R0进行F函数运算:

    1. E扩展

      R0经过扩展变换E获得48bit的新变量E(R0), E表如下

      image-20220805172330114

    2. 与子密钥Ki进行异或运算, 此时E(Ri)与子密钥Ki都是48bit, 获得B=E®⊕Ki

    3. S盒压缩, 将得到的B(48bit)分成八组, 每6bit, 其中第一,最后一位拼接,中间四位拼接,例如 B1B2B3B4B5B6, 其中B1与B6组成S盒的行数,B2B3B4B5对应S盒的列数

      s1 =[
      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
      ]

      这里S盒中 第0行为14,4,13……所在行, 依次往后推, 第0列为14,0,4,15所在列,依次往后推, 假设B = [011001 110011 ……] , 其中的011001, B1B6=01对应第1行, B2B3B4B5=1100,对应第12列,查表S1可得对应转换的数为9=1001. 以此类推,将48bit的数据压缩到32bit( 每组减少2bit, 2*8=16),名为变量C

    4. P盒置换, 将C通过P表进行置换为P©,P表如下:
      image-20220805180734819

  4. P©与L0异或得到L1,并令R1=L0, 将L1,R2重复2-4(大)步骤,一直到第十六轮

  5. 对L16, R16进行IP逆置换,Y = IP-1(R16, L16),此时Y就是密文. 这里注意左右密钥位置

解密过程分析

image-20220805183258166

​ 算法支撑部分目前没能力分析, 对合变换这块没看太懂

​ **解密时将子密钥逆置即可实现 **

​

​

代码实现(Golang)

子密钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func generateKey(data string) [][]int {
	formKey := byteConBit(data)
	resList := make([][]int, 16, 48)
	var off = []int{1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}

	// pc-1置换
	formKey = displace(pc1Table, formKey, len(pc1Table))
	leftKey := formKey[:len(formKey)/2]
	rightKey := formKey[len(formKey)/2:]

	TempresList := make([][]int, 16, 56)
	// 双左移且迭代16次
	for i := 0; i < len(off); i++ {
		leftKey = leftOffX(leftKey, off[i])
		rightKey = leftOffX(rightKey, off[i])
		TempresList[i] = append(leftKey, rightKey...)
		resList[i] = displace(pc2Table, TempresList[i], len(pc2Table))
	}
	// pc-2置换
	return resList
}

这里的PC-1置换中displace函数如下:

1
2
3
4
5
6
7
func displace(table []int, data []int, length int) []int {
	resTable := make([]int, length)
	for i := 0; i < length; i++ {
		resTable[i] = data[table[i]-1]
	}
	return resTable
}

table就是对应的表, data是要修改的数据, 最后按照表的逻辑结构返回一个长度为length的新数组

leftOffX函数如下

1
2
3
func leftOffX(key []int, off int) []int {
	return append(key[off:], key[:off]...)
}

其中off是偏移量, key是要修改的数据, 之后PC-2跟PC-1用的同一个函数,置换后的子密钥全都存放在resList数组里

加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func des(data string, cipherKey string) (resList []int) {
	if len(data)%8 != 0 {
		var crush byte
		// 填充字符串
		dataLackLength := 8 - len(data)%8
		for i := 0; i < dataLackLength; i++ {
			data += string(crush)
		}
	}
	plainText := displace(ipDisplace, byteConBit(data), len(ipDisplace))
	// 子密钥生成
	childrenKeyList := generateKey(cipherKey) // 16轮子密钥获取 Ki
	// 加密
	leftData := plainText[:len(plainText)/2]
	rightData := plainText[len(plainText)/2:]

	for i := 0; i < len(childrenKeyList); i++ {
		leftData, rightData = goRound(leftData, rightData, childrenKeyList[i])
	}
	// print("迭代结果:")
	// fmt.Println(append(leftData, rightData...))
	resList = displace(reIpDisplace, append(rightData, leftData...), 64)
	return
}

这里填充字符的方式是EBC, 不适合加密文件,会造成空白以及重复

1
2
3
4
5
6
7
8
9
	if len(data)%8 != 0 {
		var crush byte
		// 填充字符串
		dataLackLength := 8 - len(data)%8
		for i := 0; i < dataLackLength; i++ {
			data += string(crush)
		}
	}
// data=11001      填充后data=00011001

byteConBit函数: 将输入的字符串全转换为64bit的数组, 不够的前边用0填充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func byteConBit(data string) (initDataList []int) {
	newData := []uint8(data) // 将数据全部转化为比特
	initDataList = make([]int, 64)
	toBinaryList := "" // 存放下边填充后的toBinary
	for _, v := range newData {
		// newData组里每个元素都转为2进制
		toBinary := strconv.FormatUint(uint64(v), 2)
		for len(toBinary) < 8 {
			toBinary = "0" + toBinary
		}
		toBinaryList += toBinary
	}

	for i := 0; i < len(toBinaryList); i++ {
		initDataList[i], _ = strconv.Atoi(string(toBinaryList[i])) // 这里如果不满足指定位数会大端序补零
	}
	return
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
package main

import (
	"fmt"
	"strconv"
)

/**
author: i4mhmh

*/

// ip置换
var ipDisplace = []int{
	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,
}

// ip逆置换
var reIpDisplace = []int{
	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,
}

// f函数部分表

var ebox = []int{
	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,
}

var pc1Table = []int{
	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,
}

var pc2Table = []int{
	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,
}

var sBoxzip = [][]int{
	{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},
	{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},
	{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},
	{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},
	{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},
	{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},
	{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},
	{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},
}

// p置换

var pDisplace = []int{
	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,
}

// goRound进行16轮迭代

func goRound(leftData, rightData, subKey []int) ([]int, []int) {
	return rightData, dealXor(leftData, Feistel(rightData, subKey))
}

//f函数
func Feistel(rightData, subKey []int) []int {
	rightData = displace(ebox, rightData, 48) // e扩展
	Data := dealXor(rightData, subKey)
	Data = sBox(Data) // s盒压缩
	Data = displace(pDisplace, Data, 32)
	return Data
}

// 子密钥生成分支
func generateKey(data string) [][]int {
	formKey := byteConBit(data)
	resList := make([][]int, 16, 48)
	var off = []int{1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}

	// pc-1置换
	formKey = displace(pc1Table, formKey, len(pc1Table))
	leftKey := formKey[:len(formKey)/2]
	rightKey := formKey[len(formKey)/2:]

	TempresList := make([][]int, 16, 56)
	// 双左移且迭代16次
	for i := 0; i < len(off); i++ {
		leftKey = leftOffX(leftKey, off[i])
		rightKey = leftOffX(rightKey, off[i])
		TempresList[i] = append(leftKey, rightKey...)
		resList[i] = displace(pc2Table, TempresList[i], len(pc2Table))
	}
	// fmt.Println(resList)
	// pc-2置换
	return resList
}

// 循环左移函数
func leftOffX(key []int, off int) []int {
	return append(key[off:], key[:off]...)
}

//字节转换为比特 <= 8字节
func byteConBit(data string) (initDataList []int) {
	newData := []uint8(data) // 将数据全部转化为比特
	initDataList = make([]int, 64)
	toBinaryList := "" // 存放下边填充后的toBinary
	for _, v := range newData {
		// newData组里每个元素都转为2进制
		toBinary := strconv.FormatUint(uint64(v), 2)
		for len(toBinary) < 8 {
			toBinary = "0" + toBinary
		}
		toBinaryList += toBinary
	}

	for i := 0; i < len(toBinaryList); i++ {
		initDataList[i], _ = strconv.Atoi(string(toBinaryList[i])) // 这里如果不满足指定位数会大端序补零
	}
	return
}

// 解密置换
func decodeByteConBit(newData []uint8) (initDataList []int) {
	initDataList = make([]int, 64)
	toBinaryList := "" // 存放下边填充后的toBinary
	for _, v := range newData {
		// newData组里每个元素都转为2进制
		toBinary := strconv.FormatUint(uint64(v), 2)
		for len(toBinary) < 8 {
			toBinary = "0" + toBinary
		}
		toBinaryList += toBinary
	}

	for i := 0; i < len(toBinaryList); i++ {
		initDataList[i], _ = strconv.Atoi(string(toBinaryList[i])) // 这里如果不满足指定位数会大端序补零
	}
	return
}

// 一个盒table, 修改的表data, 输出长度length 用于置换
func displace(table []int, data []int, length int) []int {
	resTable := make([]int, length)
	for i := 0; i < length; i++ {
		resTable[i] = data[table[i]-1]
	}
	return resTable
}

// 异或函数
func dealXor(a, b []int) []int {
	xoResult := make([]int, len(a))
	for i := 0; i < len(a); i++ {
		xoResult[i] = a[i] ^ b[i]
	}
	return xoResult
}

func sBox(data []int) []int {
	resStr := ""
	for i := 0; i < 8; i++ {
		s := data[i*6 : (i+1)*6]
		x := s[0]*2 + s[5]
		y := s[1]*8 + s[2]*4 + s[3]*2 + s[4]
		// s盒关键处理
		temp := strconv.FormatInt(int64(sBoxzip[i][x*16+y]), 2)
		for len(temp) < 4 {
			temp = "0" + temp
		}
		resStr += temp
	}

	res := make([]int, len(resStr))
	for i := 0; i < len(resStr); i++ {
		res[i], _ = strconv.Atoi(string(resStr[i]))
	}
	return res
}

// 得到的二进制数组转换为字符串
func binToByte(data []int) (result []uint8) {
	for i := 0; i < 8; i++ {
		tempStr := ""
		binData := data[i*8 : (i+1)*8]
		for _, v := range binData {
			tempStr += strconv.Itoa(v)
		}
		temp, _ := strconv.ParseInt(tempStr, 2, 64)
		result = append(result, uint8(temp))
	}

	return
}

func formData(data string) {

}

func des(data string, cipherKey string) (resList []int) {
	if len(data)%8 != 0 {
		var crush byte
		// 填充字符串
		dataLackLength := 8 - len(data)%8
		for i := 0; i < dataLackLength; i++ {
			data += string(crush)
		}
	}
	fmt.Println(len(data))
	plainText := displace(ipDisplace, byteConBit(data), len(ipDisplace))
	// 子密钥生成
	childrenKeyList := generateKey(cipherKey) // 16轮子密钥获取 Ki
	// 加密
	leftData := plainText[:len(plainText)/2]
	rightData := plainText[len(plainText)/2:]

	for i := 0; i < len(childrenKeyList); i++ {
		leftData, rightData = goRound(leftData, rightData, childrenKeyList[i])
	}
	// print("迭代结果:")
	// fmt.Println(append(leftData, rightData...))
	resList = displace(reIpDisplace, append(rightData, leftData...), 64)
	return
}

func main() {
	//IP置换

	fmt.Println(des("桂林", "11223344"))

	encode_res := des("桂林", "11223344")

	decodeText := displace(ipDisplace, encode_res, 64)
	leftDecodeData := decodeText[:len(decodeText)/2]
	rightDecodeData := decodeText[len(decodeText)/2:]

	childrenKeyList := generateKey("11223344")
	for i := 15; i >= 0; i-- {
		leftDecodeData, rightDecodeData = goRound(leftDecodeData, rightDecodeData, childrenKeyList[i])
	}
	decode_res := displace(reIpDisplace, append(rightDecodeData, leftDecodeData...), 64)
	fmt.Print("解密结果:")
	fmt.Println(string(binToByte(decode_res)))
}

这里代码还没有整理, 先push上能跑起来, 结果如下:

加密过后生成的64bit的密文

image-20220805183720593

解密:

image-20220805184012653