Caché实现SM3密码杂凑算法

0. 算法概述

SM3密码杂凑算法是中国国家密码管理局2010年公布的中国商用密码杂凑算法标准。该算法于2012年发布为密码行业标准(GM/T 0004-2012)，2016年发布为国家密码杂凑算法标准(GB/T 32905-2016)。

SM3适用于商用密码应用中的数字签名和验证，是在[SHA-256]基础上改进实现的一种算法，其安全性和SHA-256相当。SM3和MD5的迭代过程类似，也采用Merkle-Damgard结构。消息分组长度为512位，摘要值长度为256位。

整个算法的执行过程可以概括成四个步骤：消息填充、消息扩展、迭代压缩、输出结果。

1. 消息填充

SM3的消息扩展步骤是以512位的数据分组作为输入的。因此，我们需要在一开始就把数据长度填充至512位的倍数。具体步骤如下：

1、先填充一个“1”，后面加上k个“0”。其中k是满足(n+1+k) mod 512 = 448的最小正整数。

2、追加64位的数据长度。

2. 消息分组扩展

将填充后的消息m′按512比特进行分组：m′ = B(0)B(1)...B(n−1) 其中n=(l+k+65)/512。

SM3的迭代压缩步骤没有直接使用数据分组进行运算，而是使用这个步骤产生的132个消息字。（一个消息字的长度为32位/4个字节/8个16进制数字）概括来说，先将一个512位数据分组划分为16个消息字，并且作为生成的132个消息字的前16个。再用这16个消息字递推生成剩余的116个消息字。

3. 迭代压缩

SM3使用消息扩展得到的消息字进行迭代运算。

初值IV被放在A、B、C、D、E、F、G、H八个32位变量中，整个算法中最核心、也最复杂的地方就在于压缩函数。压缩函数将这八个变量进行64轮相同的计算。

4. 输出结果

将得到的A、B、C、D、E、F、G、H八个变量拼接输出，就是SM3算法的输出。

5. 附录

6. Caché实现

