Getting an uncompressed ECDSA public key from a compressed

Question

I'm currently trying to extract the ECDSA public compressed public key in bitcoin from the compressed.

According to this link, another link in the Bitcoin quiz, it should be as simple as solving the equation:

Y ^ 2 = X ^ 3 + 7

However, I can’t get there. My meaning for Y is just far. Here is my code (the value for the public key comes from the Wiki-Bitcoin 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' 

Thank you for your help!

Answer 1

You need to calculate in the field , which basically means that you need to reduce your number to the remainder after dividing by p after each calculation. The calculation of this is called modulo acceptance and is written as % p in python.

The exponentiality in this field can be performed more efficiently than the naive way of simply multiplying and decreasing many times. This is called modular exponentiation. The Python built-in exponential function pow (n, e, p) can take care of this.

The rest of the problem is finding the square root. Fortunately, secp256k1 is selected in a special way ( ), so it’s easy to take square roots: the square root of x is .

Thus, a simplified version of your code will look like this:

 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

The field of the elliptic curve is not located above the field of real numbers. It is over a finite field modulo some prime.

For Secp256k1, the prime p = 2 ^ 256 - 2 ^ 32 - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1.

Thus: y ^ 2 = (x ^ 3) + 7 (mod p)

There is no direct way to solve the equation, you will need to use the Cipolla algorithm: https://en.wikipedia.org/wiki/Cipolla%27s_algorithm