加密技术概览

• 风险行为
• 对称加密/共享密钥加密
  • One-Time Pad/一次性密码本
  • DES（Data Encryption Standard）/3DES
    • DES-CBC简单实现
    • Feistel网格结构
    • feistel函数(cipherFunc)
    • 密钥置换
  • AES（Advanced Encryption Standard）
    • AES-CBC简单实现
    • Add Round Key
    • SubBytes
    • ShiftRows步骤
    • MixColumns
  • Padding方案
  • 分组模式
    • EBC(electronic code book)/电子密码本
    • CBC(cipher block chaining)/密文分组链接
    • CTR(CounTeR)/计数器模式
• 非对称加密/公钥加密
  • RSA
    • 中间人攻击
• 消息认证码（Message Authentication Code/MAC)
  • 单向散列函数
  • HMAC （Hash MAC)
• 数字签名
• 数字证书
• 随机数
  • 伪随机
    • 线性同余生成器/Linear congruential generator(LCG)
    • 单向散列函数/密码法/etc
  • "真“随机（密码安全伪随机）

风险行为

窃听

篡改

假冒

否认

对称加密/共享密钥加密

One-Time Pad/一次性密码本

无条件安全的，理论上绝对无法破译（无穷计算能力计算器遍历密钥空间条件下，无法确定是不是明文）

XOR：A xor B = C , C xor B = A

缺点

• 密匙长度和明文必须等长
• 密匙如何安全的告诉对方（因为上面一点等同于明文如何安全告诉对方，矛盾）
• 密匙要随机不重复

DES（Data Encryption Standard）/3DES

数据加密标准（英语：Data Encryption Standard，缩写为 DES）是一种对称密钥加密块密码算法，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），它基于使用56位密钥的对称算法。
DES现在已经不是一种安全的加密方法，主要因为它使用的56位密钥过短。1999年1月，distributed.net与电子前哨基金会合作，在22小时15分钟内即公开破解了一个DES密钥。虽然在实际中难以应用。为了提供实用所需的安全性，可以使用DES的派生算法3DES来进行加密，虽然3DES也存在理论上的攻击方法。DES标准和3DES标准已逐渐被高级加密标准（AES）所取代。另外，DES已经不再作为国家标准科技协会（前国家标准局）的一个标准

DES-CBC简单实现

func DesCBCEncrypt() ([]bytes, error) {
  // key是8个byte共64bit数据,iv是用于cbc分组的初始化向量64bit数据
	data := []byte("raw data")
	key := []byte("12345678")
	iv := []byte("10242398")

	block, err := des.NewCipher(key)
	if err != nil {
		return nil, err
	}
   
  // PKCS7分组，分成blocksize(8bytes)大小的数据块
	data = pkcs7Padding(data, block.BlockSize())
	cryptText := make([]byte, len(data))

	blockMode := cipher.NewCBCEncrypter(block, iv)
	blockMode.CryptBlocks(cryptText, data)
	return cryptText, err
}

Feistel网格结构

费斯妥结构保证了加密和解密过程足够相似—唯一的区别在于子密钥在解密时是以反向的顺序应用的，而剩余部分均相同。这样的设计大大简化了算法的实现，尤其是硬件实现，因为没有区分加密和解密算法的需要

Initial Permutation|初始置换

将64bit打乱

func permuteInitialBlock(block uint64) uint64 {
  DoSomething...
  // block is the permutation:
	// 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
	return block
}

feistel函数(cipherFunc)

1. 扩张：32位输入通过E扩张，到8个6bit块,每块包含4位对应的输入位，加上两个邻接的块中紧邻的位,共48位
2. 混合：上述的48bit结果与48bit key 异或
3. s盒处理：将异或结果分为8个6bit块分别输入对应的s盒，8个S盒的每一个都使用以查找表方式提供的非线性的变换将它的6个输入位变成4个输出位。S盒提供了DES的核心安全性—如果没有S盒，密码会是线性的，很容易破解
4. 置换：S盒的32个输出位利用固定的置换，“P置换”进行重组。这个设计是为了将每个S盒的4位输出在下一回次的扩张后，使用4个不同的S盒进行处理