/// SM3密码杂凑算法是中国国家密码管理局2010年公布的中国商用密码杂凑算法标准
/// 该算法于2012年发布为密码行业标准(GM/T 0004-2012)，2016年发布为国家密码杂凑算法标准(GB/T 32905-2016)。
/// 对长度为l(l < 2^64)比特的消息m，SM3杂凑算法经过填充和迭代压缩，生成杂凑值，杂凑值长度为256比特。
Class Utility.SM3 Extends %RegisteredObject
{

/// Creator：    wyh
/// CreatDate：  2022-11-01
/// Description：SM3加密
/// Input:  	 msg:原文 
/// Output：     16进制密文
/// Debug： w ##class(Utility.SM3).Hashsm3("{""appId"":""60C90F3B796B41878B8D9C393E2B6329"",""nonceStr"":""1234567890"",""timestamp"":""60C90F3B796B41878B8D9C393E2B6329"",""version"":""V2.0.0""}F2D8D966CD3D47788449C19D5EF2081B")
ClassMethod Hashsm3(msg)
{
#;	初始值IV =7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e
	s V(0) = "01110011100000000001011001101111 01001001000101001011001010111001 00010111001001000100001011010111 11011010100010100000011000000000 10101001011011110011000010111100 00010110001100010011100010101010 11100011100011011110111001001101 10110000111110110000111001001110"
		
#;	1. 消息填充
	s m = ..s2m(msg)
	
#;	2. 消息分组
#;	将填充后的消息m′按512比特进行分组：m′ = B(0)B(1)...B(n−1)
#;	其中n=(l+k+65)/512。
	s n = $l(m)/512
	f i = 0 : 1 : n-1 d
	.s B(i) = $e(m, 512 * i + 1, 512 * (i + 1))
	
#;	3. 迭代压缩
#;	对m′按下列方式迭代：
#;	FOR i=0 TO n-1
#;		V(i+1) = CF(V(i),B(i))
#;	ENDFOR
#;	其中CF是压缩函数，V(0)为256比特初始值IV，B(i)为填充后的消息分组，迭代压缩的结果为V(n)。
	.s V(i+1) = ..CF(V(i) ,B(i))

#;	4. 杂凑输出
#;	ABCDEFGH = V(n)
#;	输出256比特的杂凑值y = ABCDEFGH。
	s rtn = ""
	f i = 1 : 1 : 8 d
	.s bit = $p(V(n), " ", i)
	.s num = ..bs2n(bit)
	.s hex = $ZHEX(num)
	.i $l(hex) < 8 d
	..f j = 1 : 1 : 8 - $l(hex)  d
	...s hex = "0" _ hex
	.s rtn = rtn _ hex
	
	s rtn = $zcvt(rtn, "L")
	return rtn
}

/// 1. 消息填充
/// 将填充后的消息m′按512比特进行分组：m′ = B(0)B(1)...B(n−1)
/// 其中n=(l+k+65)/512
ClassMethod s2m(msg)
{
	s len = $l(msg)
	s r = ""
	f i = 1 : 1 : len d
	.s num = $ascii($e(msg, i))
	.s bs = ..n2bs(num)
	.s r = r _ bs
	
	s rtn = r
	s rtn = rtn _ "1"
	
	s k = 512 - (64 + ($l(r) + 1)) # 512
	f i = 1 : 1 : k d
	.s rtn = rtn _ "0"
	
	s lenbs = ..n2bs($l(r))
	s t = 64 - $l(lenbs)
	f i = 1 : 1 : t d
	.s rtn = rtn _ "0"
	
	s rtn = rtn _ lenbs
	return rtn
}

/// 3. 迭代压缩
/// 令A,B,C,D,E,F,G,H为字寄存器,SS1,SS2,TT1,TT2为中间变量,压缩函数V(i+1) = CF(V(i),B(i)), 0<=i<=n-1。计算过程描述如下：
/// ABCDEFGH=V(i)
/// FOR j=0 TO 63
/// 	SS1 = ((A<<12) + E + (T(j)<<j))<<7
/// 	SS2 = SS1 ^	(A<<12)
/// 	TT1 = FF(j)(A,B,C) + D + SS2 +W′(j)
/// 	TT2 = GG(j)(E,F,G) + H + SS1 +W(j)
/// 	D = C
/// 	C = B<<9
/// 	B = A
/// 	A = TT1
/// 	H = G
/// 	G = F<<19
/// 	F = E
/// 	E = P0(TT2)
/// ENDFOR
/// V(i+1) = ABCDEFGH ^ V(i)
/// 其中，字的存储为大端(big-endian)格式。
ClassMethod CF(Vi, Bi)
{
	s A = $p(Vi," ",1), B = $p(Vi," ",2), C = $p(Vi," ",3), D = $p(Vi," ",4), E = $p(Vi," ",5), F = $p(Vi," ",6), G = $p(Vi," ",7), H = $p(Vi," ",8)

#;	常量
#;	T(j) = 79cc4519 0<=j<=15
#;		   7a879d8a 16<=j<=63
	f i = 0 : 1 : 15 d
	.s T(i) = "01111001110011000100010100011001"
	f i = 16 : 1 : 63 d
	.s T(i) = "01111010100001111001110110001010"
	
#;	3.1 消息扩展
#;	将消息分组B(i)按以下方法扩展生成132个字W(0),W(1),...,W(67),W′(0),W′(1),...,W′(63)，用于压缩函数CF：
#;	a)将消息分组B(i)划分为16个字W(0),W(1),...,W(15)。
#;	b)FOR j=16 TO 67
#;		W(j) = P1(W(j−16)^W(j−9)^(W(j−3)≪15)) ^ (W(j−13)≪7) ^ W(j−6)
#;	  ENDFOR
#;	c)FOR j=0 TO 63
#;		W′(j) = W(j) ^ W(j+4)
#;	  ENDFOR
	f i = 0 : 1 : 15 d
	.s W(i) = $e(Bi, 32 * i + 1, 32 * (i + 1))
	f i = 16 : 1 : 67 d
	.s W(i) = ..XOR(..XOR(..P1(..XOR(..XOR(W(i-16), W(i-9)), ..rotateleft(W(i-3), 15))), ..rotateleft(W(i-13), 7)), W(i-6))
	f i = 0 : 1 : 63 d
	.s W2(i) = ..XOR(W(i), W(i+4))
	
	f i = 0 : 1 : 63 d
	.s SS1 = ..n232bs(..bs2n(..rotateleft(..n232bs((..bs2n(..rotateleft(A, 12)) + ..bs2n(E) + ..bs2n(..rotateleft(T(i), i))) # $zpower(2, 32)), 7)) # $zpower(2, 32))
	.s SS2 = ..n232bs(..bs2n(..XOR(SS1, ..rotateleft(A, 12))) # $zpower(2, 32))
	.s TT1 = ..n232bs((..bs2n(..FF(A, B, C, i)) + ..bs2n(D) + ..bs2n(SS2) + ..bs2n(W2(i))) # $zpower(2, 32))
	.s TT2 = ..n232bs((..bs2n(..GG(E, F, G, i)) + ..bs2n(H) + ..bs2n(SS1) +..bs2n(W(i))) # $zpower(2, 32))
	.s D = C
    .s C = ..rotateleft(B, 9)
    .s B = A
    .s A = TT1
    .s H = G
    .s G = ..rotateleft(F, 19)
    .s F = E
    .s E = ..P0(TT2)
    
    s A = ..XOR(A, $p(Vi," ",1))
    s B = ..XOR(B, $p(Vi," ",2))
    s C = ..XOR(C, $p(Vi," ",3))
    s D = ..XOR(D, $p(Vi," ",4))
    s E = ..XOR(E, $p(Vi," ",5))
    s F = ..XOR(F, $p(Vi," ",6))
    s G = ..XOR(G, $p(Vi," ",7))
    s H = ..XOR(H, $p(Vi," ",8))
    
    return A_" "_B_" "_C_" "_D_" "_E_" "_F_" "_G_" "_H
}

/// 布尔函数
/// FF(j)(X, Y, Z)= X ^ Y ^ Z 0<=j<=15
/// 			   (X & Y) | (X & Z) | (Y & Z) 16<=j<=63
ClassMethod FF(X, Y, Z, j)
{
	i j <= 15 d
	.s ret = ..XOR(..XOR(X, Y), Z)
	e  d
	.s ret = ..OR(..OR(..AND(X, Y), ..AND(X, Z)), ..AND(Y, Z))
	
	return ret
}

/// 布尔函数
/// GG(j)(X, Y, Z)= X ^ Y ^ Z 0<=j<=15
/// 			   (X & Y ) | (~X & Z) 16<=j<=63
ClassMethod GG(X, Y, Z, j)
{
	i j <= 15 d
	.s ret = ..XOR(..XOR(X, Y), Z)
	e  d
	.s ret = ..OR(..AND(X, Y), ..AND(..NOT(X), Z))
	
	return ret
}

/// 置换函数P0(X) = X ^ (X<<9) ^ (X<<17)
ClassMethod P0(X)
{
	return ..XOR(..XOR(X, ..rotateleft(X, 9)), ..rotateleft(X, 17))
}

/// 置换函数P1(X) = X ^ (X<<15) ^ (X<<23)
ClassMethod P1(X)
{
	return ..XOR(..XOR(X, ..rotateleft(X, 15)), ..rotateleft(X, 23))
}

/// 32比特循环左移k比特运算
ClassMethod rotateleft(a, k)
{
	s k = k # 32
	s a1 = $e(a, k + 1, 32)
	s a2 = $e(a, 1, k)
	return a1 _ a2
}

/// 32比特与运算
ClassMethod AND(a, b)
{
	s rtn = ""
	f i = 1 : 1 : 32 d
	.s bit = $e(a, i) && $e(b, i)
	.s rtn = rtn _ bit
	
	return rtn
}

/// 32比特或运算
ClassMethod OR(a, b)
{
	s rtn = ""
	f i = 1 : 1 : 32 d
	.s bit = $e(a, i) || $e(b, i)
	.s rtn = rtn _ bit
	
	return rtn
}

/// 32比特异或运算
ClassMethod XOR(a, b)
{
	s rtn = ""
	f i = 1 : 1 : 32 d
	.i $e(a, i) = $e(b, i) d
	..s rtn = rtn _ "0"
	.e  d
	..s rtn = rtn _ "1"
	
	return rtn
}

/// 32比特非运算
ClassMethod NOT(a)
{
	s rtn = ""
	f i = 1 : 1 : 32 d
	.i $e(a, i) = "0" d
	..s rtn = rtn _ "1"
	.e  d
	..s rtn = rtn _ "0"
	
	return rtn
}

/// 数字转二进制字符
ClassMethod n2bs(num)
{
	s bit = $factor(num)
	s count = $bitcount(bit)
	s bitstr = ""
 	f i = count : -1 : 1 {
  		s b = $bit(bit , i)
  		s bitstr = bitstr _ b
  	}
  	
 	s l = $l(bitstr,"00000000")
 	s bitstr = $p(bitstr ,"00000000", l)
 	
 	return bitstr
}

/// 数字转32位二进制字符
ClassMethod n232bs(num)
{
	s bit = $factor(num)
	s count = $bitcount(bit)
	s bitstr = ""
 	f i = count : -1 : 1 {
  		s b = $bit(bit , i)
  		s bitstr = bitstr _ b
  	}
  	
 	s l = $l(bitstr)
 	s bitstr = $e(bitstr ,* - 31, *)
 	
 	return bitstr
}

/// 二进制字符转数字
ClassMethod bs2n(bStr)
{
	s len = $l(bStr)
	s decimal = 0
	f i = len : -1 : 1 d
	.s bit = $e(bStr, i)
	.i bit = 1 d
	..s decimal = decimal + $zpower(2, len - i)
	
	return decimal
}

}