国密算法Go语言实现（详解）(二) ——SM3(杂凑算法)

原创代码：https://github.com/ZZMarquis/gm

引用时，请导入原创代码库。本文仅以注释方式详解代码逻辑，供学习研究使用。

对原创代码的修改内容

  1. 修改了部分常量、变量、结构体属性的名称, 以便与GO语言标准包规范相统一
  2. 加入中文注释，解释代码逻辑
  3. 在SM3算法中，将常数BlockSize修改为“字节长度”而不是“字长”，与GO语言标准包相统一

注释者及联系邮箱

Paul Lee
paul_lee0919@163.com

// Write() 为哈希摘要的“写”方法，是GO语言hash类的标准接口方法，为公共方法，可外部调用。
// 其功能旨在将输入消息按照SM3国标规定的分组、迭代、压缩函数整理写入8个字寄存器。
// 鉴于输入消息写入时可能为多次、持续的过程，所以，Write()方法并没有将“填充”步骤考虑在内，
// 而是将“填充”步骤放到最后，在收尾函数finish()方法中再实现输入消息的“填充”步骤。
func (digest *digest) Write(p []byte) (n int, err error) {
	_ = p[0]
	inLen := len(p)

	i := 0
	// endOfInBuf 不为0，代表着前一次写操作，存在不能凑成“字”（4个字节）的尾部数据。
	if digest.endOfInBuf != 0 {
		for i < inLen {
			digest.inBuf[digest.endOfInBuf] = p[i]
			digest.endOfInBuf++
			i++
			if digest.endOfInBuf == 4 {
				digest.processWord(digest.inBuf[:], 0)
				digest.endOfInBuf = 0
				break
			}
		}
	}

	// &^3相当于将本数X的尾部2位清零，相当于X减去其对4取模的余数，结果将获得小于等于本数X的最大的4的倍数
	limit := ((inLen - i) & ^3) + i
	// i 以4为单位累加循环，将输入消息写入inWords[]
	for ; i < limit; i += 4 {
		digest.processWord(p, int32(i))
	}

	// 将输入消息的尾部信息写入寄存数组inBuf[]
	for i < inLen {
		digest.inBuf[digest.endOfInBuf] = p[i]
		digest.endOfInBuf++
		i++
	}

	// 累加输入消息的字节长度到lenInBytes
	digest.lenInBytes += int64(inLen)

	// 返回本次写操作的字节长度
	n = inLen
	return
}

Write() 为SM3哈希摘要的“写”方法，是GO语言hash类的标准接口方法，为公共方法，可外部调用。其功能旨在将输入消息按照SM3国标规定的分组、迭代、压缩函数整理写入8个"字"寄存器。鉴于输入消息写入时可能为多次、持续的过程，所以，Write()方法并没有将国标中规定的对输入消息尾部的填充操作考虑在内，而是将“填充”步骤放到最后，在收尾函数finish()方法中再实现输入消息的“填充”步骤。

// finish() 为SM3算法的收尾方法:
// (1) 确认输入消息已经完全写入，并计算输入消息的长度;
// (2) 根据输入消息的长度，完成尾部数据的“填充”操作;
// (3) 将填充完毕的尾部数据进行分组、迭代和压缩运算。
func (digest *digest) finish() {

	// 左移3位，相当于左边数字乘以2的3次幂（即乘以8），实质上是将字节数折算成比特“位”数。
	bitLength := digest.lenInBytes << 3

	// 首位为“1”其余位为“0”的字节，为输入消息结束后“填充”操作的第一个步骤，即在消息末尾填充比特“1”。
	digest.Write([]byte{128})

	// 若存在不能凑成“字”的零散尾部数据，则填充“0”字节，凑成完整的“字”。
	for digest.endOfInBuf != 0 {
		digest.Write([]byte{0})
	}

	// 调用processLength()方法, 完成“填充”步骤，制作成最后的长度为512位整数倍的分组数据。
	digest.processLength(bitLength)

	// 调用processBlock()方法, 就“填充”完成后的尾部数据，进行国标5.3部分的迭代、压缩运算。
	digest.processBlock()
}

