派生一個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從壓縮的一個未壓縮的公鑰

回答

相關問題