3

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:

040F031CA83F3FB372BD6C2430119E0B947CF059D19CDEA98F4CEFFEF620C584F9F064F1FDE4BC07D4F48C5114680AD1ADAF5F6EAA2166F7E4B4887703A681B548

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
7

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)
`F064F1FDE4BC07D4F48C5114680AD1ADAF5F6EAA2166F7E4B4887703A681B548`

This is the even number which is the last 64 characters of the hex that starts with 04.

Note that the address is computed off either of the compressed or uncompressed SEC formats. This computation is a SHA256 hash followed by a RIPEMD160 hash. This is not reversible, so you can't get the SEC format from the address, though you can go the other way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.