c# - privadas - ¿Cómo obtengo una clave pública ECDSA de solo una firma de Bitcoin?... Recuperación de la clave SEC1 4.1.6 para curvas sobre campos(mod p)

ecdsa algoritmo

Question

Actualización: solución parcial disponible en Git

EDITAR: una versión compilada de esto está disponible en https://github.com/makerofthings7/Bitcoin-MessageSignerVerifier

Tenga en cuenta que el mensaje que se debe verificar debe tener Bitcoin Signed Message:/n como prefijo. Fuente1 Fuente2

Hay algo mal en la implementación de C # que probablemente pueda corregir de esta implementación de Python

Parece tener un problema con la búsqueda de la dirección correcta de Base 58.

Tengo el siguiente mensaje, firma y dirección Base58 a continuación. Tengo la intención de extraer la clave de la firma, hash esa clave y comparar los hashe Base58.

Mi problema es: ¿cómo extraigo la clave de la firma? (Editar Encontré el código de C ++ en la parte inferior de esta publicación, lo necesito en Bouncy Castle / o C #)

Mensaje

StackOverflow test 123

Firma

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

Base58 Bitcoin dirección "hash"

1Kb76YK9a4mhrif766m321AMocNvzeQxqV

Como la dirección de Base58 Bitcoin es solo un hash, no puedo usarlo para la validación de un mensaje de Bitcoin. Sin embargo, es posible extraer la clave pública de una firma.

Editar: estoy enfatizando que estoy derivando la clave pública de la firma en sí, y no del hash de clave pública Base58. Si quiero (y de hecho quiero) debería ser capaz de convertir estos bits de clave pública en el hash Base58. No necesito ayuda para hacerlo, solo necesito ayuda para extraer las claves públicas y verificar la firma.

Pregunta

1. En la Firma anterior, ¿en qué formato está esta firma? PKCS10? (Respuesta: no, es propiedad como se describe aquí )

2. ¿Cómo extraigo la clave pública en Bouncy Castle?

3. ¿Cuál es la forma correcta de verificar la firma? (Supongamos que ya sé cómo convertir los bits de clave pública en un hash que es igual al hash de Bitcoin anterior)

Investigaciones anteriores

Este enlace describe cómo usar las curvas ECDSA, y el siguiente código me permitirá convertir una clave pública en un objeto BC, pero no estoy seguro de cómo obtener el punto Q de la firma.

En el ejemplo a continuación, Q es el valor codificado

  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);

Investigación adicional:

ESTA es la fuente de Bitcoin que verifica un mensaje.

Después de decodificar Base64 de la firma, se llama RecoverCompact (hash de mensaje, firma) . No soy un programador de C ++, así que supongo que necesito descubrir cómo funciona la key.Recover . La key.Recover funciona. Esa o key.GetPubKey

Este es el código C ++ que creo que necesito en C #, idealmente en castillo hinchable ... pero tomaré todo lo que funcione.

// 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;
}

... el código para ECDSA_SIG_recover_key_GFp está aquí

Formato de firma personalizada en Bitcoin

Esta respuesta dice que hay 4 claves públicas posibles que pueden producir una firma, y ​​esto está codificado en las firmas más nuevas.

Answer 1

Después de hacer referencia a BitcoinJ, parece que algunas de estas muestras de código carecen de la preparación adecuada del mensaje, doble hash SHA256 y posible codificación comprimida del punto público recuperado que se ingresa al cálculo de la dirección.

El siguiente código solo debería necesitar BouncyCastle (probablemente necesite una versión reciente de github, no estoy seguro). Toma prestadas algunas cosas de BitcoinJ, y hace lo suficiente para que funcionen pequeños ejemplos, consulte los comentarios en línea para conocer las restricciones de tamaño de los mensajes.

Solo calcula hasta el hash RIPEMD-160, y utilicé http://gobittest.appspot.com/Address para verificar la dirección final que resulta (desafortunadamente ese sitio web no parece ser compatible con la introducción de una codificación comprimida para la clave pública )

    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();
    }

Ejemplo de salida para los datos iniciales en la pregunta:

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

Si conectamos el valor RIPEMD-160 en el corrector de direcciones, regresa

1Kb76YK9a4mhrif766m321AMocNvzeQxqV

como se da en la pregunta.

Answer 2

Me temo que hay algunos problemas con sus datos de muestra. En primer lugar, su muestra Q tiene 61 bytes de longitud, pero las claves públicas de Bitcoin (que utilizan la curva secp256k1) deben tener 65 bytes en su forma no comprimida. La Q que proporcionó no verifica el mensaje correctamente, pero la QI calculada parece verificarlo.

Escribí un código que calcula la clave pública correcta para la cadena " test 123" y la verifica con ECDsaSigner. Sin embargo, el hash para esta clave pública es 1HRDe7G7tn925iNxQaeD7R2ZkZiKowN8NW lugar de 1Kb76YK9a4mhrif766m321AMocNvzeQxqV .

¿Puedes verificar que tus datos sean correctos y tal vez dar el hash exacto de la cadena del mensaje para que podamos intentar depurar, un hash incorrecto puede estropear las cosas bastante mal? El código que he usado es el siguiente:

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 = " 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("-","");
  }
}

EDITAR Veo que esto todavía no se comenta ni se acepta, así que escribí una prueba completa que genera una clave privada y una clave pública, luego genera una firma válida usando la clave privada. Después de eso, recupera la clave pública de la firma y el hash y usa esa clave pública para verificar la firma del mensaje. Vea a continuación, si todavía hay algunas preguntas, hágamelo saber.

  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));
  }