SM3 哈希密码算法实现

这学期欧气爆棚，有幸在第一轮选到了密码学研学项目的非正式课程。第一个要学习的算法是SM3

SM3 Hash

SM3 是一个哈希算法而不是加密。哈希是将一个任意长的输入映射到一个固定长的输出的函数。在 SM3 中输出为 256bit 长度。它的特点就是具有单向性，并且同样的输入总是映射到同样的输出。单向性从输入能轻松求出输出。但是却很难从输出反推输入。这样的性质让 Hash 有了它的应用。比如说网站后台的密码存储通常不会存储明文而是存储密码的哈希值。在需要验证密码的时候只需要计算并比对哈希值。而比特币的工作量证明也是通过不断尝试 nonce 反推哈希来实现的。

Hash 通用结构

哈希算法总是有通用的结构

将输入 padding 直到恰好可以分组
将输入分成 n 组 $B_{0} \ldots B_{n-1}$
对初始 iv 置数
迭代压缩函数 $IV_{n}=CF \left( IV_{n-1},B_{n-1} \right)$
最后一个 IV 就是 Hash 值

SM3 实现

按照文档和网上查到的资料，我也实现了一个 SM3。代码放在了 GitHub。头文件如下。里面的几个函数分别对应其中的几个步骤。

#ifndef _sm3_H_
#define _sm3_H_

#include <stddef.h>

typedef unsigned char byte;
typedef unsigned int word;

// padding
byte *padding(const byte *src, size_t src_len, size_t *out_len);

// 生成拓展 Block CF 需要用到
word *expand_blk(const char *block, word **W_p);

void reverse_by_byte(byte * const le, size_t len);

// 初始化 IV
void iv_init(word * const ivs);

// CF
void CF(word * const iv, byte* blk, const word * const W, const word * const W_p);

byte *sm3(const char * const s);

#endif

下面从依次分析这几个步骤
操作的层次或者说对象各有不同，主要分为 byte 和 word（根据文档中的定义是 4byte）

具体步骤

padding

padding 的操作对象是 byte，在这一层次上可以忽略大小端。因为对象是一个 byte

Padding 的规则在文档中写的很清楚。

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

实现上我们首先需要算出最终输出的长度来分配内存。关键需要计算出填充的 0 的个数 k。k 可以通过(448 - ((l % 512) + 1) + 512) % 512算出。加上 512 再模 512 可以避免得到负数的情况。然后只需要分配合适大小的内存置零并将 m 复制过去。这样我们填充 0 的部分和明文部分就算做好了。

然后还有两个步骤，明文后面的一位需要置 1，然后最后的 64 位需要置为明文长度的二进制表示。

明文后一 byte 可以通过 m [l] 得到，然后只需要对这一位跟 0x80 做位或运算就好了。
而最后的 64 位长度表示则有大小端的差别在小端机器上需要先转换为大端表示。

拓展消息

拓展消息这里就是按照文档套公式。在实现上由于操作对象变成了 word 需要注意的是大小端问题。因为牵涉到字的位移操作所以大小端尤为重要。在我这个实现中 padding 产生的 bytes 是按照大端排列的。所以需要先转成小端再计算。

CF 压缩函数

CF 也是照着文档套公式实现。因为 + 是模 2^32 加法，所以我们应该选择 unsigned int 来作为 word 的具体数字类型。之后就没有什么特别需要注意了。

注意的点

大小端判断和转换

大小端的判断参考了大佬的博文。通过在内存中分配一个 int 变量，通过强转它的指针为 char 判断低地址 byte 的值判断机器是大端还是小端。

例如

static const int endianTest = 0x12345678;

大端中表示为 0x12 0x34 0x56 0x78
小端中表示为 0x78 0x56 0x34 0x12

转换也是通过强转指针为 char，参考以下代码

void reverse_by_byte(byte * const le, size_t len) {
	for (size_t i=0;i<len>>1;i++) {
		byte tmp = le[i];
		le[i] = le[len-1-i];
		le[len-1-i]=tmp;
	}
}

循环移位

#define ls_w(a, n) (a >> (32 - n) | a << n)

先保留剩下的位再和要移过去的位或

用移位代替除法

为了效率我们可以使用右移代替除法。乘法一般都能被编译器优化掉。但是除法因为DIV指令会将余数放到寄存器里面所以不能优化掉，可以用右移代替。

体会

算法的实现方面其实不多考虑效率单纯实现的话不难。比较需要注意的就是大小端的问题。C 语言可以直接操作内存所以还是比较舒服的。
至于算法的原理，为什么要那样设计就不知道了。这也应该是正式上课的时候应该注意的问题。

参考文章

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处。

本文链接: https://www.fengkx.top/post/sm3-implementing/

发布于: 2019-11-06

fengkx's Blog

fengkx

Student & Coder