Golang中并没有使用expand，而是采用了另外的方式

// 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,
}

// feistelBox[s][16*i+j] contains the output of permutationFunction
// for sBoxes[s][i][j] << 4*(7-s)
var feistelBox [8][64]uint32

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]
  //......
}

密钥置换

1. 64bit key 通过选择置换1 选出56bit数据

   // 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,
   }

2. 将置换的数据分为左右28bit，分16轮进入rotate函数分别得到16组旋转后的28bit数据

   // Size of left rotation per round in each half of the key schedule
   var ksRotations = [16]uint8{1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}
   
   // rotate halves of permuted key according to the rotation schedule
   leftRotations := ksRotate(uint32(permutedKey >> 28))
   rightRotations := ksRotate(uint32(permutedKey<<4) >> 4)
   
   func ksRotate(in uint32) (out []uint32) {
   	out = make([]uint32, 16)
   	last := in
   	for i := 0; i < 16; i++ {
   		// 28-bit circular left shift
   		left := (last << (4 + ksRotations[i])) >> 4
   		right := (last << 4) >> (32 - ksRotations[i])
   		out[i] = left | right
   		last = out[i]
   	}
   	return
   }

3. 将旋转后的left，right组合输入选择置换2，生成48bit subkey用于feistel网格

   // 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[:]))
   	}

AES（Advanced Encryption Standard）

高级加密标准（英语：Advanced Encryption Standard，缩写：AES），又称Rijndael加密法（荷兰语发音：[ˈrɛindaːl]，音似英文的“Rhine doll”），是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPS PUB 197，并在2002年5月26日成为有效的标准。现在，高级加密标准已然成为对称密钥加密中最流行的算法之一。

AES-CBC简单实现

func AesEncrypt(plaintext []byte, key, iv []byte) ([]byte, error) {
    block, err := aes.NewCipher(key)
    if err != nil {
        return nil, err
    }
    blockSize := block.BlockSize()//16 bytes
    plaintext = PKCS7Padding(plaintext, blockSize)
    blockMode := cipher.NewCBCEncrypter(block, iv)
    crypted := make([]byte, len(plaintext))
    blockMode.CryptBlocks(crypted, plaintext)
    return crypted, nil
}

AES是Rijndael的一种标准实现，AES blocksize固定128bit，密钥可以为128，192，256bit，Rijindael blocksize和密钥长度均可以为128，192，256

a矩阵代表plaintext 128bit的block，矩阵4X4 每个元素是一个byte

b矩阵是通过Rijndael密钥生成方案将key转化的矩阵

Add Round Key

矩阵中的每一个字节都与该次回合密钥（round key）做XOR运算；每个子密钥由密钥生成方案产生

SubBytes

在SubBytes步骤中，矩阵中的各字节透过一个8位的S-box进行转换。这个步骤提供了加密法非线性的变换能力

ShiftRows步骤

第一列维持不变，第二列里的每个字节都向左循环移动一格。同理，第三列及第四列向左循环位移的偏移量就分别是2和3

MixColumns

Rijndael有限域内的矩阵乘法，主要是让转换后的每个byte依赖于之前整列的byte

有限域计算： wiki

${\left[ \begin{array}{cccc}2 & 3 & 1 & 1\1 & 2 & 3 & 1\1 & 1 & 2 & 3\3 & 1 & 1 & 2\end{array} \right ]}\times{\left[ \begin{array}{cccc}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3}\ a_{1,0} &a_{1,1} & a_{1,2} & a_{1,3}\ a_{2,0} &a_{2,1} & a_{2,2} & a_{2,3}\ a_{3,0} &a_{3,1} & a_{3,2} & a_{3,3}\end{array}\right ]}={\left[ \begin{array}{cccc}r_{0,0} & r_{0,1} & r_{0,2} & r_{0,3}\ r_{1,0} &r_{1,1} & r_{1,2} & r_{1,3}\ r_{2,0} &r_{2,1} & r_{2,2} & r_{2,3}\ r_{3,0} &r_{3,1} & r_{3,2} & r_{3,3}\end{array}\right ]}$

