从压缩的公钥中派生ECDSA未压缩的公钥

问题描述 投票：8回答：4

我目前正在尝试从压缩的公钥中派生出比特币未压缩的ECDSA公钥。

根据这个link on the Bitcoin wiki，有可能这样做......但是怎么样？

为了给你更多细节：截至目前，我已经在比特币网络上收集了压缩密钥（33字节长）。

它们具有以下格式：<1字节长前缀> <32字节长X>。从那里，我想获得一个未压缩的密钥（65字节长），其格式为：<1字节长前缀> <32字节长X> <32字节长Y>

根据这个other link on the Bitcoin wiki，它应该像解决方程一样简单：

Y ^ 2 = X ^ 3 + 7

但是，我似乎无法到达那里。我对Y的价值远远不够。这是我的代码（公钥的值来自Bitcoin wiki example）：

import binascii
from decimal import *

expected_uncompressed_key_hex = '0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6'
expected_y_hex = expected_uncompressed_key_hex[-64:]
expected_y_dec = int(expected_y_hex, 16)
x_hex = expected_uncompressed_key_hex[2:66]
if expected_y_dec % 2 == 0:
    prefix = "02"
else:
    prefix = "03"

artificial_compressed_key = prefix + x_hex

getcontext().prec = 500
test_dec = Decimal(int(x_hex, 16))
y_square_dec = test_dec**3 + 7
if prefix == "02":
    y_dec = - Decimal(y_square_dec).sqrt()
else:
    y_dec = Decimal(y_square_dec).sqrt()

computed_y_hex = hex(int(y_dec))
computed_uncompressed_key = "04" + x + computed_y_hex

有关信息，我的输出是：

computed_y_hex = '0X2D29684BD207BF6D809F7D0EB78E4FD61C3C6700E88AB100D1075EFA8F8FD893080F35E6C7AC2E2214F8F4D088342951'
expected_y_hex = '2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6'

谢谢您的帮助！

python bitcoin public-key ecdsa
4个回答
5
投票

您需要在字段中进行计算，这主要意味着您必须在每次计算后用p除以后将数字减少到余数。计算它被称为取模，并在python中写为% p。

在这个领域中的指数可以比仅仅乘法和减少很多次的天真方式更有效地完成。这称为模幂运算。 Python的内置指数函数pow（n，e，p）可以解决这个问题。

剩下的问题是找到平方根。幸运的是，secp256k1以一种特殊的方式选择（），因此取平方根很容易：x的平方根是。

因此，代码的简化版本变为：

import binascii

p_hex = 'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F'
p = int(p_hex, 16)
compressed_key_hex = '0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352'
x_hex = compressed_key_hex[2:66]
x = int(x_hex, 16)
prefix = compressed_key_hex[0:2]

y_square = (pow(x, 3, p)  + 7) % p
y_square_square_root = pow(y_square, (p+1)/4, p)
if (prefix == "02" and y_square_square_root & 1) or (prefix == "03" and not y_square_square_root & 1):
    y = (-y_square_square_root) % p
else:
    y = y_square_square_root

computed_y_hex = format(y, '064x')
computed_uncompressed_key = "04" + x_hex + computed_y_hex

print computed_uncompressed_key
3
投票

椭圆曲线的场不在实数域上。它超过了有限域模数的一些素数。

对于Secp256k1，素数p = 2 ^ 256 - 2 ^ 32 - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1。

因此：y ^ 2 =（x ^ 3）+ 7（mod p）

没有直接的方法来解决这个等式，你需要使用Cipolla的算法：https://en.wikipedia.org/wiki/Cipolla%27s_algorithm

1
投票

这里是一个没有任何第三方python库的示例代码：

def pow_mod(x, y, z):
    "Calculate (x ** y) % z efficiently."
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number

# prime p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

# bitcoin's compressed public key of private key 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641
compressed_key = '0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267'

y_parity = int(compressed_key[:2]) - 2
x = int(compressed_key[2:], 16)

a = (pow_mod(x, 3, p) + 7) % p
y = pow_mod(a, (p+1)//4, p)

if y % 2 != y_parity:
    y = -y % p

uncompressed_key = '04{:x}{:x}'.format(x, y)
print(uncompressed_key) 
# should get 0414fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267be5645686309c6e6736dbd93940707cc9143d3cf29f1b877ff340e2cb2d259cf

请参考比特币谈话：https://bitcointalk.org/index.php?topic=644919.0

0
投票

我知道这个问题已得到解答，我实际上从这个答案中受益，所以谢谢。问题是我在C＃中寻找相同的解决方案时发现了这些答案3次，而且我并没有在python中编写代码:)。因此，对于任何试图解决这个问题的人来说，这是一个C＃解决方案，玩得开心！ ：）（它使用BouncyCastle库）。

using System;
using System.Collections.Generic;
using System.Linq;
using MoreLinq;
using NBitcoin;
using Org.BouncyCastle.Asn1.X9;
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Math;
using Org.BouncyCastle.Math.EC;

