模逆元的概念

在数学上，乘法逆元有一个更加广为人知的别名“倒数”。也就是说，对于实数 a，其倒数 a-1 满足 a*a-1=1。因为 1 是实数域的乘法单位元，故而倒数 a-1 为实数 a 的乘法逆元。

而在无限域模运算中，乘法逆元的定义要更简单一些：如果 a 和 m 都是正整数且满足 gcd(a,m)=1，那么在模 m 意义下，存在一个整数 b，使得 ab≡1(mod m)，此时 b 就是 a 在模 m 运算下的逆元，常示意为 a-1，简称为模逆元。 因为引入了模运算，在实数域上简略求倒数取得逆元的办法并不能间接求得无限域上的模逆元，须要改用更为简单的形式求解运算后果。

在 SM2 数字签名算法中，存在两个必须计算模逆元的步骤：一是将椭圆曲线公钥点 PK 由仿射坐标转化为雅可比坐标时，须要计算 z 轴坐标 z1 对素数域参数 p 的模逆元；二是在签名计算过程中，须要求解私钥 dA+1 对椭圆曲线阶数 n 的模逆元。因为模逆元的计算非常复杂，是椭圆曲线中开销最大的单体运算 （无任何优化时计算耗时是模乘法的数千倍） ，且运算处于数字签名算法流程的要害链路上， 因而是制约 SM2 数字签名性能的瓶颈之一。目前，铜锁我的项目为 SM2 数字签名算法提供了通用的模逆元优化实现，尚未针对 SM2 曲线实现特定优化，存在能够进一步优化晋升的空间。

优化计划比拟选型

在数学上，有两种算法能够疾速地计算模逆元，它们别离是拓展欧几里得算法和基于费马小定理的求解算法。上面咱们简要介绍这两类算法，探讨各算法的优缺点以及在铜锁的工程实现中抉择基于费马小定理的求解算法的起因。

1 拓展欧几里得算法求解模逆元

用于求解最大公约数的欧几里得算法最早在欧几里得的《几何本来》中被提出，拓展欧几里得算法是对这一古老算法的扩大。在求解最大公约数的根底上，拓展欧几里得算法通过收集辗转相除过程中的余式，求得线性方程 ax+by=gcd(a,b) 的整数解。因为阶数 n 是一个质数，因而 gcd(a,n)=1，那么该线性方程即转化为 ax+ny=1，恰巧是同余线性方程 ax≡1(mod n) 的个别示意模式，所求的 x 即为 a 的模 n 逆元。

对于古代计算机而言，拓展欧几里得算法的一个毛病是在计算过程中存在大量除法运算，而 CPU 在解决除法运算时的效率通常比其余根本运算 （如加、减、乘） 要低得多。针对这一缺点，约瑟夫 · 斯提芬于 1967 年提出了二进制拓展欧几里得算法[1], 该算法用简略的移位操作和减法代替了简单的除法运算。上面是利用二进制拓展欧几里得算法求模 n 逆元的伪代码：

拓展欧几里得算法求解模逆元的长处是：能够求解任意模数下的逆元，不受模数是否为素数的限度；算法效率高，相较于费马小定理求模逆元有肯定的性能劣势。然而，拓展欧几里得算法相应的也存在一些毛病：实现代码较为简单，容易出错；代码中有大量的分支和判断语句，难以实现恒定工夫 （Constant time） 算法，对于侧信道攻打的抵制较弱，在密码学算法中可能会导致对于私钥或明文的信息产生透露。

2 费马小定理求解模逆元

费马小定理 （Fermat's little theorem） 是数论中的一个重要定理，最早由数学家费马于 1636 年提出。定理的内容是：如果 a 是一个整数，p 是一个质数，那么有：

在 SM2 曲线中，数 a 和参数 n，p 满足 a<p，n<p<2n，且 p 和 n 均为素数，因而数 a，n，p 三者两两互质。此时，费马小定理有如下模式：

数 a，p 互质，那么有 ax=1(mod n)，联立可得：

也就是说，若要计算数 a 对素数 p 的模逆元 x，只须要求解 ap-2mod p 即可。借助费马小定理的转换，模逆元求解的过程即转化为应用模乘与模平方运算结构 ap-2 的过程，大大简化了计算。

使用费马小定理求解模逆元的长处是：算法简略，运算过程只须要模乘与模平方运算参加，没有进位和分支操作，很容易实现恒定工夫算法，在抵制侧信道攻打方面相较于拓展欧几里得算法有较大劣势；相应地，使用费马小定理求解模逆元的毛病有：适用范围较窄，只实用于模数为素数的状况；模数较大时，须要计算的幂次比拟大，相较于应用拓展欧几里得算法求解模逆元的性能稍劣。

3 计划选型

在铜锁中，SM2 数字签名算法的疾速模逆元优化实现最终抉择了基于费马小定理求解模逆元的算法，次要起因有以下两点：

作为铜锁国密通信协议、国密证书签发等要害利用的根底，SM2 数字签名算法在实现时应尤其留神安全性，特地是在抗侧信道攻打方面，应精心设计以防止私钥泄露；基于费马小定理求解模逆元的算法在设计恒定工夫算法、抵制侧信道攻打方面有较大劣势。

费马小定理求模逆元的一些毛病在 SM2 算法的优化实现中可能无效躲避。例如，SM2 曲线的参数 n，p 均为素数，满足费马小定理只实用于模数为素数的条件；对于性能问题，在具体实现时，能够通过加法链结构 ap-2 缩小计算模逆元所需的模乘与模平方运算次数，补救费马小定理求逆的些许性能劣势。

