Deriving an ECDSA uncompressed public key from a compressed one

Here a sample code without any 3rd party python libs:

def pow_mod(x, y, z):
    "Calculate (x ** y) % z efficiently."
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number

# prime p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

# bitcoin's compressed public key of private key 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641
compressed_key = '0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267'

y_parity = int(compressed_key[:2]) - 2
x = int(compressed_key[2:], 16)

a = (pow_mod(x, 3, p) + 7) % p
y = pow_mod(a, (p+1)//4, p)

if y % 2 != y_parity:
    y = -y % p

uncompressed_key = '04{:x}{:x}'.format(x, y)
print(uncompressed_key) 
# should get 0414fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267be5645686309c6e6736dbd93940707cc9143d3cf29f1b877ff340e2cb2d259cf

refer to bitcoin talk: https://bitcointalk.org/index.php?topic=644919.0

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.

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.

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

The field of the elliptic curve is not over the field of real numbers. It's 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's no direct way to solve the equation, you would need to use Cipolla's algorithm: https://en.wikipedia.org/wiki/Cipolla%27s_algorithm