【零依赖实现国密算法C语言版】国密SM2之大数转换

# 定义大数

typedef uint64_t gm_bn_t[8];

这里用8个uint64_t来表示256-bit的大数，为什么用uint64_t，而不是用8个uint32_t或4个uint64_t呢。因为如果用8个uint32_t表示，那么加减法中进位和借位就不好算了，4个uint64_t同理，而如果用8个uint64_t，加法不会产生进位，好计算。

WARNING

数组中，每个元素只用低4字节，高4字节用于后续计算存储进位用

# 约定

定义gm.h、gm.c两个文件，一个为头文件，一个为相应实现

函数大数部分以gm_bn_为前缀

函数点部分以gm_point_为前缀

常量及其它以GM_或gm_为前缀

# SM2推荐曲线参数

推荐使用素数域256位椭圆曲线。

椭圆曲线方程:

曲线参数:

p  = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a  = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
b  = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
n  = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
Gx = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
Gy = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0

1
2
3
4
5
6

# 计算机中存储大数

拿参数b来举例，那么它在我们定义的大数中是怎么存储的呢

|========|========|========|========|========|========|========|========|
|  b[7]  |  b[6]  |  b[5]  |  b[4]  |  b[3]  |  b[2]  |  b[1]  |  b[0]  |
|========|========|========|========|========|========|========|========|
|28E9FA9E|9D9F5E34|4D5A9E4B|CF6509A7|F39789F5|15AB8F92|DDBCBD41|4D940E93|
|--------|--------|--------|--------|--------|--------|--------|--------|

1
2
3
4
5

有了这个存储规则，那我们实现相应的转换代码就简单了

# 大数到字节串

假设有一个字节串uint8_t out[32]，那么out[0]应该是多少，out[31]应该是多少。

如果需要仔细研究的话，可以参照国密相关规范文档SM2-第1部分-第4章节数据类型及其转换，这里我就直接给出结果，实话说我没太看懂，数学不好。

out[0] = b[7]的高位，即0x28
out[3] = b[7]的低位，即0x9E

out[31] = b[0]的低位，即0x93

1
2
3
4

那将一个4字节整数，转成uint8_t数组，就需要先写一个转换宏：

#define GM_PUTU32(p,V) \
	((p)[0] = (uint8_t)((V) >> 24), \
	 (p)[1] = (uint8_t)((V) >> 16), \
	 (p)[2] = (uint8_t)((V) >>  8), \
	 (p)[3] = (uint8_t)(V))

1
2
3
4
5

最终的转换函数定义及实现如下：

void gm_bn_to_bytes(const gm_bn_t a, uint8_t out[32]) {
    int i;
    for (i = 7; i >= 0; i--) {
        GM_PUTU32(out, a[i]);
        out += 4;
    }
}

1
2
3
4
5
6
7

# 字节串到大数

由上一章节可知，从字节串到大数，我们大数是用8个uint64_t来存储，当然每个元素只用4字节。

先写一个字节串转uint32_t的宏:

#define GM_GETU32(p) \
    ((uint32_t)(p)[0] << 24 | \
	 (uint32_t)(p)[1] << 16 | \
	 (uint32_t)(p)[2] <<  8 | \
	 (uint32_t)(p)[3])

1
2
3
4
5

再来实现转换函数：

void gm_bn_from_bytes(gm_bn_t r, const uint8_t in[32]) {
    int i;
    for (i = 7; i >= 0; i--) {
        r[i] = GM_GETU32(in);
        in += 4;
    }
}

1
2
3
4
5
6
7

# 大数到十六进制字符串

这个可以借助sprintf格式化输出来实现，这个比较简单就直接贴代码了

void gm_bn_to_hex(const gm_bn_t a, char hex[64]) {
    int i;
    for (i = 7; i >= 0; i--) {
        int len;
        len = sprintf(hex, "%08X", (uint32_t)a[i]);
        assert(len == 8);
        hex += 8;
    }
}

1
2
3
4
5
6
7
8
9

# 十六进制字符串到大数

已经实现了字节串到大数，那么只需要将十六进制字符串转换为字节串即可，这块网上也有很多代码，也不细说了，上代码

static int gm_hex2int(char c) {
    if(c >= '0' && c <= '9') {
        return c - '0';
    }else if(c >= 'a' && c <= 'f') {
        return c - 'a' + 10;
    }else if(c >= 'A' && c <= 'F') {
        return c - 'A' + 10;
    }
    return -1;
}

static int gm_hex2bin(const char * in, int in_len, uint8_t * out) {
    int c = 0;
    if((in_len % 2) != 0) {
        return -1;
    }

    while (in_len) {
        if ((c = gm_hex2int(*in++)) < 0) {
            return -1;
        }
        *out = (uint8_t)c << 4;

        if ((c = gm_hex2int(*in++)) < 0) {
            return -1;
        }
        *out |= (uint8_t)c;

        in_len -= 2;
        out++;
    }
    return 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

转换函数：

int gm_bn_from_hex(gm_bn_t r, const char hex[64]) {
    uint8_t buf[32];
    if (gm_hex2bin(hex, 64, buf) < 0)
        return -1;
    gm_bn_from_bytes(r, buf);
    return 1;
}

1
2
3
4
5
6
7

# 大数到比特串

如何将大数转到char bits[256]的比特串呢，同样的只要知道规则就好写

bits[0] = b[7]最高位比特
bits[255] = b[0]最低位比特

1
2

相应转换函数：

void gm_bn_to_bits(const gm_bn_t a, char bits[256]) {
    int i, j;
    for (i = 7; i >= 0; i--) {
        uint64_t w = a[i];
        for (j = 0; j < 32; j++) {
            *bits++ = (w & 0x080000000ULL) ? '1' : '0';
            w <<= 1;
        }
    }
}

1
2
3
4
5
6
7
8
9
10

# 定义常量备用

知道了转换规则，接下来将国密推荐曲线后续需要用到的一些常用大数事先定义一下

// P参数
const gm_bn_t GM_BN_P = {
        0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF,
        0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE
};

// N参数
const gm_bn_t GM_BN_N = {
        0x39D54123, 0x53BBF409, 0x21C6052B, 0x7203DF6B,
        0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE
};

// 0
static const gm_bn_t GM_BN_ZERO = {
        0x0, 0x0, 0x0, 0x0,
        0x0, 0x0, 0x0, 0x0
};

// 1
static const gm_bn_t GM_BN_ONE = {
        0x1, 0x0, 0x0, 0x0,
        0x0, 0x0, 0x0, 0x0
};

// 2
static const gm_bn_t GM_BN_TWO = {
        0x2, 0x0, 0x0, 0x0,
        0x0, 0x0, 0x0, 0x0
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

这里部分加了static修饰，表示限本文件使用，外部无法使用，这个基本C语言语法后面不赘述了

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

← 绪大数比较 →