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

回到在这篇公钥恢复的文章,讲了secp256k1曲线根据签名结果反推公钥的原理,本篇在这个基础上继续说实现的部分。

## 写在前面 上一节讲了[Cipolla算法补充说明](https://learnblockchain.cn/article/1518),我们知道了一种求解二次剩余根的方法。 回到在[这篇](https://learnblockchain.cn/article/1526)公钥恢复的文章,讲了secp256k1曲线根据签名结果反推公钥的原理,本篇在这个基础上继续说实现的部分。 本篇假定熟悉签名过程等之前内容,不行自补!否则不易理解。 ## 可能的公钥数量 根据secp256k1曲线根据[签名过程](https://learnblockchain.cn/article/1551),计算点𝑘𝐺,其𝑋坐标(整数模𝑝,因此在0到𝑝−1范围内)被约化模𝑛,从而得到一个介于0和𝑛−1之间的值。结果是𝑟。由于𝑛略低于𝑝(由[secp256k1曲线参数](https://learnblockchain.cn/article/1526)可得),因此可以有两个值𝑋与𝑟匹配。一般来说只有一个,但是如果 𝑟 < 𝑝-𝑛 ,那么就会有两个。 对于每个可能的坐标𝑋,可以有两个对应的点。这一点容易从曲线曲线方程得到: $y^2 \equiv x^3 +ax +b$ 因此,如果(𝑋,𝑌)是曲线上的一个点,那么(𝑋,−𝑌)也是曲线上的一个点,并且具有相同的坐标𝑋。 综合可得:从值𝑟(在签名中),可以有两个候选的𝑋坐标𝑃,并且从每个这样的候每个坐标,可以有两个匹配点。总共可以有四个曲线点𝑃与签名中的𝑟值匹配。 对于它们中的每一个,都可以计算相应的公钥𝑄。但请注意,单个𝑟坐标有两个可能的情况是非常罕见的; 事实上,这可能是随机发生的,出现概率大约为 $ 2^{-128}$。换句话说,在实践中从未发生过(尽管可以使用精心编制的数据强制构造来执行)。 因此,通常可以期望恢复出两个公钥,但是必须知道(至少在理论上)可能会得到四个。 纸上得来终觉浅,下面看下具体处理过程。 ## 实现过程 由于已经知道总共可能得到四个公钥,在原始签名的过程中,加上额外处理:**找到公钥恢复的过程对应的索引,记为recId,附加到签名中**。 在接收者验证过程中直接使用记为recId进行恢复,从而进一步验证签名合法性。 下面列出支持公钥恢复的签名实现片段(代码PC端查看): “` public ECDSASignature sign(byte[] messageHash) { ECDSASignature sig = doSign(messageHash); // Now we have to work backwards to figure out the recId needed to recover the signature. int recId = -1; byte[] thisKey = this.pub.getEncoded(false); // {1.1. Let x = r + jn ……… int h = 4; // h means how many possible point we can get. from 𝑟 (in the signature),, for (int i = 0; i < h; i++) { byte[] k = ECKey.recoverPubBytesFromSignature(i, sig, messageHash); if (k != null && Arrays.equals(k, thisKey)) { recId = i; break; } } if (recId == -1) { throw new RuntimeException( “Could not construct a recoverable key. This should never happen.”); } ** sig.v = (byte) (recId + ECDSASignature.vBase);** return sig; } “` 恢复过程根据[公钥恢复原理](https://learnblockchain.cn/article/1526)进行,英文链接参考: https://www.secg.org/sec1-v2.pdf 主要代码片段: “` byte[] recoverPubBytesFromSignature(int recId, ECDSASignature sig, byte[] messageHash) { // omit params validation BigInteger n = CURVE.getN(); // Curve order. BigInteger i = BigInteger.valueOf((long) recId / 2); BigInteger x = sig.r.add(i.multiply(n)); ECCurve.Fp curve = (ECCurve.Fp) CURVE.getCurve(); BigInteger prime = curve.getQ(); // Bouncy Castle is not consistent about the letter it uses for the prime. if (x.compareTo(prime) >= 0) { // Cannot have point co-ordinates larger than this as everything takes place // modulo Q. return null; } // Compressed keys require you to know an extra bit of data about the y-coord as // there are two possibilities. // So it’s encoded in the recId. ECPoint R = decompressKey(x, (recId & 1) == 1); // 1.4. If nR != point at infinity, then do another iteration of Step 1 (callers // responsibility). if (!R.multiply(n).isInfinity()) return null; // 1.5. Compute e from M using Steps 2 and 3 of ECDSA signature verification. BigInteger e = new BigInteger(1, messageHash); BigInteger eInv = BigInteger.ZERO.subtract(e).mod(n); BigInteger rInv = sig.r.modInverse(n); BigInteger srInv = rInv.multiply(sig.s).mod(n); BigInteger eInvrInv = rInv.multiply(eInv).mod(n); ECPoint.Fp q = (ECPoint.Fp) ECAlgorithms.sumOfTwoMultiplies(CURVE.getG(), eInvrInv, R, srInv); return q.getEncoded(false); } “` 基本上是按照之前文章公钥恢复推导的过程来实现的。 ## 小结 Cipolla算法是一般性求解二次剩余的方法,具体到secp256k1,我们利用其曲线和签名特性可以使用更针对性的高效方法来解决。到此,secp256k1公钥恢复主题相关内容从理论到实践描述完毕。 最近几篇文章的思路: secp256k1公钥恢复–>二次剩余–>原根–> 二次剩余求解 –> Cipolla算法补充说明–>secp256k1公钥恢复实现 已形成闭环!从下一篇起讲下[基于椭圆曲线的密钥交换和国密sm2等算法](https://learnblockchain.cn/article/1516)。 — 欢迎关注公众号:blocksight

