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文件定义了一些函数宏和数据结构

1.  
   #ifndef __lk_sm3_h__
2.  
   #define __lk_sm3_h__
3.  
    
4.  
   #ifdef __cpluscplus
5.  
   extern "C" {
6.  
   #endif
7.  
    
8.  
   #include <strings.h>
9.  
    
10.  
    #ifdef __cpluscplus
11.  
    }
12.  
    #endif
13.  
     
14.  
    #define LK_GVALUE_LEN 64
15.  
    #define LK_WORD_SIZE 32
16.  
    #define LK_GVALUE_BITLEN 256
17.  
    #define LK_HASH_NMEMB 8
18.  
     
19.  
    typedef unsigned int UINT;
20.  
    #ifdef i386
21.  
    typedef unsigned long long UWORD;
22.  
    #else
23.  
    typedef unsigned long UWORD;
24.  
    #endif
25.  
    typedef unsigned char UCHAR;
26.  
     
27.  
    //常量
28.  
    // 0 <= j <= 15
29.  
    #define LK_T0 0x79cc4519
30.  
    // 16 <= j <= 63
31.  
    #define LK_T1 0x7a879d8a
32.  
    //循环左移
33.  
    #define LOOPSHFT(a, n) ( ((a) << (n)) | ((a) >> (LK_WORD_SIZE - (n))))
34.  
    //布尔函数
35.  
    #define LK_FF0(x, y, z) ((x)^(y)^(z))
36.  
    #define LK_FF1(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
37.  
    #define LK_GG0(x, y, z) ((x)^(y)^(z))
38.  
    #define LK_GG1(x, y, z) (( (x) & (y) ) | ((~x) & (z)))
39.  
     
40.  
    //置换函数
41.  
    #define LK_P0(x) (\
42.  
    (x)^(LOOPSHFT((x), 9))^(LOOPSHFT((x), 17)) )
43.  
    #define LK_P1(x) (\
44.  
    (x)^(LOOPSHFT((x), 15))^(LOOPSHFT((x), 23)) )
45.  
     
46.  
    //标准中给出的IV初始值
47.  
    #define LK_INIT_VALUE(t) {\
48.  
    lk_sm3_context_t *x = (t);\
49.  
    x->v[0] = 0x7380166f;\
50.  
    x->v[1] = 0x4914b2b9;\
51.  
    x->v[2] = 0x172442d7;\
52.  
    x->v[3] = 0xda8a0600;\
53.  
    x->v[4] = 0xa96f30bc;\
54.  
    x->v[5] = 0x163138aa;\
55.  
    x->v[6] = 0xe38dee4d;\
56.  
    x->v[7] = 0xb0fb0e4e;\
57.  
    bzero(x->data, LK_GVALUE_LEN);\
58.  
    x->total = 0;\
59.  
    x->len = 0;}
60.  
     
61.  
    #define LK_LE_ONE(t) {\
62.  
    lk_sm3_context_t *x = (t);\
63.  
    UINT l_z, l_d;\
64.  
    for (l_z = 0; l_z < LK_HASH_NMEMB; l_z ) {\
65.  
    l_d = x->v[l_z];\
66.  
    x->output[l_z*4] = ((l_d >> 24) & 0x000000ff);\
67.  
    x->output[l_z*4 1] = ((l_d >> 16) & 0x000000ff);\
68.  
    x->output[l_z*4 2] = ((l_d >> 8) & 0x000000ff);\
69.  
    x->output[l_z*4 3] = (l_d & 0x000000ff);\
70.  
    }}
71.  
     
72.  
    //大端转化
73.  
    #define LK_GE_ONE(c) (\
74.  
    ((c&0x00000000000000ffUL) << 56) | (((c&0x000000000000ff00UL) << 40)) |\
75.  
    ((c&0x0000000000ff0000UL) << 24) | (((c&0x00000000ff000000UL) << 8)) |\
76.  
    ((c&0x000000ff00000000UL) >> 8) | (((c&0x0000ff0000000000UL) >> 24)) |\
77.  
    ((c&0x00ff000000000000UL) >> 40) | (((c&0xff00000000000000UL) >> 56)) )
78.  
    #define LK_GE(w, c) \
79.  
    int j2;\
80.  
    for (j = 0; j <= 15; j ) {\
81.  
    j2 = j*4;\
82.  
    w[j] = ((c[j2] << 24) | ((c[j2 1] << 16)) |\
83.  
    (c[j2 2] << 8) | (c[j2 3]));\
84.  
    }
