1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package des
6
7import "encoding/binary"
8
9func cryptBlock(subkeys []uint64, dst, src []byte, decrypt bool) {
10	b := binary.BigEndian.Uint64(src)
11	b = permuteInitialBlock(b)
12	left, right := uint32(b>>32), uint32(b)
13
14	left = (left << 1) | (left >> 31)
15	right = (right << 1) | (right >> 31)
16
17	if decrypt {
18		for i := 0; i < 8; i++ {
19			left, right = feistel(left, right, subkeys[15-2*i], subkeys[15-(2*i+1)])
20		}
21	} else {
22		for i := 0; i < 8; i++ {
23			left, right = feistel(left, right, subkeys[2*i], subkeys[2*i+1])
24		}
25	}
26
27	left = (left << 31) | (left >> 1)
28	right = (right << 31) | (right >> 1)
29
30	// switch left & right and perform final permutation
31	preOutput := (uint64(right) << 32) | uint64(left)
32	binary.BigEndian.PutUint64(dst, permuteFinalBlock(preOutput))
33}
34
35// Encrypt one block from src into dst, using the subkeys.
36func encryptBlock(subkeys []uint64, dst, src []byte) {
37	cryptBlock(subkeys, dst, src, false)
38}
39
40// Decrypt one block from src into dst, using the subkeys.
41func decryptBlock(subkeys []uint64, dst, src []byte) {
42	cryptBlock(subkeys, dst, src, true)
43}
44
45// DES Feistel function
46func feistel(l, r uint32, k0, k1 uint64) (lout, rout uint32) {
47	var t uint32
48
49	t = r ^ uint32(k0>>32)
50	l ^= feistelBox[7][t&0x3f] ^
51		feistelBox[5][(t>>8)&0x3f] ^
52		feistelBox[3][(t>>16)&0x3f] ^
53		feistelBox[1][(t>>24)&0x3f]
54
55	t = ((r << 28) | (r >> 4)) ^ uint32(k0)
56	l ^= feistelBox[6][(t)&0x3f] ^
57		feistelBox[4][(t>>8)&0x3f] ^
58		feistelBox[2][(t>>16)&0x3f] ^
59		feistelBox[0][(t>>24)&0x3f]
60
61	t = l ^ uint32(k1>>32)
62	r ^= feistelBox[7][t&0x3f] ^
63		feistelBox[5][(t>>8)&0x3f] ^
64		feistelBox[3][(t>>16)&0x3f] ^
65		feistelBox[1][(t>>24)&0x3f]
66
67	t = ((l << 28) | (l >> 4)) ^ uint32(k1)
68	r ^= feistelBox[6][(t)&0x3f] ^
69		feistelBox[4][(t>>8)&0x3f] ^
70		feistelBox[2][(t>>16)&0x3f] ^
71		feistelBox[0][(t>>24)&0x3f]
72
73	return l, r
74}
75
76// feistelBox[s][16*i+j] contains the output of permutationFunction
77// for sBoxes[s][i][j] << 4*(7-s)
78var feistelBox [8][64]uint32
79
80// general purpose function to perform DES block permutations
81func permuteBlock(src uint64, permutation []uint8) (block uint64) {
82	for position, n := range permutation {
83		bit := (src >> n) & 1
84		block |= bit << uint((len(permutation)-1)-position)
85	}
86	return
87}
88
89func init() {
90	for s := range sBoxes {
91		for i := 0; i < 4; i++ {
92			for j := 0; j < 16; j++ {
93				f := uint64(sBoxes[s][i][j]) << (4 * (7 - uint(s)))
94				f = permuteBlock(f, permutationFunction[:])
95
96				// Row is determined by the 1st and 6th bit.
97				// Column is the middle four bits.
98				row := uint8(((i & 2) << 4) | i&1)
99				col := uint8(j << 1)
100				t := row | col
101
102				// The rotation was performed in the feistel rounds, being factored out and now mixed into the feistelBox.
103				f = (f << 1) | (f >> 31)
104
105				feistelBox[s][t] = uint32(f)
106			}
107		}
108	}
109}
110
111// permuteInitialBlock is equivalent to the permutation defined
112// by initialPermutation.
113func permuteInitialBlock(block uint64) uint64 {
114	// block = b7 b6 b5 b4 b3 b2 b1 b0 (8 bytes)
115	b1 := block >> 48
116	b2 := block << 48
117	block ^= b1 ^ b2 ^ b1<<48 ^ b2>>48
118
119	// block = b1 b0 b5 b4 b3 b2 b7 b6
120	b1 = block >> 32 & 0xff00ff
121	b2 = (block & 0xff00ff00)
122	block ^= b1<<32 ^ b2 ^ b1<<8 ^ b2<<24 // exchange b0 b4 with b3 b7
123
124	// block is now b1 b3 b5 b7 b0 b2 b4 b7, the permutation:
125	//                  ...  8
126	//                  ... 24
127	//                  ... 40
128	//                  ... 56
129	//  7  6  5  4  3  2  1  0
130	// 23 22 21 20 19 18 17 16
131	//                  ... 32
132	//                  ... 48
133
134	// exchange 4,5,6,7 with 32,33,34,35 etc.
135	b1 = block & 0x0f0f00000f0f0000
136	b2 = block & 0x0000f0f00000f0f0
137	block ^= b1 ^ b2 ^ b1>>12 ^ b2<<12
138
139	// block is the permutation:
140	//
141	//   [+8]         [+40]
142	//
143	//  7  6  5  4
144	// 23 22 21 20
145	//  3  2  1  0
146	// 19 18 17 16    [+32]
147
148	// exchange 0,1,4,5 with 18,19,22,23
149	b1 = block & 0x3300330033003300
150	b2 = block & 0x00cc00cc00cc00cc
151	block ^= b1 ^ b2 ^ b1>>6 ^ b2<<6
152
153	// block is the permutation:
154	// 15 14
155	// 13 12
156	// 11 10
157	//  9  8
158	//  7  6
159	//  5  4
160	//  3  2
161	//  1  0 [+16] [+32] [+64]
162
163	// exchange 0,2,4,6 with 9,11,13,15:
164	b1 = block & 0xaaaaaaaa55555555
165	block ^= b1 ^ b1>>33 ^ b1<<33
166
167	// block is the permutation:
168	// 6 14 22 30 38 46 54 62
169	// 4 12 20 28 36 44 52 60
170	// 2 10 18 26 34 42 50 58
171	// 0  8 16 24 32 40 48 56
172	// 7 15 23 31 39 47 55 63
173	// 5 13 21 29 37 45 53 61
174	// 3 11 19 27 35 43 51 59
175	// 1  9 17 25 33 41 49 57
176	return block
177}
178
179// permuteInitialBlock is equivalent to the permutation defined
180// by finalPermutation.
181func permuteFinalBlock(block uint64) uint64 {
182	// Perform the same bit exchanges as permuteInitialBlock
183	// but in reverse order.
184	b1 := block & 0xaaaaaaaa55555555
185	block ^= b1 ^ b1>>33 ^ b1<<33
186
187	b1 = block & 0x3300330033003300
188	b2 := block & 0x00cc00cc00cc00cc
189	block ^= b1 ^ b2 ^ b1>>6 ^ b2<<6
190
191	b1 = block & 0x0f0f00000f0f0000
192	b2 = block & 0x0000f0f00000f0f0
193	block ^= b1 ^ b2 ^ b1>>12 ^ b2<<12
194
195	b1 = block >> 32 & 0xff00ff
196	b2 = (block & 0xff00ff00)
197	block ^= b1<<32 ^ b2 ^ b1<<8 ^ b2<<24
198
199	b1 = block >> 48
200	b2 = block << 48
201	block ^= b1 ^ b2 ^ b1<<48 ^ b2>>48
202	return block
203}
204
205// creates 16 28-bit blocks rotated according
206// to the rotation schedule
207func ksRotate(in uint32) (out []uint32) {
208	out = make([]uint32, 16)
209	last := in
210	for i := 0; i < 16; i++ {
211		// 28-bit circular left shift
212		left := (last << (4 + ksRotations[i])) >> 4
213		right := (last << 4) >> (32 - ksRotations[i])
214		out[i] = left | right
215		last = out[i]
216	}
217	return
218}
219
220// creates 16 56-bit subkeys from the original key
221func (c *desCipher) generateSubkeys(keyBytes []byte) {
222	// apply PC1 permutation to key
223	key := binary.BigEndian.Uint64(keyBytes)
224	permutedKey := permuteBlock(key, permutedChoice1[:])
225
226	// rotate halves of permuted key according to the rotation schedule
227	leftRotations := ksRotate(uint32(permutedKey >> 28))
228	rightRotations := ksRotate(uint32(permutedKey<<4) >> 4)
229
230	// generate subkeys
231	for i := 0; i < 16; i++ {
232		// combine halves to form 56-bit input to PC2
233		pc2Input := uint64(leftRotations[i])<<28 | uint64(rightRotations[i])
234		// apply PC2 permutation to 7 byte input
235		c.subkeys[i] = unpack(permuteBlock(pc2Input, permutedChoice2[:]))
236	}
237}
238
239// Expand 48-bit input to 64-bit, with each 6-bit block padded by extra two bits at the top.
240// By doing so, we can have the input blocks (four bits each), and the key blocks (six bits each) well-aligned without
241// extra shifts/rotations for alignments.
242func unpack(x uint64) uint64 {
243	var result uint64
244
245	result = ((x>>(6*1))&0xff)<<(8*0) |
246		((x>>(6*3))&0xff)<<(8*1) |
247		((x>>(6*5))&0xff)<<(8*2) |
248		((x>>(6*7))&0xff)<<(8*3) |
249		((x>>(6*0))&0xff)<<(8*4) |
250		((x>>(6*2))&0xff)<<(8*5) |
251		((x>>(6*4))&0xff)<<(8*6) |
252		((x>>(6*6))&0xff)<<(8*7)
253
254	return result
255}
256