Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

Question

Given an x-coordiante of a point on the SECP256K1 curve, is it possible to calculate the corresponding y-coorindate? (Assuming the point is a verifying public key that complies with the Bitcoin standards.)

I am new to the cryptographic realm so please forgive me if the question is naive. From what I know, the public key is a point, or a pair of integers. The SECP256K1 curve is a curve where any point (x, y) on it satisfies

(y ** 2) mod p == (x ** 3 + 7) mod p

where p = 2**256 - 2**32 - 977.

Now let's confine the discussion within the Bitcoin scope. Assume we have a private key that complies with the Bitcoin standards, and from it we can derive the public key, which can be represented as a point (x, y) on the SECP256K1 curve.

Now given only such a x, is it possible to calculate the y?

As a real example, given only x as

0x6778ec0abf66f1ba4d93aa45cad77dc26c593f520448f6fff5b70357270154ba

is it possible get the y as

0x6a5e8cd7276f80ee2f7c081702eff3e14134b006acd0afc8467be94a0a3a0558

Answer 1

Given an $x$-coordinate of a point on the SECP256K1 curve, is it possible to calculate the corresponding $y$-coordinate?

Yes, if there exists such $y$ for the given $x$. And, absent other indication, such $y$ can only be found within sign (or equivalently, parity). That limitation is because if $y^2\equiv x^3+7\pmod p$ with $p=2^{256}−2^{32}−2^{10}+2^6-2^4−1$ as in secp256k1 has a solution $y_0$ in $[0,p)$, then $y_1=p-y_0$ also is a solution.

Note: in some cases including secp256k1 as used in Bitcoin, a public key with $x$ and without $y$ (that is, in compressed form) comes with a prefix of 02 if $y$ is even, 03 if $y$ is odd, and that allows to fully recover $y$.

By Euler's criterion, $x^3+7$ has a square root modulo $p$ if and only if $(x^3+7)^{(p-1)/2}\bmod p=1$. That holds for the question's $x$, thus there are solutions.

In the general case, the Tonelli–Shanks algorithm can be used to find modular square roots. Since $p\equiv3\pmod4$, that algorithm reduces to computing $y_0\gets (x^3+7)^{(p+1)/4}\bmod p$ and $y_1\gets p-y_0$. The question's $y$ happens to be $y_1$.

Justification: when we have checked $(x^3+7)^{(p-1)/2}\bmod p=1$, and computed $y_0$ as $(x^3+7)^{(p+1)/4}\bmod p$, the later is such that $$\begin{array}{} {y_0}^2 &\equiv&\left((x^3+7)^{(p+1)/4}\right)^2 &\pmod p \\ & \equiv&(x^3+7)^{(p+1)/2} &\pmod p \\ &\equiv&(x^3+7)^{(p-1)/2}\,(x^3+7)&\pmod p\\ &\equiv&x^3+7 &\pmod p & \text{since}\;(x^3+7)^{(p-1)/2}\bmod p=1\end{array}$$ thus $y_0$ is a solution to $y^2\equiv x^3+7\pmod p$.

---

Definitions: $$\begin{array}{l} u\equiv v\pmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\\ u=v\bmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\;\text{ and }0\le u<p\; \end{array}$$

Answer 2

The curve used by bitcoin is secp256k1, which has the equation $$y^2 = x^3 + 7$$

That means every single point $P = (x, y)$ on the curve must satisfy this equation.

So, given $x$, we can compute the right hand side of the equation $x^3 + 7$ to obtain $y^2$. Then we need to "square root" this in the field $F_p$ to find $y$. Note that is not the same as taking the square root of a real number.

We shall require that $p \equiv 3 \pmod{4}$, which is true of the prime $p$ ($= 2^{256} - 2^{32} - 977$) which is used in secp256k1. The way to compute this "square root" of an element $a$ in $F_p$, when $p \equiv 3 \pmod{4}$, is to use the equation: $$y = a^{(p+1)/4} \pmod{p}$$

You can check that this is true because suppose $a = y^2$. then $$\left( a^{(p+1)/4} \right)^2 \equiv a^{(p+1)/2} \equiv y^{p+1} \pmod{p}$$ and then, by Fermat's little theorem: $$y^{p+1} \equiv y^2 \equiv a \pmod{p}$$

Your example is not great, because $10^3 + 7 \equiv 0 \pmod{19}$. So $y = 0$ is a trivial square root.

Using a different example, let's work over $F_{23}$, with $p = 23$, and keep the same value of $x = 10$. Then $10^3 + 7 \equiv 18 \pmod{23}$. Now, to compute $y$ such that $y^2 \equiv 18 \pmod{23}$, we use the above equation: $$y = 18^{(23+1)/4} = 18^6 \equiv 8 \pmod{23}$$

To confirm this, we can check that $8^2$ does indeed equal $18$ modulo 23. So the point we are looking for is $(10, 8)$. Note too that there is the "negative" version of the point with the same x-coordinate, $(10, -8) \equiv (10, 15)$, because $y^2 = (-y)^2$. We can check this too, because $15^2 \equiv 18 \pmod{23}$ as expected.

Note that not all $x$ values will have a valid corresponding $y$ value. We expect roughly half the possible choices of $x$ to correspond to (usually) two points each. When $a = x^3 + 7$ does indeed have a corresponding $y$ value such that $y^2 = a$, then we say a is a quadratic residue modulo $p$.