一个关于国密 SM4 的故事

周三不加班

发布于 2019-06-04 18:11:13

2.2K1

发布于 2019-06-04 18:11:13

文章被收录于专栏：程序猿杂货铺

原文 | https://dwz.cn/zJwokV1S

整理 | 程序猿杂货铺

我的名字叫 SM4，我还有三位兄长，分别是大哥 SM1，二哥 SM2，和三哥 SM3。说起我的名字，故事要回到2006 年的时候，我出生的时候并不是叫 SM4 的，而是叫做 SMS4。只是 2012 年的时候我父亲给我改名了。虽然我起了一个洋气的名字，但我必须郑重地说，我是一个中国人。名字可能只是为了与国际接轨。

我的家族

先简单地介绍一下我的家族，我的父亲是国家密码管理局，我们几兄弟就主要负责起国家信息安全中的加密。我由一出生起，就不断地被家人提醒我要肩负重任。因此，我也非常努力，不断地学习和完善提升自我。

大哥主要负责硬件的加密，不知道是不是因为大哥身为长兄，所以份外地冷酷，他的加密算法和二哥三哥和我都不同，我们的算法都是公开的，但是大哥却埋藏得很深，我们都不知道他的算法是怎样的。

几兄弟里，我和二哥比较亲密，可能是因为他的业务名称和我比较像吧，他主要负责的是非对称加密。我有什么不懂都是经常跑去请教他的。

三哥主要负责哈希算法的。而我，则是负责对称加密。别看我现在说得头头是道，其实一开始我完全不理解这些名词到底是什么意思，于是我首先就走去问二哥。

我是干啥的

我说，二哥，父亲告诉我要负责对称加密，其实我到底是要做些什么呢？

二哥耐心地告诉我，在我们这个密码学的大家族里，加密算法主要可以分为两种，一个是非对称加密算法，另一个就是对称加密算法。也就是我和你主要负责的。对称加密简单来说就是有一个明文，通过一个密钥加密之后得到一个密文，这个密文可以通过相同的密要解密得出和原来相同的明文。

我听了之后觉得有点理解了，我说，那不是很简单吗，比如说明文是 123 ，密码是 456 ，我只要将 123+456 那就变成了 579，别人不就看不懂了吗？

二哥哈哈大笑，你是不是看金田一和柯南的侦探小说太多了，你说的原理是没有错的，但是你太少瞧黑客和攻击者了，如此简单的加密算法，有经验的攻击者不用 1 秒钟就可以解开了，你肩负的是我们全国的安全啊，你必须要有一种安全的加密算法才可以。而且你这种算法必须是可以公开的，只要密钥足够复杂，别人就永远也解不开，这样才能形成一种标准，四弟，你需要像我一样成为一种标准，而不仅仅成为一种算法。

我眉头紧皱，心想算法也可以公开？这也太难了吧。我委屈地说，二哥，这个太难了，我不能学大哥那样子不公开算法吗？

二哥回答，我的算法也是公开的，不也是什么事也没有吗？你可以看看前人是怎么实现类似的功能，你应该在前人的基础上不断创新，而不是从零开始，因循守旧。

我恍然大悟，前人？有谁啊？

有非常多，早在 1977 年，美国就颁布了一种对称加密算法，叫 DES。虽然这种算法已经被证明是不安全的，但是你也可以去学习学习。又比如比利时有两位密码学家，在 1998 年就提出了一种著名的对称加密算法，现在已经被全世界广泛使用，就是鼎鼎大名的 AES，我们喜欢叫做算法，但其实他已经是一种标准了。

二哥果然是博古通今，我听后大受启发，马上就跑回书房跃跃欲试。

我的算法标准

我查了一下书籍，果然大有发现，对称加密分为了块加密和流加密，流比较偏门，于是我先跳过了，我把已经出现的块加密算法列举了一下。

于是我了解了一下目前公认比较安全的 AES。

这个过程中，我还发现了一些秘密，原来其实大哥也是对称加密的，还有个名字另类的兄弟叫 ZUC。我好像还有一些弟弟也是对称，叫 SM7 的，但是族谱里现在还没有看见，所以我也没有深入研究了。

研究了 AES 之后发现，要实现一个可靠的加密算法，效率非常重要，想像一下，要加密的明文长度比较短还可以接受，万一非常非常长的，加密的效率就非常重要了。要提高效率，我首先想到的就是并行计算，而要并行计算，就需要对明文首先划分成相同的长度，这个过程我称之为分组。

由于要划分成相同的长度才好实现统一的加密解密处理，那么就必然会出现分组后最后的那一组字符串会出现长度不够的问题，那么就需要把缺失的长度补充上去，这个过程我称之为填充。

像我刚才跟二哥说的那个例子一样，简单的一次加密计算，必然是很容易被破解的，所以要增加算法的安全性，就需要对明文的计算转换进行多次，我把每一次的计算称之为迭代。

