本章节对应规范文档第5章

5.1 概述

对长度为$l(l < 2^{64}$) 比特的消息m，SM3杂凑算法经过填充和迭代压缩，生成杂凑值，杂凑值长度为256比特，也就是32字节。

5.2 填充

假设消息m 的长度为l 比特。首先将比特“1”添加到消息的末尾，再添加k 个“0”，k是满足$l + 1 + k \equiv 448 \pmod {512}$ 的最小的非负整数。然后再添加一个64位比特串，该比特串是长度l的二进制表示。填充后的消息m′ 的比特长度为512的倍数。

这里说这么多，总结来说就是，消息经过填充及添加8字节消息长度后，必须是64字节的倍数。

也就是说SM3摘要算法的BlockSize是64字节，假定待计算的消息为abc，十六进制表示0x616263，消息的比特长度是3 * 8=24=0x18。按照填充规则，首先是在消息的尾部加一个比特1，后再填充N个0，最后添加8字节消息长度，总长度为64字节。

按比特来表示可能没必要，因为消息的长度肯定是8-bit的倍数，那修改一下填充规则就是，首先填充一个0x80，再填充N字节的0x0，最后添加8字节消息长度。

那么总的填充长度（包含0x80的填充）应该是多少呢：

PADLEN = (ByteLength(m) + 1 + 8) < 64 ? ( 64 - 8 - ByteLength(m) ) : ( 128 - 8 - ByteLength(m) )

注意

按照填充规则，不论消息长度是多少，必定要先填充一个比特1，也就是说必定要先填充一个0x80，所以这里计算的时候是消息长度+1字节后，再与64字节比较

简化一下就是：

PADLEN = (ByteLength(m) + 1) < 56 ? ( 56 - ByteLength(m) ) : ( 120 - ByteLength(m) )

最终abc经过填充及添加消息长度后，十六进制表示待计算数据应为：

61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018

5.3 迭代压缩

5.3.1 迭代过程

规范文档解析：

经过填充后的消息表示为m′，按64字节为一组进行分组，迭代过程就是将分组后的消息B(i)逐一调用压缩函数CF进行压缩，每一轮的压缩结果表示为Vi，最终结果为Vn，迭代结束后，消息的杂凑值就等于Vn。

在压缩之前，需要将消息分组按规范进行两轮扩展，也就是Bi -> W，W -> W1

5.3.2 消息扩展

先来看看将消息Bi -> W的过程，过程分两步

a)将消息分组B(i)划分为16个字W0, W1, · · · , W15。   
b)   
FOR j = 16 TO 67   
     Wj ← P1(W{j−16} ⊕ W{j−9} ⊕ (W{j−3} ≪ 15)) ⊕ (W{j−13} ≪ 7) ⊕ W{j−6}
ENDFOR

实现第一步，先把Bi划分为16个字，每个字是4字节，先写一下宏来实现字节转字（注意是大端模式）：

#ifndef GM_GET_UINT32_BE
#define GM_GET_UINT32_BE(n,b,i)                         \
{                                                       \
    (n) = ( (uint32_t) (b)[(i)    ] << 24 )             \
        | ( (uint32_t) (b)[(i) + 1] << 16 )             \
        | ( (uint32_t) (b)[(i) + 2] <<  8 )             \
        | ( (uint32_t) (b)[(i) + 3]       );            \
}
#endif

然后就是循环调用这个宏定义了

第二步比较简单，看一下最终代码：

static void gm_sm3_BiToW(unsigned char * Bi, unsigned int * W)
{
    int i;
    unsigned int tmp;

    GM_GET_UINT32_BE( W[ 0], Bi,  0 );
    GM_GET_UINT32_BE( W[ 1], Bi,  4 );
    GM_GET_UINT32_BE( W[ 2], Bi,  8 );
    GM_GET_UINT32_BE( W[ 3], Bi, 12 );
    GM_GET_UINT32_BE( W[ 4], Bi, 16 );
    GM_GET_UINT32_BE( W[ 5], Bi, 20 );
    GM_GET_UINT32_BE( W[ 6], Bi, 24 );
    GM_GET_UINT32_BE( W[ 7], Bi, 28 );
    GM_GET_UINT32_BE( W[ 8], Bi, 32 );
    GM_GET_UINT32_BE( W[ 9], Bi, 36 );
    GM_GET_UINT32_BE( W[10], Bi, 40 );
    GM_GET_UINT32_BE( W[11], Bi, 44 );
    GM_GET_UINT32_BE( W[12], Bi, 48 );
    GM_GET_UINT32_BE( W[13], Bi, 52 );
    GM_GET_UINT32_BE( W[14], Bi, 56 );
    GM_GET_UINT32_BE( W[15], Bi, 60 );

    for (i = 16; i <= 67; i++)
    {
        tmp = W[i - 16]    ^ W[i - 9] ^ GM_SM3_ROTL(W[i - 3], 15);
        W[i] = GM_SM3_P_1(tmp) ^ (GM_SM3_ROTL(W[i - 13], 7)) ^ W[i - 6];
    }
}