85.  
     
86.  
     
87.  
    //压缩计算摘要函数
88.  
    #define LK_MSG_CF(t) {\
89.  
    UINT j;\
90.  
    lk_sm3_context_t *x = t;\
91.  
    UCHAR *data = x->data;\
92.  
    UINT W1[68];\
93.  
    UINT W2[64];\
94.  
    UINT a,b,c,d,e,f,g,h;\
95.  
    a = x->v[0];\
96.  
    b = x->v[1];\
97.  
    c = x->v[2];\
98.  
    d = x->v[3];\
99.  
    e = x->v[4];\
100.  
     f = x->v[5];\
101.  
     g = x->v[6];\
102.  
     h = x->v[7];\
103.  
     LK_GE(W1, data)\
104.  
     for ( j = 16; j <= 67; j ) {\
105.  
     W1[j] = LK_P1(W1[j-16]^W1[j-9]^(LOOPSHFT(W1[j-3], 15))) ^ LOOPSHFT(W1[j-13], 7) ^ W1[j-6];\
106.  
     }\
107.  
     for ( j = 0; j <= 63; j ) {\
108.  
     W2[j] = W1[j] ^ W1[j 4];\
109.  
     }\
110.  
     for ( j = 0; j <= 63; j ) {\
111.  
     UINT T, ss1, ss2, tt1, tt2;\
112.  
     if ( j >= 0 && j <= 15 )\
113.  
     T = LK_T0;\
114.  
     else\
115.  
     T = LK_T1;\
116.  
     ss1 = LOOPSHFT( (LOOPSHFT(a, 12) e LOOPSHFT(T, j)), 7 );\
117.  
     ss2 = ss1 ^ LOOPSHFT(a, 12);\
118.  
     if ( j >= 0 && j <= 15 ) {\
119.  
     tt1 = LK_FF0(a, b, c) d ss2 W2[j];\
120.  
     tt2 = LK_GG0(e, f, g) h ss1 W1[j];\
121.  
     } else {\
122.  
     tt1 = LK_FF1(a, b, c) d ss2 W2[j];\
123.  
     tt2 = LK_GG1(e, f, g) h ss1 W1[j];\
124.  
     }\
125.  
     d = c;\
126.  
     c = LOOPSHFT(b, 9);\
127.  
     b = a;\
128.  
     a = tt1;\
129.  
     h = g;\
130.  
     g = LOOPSHFT(f, 19);\
131.  
     f = e;\
132.  
     e = LK_P0(tt2);\
133.  
     }\
134.  
     x->v[0] = a ^ x->v[0];\
135.  
     x->v[1] = b ^ x->v[1];\
136.  
     x->v[2] = c ^ x->v[2];\
137.  
     x->v[3] = d ^ x->v[3];\
138.  
     x->v[4] = e ^ x->v[4];\
139.  
     x->v[5] = f ^ x->v[5];\
140.  
     x->v[6] = g ^ x->v[6];\
141.  
     x->v[7] = h ^ x->v[7];\
142.  
     x->len = 0;\
143.  
     }
144.  
      
145.  
     typedef struct lk_sm3_context_s
146.  
     {
147.  
     UINT len;
148.  
     UINT total;
149.  
     UCHAR data[LK_GVALUE_LEN];
150.  
     UINT v[LK_HASH_NMEMB];
151.  
     UCHAR output[LK_WORD_SIZE];
152.  
     } lk_sm3_context_t;
153.  
      
154.  
     #ifdef __cpluscplus
155.  
     extern "C" {
156.  
     #endif
157.  
      
158.  
     extern void lk_sm3_final(lk_sm3_context_t *context);
159.  
     extern void lk_sm3_update (lk_sm3_context_t *context, UCHAR *data, UINT len);
160.  
      
161.  
     #ifdef __cpluscplus
162.  
     }
163.  
     #endif
164.  
      
165.  
     #endif

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

1.  
   #include <stdio.h>
2.  
   #include <string.h>
3.  
    
4.  
   #include "lk_sm3.h"
5.  
    
6.  
   static void lk_sm3_cf(lk_sm3_context_t *context)
7.  
   {
8.  
   LK_MSG_CF(context)
9.  
   }
10.  
     
11.  
    void lk_sm3_update (lk_sm3_context_t *context, UCHAR *data, UINT len)
