Source file src/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 (
     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 b7, 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