对称加密-DES的原理和实现（Golang源码）

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和函数的自身的置换（Permutation Function，PF），而是在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中会不会出现相同的问题。

---

到此这篇关于“对称加密-DES的原理和实现（Golang源码）”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
密码学之对称加密
对称加密-DES的原理和实现（Golang源码）
C#加密算法 六种C#加密算法分享
Python：常见的加密方式
PHP加密扩展库Mcrypt的例子
修改Zend引擎实现PHP源码加密的原理及实践
php mcrypt启用、加密以及解密的方法介绍
C#做的一个加密/解密的类
php中加密解密DES的正确使用姿势
php base64加密解密的实现代码