常数时间国密算法（三）：SM2的素域求逆技术

无底洞

本期作者郭伟基哔哩哔哩技术专家负责B站高能链密码学、区块链相关技术研究与开发，特别是密码学技术的安全、高效实现，以及应用密码学技术实现链上隐私保护和业务赋能。现在我们来看SM2常数时间实现的另一个技术点，即素域求逆。在这篇文章，我们先介绍SM2的签名验签算法，指出实现中的安全隐患，然后介绍相关的数学知识，最后讲解如何安全地实现签名验签算法。01 SM2签名算法简单介绍素域求逆是SM2签名算法所要求的。使用规范文本GMT 0003.2-2012的符号约定：e ?? 为原始待签名信息、椭圆曲线公共参数、签名者信息的综合摘要，为一个256位整数；k ?? 为使用安全的随机数生成器所生成的随机数，取值范围[1, n-1]，其中n为椭圆曲线的参数，并且是一个素数；dA? 为签名用户的私钥，为一个256位的整数。则SM2所规定的签名算法要求计算：(x1, y1) = [k]Gr = (e + x1) mod n，其中mod表示同余判断 r 是否为0或者r + k = n。如是（概率极小），需要重新生成k、重复以上计算步骤，否则进入下一步；s = (k - r*dA) / (1 + dA) mod n如果s非零（大概率），则返回（r, s）作为签名结果。否则需要重新生成k、重复以上计算步骤。在以上计算s的公式中，需要除以（1 + dA），或者说需要乘以（1 + dA）的乘法逆元。这就是求逆计算的来源。细心的读者可能会问，如果我们一直处理的都是各种大整数，那么这里的除法要怎么做，除不尽又怎么办呢？这就不得不说，这里其实有一套特殊的计算法则，不会除不尽了。02?素域与素域求逆一般而言，两个大整数相除，很可能会发生除不尽、产生小数甚至分数（无限循环小数）的情况。我们知道，浮点数在计算机中可能无法精确表示，针对浮点数的计算，常常会产生各种误差。这种误差在密码学中极为致命，一般不允许出现。密码学中，需要一套计算法则来避免这种情况。这就是有限域，其中基于某个素数p产生的有限域称为素域，一般记为Fp。素域Fp的计算法则其实非常简单：它只需要在通常的加法和乘法规则上加一个除以该p取余数的规定。而所谓的“有限”（域），也很直观：素域Fp的元素个数有限，不多不少正好p个。在这些元素中，0为加法的单位元，也就是任何元素与之相加，所得仍是该数；1为乘法的单位元。我们可以把减法定义为加法的逆运算，除法定义为乘法的逆运算，但一般不使用除法这个术语，而称为乘法求逆：某个元素a（非零）的乘法逆元a-1定义为某个b，使得：a * b ≡ 1 mod?p在数学上，这样的逆元总是存在的（前提是a ≠ 0）。这也就回答了之前的问题：除不尽怎么办。因此，我们总是能够完成以上计算s值的步骤（规范要求dA ≠ n - 1，以保证分母不为零）。现在，我们只是说了非零元素的逆元总是存在，那么要怎么样才能把逆元计算出来呢？一般而言可以使用扩展欧几里得算法，一般在大整数相关的函数库或类库中均有实现；另外就是费马小定理方法。下面分别加以介绍。03 辗转相除法与扩展欧几里得算法小时候学习过奥数，或者正在辅导小孩学奥数的读者可能对辗转相除法不陌生，这是求两个数的最大公约数（gcd）的一种方法：设有a, b两数，我们反复以其中较小者去除其中较大者，然后取余数以替代除数，原除数作为新的被除数，直到余数为零，则最后一个除数即为 a 和 b 两者的最大公约数。此方法可以制作成表格形式，更为直观，譬如计算gcd(32, 12)：以上表格，最后一行我们得到余数为0，那么该行的除数也就是所求的最大公约数了，因此gcd(32, 12) = 4。这就是辗转相除法，又称欧几里得算法。而所谓的扩展欧几里得算法，就是将上表再加以扩展，添加若干列，以便求得u, v使得u*a + v*b = gcd(a, b)。具体讲解该方法之前，我们需要解释一下，为何使用扩展欧几里得算法就能求得素域元素的乘法逆元。假设有p, b两个数，其中 p 为素数，b