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