This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
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的进一步优化；