namespace BitcoinPublicKeyDecompression
{
    public class Program
    {
        public static void Main()
        {
            const string cPubKey = "0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352";
            var uPubKey = cPubKey.ToHexByteArray().BitcoinDecompressPublicKey().ToHexString();
            var expectedUPubKey = new PubKey(cPubKey).Decompress().ToString();

            Console.WriteLine($"Public Key:\n\n{cPubKey}\n\nhas been {(uPubKey == expectedUPubKey ? "correctly" : "incorrectly")} decompressed to:\n\n{uPubKey}");

            Console.WriteLine("\nPress any key to quit...");
            Console.ReadKey();
        }
    }

    public static class Extensions
    {
        public static readonly byte[] EmptyByteArray = new byte[0];

        public static byte[] BitcoinDecompressPublicKey(this byte[] bPubC)
        {
            var ecPubKey = bPubC.BitcoinCompressedPublicKeyToECPublicKey();
            return ecPubKey.ToBitcoinUncompressedPublicKey();
        }

        public static ECPublicKeyParameters BitcoinCompressedPublicKeyToECPublicKey(this byte[] bPubC)
        {
            var pubKey = bPubC.Skip(1).ToArray();

            var curve = ECNamedCurveTable.GetByName("secp256k1");
            var domainParams = new ECDomainParameters(curve.Curve, curve.G, curve.N, curve.H, curve.GetSeed());

            var yParity = new BigInteger(bPubC.Take(1).ToArray()).Subtract(BigInteger.Two);
            var x = new BigInteger(1, pubKey);
            var p = ((FpCurve)curve.Curve).Q;
            var a = x.ModPow(new BigInteger("3"), p).Add(new BigInteger("7")).Mod(p);
            var y = a.ModPow(p.Add(BigInteger.One).FloorDivide(new BigInteger("4")), p);

            if (!y.Mod(BigInteger.Two).Equals(yParity))
                y = y.Negate().Mod(p);

            var q = curve.Curve.CreatePoint(x, y);
            return new ECPublicKeyParameters(q, domainParams);
        }

        public static byte[] ToBitcoinUncompressedPublicKey(this AsymmetricKeyParameter ecPublicKey)
        {
            var publicKey = ((ECPublicKeyParameters)ecPublicKey).Q;
            var xs = publicKey.AffineXCoord.ToBigInteger().ToByteArrayUnsigned().PadStart(32);
            var ys = publicKey.AffineYCoord.ToBigInteger().ToByteArrayUnsigned().PadStart(32);
            return new byte[] { 0x04 }.ConcatMany(xs, ys).ToArray();
        }

        public static BigInteger FloorDivide(this BigInteger a, BigInteger b)
        {
            if (a.CompareTo(BigInteger.Zero) > 0 ^ b.CompareTo(BigInteger.Zero) < 0 && !a.Mod(b).Equals(BigInteger.Zero))
                return a.Divide(b).Subtract(BigInteger.One);

            return a.Divide(b);
        }

        public static byte[] ToHexByteArray(this string str)
        {
            byte[] bytes;
            if (string.IsNullOrEmpty(str))
                bytes = EmptyByteArray;
            else
            {
                var string_length = str.Length;
                var character_index = str.StartsWith("0x", StringComparison.Ordinal) ? 2 : 0;
                var number_of_characters = string_length - character_index;
                var add_leading_zero = false;

                if (0 != number_of_characters % 2)
                {
                    add_leading_zero = true;
                    number_of_characters += 1;
                }

                bytes = new byte[number_of_characters / 2];

                var write_index = 0;
                if (add_leading_zero)
                {
                    bytes[write_index++] = CharacterToByte(str[character_index], character_index);
                    character_index += 1;
                }

                for (var read_index = character_index; read_index < str.Length; read_index += 2)
                {
                    var upper = CharacterToByte(str[read_index], read_index, 4);
                    var lower = CharacterToByte(str[read_index + 1], read_index + 1);

                    bytes[write_index++] = (byte)(upper | lower);
                }
            }

            return bytes;
        }

        public static byte CharacterToByte(char character, int index, int shift = 0)
        {
            var value = (byte)character;
            if (0x40 < value && 0x47 > value || 0x60 < value && 0x67 > value)
            {
                if (0x40 != (0x40 & value))
                    return value;
                if (0x20 == (0x20 & value))
                    value = (byte)((value + 0xA - 0x61) << shift);
                else
                    value = (byte)((value + 0xA - 0x41) << shift);
            }
            else if (0x29 < value && 0x40 > value)
                value = (byte)((value - 0x30) << shift);
            else
                throw new InvalidOperationException($"Character '{character}' at index '{index}' is not valid alphanumeric character.");

            return value;
        }

        public static string ToHexString(this byte[] value, bool prefix = false)
        {
            var strPrex = prefix ? "0x" : "";
            return strPrex + string.Concat(value.Select(b => b.ToString("x2")).ToArray());
        }

        public static IEnumerable<T> ConcatMany<T>(this IEnumerable<T> enumerable, params IEnumerable<T>[] enums)
        {
            return enumerable.Concat(enums.SelectMany(x => x));
        }
    } 
}

结果：

enter image description here

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.