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