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

Question

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

根据比特币维基上的这个链接,有可能这样做......但是怎么样？

为了给你更多细节:截至目前,我已经在比特币网络上收集了压缩密钥(33字节长).

它们具有以下格式:<1字节长前缀> <32字节长X>.从那里,我想获得一个未压缩的密钥(65字节长),其格式为:<1字节长前缀> <32字节长X> <32字节长Y>

根据比特币维基上的这个其他链接,它应该像解决方程一样简单:

Y ^ 2 = X ^ 3 + 7

但是,我似乎无法到达那里.我对Y的价值远远不够.这是我的代码(公钥的值来自比特币维基示例):

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'

谢谢您的帮助!

Answer 1

你需要在现场计算 ,这意味着你必须在每次计算后用p除以后将数量减少到余数.计算它被称为取模,并% p在python中编写.

在这个领域中的指数可以比仅仅乘法和减少很多次的天真方式更有效地完成.这称为模幂运算.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

Answer 2

这里是一个没有任何第三方 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