Подтвердить что ты не робот

Как получить открытый ключ ECDSA только под подписью Bitcoin?... SEC1 4.1.6 восстановление ключа для кривых над (mod p) -полями

Обновление: Частичное решение доступно на Git

EDIT: скомпилированная версия этого доступна в https://github.com/makerofthings7/Bitcoin-MessageSignerVerifier

Обратите внимание, что сообщение, которое должно быть проверено, должно иметь Bitcoin Signed Message:\n в качестве префикса. Source1 Источник2

В реализации С# что-то не так, что я, вероятно, могу исправить из эту реализацию Python


Кажется, что проблема связана с правильным адресом базы 58.

У меня есть следующее сообщение, подпись и адрес Base58 ниже. Я намерен извлечь ключ из подписи, использовать этот ключ и сравнить хэши Base58.

Моя проблема: как извлечь ключ из подписи? (Edit Я нашел код С++ в нижней части этой записи, нужно это в Bouncy Castle/или С#)

Сообщение

StackOverflow test 123

Подпись

IB7XjSi9TdBbB3dVUK4+Uzqf2Pqk71XkZ5PUsVUN+2gnb3TaZWJwWW2jt0OjhHc4B++yYYRy1Lg2kl+WaiF+Xsc=

Base58 Биткойн адрес "хэш"

1Kb76YK9a4mhrif766m321AMocNvzeQxqV

Поскольку адрес Bitcoin Base58 - это всего лишь хеш, я не могу использовать его для проверки сообщения Bitcoin. Тем не менее, можно извлечь открытый ключ из подписи.

Изменить: я подчеркиваю, что я получаю открытый ключ из самой подписи, а не из хэша открытого ключа Base58. Если я хочу (и я действительно хочу), я должен иметь возможность преобразовывать эти биты открытого ключа в хэш-таблицу Base58. Мне не нужна помощь в этом, мне просто нужна помощь в извлечении бит открытого ключа и проверке подписи.

Вопрос

  • В подписи выше, в каком формате находится эта подпись? PKCS10? (Ответ: нет, он проприетарно как описано здесь)

  • Как извлечь открытый ключ в Bouncy Castle?

  • Каков правильный способ проверки подписи? (предположим, что я уже знаю, как преобразовать бит открытого ключа в хеш, который равен хэшу биткойна выше)

Предыдущие исследования

Эта ссылка описывает, как использовать кривые ECDSA, и следующий код позволит мне преобразовать открытый ключ в объект BC, но Я не уверен, как получить точку Q от подписи.

В приведенном ниже примере Q - твердое кодированное значение

  Org.BouncyCastle.Asn1.X9.X9ECParameters ecp = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
  ECDomainParameters params = new ECDomainParameters(ecp.Curve, ecp.G, ecp.N, ecp.H);
  ECPublicKeySpec pubKeySpec = new ECPublicKeySpec(
  ecp .curve.decodePoint(Hex.decode("045894609CCECF9A92533F630DE713A958E96C97CCB8F5ABB5A688A238DEED6DC2D9D0C94EBFB7D526BA6A61764175B99CB6011E2047F9F067293F57F5")), // Q
        params);
  PublicKey  pubKey = f.generatePublic(pubKeySpec);


 var signer = SignerUtilities.GetSigner("ECDSA"); // possibly similar to SHA-1withECDSA
 signer.Init(false, pubKey);
 signer.BlockUpdate(plainTextAsBytes, 0, plainTextAsBytes.Length);
 return signer.VerifySignature(signature);

Дополнительные исследования:

ЭТО является источником биткойнов, который проверяет сообщение.

После декодирования Base64 подписи вызывается RecoverCompact (хэш сообщения, подпись). Я не программист на С++, поэтому я предполагаю, что мне нужно выяснить, как работает key.Recover. Это или key.GetPubKey

Это код на С++, который, как мне кажется, мне нужен в С#, в идеале в надуманном замке... но я возьму все, что работает.

// reconstruct public key from a compact signature
// This is only slightly more CPU intensive than just verifying it.
// If this function succeeds, the recovered public key is guaranteed to be valid
// (the signature is a valid signature of the given data for that key)
bool Recover(const uint256 &hash, const unsigned char *p64, int rec)
{
    if (rec<0 || rec>=3)
        return false;
    ECDSA_SIG *sig = ECDSA_SIG_new();
    BN_bin2bn(&p64[0],  32, sig->r);
    BN_bin2bn(&p64[32], 32, sig->s);
    bool ret = ECDSA_SIG_recover_key_GFp(pkey, sig, (unsigned char*)&hash, sizeof(hash), rec, 0) == 1;
    ECDSA_SIG_free(sig);
    return ret;
}

... код ECDSA_SIG_recover_key_GFp здесь

Формат пользовательской подписи в биткойне

В этом ответе говорится, что есть 4 возможных открытых ключа, которые могут создавать подпись, и это закодировано в новых подписях.

4b9b3361

Ответ 1

После ссылки на BitcoinJ, кажется, что некоторые из этих образцов кода не содержат правильной подготовки сообщения, хэширования с двумя SHA256 и возможного сжатого кодирования восстановленной общедоступной точки, которая вводится в вычисление адреса.

В следующем коде должен быть только BouncyCastle (возможно, вам понадобится последняя версия из github, не уверен). Он заимствует несколько вещей из BitcoinJ и делает достаточно, чтобы работать с небольшими примерами, см. Встроенные комментарии для ограничений размера сообщения.

Он вычисляет только до хеша RIPEMD-160, и я использовал http://gobittest.appspot.com/Address, чтобы проверить окончательный адрес, который приводит (к сожалению, этот веб-сайт похоже, не поддерживает ввод сжатого кодирования для открытого ключа).

    public static void CheckSignedMessage(string message, string sig64)
    {
        byte[] sigBytes = Convert.FromBase64String(sig64);
        byte[] msgBytes = FormatMessageForSigning(message);

        int first = (sigBytes[0] - 27);
        bool comp = (first & 4) != 0;
        int rec = first & 3;

        BigInteger[] sig = ParseSig(sigBytes, 1);
        byte[] msgHash = DigestUtilities.CalculateDigest("SHA-256", DigestUtilities.CalculateDigest("SHA-256", msgBytes));

        ECPoint Q = Recover(msgHash, sig, rec, true);

        byte[] qEnc = Q.GetEncoded(comp);
        Console.WriteLine("Q: " + Hex.ToHexString(qEnc));

        byte[] qHash = DigestUtilities.CalculateDigest("RIPEMD-160", DigestUtilities.CalculateDigest("SHA-256", qEnc));
        Console.WriteLine("RIPEMD-160(SHA-256(Q)): " + Hex.ToHexString(qHash));

        Console.WriteLine("Signature verified correctly: " + VerifySignature(Q, msgHash, sig));
    }

    public static BigInteger[] ParseSig(byte[] sigBytes, int sigOff)
    {
        BigInteger r = new BigInteger(1, sigBytes, sigOff, 32);
        BigInteger s = new BigInteger(1, sigBytes, sigOff + 32, 32);
        return new BigInteger[] { r, s };
    }

    public static ECPoint Recover(byte[] hash, BigInteger[] sig, int recid, bool check)
    {
        X9ECParameters x9 = SecNamedCurves.GetByName("secp256k1");

        BigInteger r = sig[0], s = sig[1];

        FpCurve curve = x9.Curve as FpCurve;
        BigInteger order = x9.N;

        BigInteger x = r;
        if ((recid & 2) != 0)
        {
            x = x.Add(order);
        }

        if (x.CompareTo(curve.Q) >= 0) throw new Exception("X too large");

        byte[] xEnc = X9IntegerConverter.IntegerToBytes(x, X9IntegerConverter.GetByteLength(curve));

        byte[] compEncoding = new byte[xEnc.Length + 1];
        compEncoding[0] = (byte)(0x02 + (recid & 1));
        xEnc.CopyTo(compEncoding, 1);
        ECPoint R = x9.Curve.DecodePoint(compEncoding);

        if (check)
        {
            //EC_POINT_mul(group, O, NULL, R, order, ctx))
            ECPoint O = R.Multiply(order);
            if (!O.IsInfinity) throw new Exception("Check failed");
        }

        BigInteger e = CalculateE(order, hash);

        BigInteger rInv = r.ModInverse(order);
        BigInteger srInv = s.Multiply(rInv).Mod(order);
        BigInteger erInv = e.Multiply(rInv).Mod(order);

        return ECAlgorithms.SumOfTwoMultiplies(R, srInv, x9.G.Negate(), erInv);
    }

    public static bool VerifySignature(ECPoint Q, byte[] hash, BigInteger[] sig)
    {
        X9ECParameters x9 = SecNamedCurves.GetByName("secp256k1");
        ECDomainParameters ec = new ECDomainParameters(x9.Curve, x9.G, x9.N, x9.H, x9.GetSeed());
        ECPublicKeyParameters publicKey = new ECPublicKeyParameters(Q, ec);
        return VerifySignature(publicKey, hash, sig);
    }

    public static bool VerifySignature(ECPublicKeyParameters publicKey, byte[] hash, BigInteger[] sig)
    {
        ECDsaSigner signer = new ECDsaSigner();
        signer.Init(false, publicKey);
        return signer.VerifySignature(hash, sig[0], sig[1]);
    }

    private static BigInteger CalculateE(
        BigInteger n,
        byte[] message)
    {
        int messageBitLength = message.Length * 8;
        BigInteger trunc = new BigInteger(1, message);

        if (n.BitLength < messageBitLength)
        {
            trunc = trunc.ShiftRight(messageBitLength - n.BitLength);
        }

        return trunc;
    }

    public static byte[] FormatMessageForSigning(String message)
    {
        MemoryStream bos = new MemoryStream();
        bos.WriteByte((byte)BITCOIN_SIGNED_MESSAGE_HEADER_BYTES.Length);
        bos.Write(BITCOIN_SIGNED_MESSAGE_HEADER_BYTES, 0, BITCOIN_SIGNED_MESSAGE_HEADER_BYTES.Length);
        byte[] messageBytes = Encoding.UTF8.GetBytes(message);

        //VarInt size = new VarInt(messageBytes.length);
        //bos.write(size.encode());
        // HACK only works for short messages (< 253 bytes)
        bos.WriteByte((byte)messageBytes.Length);

        bos.Write(messageBytes, 0, messageBytes.Length);
        return bos.ToArray();
    }

Пример вывода для исходных данных в вопросе:

Q: 0283437893b491218348bf5ff149325e47eb628ce36f73a1a927ae6cb6021c7ac4
RIPEMD-160(SHA-256(Q)): cbe57ebe20ad59518d14926f8ab47fecc984af49
Signature verified correctly: True

Если мы вставим значение RIPEMD-160 в адресную проверку, он вернет

1Kb76YK9a4mhrif766m321AMocNvzeQxqV

как указано в вопросе.

Ответ 2

Я боюсь, что есть некоторые проблемы с вашими примерными данными. Прежде всего, ваш образец Q имеет длину 61 байт, но открытые ключи биткойна (с использованием кривой secp256k1) должны быть 65 байтов в их несжатой форме. Q, который вы предоставили, не проверяет сообщение правильно, но Q, который я вычислил, похоже, проверяет его.

Я написал код, который вычисляет правильный открытый ключ для строки "StackOverflow test 123" и проверяет его с помощью ECDsaSigner. Однако хэш для этого открытого ключа 1HRDe7G7tn925iNxQaeD7R2ZkZiKowN8NW вместо 1Kb76YK9a4mhrif766m321AMocNvzeQxqV.

Не могли бы вы убедиться, что ваши данные верны и, возможно, дают точный хэш строки сообщений, чтобы мы могли попытаться отладить, неправильный хэш может испортить ситуацию довольно плохо. Код, который я использовал, следующий:

using System;
using System.Text;
using System.Security.Cryptography;

using Org.BouncyCastle.Math;
using Org.BouncyCastle.Math.EC;
using Org.BouncyCastle.Asn1.X9;
using Org.BouncyCastle.Crypto.Signers;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Utilities.Encoders;

public class Bitcoin
{
  public static ECPoint Recover(byte[] hash, byte[] sigBytes, int rec)
  {
    BigInteger r = new BigInteger(1, sigBytes, 0, 32);
    BigInteger s = new BigInteger(1, sigBytes, 32, 32);
    BigInteger[] sig = new BigInteger[]{ r, s };
    ECPoint Q = ECDSA_SIG_recover_key_GFp(sig, hash, rec, true);
    return Q;
  }

  public static ECPoint ECDSA_SIG_recover_key_GFp(BigInteger[] sig, byte[] hash, int recid, bool check)
  {
    X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    int i = recid / 2;

    Console.WriteLine("r: "+ToHex(sig[0].ToByteArrayUnsigned()));
    Console.WriteLine("s: "+ToHex(sig[1].ToByteArrayUnsigned()));

    BigInteger order = ecParams.N;
    BigInteger field = (ecParams.Curve as FpCurve).Q;
    BigInteger x = order.Multiply(new BigInteger(i.ToString())).Add(sig[0]);
    if (x.CompareTo(field) >= 0) throw new Exception("X too large");

    Console.WriteLine("Order: "+ToHex(order.ToByteArrayUnsigned()));
    Console.WriteLine("Field: "+ToHex(field.ToByteArrayUnsigned()));

    byte[] compressedPoint = new Byte[x.ToByteArrayUnsigned().Length+1];
    compressedPoint[0] = (byte) (0x02+(recid%2));
    Buffer.BlockCopy(x.ToByteArrayUnsigned(), 0, compressedPoint, 1, compressedPoint.Length-1);
    ECPoint R = ecParams.Curve.DecodePoint(compressedPoint);

    Console.WriteLine("R: "+ToHex(R.GetEncoded()));

    if (check)
    {
      ECPoint O = R.Multiply(order);
      if (!O.IsInfinity) throw new Exception("Check failed");
    }

    int n = (ecParams.Curve as FpCurve).Q.ToByteArrayUnsigned().Length*8;
    BigInteger e = new BigInteger(1, hash);
    if (8*hash.Length > n)
    {
      e = e.ShiftRight(8-(n & 7));
    }
    e = BigInteger.Zero.Subtract(e).Mod(order);
    BigInteger rr = sig[0].ModInverse(order);
    BigInteger sor = sig[1].Multiply(rr).Mod(order);
    BigInteger eor = e.Multiply(rr).Mod(order);
    ECPoint Q = ecParams.G.Multiply(eor).Add(R.Multiply(sor));

    Console.WriteLine("n: "+n);
    Console.WriteLine("e: "+ToHex(e.ToByteArrayUnsigned()));
    Console.WriteLine("rr: "+ToHex(rr.ToByteArrayUnsigned()));
    Console.WriteLine("sor: "+ToHex(sor.ToByteArrayUnsigned()));
    Console.WriteLine("eor: "+ToHex(eor.ToByteArrayUnsigned()));
    Console.WriteLine("Q: "+ToHex(Q.GetEncoded()));

    return Q;
  }

  public static bool VerifySignature(byte[] pubkey, byte[] hash, byte[] sigBytes)
  {
    X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    ECDomainParameters domainParameters = new ECDomainParameters(ecParams.Curve,
                                                                 ecParams.G, ecParams.N, ecParams.H,
                                                                 ecParams.GetSeed());

    BigInteger r = new BigInteger(1, sigBytes, 0, 32);
    BigInteger s = new BigInteger(1, sigBytes, 32, 32);
    ECPublicKeyParameters publicKey = new ECPublicKeyParameters(ecParams.Curve.DecodePoint(pubkey), domainParameters);

    ECDsaSigner signer = new ECDsaSigner();
    signer.Init(false, publicKey);
    return signer.VerifySignature(hash, r, s);
  }



  public static void Main()
  {
    string msg = "StackOverflow test 123";
    string sig = "IB7XjSi9TdBbB3dVUK4+Uzqf2Pqk71XkZ5PUsVUN+2gnb3TaZWJwWW2jt0OjhHc4B++yYYRy1Lg2kl+WaiF+Xsc=";
    string pubkey = "045894609CCECF9A92533F630DE713A958E96C97CCB8F5ABB5A688A238DEED6DC2D9D0C94EBFB7D526BA6A61764175B99CB6011E2047F9F067293F57F5";

    SHA256Managed sha256 = new SHA256Managed();
    byte[] hash = sha256.ComputeHash(Encoding.UTF8.GetBytes(msg), 0, Encoding.UTF8.GetByteCount(msg));
    Console.WriteLine("Hash: "+ToHex(hash));

    byte[] tmpBytes = Convert.FromBase64String(sig);
    byte[] sigBytes = new byte[tmpBytes.Length-1];
    Buffer.BlockCopy(tmpBytes, 1, sigBytes, 0, sigBytes.Length);

    int rec = (tmpBytes[0] - 27) & ~4;
    Console.WriteLine("Rec {0}", rec);

    ECPoint Q = Recover(hash, sigBytes, rec);
    string qstr = ToHex(Q.GetEncoded());
    Console.WriteLine("Q is same as supplied: "+qstr.Equals(pubkey));

    Console.WriteLine("Signature verified correctly: "+VerifySignature(Q.GetEncoded(), hash, sigBytes));
  }

  public static string ToHex(byte[] data)
  {
    return BitConverter.ToString(data).Replace("-","");
  }
}

ИЗМЕНИТЬ Я вижу, что это все еще не прокомментировано или принято, поэтому я написал полный тест, который генерирует закрытый ключ и открытый ключ, а затем генерирует действительную подпись с использованием закрытого ключа. После этого он восстанавливает открытый ключ из сигнатуры и хэша и использует этот открытый ключ для проверки подписи сообщения. Пожалуйста, см. Ниже, если есть еще некоторые вопросы, пожалуйста, дайте мне знать.

  public static void FullSignatureTest(byte[] hash)
  {
    X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    ECDomainParameters domainParameters = new ECDomainParameters(ecParams.Curve,
                                                                 ecParams.G, ecParams.N, ecParams.H,
                                                                 ecParams.GetSeed());
    ECKeyGenerationParameters keyGenParams =
      new ECKeyGenerationParameters(domainParameters, new SecureRandom());

    AsymmetricCipherKeyPair keyPair;
    ECKeyPairGenerator generator = new ECKeyPairGenerator();
    generator.Init(keyGenParams);
    keyPair = generator.GenerateKeyPair();

    ECPrivateKeyParameters privateKey = (ECPrivateKeyParameters) keyPair.Private;
    ECPublicKeyParameters publicKey = (ECPublicKeyParameters) keyPair.Public;

    Console.WriteLine("Generated private key: " + ToHex(privateKey.D.ToByteArrayUnsigned()));
    Console.WriteLine("Generated public key: " + ToHex(publicKey.Q.GetEncoded()));

    ECDsaSigner signer = new ECDsaSigner();
    signer.Init(true, privateKey);
    BigInteger[] sig = signer.GenerateSignature(hash);

    int recid = -1;
    for (int rec=0; rec<4; rec++) {
      try
      {
        ECPoint Q = ECDSA_SIG_recover_key_GFp(sig, hash, rec, true);
        if (ToHex(publicKey.Q.GetEncoded()).Equals(ToHex(Q.GetEncoded())))
        {
          recid = rec;
          break;
        }
      }
      catch (Exception)
      {
        continue;
      }
    }
    if (recid < 0) throw new Exception("Did not find proper recid");

    byte[] fullSigBytes = new byte[65];
    fullSigBytes[0] = (byte) (27+recid);
    Buffer.BlockCopy(sig[0].ToByteArrayUnsigned(), 0, fullSigBytes, 1, 32);
    Buffer.BlockCopy(sig[1].ToByteArrayUnsigned(), 0, fullSigBytes, 33, 32);

    Console.WriteLine("Generated full signature: " + Convert.ToBase64String(fullSigBytes));

    byte[] sigBytes = new byte[64];
    Buffer.BlockCopy(sig[0].ToByteArrayUnsigned(), 0, sigBytes, 0, 32);
    Buffer.BlockCopy(sig[1].ToByteArrayUnsigned(), 0, sigBytes, 32, 32);

    ECPoint genQ = ECDSA_SIG_recover_key_GFp(sig, hash, recid, false);
    Console.WriteLine("Generated signature verifies: " + VerifySignature(genQ.GetEncoded(), hash, sigBytes));
  }