圧縮された公開鍵からECDSA非圧縮公開鍵を派生させる

Question

私は現在、Bitcoin非圧縮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' 

あなたの助けをありがとう！

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": 
    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 

Answer 2

楕円曲線のフィールドは、実数のフィールドにはありません。それはいくつかのプライムを法とする有限体上にある。 Secp256k1について

素数p = 2^256から2^32 - 2^9 - 2^8 - 2^7から2^6 - 2^4 - 1.

したがって：Y^2 = （X^3）+ 7（モッズP）

方程式を解決するための直接的な方法はありません、あなたはCipollaのアルゴリズムを使用する必要があります：https://en.wikipedia.org/wiki/Cipolla%27s_algorithm