r00  = 2*a00 ^ 3*a10 ^ 1*a20 ^ 1*a30
r10  = 1*a00 ^ 2*a10 ^ 3*a20 ^ 1*a30
r20  = 1*a00 ^ 1*a10 ^ 2*a20 ^ 3*a30
r30  = 3*a00 ^ 1*a10 ^ 1*a20 ^ 2*a30

r01  = 2*a01 ^ 3*a11 ^ 1*a21 ^ 1*a31
r02  = 2*a02 ^ 3*a12 ^ 1*a22 ^ 1*a32
r03  = 2*a03 ^ 3*a13 ^ 1*a23 ^ 1*a33

// 将矩阵运算转化为4个查找表
// te0[i] = 2*i | 1*i | 1*i | 3*i
// te1[i] = 3*i | 2*i | 1*i | 1*i
// te2[i] = 1*i | 3*i | 2*i | 1*i
// te3[i] = 1*i | 1*i | 3*i | 2*i
for r := 0; r < nr; r++ {
		t0 = xk[k+0] ^ te0[uint8(s0>>24)] ^ te1[uint8(s1>>16)] ^ te2[uint8(s2>>8)] ^ te3[uint8(s3)]
		t1 = xk[k+1] ^ te0[uint8(s1>>24)] ^ te1[uint8(s2>>16)] ^ te2[uint8(s3>>8)] ^ te3[uint8(s0)]
		t2 = xk[k+2] ^ te0[uint8(s2>>24)] ^ te1[uint8(s3>>16)] ^ te2[uint8(s0>>8)] ^ te3[uint8(s1)]
		t3 = xk[k+3] ^ te0[uint8(s3>>24)] ^ te1[uint8(s0>>16)] ^ te2[uint8(s1>>8)] ^ te3[uint8(s2)]
		k += 4
		s0, s1, s2, s3 = t0, t1, t2, t3
	}

[证明过程]

Early Bounds Check

func encryptBlockGo(xk []uint32, dst, src []byte) {
	_ = src[15] // early bounds check
	s0 := binary.BigEndian.Uint32(src[0:4])
	s1 := binary.BigEndian.Uint32(src[4:8])
	s2 := binary.BigEndian.Uint32(src[8:12])
	s3 := binary.BigEndian.Uint32(src[12:16])
  //....
}

func (bigEndian) Uint32(b []byte) uint32 {
	_ = b[3] // bounds check hint to compiler; see golang.org/issue/14808
	return uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
}

func test(s []int) {
  _ = s[1]
	_ = s[2]	
}

减少CX寄存器的 CMPQ指令

对特定CPU aes加密是直接用优化后的汇编代码执行

var supportsAES = cpu.X86.HasAES || cpu.ARM64.HasAES
var supportsGFMUL = cpu.X86.HasPCLMULQDQ || cpu.ARM64.HasPMULL

func newCipher(key []byte) (cipher.Block, error) {
	if !supportsAES {
		return newCipherGeneric(key)
	}
	n := len(key) + 28
	c := aesCipherAsm{aesCipher{make([]uint32, n), make([]uint32, n)}}
	var rounds int
	switch len(key) {
	case 128 / 8:
		rounds = 10
	case 192 / 8:
		rounds = 12
	case 256 / 8:
		rounds = 14
	}

	expandKeyAsm(rounds, &key[0], &c.enc[0], &c.dec[0])
	if supportsAES && supportsGFMUL {
		return &aesCipherGCM{c}, nil
	}
	return &c, nil
}

Padding方案

RFC 2315 PKCS #7: Crytographic Message Syntax March 1998

