SM3国密杂凑值算法的原理和c语言实现

一、SM3算法介绍

杂凑值算法也可称为摘要算法或者哈希算法。通过对数据资料的填充、分组、扩展压缩等方式计算成特定长度的数值，来作为数据指纹或者数据特征使用。常见的MD5算法长度为128bit（16字节），SHA1算法计算长度为160bit（20字节），SHA256算法计算长度256bit（32字节），SHA512算法计算长度512bit（64字节），SM3算法计算长度为256bit（32字节）。

SM3密码杂凑值算法是国家密码局公布的自研算法，参见国家密码局2010年12月《SM3密码杂凑算法》，其分组长度为512bit，最终计算长度为256bit（32字节）。

二、SM3算法流程

SM3算法计算流程参见《SM3密码杂凑算法》中的说明。

1、初始化

IV =7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e

既需要定义8个32bit长的容器或者寄存器V[8]，初始值赋值为对一个IV值。

2、数据填充

进行数据填充的目的主要是为了数据分组压缩，计算SM3哈希值的数据有可能是文件、也可能是字符串，长度大小不一。SM3是以512bit为一组来进行计算的，只要长度满512bit即可进行一次压缩计算，到最后剩余字符不足512bit部分就需要进行填充。

如《SM3密码杂凑算法》中所述，“假设消息m 的长度为l 比特。首先将比特“1”添加到消息的末尾，再添加k 个“0”，k是满足l + 1 + k ≡ 448mod512 的最小的非负整数。然后再添加一个64位比特串，该比特串是长度l的二进制表示，填充后的消息m′ 的比特长度为512的倍数。

其中≡ 符号在数论中为同余，根据同余定理，l + x的值减去448之后应该是512的倍数。x为需要填充的值，填充规则是：先填充0x80一个字节，中间填充为0，最后将真实的长度值（这个值是所有有效的字符串的比特长度值，比如一个文件的长度是1000字节，可能分成了好几个组分别进行了压缩，最后一个组进行了填充，最后的填充长度为1000*8）填充到最后的64bit的位置。

3、迭代压缩

迭代压缩主要是针对每个分组进行的，分组大小为512bit（既64字节）的data。在迭代压缩过程中还会对data进行数据扩展，既填充到不同的32bit的临时变量中，然后通过异或、循环左移等操作进行数据计算，最终更新到V[8]中。

每一个分组计算完成之后，都会更新V[8]。等最后一个填充分组也进行迭代压缩之后，V[8]寄存器或者数组中的值就是本次数据计算的杂凑值。

三、SM3的c语言实现

lk_sm3.h文件定义了一些函数宏和数据结构

#ifndef __lk_sm3_h__
#define __lk_sm3_h__

#ifdef __cpluscplus
extern "C" {
#endif

#include 

#ifdef __cpluscplus
}                                                                                                                                                                           
#endif

#define LK_GVALUE_LEN       64 
#define LK_WORD_SIZE        32 
#define LK_GVALUE_BITLEN    256
#define LK_HASH_NMEMB       8

typedef unsigned int        UINT;
#ifdef i386 
typedef unsigned long long   UWORD;
#else
typedef unsigned long       UWORD;
#endif
typedef unsigned char   UCHAR;

//常量
// 0 <= j <= 15
#define LK_T0   0x79cc4519
// 16 <= j <= 63
#define LK_T1   0x7a879d8a
//循环左移
#define LOOPSHFT(a, n) ( ((a) << (n)) | ((a) >> (LK_WORD_SIZE - (n))))
//布尔函数
#define LK_FF0(x, y, z) ((x)^(y)^(z))
#define LK_FF1(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define LK_GG0(x, y, z) ((x)^(y)^(z))
#define LK_GG1(x, y, z) (( (x) & (y) ) | ((~x) & (z)))

//置换函数
#define LK_P0(x) (
    (x)^(LOOPSHFT((x), 9))^(LOOPSHFT((x), 17)) )
#define LK_P1(x) (
    (x)^(LOOPSHFT((x), 15))^(LOOPSHFT((x), 23)) )

