写在前面

上一节讲了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