派生一个ECDSA从压缩的一个未压缩的公钥

我目前试图从一个压缩派生一个比特币未压缩的ECDSA公钥。派生一个ECDSA从压缩的一个未压缩的公钥

根据这link on the Bitcoin wiki，有可能这样做......但如何？

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

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

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

Y 1 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'

谢谢您的帮助！

来源

2017-04-26 Clara-sininen

一个与比特币标签实际编程问题。这是罕见的... – jww

你需要在该领域 $\mathbb{Z}_p$ ，其主要目的是计算在每次计算后除以p后，你必须减少你的数字。计算这个称为取模，在Python中写成% p。

这个领域中的指数可以比仅仅乘以和减少许多次的天真方式更有效地完成。这被称为模数求幂。 Python内置的exponentation函数pow（n，e，p）可以处理这个问题。

剩下的问题是找到平方根。幸运的是secp256k1是以特殊方式选择的（ $p\equiv3\pmod 4$ ），所以取平方根很容易：x的平方根是 $x^{\frac{p+1}{4}} \pmod p$ 。

所以你的代码的简化版本就变成了：

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": 
    y = (-y_square_square_root) % p 
else: 
    y = y_square_square_root 

computed_y_hex = hex(y)[2:66] 
computed_uncompressed_key = "04" + x_hex + computed_y_hex 

print computed_uncompressed_key

来源

2017-04-27 09:37:25

你的散文使用'（p减1）/ 4'，但你的代码使用'（p加1）/ 4'。没有看到那个公式之前我不知道哪一个更正:)。 – bartonjs

@bartonjs：感谢您的支持。我已修复它（代码是正确的）。 –

Hello @ RasmusFaber，我想感谢您提供清晰，干净的代码和您的解释。但是，我恐怕在我实现它时不起作用。我只是将语法从Python 2更改为3，但是我得到的y的值是：'xacc68af70eb1c42c7e2fb7364ad544b527c3926b32ad2cea6af8cea8907b734'当我期望'2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6'。任何想法发生了什么？再次感谢！ –

椭圆曲线的域不超过实数域。它超过了有限域上的某些素数。

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

因此：Y^2 = （X^3）+ 7（模p）

还有求解方程没有直接的方法，你就需要使用奇波拉的算法：https://en.wikipedia.org/wiki/Cipolla%27s_algorithm

来源

2017-04-26 12:17:23

派生一个ECDSA从压缩的一个未压缩的公钥

回答

相关问题