libgo/go/crypto/des/block.go

   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 }