接下来看一下W -> W1扩展，规范文档如下：

FOR j=0 TO 63
    Wj′ =Wj ⊕ W{j+4}
ENDFOR

实现起来也比较简单：

static void gm_sm3_WToW1(unsigned int W[], unsigned int W1[])
{
    int i;

    for (i = 0; i <= 63; i++)
    {
        W1[i] = W[i] ^ W[i + 4];
    }
}

5.3.3 压缩函数

先来定义一个sm3的上下文，用来记录每一轮的状态

typedef struct {
    unsigned int state[8]; // 寄存器中间状态
    unsigned char buf[64]; // 待压缩消息
    unsigned int cur_buf_len; // 当前待压缩消息长度（字节）
    uint64_t compressed_len; // 已压缩消息长度（比特）
}gm_sm3_context;

压缩算法对照规范文档来实现，实现代码如下：

static void gm_sm3_CF(const unsigned int * W, const unsigned int * W1, gm_sm3_context * ctx)
{
    unsigned int SS1;
    unsigned int SS2;
    unsigned int TT1;
    unsigned int TT2;
    unsigned int A, B, C, D, E, F, G, H;
    unsigned int Tj;
    int j;

    // ABCDEFGH = V (i)
    A = ctx->state[0];
    B = ctx->state[1];
    C = ctx->state[2];
    D = ctx->state[3];
    E = ctx->state[4];
    F = ctx->state[5];
    G = ctx->state[6];
    H = ctx->state[7];

    for(j = 0; j < 64; j++)
    {
        if(j < 16)
        {
            // if 0 <= j <= 15 Tj = 0x79cc4519
            Tj = GM_SM3_T_0;
        }
        else
        {
            // if j > 15 Tj = 0x7a879d8a
            Tj = GM_SM3_T_1;
        }
        // SS1 = ((A <<< 12) + E + (Tj <<< j)) <<< 7
        SS1 = GM_SM3_ROTL((GM_SM3_ROTL(A, 12) + E + GM_SM3_ROTL(Tj, j)), 7);
        // SS2 = SS1 ^ (A <<< 12)
        SS2 = SS1 ^ GM_SM3_ROTL(A, 12);

        // TT1 = FFj(A, B, C) + D + SS2 + Wj1
        // TT2 = GGj(E, F, G) + H + SS1 + Wj
        if(j < 16)
        {
            TT1 = GM_SM3_FF_0(A, B, C) + D + SS2 + W1[j];
            TT2 = GM_SM3_GG_0(E, F, G) + H + SS1 + W[j];
        }
        else
        {
            TT1 = GM_SM3_FF_1(A, B, C) + D + SS2 + W1[j];
            TT2 = GM_SM3_GG_1(E, F, G) + H + SS1 + W[j];
        }

        // D = C
        D = C;
        // C = B <<< 9
        C = GM_SM3_ROTL(B, 9);
        // B = A
        B = A;
        // A = TT1
        A = TT1;
        // H = G
        H = G;
        // G = F <<< 19
        G = GM_SM3_ROTL(F, 19);
        // F = E
        F = E;
        // E = P0(TT2)
        E = GM_SM3_P_0(TT2);
    }

    // V(i+1) = ABCDEFGH ^ V(i)
    ctx->state[0] ^= A;
    ctx->state[1] ^= B;
    ctx->state[2] ^= C;
    ctx->state[3] ^= D;
    ctx->state[4] ^= E;
    ctx->state[5] ^= F;
    ctx->state[6] ^= G;
    ctx->state[7] ^= H;
}

再看看一个BlockSize的完整压缩函数：

// 压缩算法
static void gm_sm3_compress(gm_sm3_context * ctx)
{
    unsigned int W[68];
    unsigned int W1[64];

    // Bi 扩展为 W
    gm_sm3_BiToW(ctx->buf, W);

    // W 扩展为 W1
    gm_sm3_WToW1(W, W1);

    // 压缩
    gm_sm3_CF(W, W1, ctx);
}

未经本人同意，禁止转载！

上一页常数与函数

下一页算法封装