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

模板引擎对LaTeX支持不太好，可以查看静态页面:链接
个人主页

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，IP^{-1})

逆初始置换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位，L_0=Low 32 bit, R_0=high 32 bit。

(2) 通过秘钥k产生16轮加密的子秘钥(subkey)，子秘钥的为48位。

(3) 在第i轮加密中，R_{i-1}和subkey_i为作为f函数的输入，f函数的输出为32位。

(4) 第i轮加密的输出为，L_i = R_{i-1}, R_i = f(R_{i-1}) \oplus L_{i-1}, out_i= L_i << 32 | R_i。

![加密轮核心流程](https://upload-images.jianshu.io/upload_images/2421524-5c75be71f05fd1fa.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
  • f函数: 作为DES的安全性中扮演着重要的角色，其结构如图所示。首先函数的输入通过E-盒(eBox)将扩充为48位，扩充的方式是通过E盒置换，得到E(R_{i-1})。然后E(R_{i-1})和本轮的秘钥subkey_i进行异或运算，得到的输出通过S-盒置换映射为32位。最后在通过f函数内置置换（Permutation Function, PF
    ）.
    • 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的输入为a = (100100)_2, 通过a的最高位1和最低位0，可以确定行为row = \(10\)_2 = \(2\)_{10}（最高位<< 1 | 最低位),通络其余的四位(0010)_2可确定列为(2)_{10}，则置换的结果为S-Box1[2][2]。以Golang中的sBoxs为例，结果为sBoxes[0][2][2] = (14)_{10} = (1110)_{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位的C_0和D_0两个部分。当加密轮数 i = 1,2,9,16时，C_0和D_0向左循环移动一位；其他轮数时，C_0和D_0向左循环移动两位。
（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和函数f的自身的置换（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中会不会出现相同的问题。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,921评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,635评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,393评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,836评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,833评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,685评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,043评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,694评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,671评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,424评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,027评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2赞 343

推荐阅读更多精彩内容

  • 三重Des对称加密在Android、Ios 和Java 平台的实现
    引言 如今手机app五彩缤纷，确保手机用户的数据安全是开发人员必须掌握的技巧，下面通过实例介绍DES在androi...
    freesan44阅读 1,120评论 1赞 1
  • Mobile BI 移动商务智能的加密算法
    这篇文章主要讲述在Mobile BI(移动商务智能)开发过程中，在网络通信、数据存储、登录验证这几个方面涉及的加密...
    雨_树阅读 2,331评论 0赞 6
  • 对称加密
    介绍 加密和解密都使用同一把秘钥，这种加密方法称为对称加密，也称为单密钥加密。简单理解为：加密解密都是同一把钥匙 ...
    Blizzard_liu阅读 799评论 0赞 1
  • 对称加密一：DES&go实现
    密码技术### 1. 介绍 1.1 加密/解密三要素： 明文/ 密文, 秘钥， 密码算法 明文/密文:加密之前...
    husky_1阅读 1,210评论 0赞 0
  • 曾有过
    曾有过深深爱恋，犹豫间留下遗憾。 分别后自我安慰，某一天还能相见。
    蛮力阅读 308评论 2赞 8