写在前面

上一节讲了Cipolla算法补充说明,我们知道了一种求解二次剩余根的方法。

回到在这篇公钥恢复的文章,讲了secp256k1曲线根据签名结果反推公钥的原理,本篇在这个基础上继续说实现的部分。

本篇假定熟悉签名过程等之前内容,不行自补!否则不易理解。

可能的公钥数量

根据secp256k1曲线根据签名过程,计算点𝑘𝐺,其𝑋坐标(整数模𝑝,因此在0到𝑝−1范围内)被约化模𝑛,从而得到一个介于0和𝑛−1之间的值。结果是𝑟。由于𝑛略低于𝑝(由secp256k1曲线参数可得),因此可以有两个值𝑋与𝑟匹配。一般来说只有一个,但是如果 𝑟 < 𝑝-𝑛 ,那么就会有两个。

对于每个可能的坐标𝑋,可以有两个对应的点。这一点容易从曲线曲线方程得到: $y^2 \equiv x^3 +ax +b$

因此,如果(𝑋,𝑌)是曲线上的一个点,那么(𝑋,−𝑌)也是曲线上的一个点,并且具有相同的坐标𝑋。

综合可得:从值𝑟(在签名中),可以有两个候选的𝑋坐标𝑃,并且从每个这样的候每个坐标,可以有两个匹配点。总共可以有四个曲线点𝑃与签名中的𝑟值匹配。 对于它们中的每一个,都可以计算相应的公钥𝑄。但请注意,单个𝑟坐标有两个可能的情况是非常罕见的;

事实上,这可能是随机发生的,出现概率大约为 $ 2^{-128}$。换句话说,在实践中从未发生过(尽管可以使用精心编制的数据强制构造来执行)。 因此,通常可以期望恢复出两个公钥,但是必须知道(至少在理论上)可能会得到四个。

纸上得来终觉浅,下面看下具体处理过程。

实现过程

由于已经知道总共可能得到四个公钥,在原始签名的过程中,加上额外处理:找到公钥恢复的过程对应的索引,记为recId,附加到签名中

在接收者验证过程中直接使用记为recId进行恢复,从而进一步验证签名合法性。 下面列出支持公钥恢复的签名实现片段(代码PC端查看):

public ECDSASignature sign(byte[] messageHash) {
    ECDSASignature sig = doSign(messageHash);
    // Now we have to work backwards to figure out the recId needed to recover the signature.
    int recId = -1;
    byte[] thisKey = this.pub.getEncoded(false);
    // {1.1. Let x = r + jn  .........
    int h = 4;
    // h means how many possible point we can get. from 𝑟 (in the signature),,
    for (int i = 0; i < h; i++) {
      byte[] k = ECKey.recoverPubBytesFromSignature(i, sig, messageHash);
      if (k != null && Arrays.equals(k, thisKey)) {
        recId = i;
        break;
      }
    }
    if (recId == -1) {
      throw new RuntimeException(
          "Could not construct a recoverable key. This should never happen.");
    }
   ** sig.v = (byte) (recId + ECDSASignature.vBase);**
    return sig;
  }

恢复过程根据公钥恢复原理进行,英文链接参考: https://www.secg.org/sec1-v2.pdf 主要代码片段:

byte[] recoverPubBytesFromSignature(int recId, ECDSASignature sig, byte[] messageHash) {
      // omit params validation
        BigInteger n = CURVE.getN(); // Curve order.
        BigInteger i = BigInteger.valueOf((long) recId / 2);
        BigInteger x = sig.r.add(i.multiply(n));
        ECCurve.Fp curve = (ECCurve.Fp) CURVE.getCurve();
        BigInteger prime = curve.getQ(); // Bouncy Castle is not consistent about the letter it uses for the prime.
        if (x.compareTo(prime) >= 0) {
            // Cannot have point co-ordinates larger than this as everything takes place
            // modulo Q.
            return null;
        }
        // Compressed keys require you to know an extra bit of data about the y-coord as
        // there are two possibilities.
        // So it's encoded in the recId.
        ECPoint R = decompressKey(x, (recId & 1) == 1);
        // 1.4. If nR != point at infinity, then do another iteration of Step 1 (callers
        // responsibility).
        if (!R.multiply(n).isInfinity())
            return null;
        // 1.5. Compute e from M using Steps 2 and 3 of ECDSA signature verification.
        BigInteger e = new BigInteger(1, messageHash);      
        BigInteger eInv = BigInteger.ZERO.subtract(e).mod(n);
        BigInteger rInv = sig.r.modInverse(n);
        BigInteger srInv = rInv.multiply(sig.s).mod(n);
        BigInteger eInvrInv = rInv.multiply(eInv).mod(n);
        ECPoint.Fp q = (ECPoint.Fp) ECAlgorithms.sumOfTwoMultiplies(CURVE.getG(), eInvrInv, R, srInv);
        return q.getEncoded(false);
    }

基本上是按照之前文章公钥恢复推导的过程来实现的。

小结

Cipolla算法是一般性求解二次剩余的方法,具体到secp256k1,我们利用其曲线和签名特性可以使用更针对性的高效方法来解决。到此,secp256k1公钥恢复主题相关内容从理论到实践描述完毕。

最近几篇文章的思路: secp256k1公钥恢复–>二次剩余–>原根–> 二次剩余求解 –> Cipolla算法补充说明–>secp256k1公钥恢复实现

已形成闭环!从下一篇起讲下基于椭圆曲线的密钥交换和国密sm2等算法

欢迎关注公众号:blocksight

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-08-10 17:52
  • 阅读 ( 97 )
  • 学分 ( 6 )
  • 分类:入门/理论

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/27820

联系我们

aliyinhang@gmail.com