继SM3 之后下一个要实现的算法是SM4 。
SM4 对称分组加密
SM4 算法是一个对称分组加密算法,类似于 DES 或者 AES。对称加密也就是加密与解密的密钥是同一个。加密和解密时会将输入数据按固定的比特长度分块进行加密。不同于 AES 提供多个版本。SM4 的的分组长度为 128bit,密钥长度为 128bit。SM4 的一个有趣的地方在于,生成密钥的算法和加密算法本身是一致的。分组密码实际使用时,对于消息长度不是分组倍数长度的消息要进行 padding,以此也产生出了很多模式。
上一次实现了 SM3 算法 之后看了一下 OpenSSL 的实现,觉得自己有必要学习一下 OpenSSL 的函数接口组织。所以这一次先去看了看 OpenSSL 的实现并模仿了它的接口的设计,自己实现了SM4 算法 。
具体实现
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 34 35 36 37 38 39 #ifndef _sm4_H_ #define _sm4_H_ #include <stdio.h> #include <stdint.h> #define SM4_DECRYPT 0 #define SM4_ENCRYPT 1 #define SM4_BLOCK_SIZE 16 #define SM4_KEY_SCHEDULE 32 typedef struct { int mode; uint32_t rk[SM4_KEY_SCHEDULE]; } sm4_ctx; int sm4_set_key (const uint8_t *key, sm4_ctx * const ctx) ; void sm4_encrypt (const uint8_t *in, uint8_t *out, const sm4_ctx *ctx) ; void sm4_decrypt (const uint8_t *in, uint8_t *out, const sm4_ctx *ctx) ; static inline uint32_t load_uint32_be (const uint8_t *b, int n) ; static inline void store_uint32_be (uint32_t v, uint8_t * const b) ; static inline void xor_blk (uint8_t *a, uint8_t *b) ; static inline void SM4_F (uint32_t * const blks, const uint32_t *rkg) ; static inline uint32_t SM4_T (uint32_t X) ; void sm4_encrypt_file (FILE *in, FILE *out, sm4_ctx *ctx) ; void sm4_decrypt_file (FILE *in, FILE *out, sm4_ctx *ctx) ; void sm4_cbc_encrypt_file (FILE *in, FILE *out, sm4_ctx *ctx) ; void sm4_cbc_decrypt_file (FILE *in, FILE *out, sm4_ctx *ctx) ; #endif
略过几个 util 类的函数,下面来分析一下算法的一些步骤。
SM4 的操作对象为 128bit 的分块,其中的运算都将 128bit 分为 32bit 的字进行。每个块 4 个字。
生成轮秘钥
此类算法一般都会先生成轮秘钥,SM4 也不例外。SM4 生成轮秘钥的算法和加密算法是几乎一致的,只是中间的一个变换有点区别。按文档实现就好。
其中 SBox 的置换操作对于一个字来说是有四个 SBox 并排置换实现的
1 2 3 4 5 6 t |= (uint32_t )(SM4_S[(uint8_t ) (X>>24 )]) << 24 ; t |= (uint32_t )(SM4_S[(uint8_t ) (X>>16 )]) << 16 ; t |= (uint32_t )(SM4_S[(uint8_t ) (X>>8 )]) << 8 ; t |= (uint32_t )SM4_S[(uint8_t ) X]; t = t ^ ROT32L(t, 13 ) ^ ROT32L(t, 23 );
如果不是提前读了 OpenSSL 的源码,我这里可能会选择强转指针而不是移位加或运算。相对强转指针这样的算法可读性明显更好。
使用轮秘钥进行加密
加密的只要算法就是 SBox 的置换和 L 变换,文档都有详细说明了。
1 2 3 4 5 6 7 8 9 10 static inline uint32_t SM4_T (uint32_t X) { uint32_t t = 0 ; t |= ((uint32_t )SM4_S[(uint8_t )(X>>24 )]) << 24 ; t |= ((uint32_t )SM4_S[(uint8_t )(X>>16 )]) << 16 ; t |= ((uint32_t )SM4_S[(uint8_t )(X>>8 )]) << 8 ; t |= ((uint32_t )SM4_S[(uint8_t )(X)]); t ^= ROT32L(t, 2 ) ^ ROT32L(t, 10 ) ^ ROT32L(t, 18 ) ^ ROT32L(t, 24 ); return t; }
可以看到算法与轮秘钥生成算法是一样的,只是最后的 L 变换有所区别。
解密算法
SM4 解密算法与加密算法一致,只是使用轮秘钥的时候倒序使用
总结
算法实现不难。在如何提升速度方面 OpenSSL 给了一个很好的示范。它先把一个字 (32bit) 的 SBox 的置换和 L 置换的结果提前算了出来 。
实际应用 - 加密文件
Padding
实际应用过程中的 message 不一定是 128bit 整数倍的,所以需要进行 padding。padding 要考虑的东西主要是要让 padding 能够被识别出来。由于输入是二进制流所以不能通过 Magic bytes 的形式区分。在网上找相关的资料可以查到不少padding 的算法 。
在这里选用 PKCS#5 算法。该算法就是将不足 16byte 的块填充成 16byte,其中填充的每一块的数值都是 padding 的长度。一个特例是,当填充恰好为 16byte 的块的时候仍需填充额外的 16byte。
举个例子。
1 2 3 4 5 // 加入最后一块为 0x12 0x34 0x56 则填充长度为 16-3=13 0x0d 0x12 0x34 0x56 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 填充恰好 16byte 的块时,仍填充 16bytes 的 0x10
额外填充的目的是确保解密后可以准确将 padding 移除而没有歧义。
CBC
CBC 从英文全称上去理解(Cipher Block Chaining)这种模式下每一个分组的明文经过 cipher 加密之前还会和前一个分组加密后的密文异或。第一个分组则会和一个随机生成的 IV 进行异或。
解密的时候则会将解密后的输出与前一个分组的密文或者 IV 进行异或得到明文。
CBC 模式的优点在于对于重复的明文加密出来的块因为经过上一个块的异或得到的密文会不一样。这样输入与明文没有固定的关系。
具体实现
首先我们生成的 IV 要是密码安全的 random bytes。Uinx 下应该读/dev/urandom
可以做到,但是为了能够 Protable 用了一个库randombytes
下面看实现代码,之前有同学问我大文件怎么读。我的想法是只要获取了文件的长度,然后用流的方式一次进一部分就可以了。读到最后一块的时候再来 padding。读取文件长度可以通过fseek
+ftell
来实现。
需要注意的是大文件(实测 4G 左右)的时候MinGW 编译的 fseek 会出错 ,我暂时找不到很好的解决方式。有大佬知道的话还请指点一下。
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 void sm4_cbc_encrypt_file (FILE *in, FILE *out, sm4_ctx *ctx) { uint8_t iv[SM4_BLOCK_SIZE]; uint8_t buf[SM4_BLOCK_SIZE], out_buf[SM4_BLOCK_SIZE]; long sz, nremain, nread=0 , padding_byte_len; fseek(in, 0 , SEEK_END); sz = ftell(in); nremain = sz; rewind(in); randombytes(iv, SM4_BLOCK_SIZE); fwrite(iv, 1 , SM4_BLOCK_SIZE, out); int n=0 ; memcpy (out_buf, iv, SM4_BLOCK_SIZE); while (nremain >= SM4_BLOCK_SIZE) { n = fread(buf, 1 , SM4_BLOCK_SIZE, in); nremain -=n; nread += n; xor_blk(buf, out_buf); sm4_encrypt(buf, out_buf, ctx); fwrite(out_buf, 1 , SM4_BLOCK_SIZE, out); } padding_byte_len = SM4_BLOCK_SIZE - nremain; memset (buf, 0 , SM4_BLOCK_SIZE); n = fread(buf, 1 , nremain, in); nremain -= n; nread += n; if (padding_byte_len != SM4_BLOCK_SIZE) { fread(buf, 1 , nremain, in); memset (buf+n, padding_byte_len, padding_byte_len); xor_blk(buf, out_buf); sm4_encrypt(buf, out_buf, ctx); fwrite(out_buf, 1 , SM4_BLOCK_SIZE, out); } else { memset (buf, SM4_BLOCK_SIZE, SM4_BLOCK_SIZE); xor_blk(buf, out_buf); sm4_encrypt(buf, out_buf, ctx); fwrite(out_buf, 1 , SM4_BLOCK_SIZE, out); } }
解密的操作类似,知道了文件头 16byte 为 IV,先读出来,然后依次读取并且解密。因为是经过 padding 的所以最后一块一定是有 pading,而且最后一 byte 一定是 padding 长度。然后输出非 padding 部分的明文即可
1 2 3 4 5 n = fread(buf, 1 , SM4_BLOCK_SIZE, in); sm4_decrypt(buf, out_buf, ctx); xor_blk(out_buf, iv); long padding_byte_len = out_buf[SM4_BLOCK_SIZE-1 ];fwrite(out_buf, 1 , SM4_BLOCK_SIZE-padding_byte_len, out);
体会
学了点对称分组密码的基本结构还有具体实现吧。OpenSSL 为我节省了不少功夫少走的不少弯路。O (∩_∩) O 哈哈~
参考文章