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 "encoding/binary" 8 9 func 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. 36 func 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. 41 func decryptBlock(subkeys []uint64, dst, src []byte) { 42 cryptBlock(subkeys, dst, src, true) 43 } 44 45 // DES Feistel function 46 func 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) 78 var feistelBox [8][64]uint32 79 80 // general purpose function to perform DES block permutations 81 func 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 89 func 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. 113 func 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. 181 func 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 207 func 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 221 func (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. 242 func 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