finish( ) 为SM3算法的收尾方法:

  • (1) 确认输入消息已经完全写入，并计算输入消息的长度;
  • (2) 根据输入消息的长度，完成消息尾部的“填充”操作;
  • (3) 将填充完毕的尾部数据进行分组、迭代和压缩运算。

在上述代码中，值得注意的几点:

  • (1) 左移3位运算，相当于原数字乘以23（即乘以8），实质上是将字节数折算成比特“位”数。
  • (2) 128用8位二进制数表示为1000 0000 即首位为1后续7位为0，相当于国标规定的在输入消息后填充1位“1”的操作。
// checkSum() 为SM3获取哈希值的结果输出函数:
// (1) 调用收尾方法finish()，完成输入消息尾部的填充、迭代和压缩；
// (2) 以32位的“字”为单位，将哈希值写入输出数组out[];
// (3) 返回输出字节数组out[]。
func (digest *digest) checkSum() [Size]byte {
	digest.finish()
	vlen := len(digest.v)
	var out [Size]byte
	for i := 0; i < vlen; i++ {
		binary.BigEndian.PutUint32(out[i*4:(i+1)*4], digest.v[i])
	}
	return out
}

checkSum( ) 为SM3获取哈希值的结果输出函数:

  • (1) 调用收尾方法finish( )，完成输入消息尾部的填充、迭代和压缩；
  • (2) 以32位的“字”为单位，将哈希值写入字节数组;
  • (3) 返回输出字节数组out[]。

以上代码值得注意的是:

  • 调用了go标准包encoding/binary的大端存储32位无符号整数的写入方法binary.BigEndian.PutUint32()
// processBlock() 为分组数据块的处理函数，是SM3算法的核心：
// (1) 将输入消息的16个“字”数组，按照国标5.3.2(a)的算法拆分并赋值给消息扩展数组w[0]-w[15]；
// (2) 按照国标5.3.2(b)部分规定的算法，制备w[16]-w[67];
// (3) 将v[0]-v[7]的哈希运算中间结果赋值给8个“字”寄存器ABCDEFGH;
// (4) 将国标5.3.2(c)部分规定的w'[]的推导算法，和5.3.3部分规定的迭代压缩算法相结合，完成迭代压缩运算;
// (5) 将寄存器ABCDEFGH中保存的迭代运算结果与v[0]-v[7]中保存的中间结果“异或运算”后存入v[]。
func (digest *digest) processBlock() {
	for j := 0; j < 16; j++ {
		digest.w[j] = digest.inWords[j]
	}
	for j := 16; j < 68; j++ {
		wj3 := digest.w[j-3]
		r15 := (wj3 << 15) | (wj3 >> (32 - 15))
		wj13 := digest.w[j-13]
		r7 := (wj13 << 7) | (wj13 >> (32 - 7))
		digest.w[j] = p1(digest.w[j-16]^digest.w[j-9]^r15) ^ r7 ^ digest.w[j-6]
	}

	A := digest.v[0]
	B := digest.v[1]
	C := digest.v[2]
	D := digest.v[3]
	E := digest.v[4]
	F := digest.v[5]
	G := digest.v[6]
	H := digest.v[7]

	for j := 0; j < 16; j++ {
		a12 := (A << 12) | (A >> (32 - 12))
		s1 := a12 + E + gT[j]
		SS1 := (s1 << 7) | (s1 >> (32 - 7))
		SS2 := SS1 ^ a12
		Wj := digest.w[j]
		W1j := Wj ^ digest.w[j+4] // 国标5.3.2(c)部分规定的w'[]的推导算法
		TT1 := ff0(A, B, C) + D + SS2 + W1j
		TT2 := gg0(E, F, G) + H + SS1 + Wj
		D = C
		C = (B << 9) | (B >> (32 - 9))
		B = A
		A = TT1
		H = G
		G = (F << 19) | (F >> (32 - 19))
		F = E
		E = p0(TT2)
	}

	for j := 16; j < 64; j++ {
		a12 := (A << 12) | (A >> (32 - 12))
		s1 := a12 + E + gT[j]
		SS1 := (s1 << 7) | (s1 >> (32 - 7))
		SS2 := SS1 ^ a12
		Wj := digest.w[j]
		W1j := Wj ^ digest.w[j+4] // 国标5.3.2(c)部分规定的w'[]的推导算法
		TT1 := ff1(A, B, C) + D + SS2 + W1j
		TT2 := gg1(E, F, G) + H + SS1 + Wj
		D = C
		C = (B << 9) | (B >> (32 - 9))
		B = A
		A = TT1
		H = G
		G = (F << 19) | (F >> (32 - 19))
		F = E
		E = p0(TT2)
	}

	digest.v[0] ^= A
	digest.v[1] ^= B
	digest.v[2] ^= C
	digest.v[3] ^= D
	digest.v[4] ^= E
	digest.v[5] ^= F
	digest.v[6] ^= G
	digest.v[7] ^= H

	digest.endOfInWords = 0
}

