ECDSA x,y coordinate validity verification doesn't seem to work

Question

The ECDSA algorithm, secp256k1 for Bitcoin allegedly uses the equation

y ^ 2 = x ^ 3 + 7 mod P

to determine the validity of an alleged point upon the elliptical curve. Utilizing http://web2.0calc.com/

When verifying public key 1 which has the following qualities:

x = 55066263022277343669578718895168534326250603453777594175500187360389116729240

y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

I applied x ^ 3, then added 7, then mod P on that webpage. Then I square rooted it and got

180964706334543048141953325634608696715.426683454595872

Which is not y. How am I doing this wrong? My results suggests that this point is not a valid point on the curve, but everyone knows it is. Obviously I'm the one who's wrong.

EDIT: I'd like to further clarify the question. My question is, how does one actually determine (as an example) the Y value while only having the X value. Bitcoin does it, the "Bitcoin Address Utility" also does it. When someone has a compressed key (which only contains the x coordinate) they are able to get the y coordinate as well. Utilizing the aforementioned webpage calculator does not work and others are saying its "modular root". Anyone have Python 2.7.7 code which would do this or have a relatively simple way of explaining how to accomplish this whole thing? Thanks.

Answer 1

The plain text format of this equation only makes sense when you understand the theory behind it. y ^ 2 = x ^ 3 + 7 mod P means "do all math in this equation using the finite number field with definition P". It might better be written (y^2 = x^3 +7) mod p.

To keep the math simple, lets simply subtract one side from the other to see if that evaluates to zero. This lets us avoid roots. Here's code using the Python interactive shell, e.g. python from a command prompt):

>>> x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
>>> y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
>>> p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> (x**3 + 7 - y**2) % p
0

Answer 2

From your X value, you can get 2 possible Y values.

y^2 == (Y * Y) == (-Y * -Y)    (mod p)

Depending on the format of the public key in the bitcoin transaction input, you can figure out which Y is the one you want to validate against.

If the public key starts with 04, then Y is already present in the public key and you don't need to do any calculations to find Y

If the public key starts with 02, then the Y value you want is an even number.

If the public key starts with 03, then the Y value you want is on odd number.

Using your example for X,

X = 55066263022277343669578718895168534326250603453777594175500187360389116729240

I compute the possible Y values are,

Y1 = 32670510020758816978083085130507043184471273380659243275938904335757337482424
Y2 = 83121579216557378445487899878180864668798711284981320763518679672151497189239

Choose your Y depending on the format of the public key in the bitcoin transaction input.

Python code,

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
ysquared = ((x*x*x+7) % p)
print "ysquared= %s " % ysquared
y = pow(ysquared, (p+1)/4, p)
print "y1 = %s " % y
print "y2 = %s " % (y * -1 % p)

---

I prefer to look at my numbers in hex format, so here is the same example output as hex.

X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Y1 = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Y2 = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777

Python code,

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
ysquared = ((x*x*x+7) % p)    
print "ysquared= %s " % hex(ysquared)    
y = pow(ysquared, (p+1)/4, p)
print "y1 = %s " % hex(y)
print "y2 = %s " % hex(y * -1 % p)

---

An example transaction containing the public key X,Y1 (0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)

https://2xoin.com/tx/8e2c570498680261040ceffdd15e67dda6c00a885d1e5484f220125f3a5e2c56

At the time of writing, there were no transactions using the public key X,Y2

Answer 3

To go further on David's answer, the hardest part is actually the square root. It's just the number that after squaring modulo P ends up being the result you had before. That's a modular square root, and you won't easily compute it using regular arithmetic (unlike modular additions, multiplications or powers).

This wikipedia article section has more information: http://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus

Answer 4

You can also decode from b64 Q29udGFjdCBtZSBhdCBhZGl0ZWMzNUBnbWFpbC5jb20= the: x = 55066263022277343669578718895168534326250603453777594175500187360389116729240

y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

I applied x ^ 3, then added 7, then mod P on that webpage. Then I square rooted it and got

180964706334543048141953325634608696715.426683454595872