# How do I convert Public Key x value to y in Python and verify?

I have been using the BTC Address utility which enables me to type in something like:

020F031CA83F3FB372BD6C2430119E0B947CF059D19CDEA98F4CEFFEF620C584F9

Then clicking a button the program can spit out the Y value or tell me if that X value isn't valid (IE: doesn't have a valid Y value).

As an example, the result of this one would be Valid and would expand to produce the following:

Anyone know the code to do one, or both those functions in Python? (whether the code is for hexadecimal or decimal; it doesn't matter)

• It is worth noting the 1st hexadecimal number is an "compressed public key" and the 2nd is the associated "uncompressed public key". Given the one common private key, it is possible to synthesize either public key that are tightly correlated with one another. – skaht Sep 17 '16 at 0:19

First, you need to understand what the two formats actually are. The first is the compressed SEC format and the second is the uncompressed SEC format. The difference between the two is that the compressed format only includes the X value and the parity of the Y value while the uncompressed format includes both the X and Y values.

The `02` at the beginning of the compressed value indicates that the Y value should be even. `03` would indicate the odd value. The `04` at the beginning of the uncompressed value indicates that both the X and Y values follow. This is why `0F031CA83F3FB372BD6C2430119E0B947CF059D19CDEA98F4CEFFEF620C584F9` is the same for both values.

To get the Y value, is actually not that difficult. You do need to know a little bit about Elliptical Curve Cryptography. Specifically, bitcoin uses SECP256K1 whose curve is represented by `y^2 = x^3 + 7`. This is done modulo P, which in our case is `FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F`. So, plugging in X = `0F031CA83F3FB372BD6C2430119E0B947CF059D19CDEA98F4CEFFEF620C584F9` to the left side of the formula, you get:

`(x^3 + 7) mod p = EBD56984BA6A88F5D40BB496D9A7C70AC3D8DDF5F7C287E8AABEC904E3D41DB5`

The python code for this is pretty simple:

``````\$ python
>>> p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
>>> x = 0x0F031CA83F3FB372BD6C2430119E0B947CF059D19CDEA98F4CEFFEF620C584F9
>>> "%X" % ((x**3 + 7) % p)
'EBD56984BA6A88F5D40BB496D9A7C70AC3D8DDF5F7C287E8AABEC904E3D41DB5'
``````

Now you have to take the square root in order to get Y, which should yield two values, one even and one odd (due to p being odd). This is a much more involved calculation, which you can read about here: http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python

This is implemented in a library called pycoin: https://github.com/richardkiss/pycoin

You can compute it like this:

``````>>> import pycoin
>>> from pycoin.ecdsa.numbertheory import modular_sqrt
\$ python
>>> p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
>>> x = 0x0F031CA83F3FB372BD6C2430119E0B947CF059D19CDEA98F4CEFFEF620C584F9
>>> y_squared = (x**3 + 7) % p
>>> modular_sqrt(y_squared, p)
7058650705029786666096901756991264635816989543710944821299269679858359092967
>>> y = modular_sqrt(y_squared, p)
>>> "%X" % y
'F9B0E021B43F82B0B73AEEB97F52E5250A09155E99081B4B7788FB597E46E7'
``````

This happens to be the odd value (it ends in 7), so you need to compute the other possible y value which is simply p - y

``````>>> "%X" % (p-y)
This is the even number which is the last 64 characters of the hex that starts with `04`.