processBlock( ) 为分组数据块的处理函数，是SM3算法的核心：

  • (1) 将输入消息的16个“字”数组，按照国标5.3.2(a)的算法拆分并赋值给消息扩展数组w[0]-w[15]；
  • (2) 按照国标5.3.2(b)部分规定的算法，制备w[16]-w[67];
  • (3) 将v[0]-v[7]的哈希运算中间结果赋值给8个“字”寄存器ABCDEFGH;
  • (4) 将国标5.3.2.( c )部分规定的w’[]的推导算法，和5.3.3部分规定的迭代压缩算法相结合，完成迭代压缩运算;
  • (5) 将寄存器ABCDEFGH中保存的迭代运算结果与v[0]-v[7]中保存的中间结果“异或运算”后存入v[ ]。
// processWord() 为写入过程中将输入消息暂存到以“字”为单位的寄存器的方法：
// (1) 将输入的字节数据，以4字节位单位，写入inWords[];
// (2) 每当写入消息字长达到16个字，即512字节，则调用一次processBlock()方法.
func (digest *digest) processWord(in []byte, inOff int32) {
	n := binary.BigEndian.Uint32(in[inOff : inOff+4])

	digest.inWords[digest.endOfInWords] = n
	digest.endOfInWords++

	// 每达到16个字，调用一次分组数据块处理方法processBlock();
	if digest.endOfInWords >= 16 {
		digest.processBlock()
	}
}

processWord() 为输入消息写入内存的过程中，以“4字节”为单位写入寄存器的方法：

  • (1) 将输入的字节数据，以4字节位单位，写入inWords[ ];
  • (2) 每当写入消息字长达到16个字，即512字节，则调用一次processBlock( )方法，进行分组数据的处理。
  • (3) 实质上是个“凑字长”的中间过程。
// processLength() SM3算法对输入消息进行尾部数据“填充”的实现函数。
func (digest *digest) processLength(bitLength int64) {
	// 若仅剩余一个“字”的空位，则直接填充“0”、调用分组数据块处理方法。
	if digest.endOfInWords > (BlockSize/4 - 2) {
		digest.inWords[digest.endOfInWords] = 0
		digest.endOfInWords++

		digest.processBlock()
	}

	// 填充“0”占位，只剩余64位留给存储输入消息长度。
	for ; digest.endOfInWords < (BlockSize/4 - 2); digest.endOfInWords++ {
		digest.inWords[digest.endOfInWords] = 0
	}

	// 将64位整数表示的输入消息长度，拆分成两个32位“字”，分别将高位和地位存储到两个inWords[]数组元素中
	digest.inWords[digest.endOfInWords] = uint32(bitLength >> 32)
	digest.endOfInWords++
	digest.inWords[digest.endOfInWords] = uint32(bitLength)
	digest.endOfInWords++
}

processLength() SM3算法对输入消息进行尾部数据“填充”的实现函数。

  • (1) 若消息尾部距离512字节的分组长度仅剩余一个“字”的空位，则直接填充“0”、调用分组数据块处理方法。否则，
  • (2) 填充“0”占位，只剩余64位（2个字长）留下来供存储输入消息长度。
  • (3) 将64位整数表示的输入消息长度，拆分成两个32位“字”，分别将高位和地位存储到两个inWords[ ]数组元素中。

(未完待续)