文章
YuHao Wan · 十一月 1 阅读大约需 4 分钟

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
}

}

1
0 67
讨论 (2)1
登录或注册以继续

好棒的文章,强推!