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 "encoding/binary" 9 ) 10 11 func 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. 32 func 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. 37 func decryptBlock(subkeys []uint64, dst, src []byte) { 38 cryptBlock(subkeys, dst, src, true) 39 } 40 41 // DES Feistel function 42 func 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) 59 var feistelBox [8][64]uint32 60 61 // general purpose function to perform DES block permutations 62 func 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 70 func 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(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. 84 func 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. 99 func 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. 167 func 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 193 func 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 207 func (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