block.go

Documentation: crypto/des

		 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