区块链中的数学 - sm2恢复公钥问题

写在前面

上一节说了基于椭圆曲线的VRF证明验证过程，有朋友反映有些跳跃，说明前面椭圆曲线基础文章还需要在看看，空中楼阁，镜花水月都会给人一种不踏实的感觉。基础打好，才能稳定提升！

之前的文章详细说明了secp256k1公钥恢复和sm2相关内容，依然有很多朋友在咨询sm2的公钥恢复，本来不打算写这方面了，因为有了之前的文章，sm2公钥恢复基本可以照搬，只是一些细节上的不同，这是因为sm2签名过程与secp256k1略有区别造成的。

鉴于很多人关心，本节详细说说！

sm2签名恢复过程

首先sm2可恢复公钥吗？ 答案是肯定的 其次是如何恢复的过程？ 答案是与secp256k1公钥恢复高度相似

之前历史文章sm2签名过程详细说明了签名和验证的过程，本文在此基础上进行更深入说明。所有的符号含义均与之相同，不再重复。

由签名过程：

$s = (1+d_A)^{-1}（k - r d_A ）\ mod\ n$

可得：$s (1+d_A) =（k - r d_A）$ 【注：由于所有运算都有mod ，为了书写方便不再列出】

两边乘以G，

$s (1+d_A) G = sG + sd_AG = sG + sP_A = kG - r d_AG = kG - rP_A$

这里的$P_A$就是要恢复的目标公钥，到此就容易整理得： $P_A= (s+r)^{-1}* (kG - sG)$

k是未知的，令曲线上的点R = kG ， 签名结果中的r就是点R的x坐标（参见签名过程步骤3，4，5可知），于是：

$P_A= (s+r)^{-1}* (R - sG)$

现在问题转化成已知点R的x坐标，求出y坐标， 如前所述（secp256k1公钥恢复文章），得出的y会有两个，一个奇数一个偶数。

在具体代码实现中，会用recId或者v来辨识，这样在签名过程中记下使用公钥奇偶性，在还原时候得到签名所用的公钥。

具体实现

实现sm2的key recover代码基本遵循上述恢复过程：

func recoverKeyFromSignatureSM2(curve P256V1Curve,ee *big.Int, sig *Sm2Signature, msg []byte,
 iter int, doChecks bool) (*PublicKey, error) {
 // 1.1 x = (n * i) + r - e 
 Rx := new(big.Int).Mul(curve.Params().N,
  new(big.Int).SetInt64(int64(iter/2)))
 Rx.Add(Rx, sig.R)
 Rx.Sub(Rx,ee)

 if Rx.Cmp(curve.Params().P) != -1 {
  return nil, errors.New("calculated Rx is larger than curve P")
 }

 // convert 02<Rx> to point R. (step 1.2 and 1.3). If we are on an odd
 // iteration then 1.6 will be done with -R, so we calculate the other
 // term when uncompressing the point.
 Ry, err := decompressPointSM2(curve, Rx, iter%2 == 1)
 if err != nil {
  return nil, err
 }
 // 1.4 Check n*R is point at infinity
 if doChecks {
  nRx, nRy := curve.ScalarMult(Rx, Ry, curve.Params().N.Bytes())
  if nRx.Sign() != 0 || nRy.Sign() != 0 {
   return nil, errors.New("n*R does not equal the point at infinity")
  }
 }

 // 1.5 calculate e from message using the same algorithm as ecdsa
 // signature calculation.
 // e := hashToInt(msg, curve)

 // Step 1.6.1:
 // We calculate the two terms sR and eG separately multiplied by the
 // inverse of r (from the signature). We then add them to calculate
 // Q = (s+r)^-1(R-sG)
 invr := new(big.Int).ModInverse(new(big.Int).Add(sig.S,sig.R), curve.Params().N)
 // first term.
 // invrS := new(big.Int).Mul(invr, sig.S)
 // invrS.Mod(invrS, curve.Params().N)
 sRx, sRy := curve.ScalarMult(Rx, Ry, invr.Bytes())
 s := new(big.Int).Set(sig.S)
 // second term.
 s.Neg(s)
 s.Mod(s, curve.Params().N)
 s.Mul(s, invr)
 s.Mod(s, curve.Params().N)
 minuseGx, minuseGy := curve.ScalarBaseMult(s.Bytes())

 // TODO: this would be faster if we did a mult and add in one
 // step to prevent the jacobian conversion back and forth.
 Qx, Qy := curve.Add(sRx, sRy, minuseGx, minuseGy)
 return &PublicKey{
  Curve: curve,
  X:     Qx,
  Y:     Qy,
 }, nil
}

这是个go语言实现的代码，fork在这里，https://github.com/DreamWuGit/crypto-go/blob/main/gm/sm2/sm2.go 本人没有实际测试过，看起来流程都是对的，但肯定不是最优的，生产环境下慎重使用！如果你发现有什么问题，欢迎分享！

Java语言实现好像还没有现成的，抽时间可以写一个，如果你知道的话，也可以分享下！

小结

本文原计划要讲椭圆曲线中的爱德华曲线，鉴于很多朋友咨询sm2的问题，所以把sm2恢复公钥问题详细说一下，原理跟secp256k1曲线一样，没有什么新的内容，只是细节的变化。不清楚的建议本系列文章23到28篇再看看，下面的“相关阅读”可以方便找到！

高楼大厦平地起，如果地基不扎实，再小的变化也会如雾中月水中花迷失方向！

好了，下一篇再说椭圆曲线类别中的爱德华曲线（Edwards curve）！

欢迎关注公众号：blocksight

相关阅读：

区块链中的数学 - 基于椭圆曲线的VRF证明验证过程

区块链中的数学 - 基于椭圆曲线的VRF证明生成

区块链中的数学 - 基于RSA的VRF实现

区块链中的数学 - VRF（随机可验证函数）概述

区块链中的数学 - secp256k1公钥恢复原理

区块链中的数学 - secp256k1公钥恢复实现）

区块链中的数学 - sm2签名与验证

区块链中的数学 - Uniwap核心算法解析（下）

区块链中的数学 - Uniwap核心算法解析（中）