太好了！我的加密算法主要可以切分三个：分组、填充、迭代。

迭代的算法是最为核心的部分，当然要参考最为著名的 Feistel 分组加密结构。

影响 Feistel 结构的因素有如下 5 个：

块的大小：大的块会提高加密的安全性，但是会降低加密、解密的速度。截止至 2013 年，比较流行的这种方案是 64 bit。而 128 bit 的使用也比较广泛。
密钥的大小：同上。现在流行的是 64 bit ，而 128 bit 正逐渐成为主流。
循环次数（轮次数）：每多进行一轮循环，安全性就会有所提高。现阶段比较流行的是16轮。
子密钥的生成算法：生成算法越复杂，则会使得密码被破译的难度增强，即，信息会越安全。
轮函数的复杂度：轮函数越复杂，则安全性越高。

另外，还有很重要的一个迭代模式。目前也是有比较成熟的参考。

ECB 模式

CBC 模式

所有的迭代模式

好了，我定义好自己的分组长度、填充标准、轮函数的算法，我的标准终于出来了！

《SM4 分组密码算法标准英文文本》下载地址：http://suo.im/52YK0H （公众号后台回复【SM4】可以获取 PDF 版本）

我的实现

后面陆陆续续，有很多语言根据我的标准进行了实现，包括 C、Java、Python 等等。

要实现这个，还是很不容易的。首先要懂得线性代数，什么线性变换、非线性变换。对编程里的位运算也得熟悉。不过这些我都不管，让大家去实现吧，哈哈。

下面贴一下我的好朋友 Java 实现中的关键轮函数(代码量比较大，限于篇幅，此处就不全部贴出来，想进一步了解的后台可以回复【SM4】获取完整代码)。

/**
     * 轮函数F。
     *
     * 6 Round Function ?
     * 6.1 Round Function Structure
     * Suppose the input to round function is (?0 ,?1 ,?2 ,?3 ) ∈ (?43)C and the round key is
     * ?? ∈ ?43, then ? can be represented as: 3
     * ? ?0,?2,?3,?4,??   = ?0 ⊕ ?(?2 ⊕ ?3 ⊕ ?4 ⊕ ??).
     *
     * @param x0
     * @param x1
     * @param x2
     * @param x3
     * @param rk
     * @return
     */
 private long sm4F(long x0, long x1, long x2, long x3, long rk) {
 return x0 ^ sm4Lt(x1 ^ x2 ^ x3 ^ rk);
    }
/**
     * 组合T。
     * 包括：
     * （1）非线性变换?(tau)
     * （2）线性变换L。
     *
     * 6.2 Permutation ?
     * ?: ?43 → ?43 is an invertible transformation, composed of a nonlinear transformation ? 33
     * and a linear transformation ?. That is, ? ∙ = ?(?(∙)).
     *
     * (1) Nonlinear transformation ?
     * ? is composed of 4 S-boxes in parallel. Suppose ? = (? ,? ,? ,? ) ∈ (?M)C is input to 0234 3
     * ?, and ? = (? ,? ,? ,? ) ∈ (?M)C is the corresponding output, then 0234 3
     * ?0,?2,?3,?4 = ? ? = (???? ?0 ,???? ?2 ,???? ?3 ,???? ?4 ).
     * The S-box is as follows:
     * @see SboxTable
     *
     * (2) Linear transformation ?
     * The output from the nonlinear transformation ? is the input to the linear
     * transformation ?. Suppose the input to ? is ? ∈ ?43, and the corresponding output is 3
     * ? ∈ ?43, then 3
     * ?=? ? =?⊕(?<<<2)⊕(?<<<10)⊕(?<<<18)⊕(?<<<24).
     *
     * @param ka
     * @return
     */
 private long sm4Lt(long ka) {
 long bb = 0L;
 long c = 0L;
 byte[] a = new byte[4];
 byte[] b = new byte[4];
        PUT_ULONG_BE(ka, a, 0);
        b[0] = sm4Sbox(a[0]);
        b[1] = sm4Sbox(a[1]);
        b[2] = sm4Sbox(a[2]);
        b[3] = sm4Sbox(a[3]);
        bb = GET_ULONG_BE(b, 0);
        c = bb ^ ROTL(bb, 2) ^ ROTL(bb, 10) ^ ROTL(bb, 18) ^ ROTL(bb, 24);
 return c;
    }

参考资料

[1]: http://www.cnnic.net.cn/jscx/mixbz/sfjj/ [2]: https://baike.baidu.com/item/SMS4算法/16858974 [3]: https://baike.baidu.com/item/DES [4]: https://baike.baidu.com/item/Feistel/1985068 [5]: https://baike.baidu.com/item/线性变换/5904192?fr=aladdin [6]: https://baike.baidu.com/item/τ/2858554?fr=aladdin [7]: http://ris.sic.gov.cn/cn/y2016/v2/i11/1028