12.  
    {
13.  
    int real_len, free, offset = 0;
14.  
     
15.  
    real_len = len context->len;
16.  
    if (real_len < LK_GVALUE_LEN) {
17.  
    //本次数据不够一个分组大小,先缓存起来
18.  
    memcpy(context->data context->len, data offset, len);
19.  
    context->len = real_len;
20.  
    context->total = len;
21.  
    return;
22.  
    }
23.  
    free = LK_GVALUE_LEN - context->len;
24.  
    memcpy(context->data context->len, data offset, free);
25.  
    context->total = free;
26.  
    offset = free;
27.  
    len -= free;
28.  
    //进行迭代压缩
29.  
    lk_sm3_cf(context);
30.  
     
31.  
    while (1) {
32.  
    if (len < LK_GVALUE_LEN) {
33.  
    //本次数据不够一个分组大小,先缓存起来
34.  
    memcpy(context->data context->len, data offset, len);
35.  
    context->len = len;
36.  
    context->total = len;
37.  
    return;
38.  
    }
39.  
    memcpy(context->data context->len, data offset, LK_GVALUE_LEN);
40.  
    offset = LK_GVALUE_LEN;
41.  
    len -= LK_GVALUE_LEN;
42.  
    context->total = LK_GVALUE_LEN;
43.  
    //进行迭代压缩
44.  
    lk_sm3_cf(context);
45.  
    }
46.  
    }
47.  
     
48.  
    void lk_sm3_final(lk_sm3_context_t *context)
49.  
    {
50.  
    UINT tk, k, free, i, len;
51.  
    UCHAR tmp[LK_GVALUE_LEN] = {0};
52.  
     
53.  
    tk = context->total * 8 % 512;
54.  
    if (tk < 448) {
55.  
    k = 448 - tk;
56.  
    } else {
57.  
    k = 448 -tk 512;
58.  
    }
59.  
    //计算需要填充的字节
60.  
    k = k / 8 8;
61.  
    free = LK_GVALUE_LEN - context->len;
62.  
    k--;
63.  
    context->data[context->len] = 0x80;
64.  
    len = context->total * 8;
65.  
    for (i = context->len 1; i < LK_GVALUE_LEN; i , k--) {
66.  
    if (k != 8)
67.  
    context->data[i] = 0x00;
68.  
    else {
69.  
    bzero(context->data i, 8);
70.  
    UWORD *pdata = (UWORD *)&(context->data[i]);
71.  
    *pdata = LK_GE_ONE(len);
72.  
    break;
73.  
    }
74.  
    }
75.  
    //进行迭代压缩
76.  
    lk_sm3_cf(context);
77.  
    if (64 == k) {
78.  
    for (i = 0; i < LK_GVALUE_LEN; i , k--) {
79.  
    if (k != 8)
80.  
    context->data[i] = 0x00;
81.  
    else {
82.  
    bzero(context->data i, 8);
83.  
    UWORD *pdata = (UWORD *)&(context->data[i]);
84.  
    *pdata = LK_GE_ONE(len);
85.  
    break;
86.  
    }
87.  
    }
88.  
    //进行迭代压缩
89.  
    lk_sm3_cf(context);
90.  
    }
91.  
    //get result
92.  
    LK_LE_ONE(context)
93.  
    }

使用例子程序test.c

1.  
   #include <stdio.h>
2.  
   #include <string.h>
3.  
    
4.  
   #include "lk_sm3.h"
5.  
    
6.  
   int main (int argc, char **argv)
7.  
   {
8.  
   int i, rz;
9.  
   FILE *fp;
10.  
    char buffer[1024] = {0};
11.  
     
12.  
    lk_sm3_context_t context;
13.  
    //计算之前初始化
14.  
    LK_INIT_VALUE(&context);
15.  
     
16.  
    fp = fopen("/opt/1.txt", "r ");
17.  
    if ( !fp )
18.  
    return -1;
19.  
    while (!feof(fp)) {
20.  
    memset(buffer, 0x0, sizeof(buffer));
21.  
    rz = fread(buffer, 1, sizeof(buffer), fp);
22.  
    //进行分组迭代压缩计算
23.  
    lk_sm3_update(&context, buffer, rz);
24.  
    }
25.  
    //进行最后的分组填充和迭代压缩计算
26.  
    lk_sm3_final(&context);
27.  
    if (fp)
28.  
    fclose(fp);
29.  
     
30.  
    //dump
31.  
    printf("sm3:");
32.  
    for (i = 0; i < 32; i )
33.  
    printf("x", context.output[i]);
34.  
    printf("\n");
35.  
     
36.  
    return 0;
37.  
    }

这篇好文章是转载于：学新通技术网