从压缩的密钥派生ECDSA未压缩的公共密钥 [英] Deriving an ECDSA uncompressed public key from a compressed one

问题描述

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

I am currently trying to derive a Bitcoin uncompressed ECDSA public key from a compressed one.

根据比特币Wiki上的链接，可以这样做...但是如何?

According to this link on the Bitcoin wiki, it is possible to do so... But how?

为您提供更多详细信息:到目前为止，我已经在比特币网络上收集了压缩的密钥(33字节长).

To give you more details: as of now I have compressed keys (33-bytes-long) gathered on the bitcoin network.

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

They are of the following format: <1-byte-long prefix><32-bytes-long X>. From there, I would like to obtain an uncompressed key (65-bytes-long) whose format is: <1-byte-long prefix><32-bytes-long X><32-bytes-long Y>

根据此比特币Wiki上的其他链接，它应该与解决以下问题一样简单:等式:

According to this other link on the Bitcoin wiki, it should be as easy as solving the equation:

Y ^ 2 = X ^ 3 + 7

Y^2 = X^3 + 7

但是，我似乎无法到达那里.我对Y的价值简直遥不可及.这是我的代码(公用密钥的值来自比特币Wiki示例):

However, I cannot seem to get there. My value for Y is simply far-off. Here is my code (the value for the public key come from the 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

有关信息，我的输出是:

For information, my outputs are:

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

谢谢您的帮助！

推荐答案

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

You need to calculate in the field , which mostly means that you have to reduce your number to the remainder after dividing with p after each calculation. Calculating this is called taking the modulo and is written as % p in python.

在这个领域求幂比只乘和减少很多次的幼稚方式更有效.这称为模幂. Python的内置指数函数pow(n，e，p)可以解决这个问题.

Exponentiating in this field can be done more effectively than the naive way of just multiplying and reducing many times. This is called modular exponentiation. Python's built-in exponentation function pow(n,e,p) can take care of this.

剩下的问题是找到平方根.幸运的是，以特殊方式选择了secp256k1( )，这样就可以轻松求平方根:x的平方根是.

The remaining problem is to find the square root. Luckily secp256k1 is chosen in a special way (), so that taking square roots is easy: A square root of x is .

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

So a simplified version of your code becomes:

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

这篇关于从压缩的密钥派生ECDSA未压缩的公共密钥的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！