Windard +
Github Zhihu RSS

JavaScript 实现 SM4 国密算法

因最近一个项目需要用到国密算法,所以在网上找了一下国密算法的相关资料。国密算法并不是特指一种算法,而是指国家密码局认定的国产密码算法。它包括 SM2,SM3,SM4 祖冲之算法等一系列算法,可以参考这篇公告说明。

在网上也有不少国密算法的实现,比如说 北京大学信息安全实验室 开发和维护的 GmSSL ,它是支持国密算法和标准的 openSSL 分支,其代码托管在 https://github.com/guanzhi/GmSSL 上。

国密算法 SM2 是公钥算法,即非对称加密算法,类似于 RSA,不过 RSA 是基于大素数分解问题,SM2 是基于椭圆曲线问题,SM3 是消息摘要算法,类似于 md5 或 SHA-1 算法,不过 md5 和 SHA-1 都在 2005 年被中国山东大学的 王小云 教授破解,不建议使用,SM4 是传统的对称加密算法, 采用分组加密,类似于 DES 或 AES ,可以在这篇文章里看到这些算法之间的简单比较,更加深入的研究请参考论文。

网上已有 JavaScript 实现的 SM2 算法,其参考引用了很多 jsrsasign 的实现,这是一个用 JavaScript 做加密解密的库,实现了很多的加密解密算法。

JavaScript 本身是有很多缺陷的,数字只有 int 类型,虽然说是 64 位的,但是在做移位运算的时候它会被自动转换为 32 位,这就很尴尬,32 位的移位运算,一不小心就越界了,而且移位也只有左移,而没有循环移位。虽然说 Python 也是只有 int 型,不过它是真真的64 位,不会缺斤少两,网上也有文章详细的提到 JavaScript 的移位操作的缺陷

JavaScript 没有循环左移,只有左移,右移和无符号位右移。JavaScript 的复数的值等于 - (值的逆 + 1),比如说 -977410425 的二进制表示为 11000101101111011110011010000111 ,它的逆为 00111010010000100001100101111000 ,它的值的逆加1为 00111010010000100001100101111001 ,所以在 JavaScript 中就会表示为 -111010010000100001100101111001,即 x = -(~x + 1)

a=-977410425
-977410425
a.toString(2)
"-111010010000100001100101111001"
(a>>0).toString(2)
"-111010010000100001100101111001"
(a>>>0).toString(2)
"11000101101111011110011010000111"

关于 SM4 算法流程,国家密码局是已经公开了的,可以找到一份 PDF 文档,写的清清楚楚,明明白白,比我想象的要简单一些,这里就展示一下我自己实现的 循环左移 之类的函数,为什么一直在提循环左移呢?肯定是因为算法里面会用到的吖。


点击下载

JavaScript 版

function leftshift(a, n, size=32) {
	n = n % size
	return (a << n) | (a >>> (size - n))
}

Pyhton 版

def leftshift(a, n, size=32):
	n = n % size
	return (a << n) | (a >> (size - n))

或许也是因为这些不优雅的代码,使得代码的执行效率不高,或者说非常低,在官方文档中提供了一个 1000000 遍的加密样例,然而我的 JavaScript 10000 遍就需要近一分钟,Python 10000 遍近 10 秒,这样下来就需要一个多小时了,可是网上找到的 C语言 和 Java 实现的 SM4 对 1000000 遍加密只需要近一秒钟即可,或许跟代码质量也有关吧,但还是可怕的性能差异。

还有一个地方是 S 盒代换的部分,也改进了一下,速度略有提升,但是差距较大。

JavaScript 版

function sm4Sbox(a) {
	var b1 = SboxTable[(a & 0xf0000000) >>> 28][(a & 0x0f000000) >>> 24]
	var b2 = SboxTable[(a & 0x00f00000) >>> 20][(a & 0x000f0000) >>> 16]
	var b3 = SboxTable[(a & 0x0000f000) >>> 12][(a & 0x00000f00) >>>  8]
	var b4 = SboxTable[(a & 0x000000f0) >>>  4][(a & 0x0000000f) >>>  0]
	return (b1 << 24) | (b2 << 16) | (b3 << 8) | (b4 << 0)
}

python 版

def sm4Sbox(a):
	b1 = SboxTable[(a & 0xf0000000) >> 28][(a & 0x0f000000) >> 24]
	b2 = SboxTable[(a & 0x00f00000) >> 20][(a & 0x000f0000) >> 16]
	b3 = SboxTable[(a & 0x0000f000) >> 12][(a & 0x00000f00) >>  8]
	b4 = SboxTable[(a & 0x000000f0) >>  4][(a & 0x0000000f) >>  0]
	return (b1 << 24) | (b2 << 16) | (b3 << 8) | (b4 << 0)

代码都在 https://github.com/windard/sm4 了,打包下载在这里


headlogo   Windard

但行好事,莫问前程

Blog

Opinion

Project

页阅读量:  ・  站访问量:  ・  站访客数: