首页 > 编程语言 >常数时间国密算法

常数时间国密算法

时间:2022-08-29 14:25:19浏览次数:81  
标签:SM2 dA 算法 国密 计算 常数 素域 乘法

常数时间国密算法(三):SM2的素域求逆技术 https://mp.weixin.qq.com/s/4dOgGKJ7bwTxsHr-xekz0Q

常数时间国密算法(三):SM2的素域求逆技术

原创 高能链 哔哩哔哩技术 2022-08-23 12:00 发表于上海 收录于合集 #B站54个 #加密算法3个

本期作者

 

郭伟基

哔哩哔哩技术专家

负责B站高能链密码学、区块链相关技术研究与开发,特别是密码学技术的安全、高效实现,以及应用密码学技术实现链上隐私保护和业务赋能。

 

 

现在我们来看SM2常数时间实现的另一个技术点,即素域求逆。在这篇文章,我们先介绍SM2的签名验签算法,指出实现中的安全隐患,然后介绍相关的数学知识,最后讲解如何安全地实现签名验签算法。

 

01 SM2签名算法简单介绍

 

素域求逆是SM2签名算法所要求的。使用规范文本GMT 0003.2-2012的符号约定:

  • e    为原始待签名信息、椭圆曲线公共参数、签名者信息的综合摘要,为一个256位整数;

  • k    为使用安全的随机数生成器所生成的随机数,取值范围[1, n-1],其中n为椭圆曲线的参数,并且是一个素数;

  • dA  为签名用户的私钥,为一个256位的整数。

 

则SM2所规定的签名算法要求计算:

  • (x1, y1) = [k]G

  • r = (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 < p,那么这两个数互素,其最大公约数为1;如果使用扩展欧几里得算法能够得到 u 和 v 使得 u*p + v*b = gcd(p, b) = 1,那么实际上,v就是 b 在素域 Fp 上的乘法逆元:v*b ≡ 1 mod p。注意,这里我们已经只关心 v 的取值而不用管 u 了。

 

仍以前述数字为例,在表格右方添加三列:v1, v2, v3,分别逐行作如下计算(完整的扩展欧几里得算法需要添加六列,但我们这里不关心 u ):

  • 其初始值设定为:v1 := 0, v2 := 1, v3 := v- q*v2 (同一行)

  • 每一新行:v1 = 上一行的v2,v2 = 上一行的v3,v3 = v1 - q*v2 (同一行;同上)

  • 在 r = 0的那行,令 v = v2,而v3可以不用计算

图片

 

因为我们没有计算 u ,所以无法直接验证v = 3是否我们需要的结果。但是在素域求逆的情况下,这就够了。下面以p = 19, b = 10 为例,计算10在素域F19上的乘法逆元:

图片

 

得到 v = 2。验证:10 * 2 = 20 ≡ 1 mod 19

 

在SM2的签名算法计算过程中,素数 p 是既定的(椭圆曲线的参数 n ),需要保护的是被求乘法逆元的那个数(1 + dA)。然而从上述计算过程我们可以看到,所用表格的行数可能会取决于被计算的数。换句话说,以上形式的扩展欧几里得算法实现可能具有非常数时间特性,可能导致所计算元素的值被破解。以下再给出一个计算p = 19, b = 6 的实例,其计算表格比上一个实例少一行:

图片

 

得到 v = -3,在F19里面,也就是16。验证:6 * 16 = 96 = 1 + 5*19 ≡ 1 mod 19

 

因此,虽然扩展欧几里得算法具有快速、现成易得的好处,它不应该被用于在SM2的签名算法中计算(1 + dA)-1,否则可能导致私钥的破解。在上一篇文章的最后我们提到,有时候为了避免基于敏感值去作代码分支,除了应用Select方法,我们还可以将算法整体更换掉;现在,我们要使用一个新的算法来进行素域求逆计算。

 

04 费马小定理方法

 

基于费马小定理可以达到常数时间计算素域乘法逆元的目的。我们先来看费马小定理是如何表述的:

如果p为素数,则对任意整数 a 均有:ap ≡ a mod p

附加 a 不是 p 的倍数(即a, p 互素)的条件,并稍稍变换一下形式,就是:

ap-1 ≡ 1 mod p

ap-2 ≡ a-1 mod p

也就是说,要计算 a 在Fp的乘法逆元,只需要计算其 p-2 次方。在SM2的签名算法中,我们可以应用费马小定理计算

(1 + dA)-1 = (1 + dA)n-2 mod n

SM2的规范要求私钥的取值范围为 1 ≤ dA ≤  n-2,因此 1 + dA 不会为零,也不会为 n 的倍数。

同样地,我们可以应用类似DaA的方法来快速计算 n-2 次方:反复计算乘法和平方(Square and Multiply),估计大约需要256次平方运算和128次乘法运算——精确的结果是256次平方(或255次,如果把第一次节省下来)和187次乘法,因为将 n-2 二进制展开后具有很多的1——其十六进制展开前面是一串F(0b1111):

0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54121

我们可以把前面的DaA算法简单改造一下(注意每次平方或乘法后需要做一次求模):

func squareAndMultiply(x, power, mod *big.Int) *big.Int {    out := new(big.Int).SetUint64(1)    for _, bit := range power.bits { //从高位到低位遍历        out.Square(out)        out.Mod(out, mod)        if bit == 1 {            out.Multiply(out, x)            out.Mod(out, mod)        } }    return out}//modInverse(1+dA, n-2, n)给出(1 + dA)^-1

 

这个算法还能不能进一步优化呢?答案是能。由于 n 为SM2所用椭圆曲线的固定参数,还可以进一步预先将 n-2 分解为较为优化的加法链,从而以更低的运算次数达到同样的效果。目前,高能链使用addchain工具(Michael McLoughlin,项目参见:https://github.com/mmcloughlin/addchain)对 n-2 进行分解,仅需计算253次平方和41次乘法,将所需的乘法运算次数降低为原来的约四分之一(41 : 187)。具体代码比较冗长,为程序所生成,这里就不贴了。未来项目开源后,欢迎各位读者关注。以下仅举一简单例子解释addchain工具的优化作用:

bash-3.2$ addchain search 211addchain: expr: "211"addchain: hex: d3addchain: dec: 211addchain: best: opt(dictionary(sliding_window(4),heuristic(use_first(halving,delta_largest))))addchain: cost: 10_10       = 2*1_11       = 1 + _10_1100     = _11 << 2_1101     = 1 + _1100_11010000 = _1101 << 4return      _11 + _11010000

 

总的计算代价是10,分别是7次平方和3次乘法以计算x211

  • 平方得到x2

  • 乘法得到x3

  • 所得结果连续平方两次得到x12

  • 乘法得到x13

  • 所得结果连续平方四次得到x208

  • 乘以之前的x3,得到x211

 

而如果采用Square and Multiply方法,则211在二进制展开后为11010011,需要8次或7次平方,5次乘法,相较而言约高出20%的计算代价。

此外,以上squareAndMultiply函数还有一个问题在于其Mod运算——并非常数时间,效率也较低;因此虽然总体算法是常数时间的,具体实现却未必。高能链在生产应用中,除了使用addchain工具加以改进以外,底层的大数计算也应用了相关的优化技术,以避免非常数时间且代价昂贵的Mod计算。这也是我们在文章中不提供实际代码而只提供伪代码的原因:既是为了删去无关紧要的技术细节,突出算法重点,也是为了避免这些代码被直接应用于生产环境。

 

05 总结

 

素域求逆这个步骤具有一定的计算代价。在高能链的实现中,以上优化过的算法,每次仍然需要消耗大约一万纳秒(在Mac Book Pro M1上实测),约占总的SM2签名时间的18%;而同一测试设备上,扩展欧几里得算法(使用Go的big.Int.ModInverse函数)仅需三千纳秒左右。这是常数时间实现的代价。我们不得不努力在其它方面设法优化,以便最后的签名性能尚能达到较好的水平(实际上,我们在Mac Book Pro M1上小幅超越了谷歌公司BoringSSL的P-256曲线签名性能;而一般来说,由于参数的关系,同等实现技术下SM2具有比P-256更大的计算量。另外,BoringSSL的P-256实现也是常数时间的)。

这是本系列文章关于SM2椭圆曲线算法的最后一篇。关于SM2实现的常数时间技术,到此就介绍完了。在下一篇文章中,我们将探讨SM4算法的常数时间实现。

 

 

往期回顾:

常数时间国密算法(一)

常数时间国密算法(二):SM2的代码分支规避

 

标签:SM2,dA,算法,国密,计算,常数,素域,乘法
From: https://www.cnblogs.com/rsapaper/p/16635790.html

相关文章

  • 二分图最大匹配数量,匈牙利算法求解 python
    二分图最大匹配数量,匈牙利算法求解python,本质上是找增广回路"""#File:hungary.py#Time:2022/8/2821:08#Author:notomato#Description:#"""......
  • 使用 QuickSort 算法解决排序数组
    使用QuickSort算法解决排序数组这里我们将讨论一个案例,如何将一系列数字以随机排列的数组的形式排序,使其成为从最小到最大的数字序列。我们将使用最后一个元素的方法......
  • 考研数据结构与算法(七)图论
    @目录一、图的基本概念1.1图的定义1.2基本术语1.2.1有向图1.2.2无向图1.2.3简单图1.2.4多重图1.2.5完全图1.2.6子图1.2.7连通、连通分量、连通图1.2.8强连通1.2.......
  • 算法总结
    1.序列化与反序列化二叉树序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算......
  • 数据结构和算法的介绍
    声明:此系列以尚硅谷数据结构与算法(Java数据结构与算法)视频为主,包括其他大佬的文章(相关文中有引用注明来源)在此声明一次,后续文档中不再声明。目录数据结构和算法的关系算......
  • 流行的机器学习优化算法
    流行的机器学习优化算法Photoby康尼施耐德on不飞溅机器学习中的优化是在给定一组输入的情况下找到正确预测的迭代过程。在每次迭代中,目标是减少预测值与实际值之......
  • LetCode算法--3.找找两个正序数组的中位数
    给定两个大小分别为m和n的正序(从小到大)数组 nums1和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log(m+n))。来源:力扣(LeetCode......
  • STL中的算法
    参考:传智播客C++课程讲义传智扫地僧前言算法部分主要由头文件<algorithm>,<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个,其中常用到的功能范围......
  • 【算法笔记】一文解决数组类型算法题(1)
    本文主要介绍数据结构中的数组,以及LeetCode题库下面相关题型的分类和解法套路。数组理论概述定义数组是存储在一块连续内存上的,由相同元素集合组成的数据结构。利用索......
  • 哈希算法
    目录什么是哈希算法?哈希算法的应用应用一:安全加密应用二:唯一标识应用三:数据校验应用四:散列函数什么是哈希算法?将任意长度的二进制值串映射为固定长度的二进制值串,这个映......