Some content-encryption algorithms assume the
input length is a multiple of k octets, where k > 1, and
let the application define a method for handling inputs
whose lengths are not a multiple of k octets. For such
algorithms, the method shall be to pad the input at the
trailing end with k - (l mod k) octets all having value k -
(l mod k), where l is the length of the input. In other
words, the input is padded at the trailing end with one of
the following strings:
01 -- if l mod k = k-1
02 02 -- if l mod k = k-2
.
.
.
k k ... k k -- if l mod k = 0
The padding can be removed unambiguously since all input is
padded and no padding string is a suffix of another. This
padding method is well-defined if and only if k < 256;
methods for larger k are an open issue for further study.

PKCS5是 blocksize=8的PKCS7
zeroPadding是末尾固定用0补位

//golang实现
func PKCS7Padding(cipherText []byte, blockSize int) []byte {
   padding := blockSize - len(cipherText)%blockSize
   padText := bytes.Repeat([]byte{byte(padding)}, padding)
   return append(cipherText, padText...)
}

func PKCS5Padding(cipherText []byte) []byte {
   return PKCS7Padding(cipherText, 8)
}

分组模式

EBC(electronic code book)/电子密码本

优点：

• 简单
• 快速
• 支持并行

缺点：

• 无需解密就可对明文进行操作（如交换密文分组，删除密文分组等）
• 明文中的重复可以体现在密文中

案例：比如A给B汇款，可以通过修改密文顺序变更成B给A汇款

CBC(cipher block chaining)/密文分组链接

优点

• 明文重复不影响密文
• 解密支持并行

缺点：

• 加密不支持并行

CTR(CounTeR)/计数器模式

对称加密需要解决的问题就是密钥如何安全发送给接收者（蛋生鸡鸡生蛋）

以此衍生的技术是：

• 非对称加密
• 密钥交换（Diffie-Hellman）

非对称加密/公钥加密

加密用公钥加密，解密用私钥

RSA

加密

$ciphertext = plaintext^E \% N$

解密

$plaintext = ciphertext^D\%N$

公钥：(N,E) 私钥:(N,D)

步骤

1. N=pq, pq为大素数且p≠q
2. $R = \varphi(N)=\varphi(p)*\varphi(q) = (p-1)p^0(q-1)q^0=(p-1)(q-1)$，求N的欧拉函数值
3. 选择一个小于r的整数E，使E与R互质。并求得E关于R的模逆元，命名为D 即(E*D)%R=1

处理速度是对称加密的几百分之一

中间人攻击

1. B发送pubB公钥给A，被X截获，然后X将自己的pubX发给A
2. A以为pubX是B的公钥，用pubX加密内容发送给B
3. X窃取A发送的内容，用priX解密，获得明文
4. X修改内容，用pubB加密发送给B
5. B用priB解密以为是A发送的内容，实际是X发送的内容

消息认证码（Message Authentication Code/MAC)

单向散列函数

特性

• 任意输入输出长度固定

• 单向性

  对于每一个输入，函数值都容易计算（多项式时间）；但是对于一个随机的函数值，算出其对应的输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。 单向函数是否存在仍然是计算机科学中的一个开放性问题

• 碰撞抗性

  • 弱碰撞抗性：Given an input m1, it should be difficult to find a different input m2 such that hash(m1) = hash(m2)
  • 强碰撞抗性：It should be difficult to find two different messages m1 and m2 such that hash(m1) = hash(m2).

常用算法

• MD5
• SHA-1, SHA-2(SHA-256,SHA-384,SHA-512),SHA-3

MD5 由Ronald Rivest于 1991年设计以取代早期的散列函数 MD4，并于 1992 年指定为 RFC 1321。与 MD5 的冲突可以在几秒钟内计算出来，这使得该算法不适用于大多数需要加密散列的用例。MD5 生成 128 位（16 字节）的摘要。

2005年，密码分析人员发现了对SHA-1的有效攻击方法，这表明该算法可能不够安全，不能继续使用

HMAC （Hash MAC)

