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

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.

• PyBitcoinTools uses these lines. As Pieter said, it's quite complicated. Nov 20 '14 at 20:57
• Nov 6 at 21:51

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
``````
• My goal is to be able to determine y, when all I have is x. I do not disagree with your conclusion that it is ideal to avoid square roots.
– Mine
Nov 20 '14 at 17:43

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.

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

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).