//标准中给出的IV初始值
#define LK_INIT_VALUE(t) {
    lk_sm3_context_t *x = (t);
    x->v[0] = 0x7380166f;
    x->v[1] = 0x4914b2b9;
    x->v[2] = 0x172442d7;
    x->v[3] = 0xda8a0600;
    x->v[4] = 0xa96f30bc;
    x->v[5] = 0x163138aa;
    x->v[6] = 0xe38dee4d;
    x->v[7] = 0xb0fb0e4e;
    bzero(x->data, LK_GVALUE_LEN);
    x->total = 0;
    x->len = 0;}

#define LK_LE_ONE(t) {
    lk_sm3_context_t *x = (t);
    UINT l_z, l_d;
    for (l_z = 0; l_z < LK_HASH_NMEMB; l_z++) {
        l_d = x->v[l_z];
        x->output[l_z*4] = ((l_d >> 24) & 0x000000ff);
        x->output[l_z*4 + 1] = ((l_d >> 16) & 0x000000ff);
        x->output[l_z*4 + 2] = ((l_d >> 8) & 0x000000ff);
        x->output[l_z*4 + 3] = (l_d & 0x000000ff);
    }}

//大端转化
#define LK_GE_ONE(c) (
    ((c&0x00000000000000ffUL) << 56) | (((c&0x000000000000ff00UL) << 40)) |
    ((c&0x0000000000ff0000UL) << 24) | (((c&0x00000000ff000000UL) << 8)) |
    ((c&0x000000ff00000000UL)  >> 8) | (((c&0x0000ff0000000000UL) >> 24)) |
    ((c&0x00ff000000000000UL) >> 40) | (((c&0xff00000000000000UL) >> 56)) )
#define LK_GE(w, c) 
    int j2;
    for (j = 0; j <= 15; j++) {
        j2 = j*4;
        w[j] = ((c[j2] << 24) | ((c[j2+1] << 16)) |
         (c[j2+2] << 8) | (c[j2+3]));
    }


//压缩计算摘要函数
#define LK_MSG_CF(t) {
    UINT j;
    lk_sm3_context_t *x = t;
    UCHAR *data = x->data;
    UINT W1[68];
    UINT W2[64];
    UINT a,b,c,d,e,f,g,h;
    a = x->v[0];
    b = x->v[1];
    c = x->v[2];
    d = x->v[3];
    e = x->v[4];
    f = x->v[5];
    g = x->v[6];
    h = x->v[7];
    LK_GE(W1, data)
for ( j = 16; j <= 67; j++ ) {
        W1[j] = LK_P1(W1[j-16]^W1[j-9]^(LOOPSHFT(W1[j-3], 15))) ^ LOOPSHFT(W1[j-13], 7) ^ W1[j-6];
    }
    for ( j = 0; j <= 63; j++ ) {
        W2[j] = W1[j] ^ W1[j+4];
    }
    for ( j = 0; j <= 63; j++ ) {
       UINT T, ss1, ss2, tt1, tt2;
       if ( j >= 0 && j <= 15 )
           T = LK_T0;
       else
           T = LK_T1;
        ss1 = LOOPSHFT( (LOOPSHFT(a, 12) + e + LOOPSHFT(T, j)), 7 );
        ss2 = ss1 ^ LOOPSHFT(a, 12);
        if ( j >= 0 && j <= 15 ) {
            tt1 = LK_FF0(a, b, c) + d + ss2 + W2[j];
            tt2 = LK_GG0(e, f, g) + h + ss1 + W1[j];
        } else {
            tt1 = LK_FF1(a, b, c) + d + ss2 + W2[j];
            tt2 = LK_GG1(e, f, g) + h + ss1 + W1[j];
        }
        d = c;
        c = LOOPSHFT(b, 9);
        b = a;
        a = tt1;
        h = g;
        g = LOOPSHFT(f, 19);
        f = e;
        e = LK_P0(tt2);
    }
    x->v[0] = a ^ x->v[0];
    x->v[1] = b ^ x->v[1];
    x->v[2] = c ^ x->v[2];
    x->v[3] = d ^ x->v[3];
    x->v[4] = e ^ x->v[4];
    x->v[5] = f ^ x->v[5];
    x->v[6] = g ^ x->v[6];
    x->v[7] = h ^ x->v[7];
    x->len = 0;
}
    
typedef struct lk_sm3_context_s
{
    UINT    len; 
    UINT    total; 
    UCHAR   data[LK_GVALUE_LEN];
    UINT    v[LK_HASH_NMEMB];
    UCHAR   output[LK_WORD_SIZE];
} lk_sm3_context_t;