算法实现

本文以 SM2 素数域模逆元求解为例，介绍费马小定理求解模逆元的具体实现。这里首先给出 SM2 素数域参数 p：

由费马小定理可得，若要计算正整数 a 对模数 p 的逆元 a-1，只需计算：

该数的幂次十分大，如果采纳惯例形式结构，效率极低，这里咱们采纳加法链的思维以实现疾速求幂。加法链求幂是一种疾速求幂的办法，它的根本思维是将指数按二进制合成，并将幂运算合成为多个小幂数相乘的模式，从而缩小幂运算的次数。前文提到，费马小定理求解模逆元的运算过程能够合成为模乘法和模平方运算，这里咱们记模乘法次数为 xM，模平方次数为 yS，那么加法链求幂的工夫复杂度能够用 xM+yS 来掂量。

只管使加法链求幂工夫复杂度最优的问题是一个 NP-hard 问题，且证实某求解链路是否为最优解也十分艰难，但明码学界针对常见的椭圆曲线参数曾经提出了许多较优的加法链。咱们通过比拟同一曲线的不同加法链路和相近曲线的较优链路，再进一步比拟不同计划所需的两头值数量，能够比选出一个以后最优解。目前，在针对 SM2 曲线参数 p 的模逆元加法链钻研中，一个较优解是朱辉等人提出的算法[2]，此算法的工夫复杂度为 255M+14S，须要 4 个变量作为两头值，具体如下：

在计算 ap-2 时，另一个须要认真思考的是两头值溢出问题。在本系列（二）中提到，疾速模约减的输出必须小于 p2，因为 0<a<p，因而在每一次乘法或平方运算后，都须要立即调用疾速模约减函数将两头值约化到 [0,p) 范畴内，以防止两头值溢出导致后果出错的状况。最终铜锁实现的疾速模逆元算法如下所示：

static void felem_inv(felem out, const felem in){    felem t0, t1, t2, t3;    felem ftmp;    longfelem tmp;    unsigned i;    /* Step 1: t0 = a^3 = (2^2 - 2^0) * a */    felem_square(tmp, in);    felem_reduce(ftmp, tmp);    felem_mul(tmp, ftmp, in);    felem_reduce(t0, tmp);    /* Step 2: t1 = t0^2 * a = (2^3 - 2^0) * a */    felem_square(tmp, t0);    felem_reduce(ftmp, tmp);    felem_mul(tmp, ftmp, in);    felem_reduce(t1, tmp);    /* 局部中间代码略，残缺代码可见/crypto/ec/sm2p256.c*/        /* Step 14: t2= ((t3^(2^32) * t0)^(2^64) * t0)^(2^94) = (2^254 - 2^222 - 2^94) * a */    felem_assign(ftmp, t3);    for (i = 0; i < 32; i++) {        felem_square(tmp, ftmp);        felem_reduce(ftmp, tmp);    }              felem_mul(tmp, ftmp, t0);    felem_reduce(ftmp, tmp);    for (i = 0; i < 64; i++) {        felem_square(tmp, ftmp);        felem_reduce(ftmp, tmp);    }    felem_mul(tmp, ftmp, t0);    felem_reduce(ftmp, tmp);    for (i = 0; i < 94; i++) {        felem_square(tmp, ftmp);        felem_reduce(ftmp, tmp);    }    felem_assign(t2, ftmp);    /* Step 15: out = (t1 * t2)^4 * a = (2^256 - 2^224 - 2^96 + 2^64 -1) * a */    felem_mul(tmp, t1, t2);    felem_reduce(ftmp, tmp);    felem_square(tmp, ftmp);    felem_reduce(ftmp, tmp);    felem_square(tmp, ftmp);    felem_reduce(ftmp, tmp);    felem_mul(tmp, ftmp, in);    felem_reduce(out, tmp);}

能够看到，最终实现的代码没有进位和分支，且代码实现时仅调用了素数域运算的乘法、平方、疾速约减等函数，因为这些函数都是恒定工夫的，因而最终铜锁所实现的疾速模逆元函数也是恒定工夫的，从算法实现层面阻止了歹意攻击者通过计时攻打获取用户私钥的可能性。

总结与瞻望

对于铜锁 SM2 算法性能优化实际的内容大抵就是这些。在实现优化后，铜锁 SM2 数字签名算法的性能获得了不小的提高，在国密开源产品中处于领先地位，同时极大拉近了与国内支流非对称算法 （例如 ed25519、nistp256） 成熟工程实现的性能差距，有利于国家商用明码在国内的进一步落地推广，实现行业信息系统平安的自主可控。

将来，铜锁还将继续追踪密码学学术界的最新动向，踊跃推动学术研究成绩在铜锁我的项目中落地，为用户提供性能更优、安全性更好的平安产品。欢送开源社区的爱好者们与咱们一起，携手共建铜锁社区良好的我的项目生态！

欢送退出铜锁社区交换钉钉群：44810299

更多文档可关注铜锁官网语雀：https://www.yuque.com/tsdoc

【 文中链接 】

[1]二进制拓展欧几里得算法：https://www.sciencedirect.com/science/article/abs/pii/0021999...

[2]针对素数 PSCA-256 的疾速模逆算法：https://jeit.ac.cn/cn/article/doi/10.11999/JEIT211049