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 (
8	"encoding/binary"
9)
10
11func cryptBlock(subkeys []uint64, dst, src []byte, decrypt bool) {
12	b := binary.BigEndian.Uint64(src)
13	b = permuteInitialBlock(b)
14	left, right := uint32(b>>32), uint32(b)
15
16	var subkey uint64
17	for i := 0; i < 16; i++ {
18		if decrypt {
19			subkey = subkeys[15-i]
20		} else {
21			subkey = subkeys[i]
22		}
23
24		left, right = right, left^feistel(right, subkey)
25	}
26	// switch left & right and perform final permutation
27	preOutput := (uint64(right) << 32) | uint64(left)
28	binary.BigEndian.PutUint64(dst, permuteFinalBlock(preOutput))
29}
30
31// Encrypt one block from src into dst, using the subkeys.
32func encryptBlock(subkeys []uint64, dst, src []byte) {
33	cryptBlock(subkeys, dst, src, false)
34}
35
36// Decrypt one block from src into dst, using the subkeys.
37func decryptBlock(subkeys []uint64, dst, src []byte) {
38	cryptBlock(subkeys, dst, src, true)
39}
40
41// DES Feistel function
42func feistel(right uint32, key uint64) (result uint32) {
43	sBoxLocations := key ^ expandBlock(right)
44	var sBoxResult uint32
45	for i := uint8(0); i < 8; i++ {
46		sBoxLocation := uint8(sBoxLocations>>42) & 0x3f
47		sBoxLocations <<= 6
48		// row determined by 1st and 6th bit
49		// column is middle four bits
50		row := (sBoxLocation & 0x1) | ((sBoxLocation & 0x20) >> 4)
51		column := (sBoxLocation >> 1) & 0xf
52		sBoxResult ^= feistelBox[i][16*row+column]
53	}
54	return sBoxResult
55}
56
57// feistelBox[s][16*i+j] contains the output of permutationFunction
58// for sBoxes[s][i][j] << 4*(7-s)
59var feistelBox [8][64]uint32
60
61// general purpose function to perform DES block permutations
62func permuteBlock(src uint64, permutation []uint8) (block uint64) {
63	for position, n := range permutation {
64		bit := (src >> n) & 1
65		block |= bit << uint((len(permutation)-1)-position)
66	}
67	return
68}
69
70func init() {
71	for s := range sBoxes {
72		for i := 0; i < 4; i++ {
73			for j := 0; j < 16; j++ {
74				f := uint64(sBoxes[s][i][j]) << (4 * (7 - uint(s)))
75				f = permuteBlock(uint64(f), permutationFunction[:])
76				feistelBox[s][16*i+j] = uint32(f)
77			}
78		}
79	}
80}
81
82// expandBlock expands an input block of 32 bits,
83// producing an output block of 48 bits.
84func expandBlock(src uint32) (block uint64) {
85	// rotate the 5 highest bits to the right.
86	src = (src << 5) | (src >> 27)
87	for i := 0; i < 8; i++ {
88		block <<= 6
89		// take the 6 bits on the right
90		block |= uint64(src) & (1<<6 - 1)
91		// advance by 4 bits.
92		src = (src << 4) | (src >> 28)
93	}
94	return
95}
96
97// permuteInitialBlock is equivalent to the permutation defined
98// by initialPermutation.
99func permuteInitialBlock(block uint64) uint64 {
100	// block = b7 b6 b5 b4 b3 b2 b1 b0 (8 bytes)
101	b1 := block >> 48
102	b2 := block << 48
103	block ^= b1 ^ b2 ^ b1<<48 ^ b2>>48
104
105	// block = b1 b0 b5 b4 b3 b2 b7 b6
106	b1 = block >> 32 & 0xff00ff
107	b2 = (block & 0xff00ff00)
108	block ^= b1<<32 ^ b2 ^ b1<<8 ^ b2<<24 // exchange b0 b4 with b3 b7
109
110	// block is now b1 b3 b5 b7 b0 b2 b4 b7, the permutation:
111	//                  ...  8
112	//                  ... 24
113	//                  ... 40
114	//                  ... 56
115	//  7  6  5  4  3  2  1  0
116	// 23 22 21 20 19 18 17 16
117	//                  ... 32
118	//                  ... 48
119
120	// exchange 4,5,6,7 with 32,33,34,35 etc.
121	b1 = block & 0x0f0f00000f0f0000
122	b2 = block & 0x0000f0f00000f0f0
123	block ^= b1 ^ b2 ^ b1>>12 ^ b2<<12
124
125	// block is the permutation:
126	//
127	//   [+8]         [+40]
128	//
129	//  7  6  5  4
130	// 23 22 21 20
131	//  3  2  1  0
132	// 19 18 17 16    [+32]
133
134	// exchange 0,1,4,5 with 18,19,22,23
135	b1 = block & 0x3300330033003300
136	b2 = block & 0x00cc00cc00cc00cc
137	block ^= b1 ^ b2 ^ b1>>6 ^ b2<<6
138
139	// block is the permutation:
140	// 15 14
141	// 13 12
142	// 11 10
143	//  9  8
144	//  7  6
145	//  5  4
146	//  3  2
147	//  1  0 [+16] [+32] [+64]
148
149	// exchange 0,2,4,6 with 9,11,13,15:
150	b1 = block & 0xaaaaaaaa55555555
151	block ^= b1 ^ b1>>33 ^ b1<<33
152
153	// block is the permutation:
154	// 6 14 22 30 38 46 54 62
155	// 4 12 20 28 36 44 52 60
156	// 2 10 18 26 34 42 50 58
157	// 0  8 16 24 32 40 48 56
158	// 7 15 23 31 39 47 55 63
159	// 5 13 21 29 37 45 53 61
160	// 3 11 19 27 35 43 51 59
161	// 1  9 17 25 33 41 49 57
162	return block
163}
164
165// permuteInitialBlock is equivalent to the permutation defined
166// by finalPermutation.
167func permuteFinalBlock(block uint64) uint64 {
168	// Perform the same bit exchanges as permuteInitialBlock
169	// but in reverse order.
170	b1 := block & 0xaaaaaaaa55555555
171	block ^= b1 ^ b1>>33 ^ b1<<33
172
173	b1 = block & 0x3300330033003300
174	b2 := block & 0x00cc00cc00cc00cc
175	block ^= b1 ^ b2 ^ b1>>6 ^ b2<<6
176
177	b1 = block & 0x0f0f00000f0f0000
178	b2 = block & 0x0000f0f00000f0f0
179	block ^= b1 ^ b2 ^ b1>>12 ^ b2<<12
180
181	b1 = block >> 32 & 0xff00ff
182	b2 = (block & 0xff00ff00)
183	block ^= b1<<32 ^ b2 ^ b1<<8 ^ b2<<24
184
185	b1 = block >> 48
186	b2 = block << 48
187	block ^= b1 ^ b2 ^ b1<<48 ^ b2>>48
188	return block
189}
190
191// creates 16 28-bit blocks rotated according
192// to the rotation schedule
193func ksRotate(in uint32) (out []uint32) {
194	out = make([]uint32, 16)
195	last := in
196	for i := 0; i < 16; i++ {
197		// 28-bit circular left shift
198		left := (last << (4 + ksRotations[i])) >> 4
199		right := (last << 4) >> (32 - ksRotations[i])
200		out[i] = left | right
201		last = out[i]
202	}
203	return
204}
205
206// creates 16 56-bit subkeys from the original key
207func (c *desCipher) generateSubkeys(keyBytes []byte) {
208	// apply PC1 permutation to key
209	key := binary.BigEndian.Uint64(keyBytes)
210	permutedKey := permuteBlock(key, permutedChoice1[:])
211
212	// rotate halves of permuted key according to the rotation schedule
213	leftRotations := ksRotate(uint32(permutedKey >> 28))
214	rightRotations := ksRotate(uint32(permutedKey<<4) >> 4)
215
216	// generate subkeys
217	for i := 0; i < 16; i++ {
218		// combine halves to form 56-bit input to PC2
219		pc2Input := uint64(leftRotations[i])<<28 | uint64(rightRotations[i])
220		// apply PC2 permutation to 7 byte input
221		c.subkeys[i] = permuteBlock(pc2Input, permutedChoice2[:])
222	}
223}
224