#ifdef __cpluscplus
extern "C" {
#endif

extern void lk_sm3_final(lk_sm3_context_t *context);
extern void lk_sm3_update (lk_sm3_context_t *context, UCHAR *data, UINT len);

#ifdef __cpluscplus
}
#endif

#endif

lk_sm3.c文件实现了update和final两个函数

#include                                                                                                                                                           
#include 

#include "lk_sm3.h"

static void lk_sm3_cf(lk_sm3_context_t *context)
{
    LK_MSG_CF(context)
}

void lk_sm3_update (lk_sm3_context_t *context, UCHAR *data, UINT len)
{
    int real_len, free, offset = 0;  

    real_len = len + context->len;
    if (real_len < LK_GVALUE_LEN) {
        //本次数据不够一个分组大小,先缓存起来
        memcpy(context->data + context->len, data + offset, len); 
        context->len = real_len;
        context->total += len;
        return;
    }   
    free = LK_GVALUE_LEN - context->len;
    memcpy(context->data + context->len, data + offset, free);
    context->total += free;
    offset += free;
    len -= free;
    //进行迭代压缩
    lk_sm3_cf(context);

    while (1) {
        if (len < LK_GVALUE_LEN)  {
            //本次数据不够一个分组大小,先缓存起来
            memcpy(context->data + context->len, data + offset, len); 
            context->len = len;
            context->total += len;
            return;
        }
        memcpy(context->data + context->len, data + offset, LK_GVALUE_LEN); 
        offset += LK_GVALUE_LEN;
        len -= LK_GVALUE_LEN;
        context->total += LK_GVALUE_LEN;
        //进行迭代压缩
        lk_sm3_cf(context);
    }
}

void lk_sm3_final(lk_sm3_context_t *context)
{
    UINT tk, k, free, i, len;
    UCHAR tmp[LK_GVALUE_LEN] = {0}; 

    tk = context->total * 8 % 512;
    if (tk < 448) {
        k = 448 - tk;
    } else {
        k = 448 -tk + 512; 
    }
    //计算需要填充的字节
    k = k / 8 + 8;
    free = LK_GVALUE_LEN - context->len;
    k--;
    context->data[context->len] = 0x80; 
    len = context->total * 8;
    for (i = context->len + 1; i < LK_GVALUE_LEN; i++, k--) {
        if (k != 8)
            context->data[i] = 0x00;
        else {
            bzero(context->data + i, 8);
            UWORD *pdata = (UWORD *)&(context->data[i]);
            *pdata = LK_GE_ONE(len);
            break;
        }
    }
    //进行迭代压缩
    lk_sm3_cf(context);
    if (64 == k) {
        for (i = 0; i < LK_GVALUE_LEN; i++, k--) {
            if (k != 8)
                context->data[i] = 0x00;
            else {
                bzero(context->data + i, 8);
                UWORD *pdata = (UWORD *)&(context->data[i]);
                *pdata = LK_GE_ONE(len);
                break;
            }
        } 
        //进行迭代压缩
        lk_sm3_cf(context);
    }
    //get result
    LK_LE_ONE(context)
}

使用例子程序test.c

#include 
#include 

#include "lk_sm3.h"

int main (int argc, char **argv)
{
    int i, rz;
    FILE *fp;
    char buffer[1024] = {0};

    lk_sm3_context_t context;
    //计算之前初始化
    LK_INIT_VALUE(&context);

    fp = fopen("/opt/1.txt", "r+");
    if ( !fp )
        return -1;
    while (!feof(fp)) {
        memset(buffer, 0x0, sizeof(buffer));
        rz = fread(buffer, 1, sizeof(buffer), fp);
        //进行分组迭代压缩计算
        lk_sm3_update(&context, buffer, rz);                                                                                                                                
    }
    //进行最后的分组填充和迭代压缩计算
    lk_sm3_final(&context);
    if (fp)
        fclose(fp);

    //dump
    printf("sm3:");
    for (i = 0; i < 32; i++)
        printf("%02x", context.output[i]);
    printf("n");

    return 0;
}

SM3国密杂凑值算法的原理和c语言实现

C/C++/C#相关栏目本月热门文章