DES算法
DES的基本构造元件
初始置换（Initial Permutation，IP）
初始置换为64位数组，Golang中采用的初始置换如下所示
// ctypto/des/const.go
package des
// Used to perform an initial permutation of a 64-bit input block.
var initialPermutation = [64]byte{
6, 14, 22, 30, 38, 46, 54, 62,
4, 12, 20, 28, 36, 44, 52, 60,
2, 10, 18, 26, 34, 42, 50, 58,
0, 8, 16, 24, 32, 40, 48, 56,
7, 15, 23, 31, 39, 47, 55, 63,
5, 13, 21, 29, 37, 45, 53, 61,
3, 11, 19, 27, 35, 43, 51, 59,
1, 9, 17, 25, 33, 41, 49, 57,
}
对于64位输入，通过IP将byte[i]位映射到i位，如下图所示。
逆初始置换(Inverse of Initial Permutation，
)
逆初始置换Golang中采用的初始置换如下所示，置换方式不变
// ctypto/des/const.go
package des
// Used to perform a final permutation of a 4-bit preoutput block. This is the
// inverse of initialPermutation
var finalPermutation = [64]byte{
24, 56, 16, 48, 8, 40, 0, 32,
25, 57, 17, 49, 9, 41, 1, 33,
26, 58, 18, 50, 10, 42, 2, 34,
27, 59, 19, 51, 11, 43, 3, 35,
28, 60, 20, 52, 12, 44, 4, 36,
29, 61, 21, 53, 13, 45, 5, 37,
30, 62, 22, 54, 14, 46, 6, 38,
31, 63, 23, 55, 15, 47, 7, 39,
}
DES轮（Feistel），
标准中需要16轮加密，每一轮的过程为：
(1) 置换之后的64位数据会被分为高32位和低32位，
(2) 通过秘钥
(3) 在第
(4) 第
-
。然后
）.- E盒，Golang中采用的如下
// Used to expand an input block of 32 bits, producing an output block of 48 // bits. var expansionFunction = [48]byte{ 0, 31, 30, 29, 28, 27, 28, 27, 26, 25, 24, 23, 24, 23, 22, 21, 20, 19, 20, 19, 18, 17, 16, 15, 16, 15, 14, 13, 12, 11, 12, 11, 10, 9, 8, 7, 8, 7, 6, 5, 4, 3, 4, 3, 2, 1, 0, 31, }- S-盒有8个，每个将6bit数据置换为4bit。假设S-box 1的输入为
, 通过
的最高位1和最低位0，可以确定行为
（最高位<< 1 | 最低位),通络其余的四位
可确定列为
，则置换的结果为
。以Golang中的sBoxs为例，结果为sBoxes[0][2][2] =
。关于构造的S盒需要满足一定的性质，可参考相关的文献和书籍。
// Used in the DES cipher function var sBoxes = [8][4][16]uint8{ // S-box 1 { {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7}, {0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8}, {4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0}, {15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13}, }, ...... // S-box 8 { {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7}, {1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2}, {7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8}, {2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}, }, }
f函数
秘钥编排
从DES每轮的加密的过程可以知道，每轮需要一个子秘钥。如何将原始的56位秘钥中得到16个48位的子秘钥被称为秘钥编排。但是DES的秘钥其实为64位，每8位一组，每组的最后一位是奇偶校检位。流程如下：
（1） 去掉校检位之后得到的56位秘钥会经过初试秘钥置换（Permuted Choice 1, PC1）。将56位秘钥分成长度为28位的
i = 1,2,9,16时，一位；其他轮数时，两位。
（2） 在每一轮移动完成时候通过置换选择2（Permuted Choice 2, PC2）将56位置换为48位的子秘钥
image
Golang中使用的PC1和PC2如下所示。
// Used in the key schedule to select 56 bits
// from a 64-bit input.
var permutedChoice1 = [56]byte{
7, 15, 23, 31, 39, 47, 55, 63,
6, 14, 22, 30, 38, 46, 54, 62,
5, 13, 21, 29, 37, 45, 53, 61,
4, 12, 20, 28, 1, 9, 17, 25,
33, 41, 49, 57, 2, 10, 18, 26,
34, 42, 50, 58, 3, 11, 19, 27,
35, 43, 51, 59, 36, 44, 52, 60,
}
// Used in the key schedule to produce each subkey by selecting 48 bits from
// the 56-bit input
var permutedChoice2 = [48]byte{
42, 39, 45, 32, 55, 51, 53, 28,
41, 50, 35, 46, 33, 37, 44, 52,
30, 48, 40, 49, 29, 36, 43, 54,
15, 4, 25, 19, 9, 1, 26, 16,
5, 11, 23, 8, 12, 7, 17, 0,
22, 3, 10, 14, 6, 20, 27, 24,
}
DES 加密和解密
加密和解密过程就是基本构造元件按照一定的顺序组合起来。
加密过程
DES 加密过程
解密过程
DES 加密过程
Golang中DES实现
Golang中DES实现在crypto/des包中。
- crypto/des
- cipher.go // 定义DES加密类型：DES和3DES，暴露加解密方法，DES的16轮加密在Block中实现。
- block.go // 加解密的具体实现
- const.go // 定义des中的置换：IP, $IP^-1$, eBox, sBoxs, f函数的PC1和PC2
cipher.go
改文件中定义了DES每个分组的大小为8 bytes = 64 bits, 且该参数只能获取不能修改。
// The DES block size in bytes.
const BlockSize = 8
func (c *desCipher) BlockSize() int { return BlockSize }
外部调用的时候需要先调用NewCipher得到一个cipher对象，参数为64位秘钥。会生成一个desCipher类型的对象，以及调用generateSubkeys进行秘钥编排。
// NewCipher creates and returns a new cipher.Block.
func NewCipher(key []byte) (cipher.Block, error) {
if len(key) != 8 {
return nil, KeySizeError(len(key))
}
c := new(desCipher)
c.generateSubkeys(key) // block.go
return c, nil
}
NewCipher方法的返回值是接口cipher.Block，该接口的定义如下：
package cipher
// A Block represents an implementation of block cipher
// using a given key. It provides the capability to encrypt
// or decrypt individual blocks. The mode implementations
// extend that capability to streams of blocks.
type Block interface {
// BlockSize returns the cipher's block size.
BlockSize() int
// Encrypt encrypts the first block in src into dst.
// Dst and src must overlap entirely or not at all.
Encrypt(dst, src []byte)
// Decrypt decrypts the first block in src into dst.
// Dst and src must overlap entirely or not at all.
Decrypt(dst, src []byte)
}
所以desCipher需要实现接口中的方法
// desCipher is an instance of DES encryption.
type desCipher struct {
subkeys [16]uint64
}
func (c *desCipher) BlockSize() int { return BlockSize }
func (c *desCipher) Encrypt(dst, src []byte) {
if len(src) < BlockSize {
panic("crypto/des: input not full block")
}
if len(dst) < BlockSize {
panic("crypto/des: output not full block")
}
if subtle.InexactOverlap(dst[:BlockSize], src[:BlockSize]) {
panic("crypto/des: invalid buffer overlap")
}
// block.go 中实现
encryptBlock(c.subkeys[:], dst, src)
}
func (c *desCipher) Decrypt(dst, src []byte) {
if len(src) < BlockSize {
panic("crypto/des: input not full block")
}
if len(dst) < BlockSize {
panic("crypto/des: output not full block")
}
if subtle.InexactOverlap(dst[:BlockSize], src[:BlockSize]) {
panic("crypto/des: invalid buffer overlap")
}
// block.go 中实现
decryptBlock(c.subkeys[:], dst, src)
}
除此之外cipher.go中还定义了3DES类型和加解密方法。
block.go
block.go全部是实现算法的函数。
秘钥编排
上面提到des包的使用需要先NewCipher函数，该函数会进行先进行秘钥编排，具体是在block.go中的generateSubkeys函数实现的
// creates 16 56-bit subkeys from the original key
func (c *desCipher) generateSubkeys(keyBytes []byte) {
// 通过s盒产生feistelBox，简化后续加密流程，整个进程只执行一次
feistelBoxOnce.Do(initFeistelBox)
// apply PC1 permutation to key：PC1置换
// 8 bytes 转为64 bits
key := binary.BigEndian.Uint64(keyBytes)
// 执行PC1置换
permutedKey := permuteBlock(key, permutedChoice1[:])
// rotate halves of permuted key according to the rotation schedule：循环移动
leftRotations := ksRotate(uint32(permutedKey >> 28))
rightRotations := ksRotate(uint32(permutedKey<<4) >> 4)
// generate subkeys
for i := 0; i < 16; i++ {
// combine halves to form 56-bit input to PC2
pc2Input := uint64(leftRotations[i])<<28 | uint64(rightRotations[i])
// apply PC2 permutation to 7 byte input
c.subkeys[i] = unpack(permuteBlock(pc2Input, permutedChoice2[:]))
}
}
// general purpose function to perform DES block permutations
func permuteBlock(src uint64, permutation []uint8) (block uint64) {
// src = 10101...11010101，高位-低位; permutation = {7, 15, 23, 31, 39, 47, 55, 63,...}
for position, n := range permutation {
/**
pos = 0, n = 7
bit 为第七位的为1, 应该放到第0位为1
*/
bit := (src >> n) & 1
block |= bit << uint((len(permutation)-1)-position)
}
return
}
置换函数permuteBlock中bit := (src >> n) & 1和算法描述的不一致【需要进一步验证，感觉应该是bit := src & (1 << len(permutation)-1)-n】，但是不会影响算法的正确性，因为加密和解密都是采用相同的映射方法。
可以看到算法的秘钥是有caller输入，只要满足8bytes即可，每个比特不一定有校检位。在Golang实现的时候是将64位分为两个32位的整型，然后分别去掉高4位。然后在进行循环移动ksRotate，该函数会生16个组成子秘钥的左右两个部分。拼接左右两个部分之后通过unpack完成56bits到48bit的置换形成16个子秘钥。
加密
加密调用cipherObj.Encrypt()方法，具体实现在block.go:encryptBlock()中
// Encrypt one block from src into dst, using the subkeys.
func encryptBlock(subkeys []uint64, dst, src []byte) {
cryptBlock(subkeys, dst, src, false)
}
func cryptBlock(subkeys []uint64, dst, src []byte, decrypt bool) {
// 8bytes 转为 64bits
b := binary.BigEndian.Uint64(src)
// 初始置换 IP，该算法进行了优化
b = permuteInitialBlock(b)
// 分为左右两个部分
left, right := uint32(b>>32), uint32(b)
left = (left << 1) | (left >> 31)
right = (right << 1) | (right >> 31)
// 16轮加密，因为feistel网络中2轮可以在一个方法中实现，所以循环了8次
if decrypt {
for i := 0; i < 8; i++ {
left, right = feistel(left, right, subkeys[15-2*i], subkeys[15-(2*i+1)])
}
} else {
for i := 0; i < 8; i++ {
left, right = feistel(left, right, subkeys[2*i], subkeys[2*i+1])
}
}
left = (left << 31) | (left >> 1)
right = (right << 31) | (right >> 1)
// switch left & right and perform final permutation
preOutput := (uint64(right) << 32) | uint64(left)
// finalPermutation，IP-1置换
binary.BigEndian.PutUint64(dst, permuteFinalBlock(preOutput))
}
可以看到Golang实现的时候和原理阶段的加密解密过程是基本相同的，不同的地方是在进行16轮加密之前向左进行了1次循环移动，结束之后又向右循环移动。具体为什么做还不清楚，需要查阅一下相关文献。
feistel网络在对应的函数中实现。可以看到为了优化算法，Golang中没有直接使用sBoxs和函数generateSubkeys进行秘钥编排时，调用feistelBoxOnce.Do(initFeistelBox)生成了feistelBox。注意initFeistelBox在整个进程中只执行一次，所以相较于直接使用sBox和PF置换，提高了效率。并且也没有直接使用eBox进行置换，进行了相关的优化，因为eBox是bit扩充，在使用eBox的条件下也能通过移位运算实现。
// DES Feistel function. feistelBox must be initialized via
// feistelBoxOnce.Do(initFeistelBox) first.
func feistel(l, r uint32, k0, k1 uint64) (lout, rout uint32) {
var t uint32
t = r ^ uint32(k0>>32)
l ^= feistelBox[7][t&0x3f] ^
feistelBox[5][(t>>8)&0x3f] ^
feistelBox[3][(t>>16)&0x3f] ^
feistelBox[1][(t>>24)&0x3f]
t = ((r << 28) | (r >> 4)) ^ uint32(k0)
l ^= feistelBox[6][(t)&0x3f] ^
feistelBox[4][(t>>8)&0x3f] ^
feistelBox[2][(t>>16)&0x3f] ^
feistelBox[0][(t>>24)&0x3f]
t = l ^ uint32(k1>>32)
r ^= feistelBox[7][t&0x3f] ^
feistelBox[5][(t>>8)&0x3f] ^
feistelBox[3][(t>>16)&0x3f] ^
feistelBox[1][(t>>24)&0x3f]
t = ((l << 28) | (l >> 4)) ^ uint32(k1)
r ^= feistelBox[6][(t)&0x3f] ^
feistelBox[4][(t>>8)&0x3f] ^
feistelBox[2][(t>>16)&0x3f] ^
feistelBox[0][(t>>24)&0x3f]
return l, r
}
func initFeistelBox() {
for s := range sBoxes {
for i := 0; i < 4; i++ {
for j := 0; j < 16; j++ {
f := uint64(sBoxes[s][i][j]) << (4 * (7 - uint(s)))
f = permuteBlock(f, permutationFunction[:])
// Row is determined by the 1st and 6th bit.
// Column is the middle four bits.
row := uint8(((i & 2) << 4) | i&1)
col := uint8(j << 1)
t := row | col
// The rotation was performed in the feistel rounds, being factored out and now mixed into the feistelBox.
f = (f << 1) | (f >> 31)
feistelBox[s][t] = uint32(f)
}
}
}
}
图片来源声明
本文章中图片来源于《深入浅出密码学》
Golang学习
实现函数全局只执行一次
// 定义一个Once类型
var feistelBoxOnce sync.Once
// 调用Do方法；initFeistelBox只被全局执行一次
feistelBoxOnce.Do(initFeistelBox)
底层实现：通过atomic.LoadUint32(&o.done) == 0进行原子操作，当一个协程修改done之后是内存可见的。在doSlow函数中，加锁之后需要再次判断done值，防止协程gor1和gor2同时进入doSlow函数，但是gor1先获取到锁，执行完f释放锁之后，gor2拿到锁继续执行。
// sync/once.go
package sync
// Once is an object that will perform exactly one action.
type Once struct {
// done indicates whether the action has been performed.
// It is first in the struct because it is used in the hot path.
// The hot path is inlined at every call site.
// Placing done first allows more compact instructions on some architectures (amd64/x86),
// and fewer instructions (to calculate offset) on other architectures.
done uint32 // 标记位
m Mutex // 锁
}
func (o *Once) Do(f func()) {
// Note: Here is an incorrect implementation of Do:
//
// if atomic.CompareAndSwapUint32(&o.done, 0, 1) {
// f()
// }
//
// Do guarantees that when it returns, f has finished.
// This implementation would not implement that guarantee:
// given two simultaneous calls, the winner of the cas would
// call f, and the second would return immediately, without
// waiting for the first's call to f to complete.
// This is why the slow path falls back to a mutex, and why
// the atomic.StoreUint32 must be delayed until after f returns.
// done的地址空间进行原子
if atomic.LoadUint32(&o.done) == 0 {
// Outlined slow-path to allow inlining of the fast-path.
由于使用了defer所以实现了一个函数，防止锁死
o.doSlow(f)
}
}
func (o *Once) doSlow(f func()) {
// 加锁
o.m.Lock()
defer o.m.Unlock()
if o.done == 0 {
defer atomic.StoreUint32(&o.done, 1)
f()
}
}
通过上述列子可以看到可以使用Once进行单例的初始化，Golang实现的思路是双重校检。在Java中使用该方法在一些情况下还是会造成单例的重复创建，参考《Java并发编程的艺术》一书。不知道在Golang中会不会出现相同的问题。
有疑问加站长微信联系（非本文作者）
