我最近用 Rust 写了一个椭圆曲线公钥密码算法库。我所实现的是国家密码管理局的商用密码算法 SM2,但是各类椭圆曲线密码算法大同小异,因此对于其它同类算法的实现也有参考价值。这里的 SM 是“商(用)密(码)”的拼音简写,我觉得可能有人会想歪,所以解释一下。

实现椭圆曲线公钥密码算法主要包括三个部分,有限域、椭圆曲线,以及公钥密码算法本身。

有限域

SM2 标准中允许使用的 有限域有两类:素域(\( GF(p) \)) 和二次扩域(\( GF(2^n) \))。SM2 的推荐参数给出的是素域。

素域上的运算包括加法和乘法,它们本身非常简单,两个数直接相加或者相乘,然后对素域的阶数 p 进行模运算即可。但是在模运算的时候,使用简单的除法算法,速度可能会比较慢,而有必要使用一些快速算法。

常用的快速模运算算法有 Barret ReductionMontegomery Reduction,用在这里都很合适。

但是很巧,SM2 的推荐参数中,素域的 p 是一个 Solinas 素数。这是是一种非常接近 \( 2^n \) 的特殊的素数。对这样的素域,有一种更快速的 reduction 算法。我在这里就选用了这种算法。由于算法解释起来比较复杂,所以我建议直接去看论文。我的实现在这里

椭圆曲线群

这里的椭圆曲线群构建于有限域之上。主要有三种运算,相加、加倍还有数乘。其中,数乘运算又以相加和加倍为基础。

相加和加倍的原理并不复杂,但是假如直接用公式实现,会有很严重的性能问题。因为,运算公式中涉及到对有限域中的元素求逆,而求逆运算非常缓慢,比有限域运算的乘法慢几十倍。所以,在运算前最好进行投影坐标(projective coordinates)变换。常用的是 Affine CoordinatesJacobian Coordinates。有时候,混合使用这两种投影坐标效率更高,但因为提升不甚明显,所以为了实现简便,我统一使用了 Jacobian Coordinates。

数乘时,最安全的算法是 Montegomery Ladder。这种算法能够有效杜绝 side-channel attack。不过,比起最简单的数乘算法,Montegomery Ladder 都要慢了一些。要速度还是要安全性,这需要 trade-off。

另外,在对椭圆曲线群的生成元进行数乘的时候,由于 base 固定,所以可以通过预运算加速,这里用到的算法名为 fix-base comb,详情参考这篇论文。我的实现见这里还有这里

顺便一提,SM2 的推荐曲线参数被直接给出,未解释原因。若是阴谋论一点,国家密码管理局完全可以像 NSA 那样在曲线里留下后门,以实施 invalid curve attack。但这也没办法,不按它的参数实现,就不是标准的 SM2 了。

数字签名算法

完成了椭圆曲线,到这里也就很简单了,按照标准文档中的流程图实现即可。这里面再次涉及了大整数的模运算,但因为不是性能热点,所以我直接使用了 num-bigint 这个库。

其它参考链接