Skip to content

SM9实现及优化

Jump to bottom
Sun Yimin edited this page Jul 25, 2023 · 35 revisions

SM9的实现

一个算法实现的最基本要求是正确性，和SM2不同，SM9规范中的示例都是用最终选定参数来做的，这是SM9规范比SM2规范好的一面，但这并没有减少其实现的复杂度。

第一步自然是寻找参考实现，找了一下，bn256，优点是：基域通过汇编实现了乘法、加法、减法等；完整的1-2-6-12塔式扩域；优化的pairing实现；完善的代码注释，可以容易找到参考文档。缺点是：SM9以1-2-4-12塔式扩域为准，基于bn256代码改造的实现很难验证正确性（尤其对于初始实现者来说）。 gmssl sm9，优点是：1-2-4-12塔式扩域；正确性。缺点是：纯c语言实现，代码注释少，基本无优化。

第二步：以bn256项目为基础，基于SM9参数实现1-2-4-12塔式扩域。gfP和gfP2比较简单，改造程度不大，主要是添加测试，确保正确性。接着实现gfP4，gfP12，基础算法加、减、乘、平方相对容易，共轭Conjucate和Frobenius运算花了相对多一点时间。

第三步：参考sm9_alg.c和bn256，实现Pairing，这一步花了最多的时间，特别是乘扭曲线（mulLine）的正确实现以及除数处理（主要是理论基础差）。那时候的实现是这样的：bn_pair.go。第三步做完，基础已完成。

第四步：实现SM9的密钥生成、签名/验签、加解密及密钥交换，这一步相对顺利。

这四步前后花了一个月左右的时间。

SM9的优化

具体可以参考Issues / Discussions。

借鉴椭圆曲线实现

包括标量乘法的借鉴、应用加法链优化求逆和求平方根、Marshal/Unmarshal的汇编实现、基域运算实现的借鉴等。

Pairing实现向bn256项目Pairing实现的回归

先是finalExponentiation的回归，证实其实现的正确性和高效性。

接着是乘扭曲线（mulLine）的回归，去掉除数。

1-2-6-12扩域实现及相互转换

1-2-4-12和1-2-6-12塔式扩域的转换是在一篇文章里看到的，看到后就实现了SM9的1-2-6-12塔式扩域及相互转换。

分圆子群特殊平方运算

finalExponentiation中应用特殊平方运算，这是从参考文档看到的，当然人家的是1-2-6-12塔式扩域上的c语言实现，这个特殊平方有效提高了finalExponentiation的性能。 （在finalExponentiation中，in ^ ((p^6 - 1) * (p^2 + 1))为什么是分圆子群的元素？因为(in ^ ((p^6 - 1) * (p^2 + 1)))^(p^4-p^2+1) = in^(p^12-1) = 1）

米勒运算中的line add/double不新建、返回对象

Go语言相对简单，但是为了简单，编译器做了很多额外的操作，譬如切片操作边界检查；返回栈中对象的内存迁移等等。有些对性能影响还是挺大的。

应用SIMD复制值

也就是Set操作的汇编实现，同时也尽量减少Set操作（这个“优化”导致了实现的复杂性、影响了代码的可维护性，可能不值得）。

Neg改用Sub实现

最后发现是我自己不小心引入了个bug，源自bn256 ：gfpNeg的函数 // go:noescape， 多了个空格！

无意中发现Neg方法不如后来实现的Sub性能好，这个挺奇怪的，单独测试，gfpNeg性能(BenchmarkGfPNeg-6)要比gfpSub()性能好(BenchmarkGfPNeg2-6)：

goos: windows
goarch: amd64
pkg: github.com/emmansun/gmsm/sm9/bn256
cpu: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
BenchmarkGfPNeg-6   	349538827	         3.399 ns/op	       0 B/op	       0 allocs/op
BenchmarkGfPNeg2-6   	282038318	         4.208 ns/op	       0 B/op	       0 allocs/op

但是应用到gfP2的MulUNC方法： gfpNeg

goos: windows
goarch: amd64
pkg: github.com/emmansun/gmsm/sm9/bn256
cpu: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
BenchmarkGfP2MulU-6   	 8290990	       141.1 ns/op	      64 B/op	       1 allocs/op
BenchmarkGfP2SquareU-6   	10009350	       117.0 ns/op	      64 B/op	       1 allocs/op

gfpSub

goos: windows
goarch: amd64
pkg: github.com/emmansun/gmsm/sm9/bn256
cpu: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
BenchmarkGfP2MulU-6   	12727611	        92.70 ns/op	       0 B/op	       0 allocs/op
BenchmarkGfP2SquareU-6   	17728008	        66.35 ns/op	       0 B/op	       0 allocs/op

使用投影坐标下的完全加法、Double

原来的方法不是constant-time运行的，安全性不高。 https://github.com/emmansun/gmsm/issues/144

下一步

SM9算法好像比较冷门、应用也没有SM2广泛，因为128位安全性挑战？还是因为实现复杂度和性能？

  • 参考《New software speed records for cryptographic pairings》使用浮点运算和SIMD实现？
  • High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves，平方扩域上的运算优化，不过由于他的p选择，有其特殊性，基本无参考价值。
  • 小步的优化：
    • gfP2 乘法、平方等的asm实现，这个实现提高性能不足10%（amd64）；
    • curvePoint/G1 曲线运算add/dobule的进一步优化；
Clone this wiki locally