rfc2104:
We define two fixed and different strings ipad and opad as follows
(the 'i' and 'o' are mnemonics for inner and outer):
ipad = the byte 0x36 repeated B times
opad = the byte 0x5C repeated B times.
To compute HMAC over the data `text' we perform
H(K XOR opad, H(K XOR ipad, text))

H 是加密哈希函数（任何加密用散列函数，比如sha家族）
m是要认证的消息
K是密钥
K '是从密钥K派生的块大小的密钥；要么用 0 向右填充到块大小，要么先散列到小于或等于块大小，然后用零填充到右边
‖ 表示串联
⊕ 表示按位异或(XOR)
opad是块大小的外部填充，由值为 0x5c 的重复字节组成
ipad是块大小的内部填充，由值为 0x36 的重复字节组成

数字签名

生成签名

$signature = plaintext^D \% N$

验证

$plaintext = signature^E\%N$

如何确定B的pubA就是A生成的？

数字证书

1. A用生成的pubA想CA（证书认证机构)注册
2. CA用自己的私钥生成数字签名
3. A发送证书给B
4. B通过CA的pubC验证证书是否合法
5. 合法后提取pubA

随机数

随机数围绕3个特性，越往下越难实现。

1. 随机性：不存在统计学偏差，杂乱无章 (弱伪随机）
2. 不可预测：不能通过过去的数推到下一个数 （密码学安全伪随机，强伪随机）
3. 不可重现

其定义为随机样本不可重现。实际上只要给定边界条件，真随机数并不存在，可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉（比如当地的背景辐射波动值），可以认为用这个方法演算出来了真随机数。但实际上，这也只是非常接近真随机数的伪随机数，一般认为，无论是背景辐射、物理噪音、抛硬币等等都是可被观察了解的，任何基于经典力学产生的随机数，都只是伪随机数。

伪随机

线性同余生成器/Linear congruential generator(LCG)

$$X_{n+1} = (aX_n+c) \%m$$

线性同余方法可见C的rand和java的util.Random方法
c的rand还包含了线性累加反馈法，即LAFM（linear additive feedback method）的实现具体使用取决于state状态

// a = 1103515245, c = 12345, m = 2^31
int
__random_r (struct random_data *buf, int32_t *result)
{
  //.....
  if (buf->rand_type == TYPE_0)
    {
      int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff;
      state[0] = val;
      *result = val;
    } else {
      //.....
    }
}

1.必须遍历2^31后才能轮到"同一个"数
2.具有周期性，不具备不可预测性

单向散列函数/密码法/etc

"真“随机（密码安全伪随机）

在linux系统，crypto/rand 使用syscall获取信息熵来作为随机数，可以在密码学上认为接近真随机

// golang: crypto/rand
const urandomDevice = "/dev/urandom"
var altGetRandom func([]byte) (ok bool)

func (r *devReader) Read(b []byte) (n int, err error) {
	if atomic.CompareAndSwapInt32(&r.used, 0, 1) {
		// First use of randomness. Start timer to warn about
		// being blocked on entropy not being available.
		t := time.AfterFunc(60*time.Second, warnBlocked)
		defer t.Stop()
	}
	if altGetRandom != nil && r.name == urandomDevice && altGetRandom(b) {
		return len(b), nil
	}
	r.mu.Lock()
	defer r.mu.Unlock()
	if r.f == nil {
		f, err := os.Open(r.name)
		if f == nil {
			return 0, err
		}
		if runtime.GOOS == "plan9" {
			r.f = f
		} else {
			r.f = bufio.NewReader(hideAgainReader{f})
		}
	}
	return r.f.Read(b)
}

od -vAn -N4 -tu4 < /dev/urandom
可以使用od工具查看urandom产生的结果

---

Linear congruential generator - Wikipedia

@https://m.sohu.com/n/476868293/?wscrid=95360_2

@[https://www.mscs.dal.ca/~selinger/random/](https://www.mscs.dal.ca/~selinger/random/)

資料加密標準 - 维基百科，自由的百科全书

@https://www.ruanx.net/des/

@https://en.wikipedia.org/wiki/HMAC

@https://zh.wikipedia.org/wiki/S盒