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

<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. <code>python</code> from a command prompt):</p>

<pre><code>&gt;&gt;&gt; x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
&gt;&gt;&gt; y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
&gt;&gt;&gt; p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
&gt;&gt;&gt; (x**3 + 7 - y**2) % p
0
</code></pre>

CC BY-SA 3.0
2014-11-20T17:43:41.310Z
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
CC BY-SA 4.0
2021-11-21T06:44:08.867Z
Was this ever solved?
Tim Coulter
CC BY-SA 3.0
2014-11-20T14:19:57.770Z
2014-11-20T14:19:57.770Z
David A. Harding
<p>From your X value, you can get 2 possible Y values.</p>
<pre><code>y^2 == (Y * Y) == (-Y * -Y)    (mod p)
</code></pre>
<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.</p>
<p>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</p>
<p>If the public key starts with 02, then the Y value you want is an even number.</p>
<p>If the public key starts with 03, then the Y value you want is on odd number.</p>
<p>Using your example for X,</p>
<pre><code>X = 55066263022277343669578718895168534326250603453777594175500187360389116729240
</code></pre>
<p>I compute the possible Y values are,</p>
<pre><code>Y1 = 32670510020758816978083085130507043184471273380659243275938904335757337482424
Y2 = 83121579216557378445487899878180864668798711284981320763518679672151497189239
</code></pre>
<p>Choose your Y depending on the format of the public key in the bitcoin transaction input.</p>
<p>Python code,</p>
<pre><code>p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
ysquared = ((x*x*x+7) % p)
print &quot;ysquared= %s &quot; % ysquared
y = pow(ysquared, (p+1)/4, p)
print &quot;y1 = %s &quot; % y
print &quot;y2 = %s &quot; % (y * -1 % p)
</code></pre>
<hr />
<p>I prefer to look at my numbers in hex format, so here is the same example output as hex.</p>
<pre><code>X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Y1 = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Y2 = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777
</code></pre>
<p>Python code,</p>
<pre><code>p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
ysquared = ((x*x*x+7) % p)    
print &quot;ysquared= %s &quot; % hex(ysquared)    
y = pow(ysquared, (p+1)/4, p)
print &quot;y1 = %s &quot; % hex(y)
print &quot;y2 = %s &quot; % hex(y * -1 % p)
</code></pre>
<hr />
<p>An example transaction containing the public key X,Y1 (0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)</p>
<p><a href="https://2xoin.com/tx/8e2c570498680261040ceffdd15e67dda6c00a885d1e5484f220125f3a5e2c56" rel="nofollow noreferrer">https://2xoin.com/tx/8e2c570498680261040ceffdd15e67dda6c00a885d1e5484f220125f3a5e2c56</a></p>
<p>At the time of writing, there were no transactions using the public key X,Y2</p>

CC BY-SA 4.0
2014-12-12T10:02:50.897Z
2020-12-27T15:44:06.343Z
2020-12-27T15:44:06.343Z
Sean Bradley
<p>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).</p>

<p>This wikipedia article section has more information: <a href="http://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus" rel="nofollow">http://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus</a></p>

CC BY-SA 3.0
2014-11-20T19:32:12.507Z
How is bitcoin determining the y coordinate when it has only the X as in compressed public keys?
Mine
CC BY-SA 3.0
2014-11-21T00:02:14.277Z
We ask OpenSSL (for now), which uses computes the (p+1)/4'th power of the number modulo p, as is listed in that Wikipedia article above.
Pieter Wuille
CC BY-SA 3.0
2014-11-20T17:56:00.347Z
2014-11-20T17:56:00.347Z
Pieter Wuille
<p>You can also decode from b64 Q29udGFjdCBtZSBhdCBhZGl0ZWMzNUBnbWFpbC5jb20=
the:
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240</p>
<p>y = 32670510020758816978083085130507043184471273380659243275938904335757337482424</p>
<p>I applied x ^ 3, then added 7, then mod P on that webpage. Then I square rooted it and got</p>
<p>180964706334543048141953325634608696715.426683454595872</p>

CC BY-SA 4.0
2021-11-05T05:23:09.340Z
2021-11-05T05:23:09.340Z
Adi Tech
<p>The ECDSA algorithm, secp256k1 for Bitcoin allegedly uses the equation</p>

<p>y ^ 2 = x ^ 3 + 7 mod P</p>

<p>to determine the validity of an alleged point upon the elliptical curve.  Utilizing 
<a href="http://web2.0calc.com/" rel="nofollow">http://web2.0calc.com/</a></p>

<p>When verifying public key 1 which has the following qualities:</p>

<p>x = 55066263022277343669578718895168534326250603453777594175500187360389116729240</p>

<p>y = 32670510020758816978083085130507043184471273380659243275938904335757337482424</p>

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

<p>180964706334543048141953325634608696715.426683454595872</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-11-20T20:57:28.947Z
PyBitcoinTools uses [these lines](https://github.com/vbuterin/pybitcointools/blob/master/bitcoin/main.py#L252-L256).  As Pieter said, it's quite complicated.
David A. Harding
CC BY-SA 4.0
2021-11-06T21:51:49.533Z
Related: https://security.stackexchange.com/questions/233099/validating-an-ed25519-public-key
mti2935
<security><address><ecdsa>
ECDSA x,y coordinate validity verification doesn't seem to work
Mine
# ECDSA x,y coordinate validity verification doesn't seem to work

(Asked by: username_0 on 2014-11-20)

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.

**Tags:** security, address, ecdsa

> **Comments:**
> **username_1**: PyBitcoinTools uses [these lines](https://github.com/vbuterin/pybitcointools/blob/master/bitcoin/main.py#L252-L256).  As Pieter said, it's quite complicated.  
> **username_2**: Related: https://security.stackexchange.com/questions/233099/validating-an-ed25519-public-key  

---

## 4 answers

### Answer by username_1 on 2014-11-20. Score: 7

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

> **Comments:**
> **username_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.  
> **username_3**: Was this ever solved?  

---

### Answer by username_4 on 2014-12-12. Score: 3

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 by username_5 on 2014-11-20. Score: 2

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>

> **Comments:**
> **username_0**: How is bitcoin determining the y coordinate when it has only the X as in compressed public keys?  
> **username_5**: We ask OpenSSL (for now), which uses computes the (p+1)/4'th power of the number modulo p, as is listed in that Wikipedia article above.  

---

### Answer by username_6 on 2021-11-05. Score: 0

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


---

