区块链中的数学 – sm2恢复公钥问题
本文原计划要讲椭圆曲线中的爱德华曲线,鉴于很多朋友咨询sm2的问题,所以把sm2恢复公钥问题详细说一下,原理跟secp256k1曲线一样,没有什么新的内容,只是细节的变化。
## 写在前面 上一节说了[基于椭圆曲线的VRF证明验证过程](https://learnblockchain.cn/article/1582),有朋友反映有些跳跃,说明前面椭圆曲线基础文章还需要在看看,空中楼阁,镜花水月都会给人一种不踏实的感觉。基础打好,才能稳定提升! 之前的文章详细说明了secp256k1公钥恢复和sm2相关内容,依然有很多朋友在咨询sm2的公钥恢复,本来不打算写这方面了,因为有了之前的文章,sm2公钥恢复基本可以照搬,只是一些细节上的不同,这是因为sm2签名过程与secp256k1略有区别造成的。 鉴于很多人关心,本节详细说说! ## sm2签名恢复过程 首先sm2可恢复公钥吗? 答案是肯定的 其次是如何恢复的过程? 答案是与secp256k1公钥恢复高度相似 之前历史文章[sm2签名过程](https://learnblockchain.cn/article/1507)详细说明了签名和验证的过程,本文在此基础上进行更深入说明。所有的符号含义均与之相同,不再重复。 由签名过程: $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)](https://learnblockchain.cn/article/1610)! 欢迎关注公众号:blocksight ### 相关阅读: [区块链中的数学 - 基于椭圆曲线的VRF证明验证过程](https://learnblockchain.cn/article/1582) [区块链中的数学 - 基于椭圆曲线的VRF证明生成](https://learnblockchain.cn/article/1545) [区块链中的数学 - 基于RSA的VRF实现](https://learnblockchain.cn/article/1544) [区块链中的数学 - VRF(随机可验证函数)概述](https://learnblockchain.cn/article/1543) [区块链中的数学 - secp256k1公钥恢复原理](https://learnblockchain.cn/article/1526) [区块链中的数学 - secp256k1公钥恢复实现](https://learnblockchain.cn/article/1517)) [区块链中的数学 - sm2签名与验证](https://learnblockchain.cn/article/1507) [区块链中的数学 - Uniwap核心算法解析(下)](https://learnblockchain.cn/article/1521) [区块链中的数学 - Uniwap核心算法解析(中)](https://learnblockchain.cn/article/1494)
写在前面
上一节说了基于椭圆曲线的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核心算法解析(中)
区块链技术网。
- 发表于 2020-10-17 12:33
- 阅读 ( 1361 )
- 学分 ( 39 )
- 分类:入门/理论
评论