4
$\begingroup$

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
$\endgroup$
11
  • 1
    $\begingroup$ SEC#1 from secg.org explains it in section 2.3.4. Octet-String-to-Elliptic-Curve-Point Conversion. $\endgroup$
    – DannyNiu
    Jul 22, 2020 at 5:34
  • 1
    $\begingroup$ @MaartenBodewes: 01 is not used; 00 is infinity aka $O$ and 04 is uncompressed. X9.62 used 06 and 07 for hybrid, but SEC1 and AFAIK everybody else just ignored hybrid as being silly and useless. $\endgroup$ Jul 22, 2020 at 23:44
  • 2
    $\begingroup$ Note that, Andreas's book is not a good source to learn elliptic curves, since they use EC multiplication instead of EC scalar multiplication that confused many How do I multiply two points on an elliptic curve? $\endgroup$
    – kelalaka
    Jan 27 at 18:08
  • 1
    $\begingroup$ You should accept the dupe when see it, this is the way of our site. It is good on the non-math side. The math side really depends on you. If you need Hash functions, Elliptic Curves, Digital signatures like ECDSA, I suggest Serious Cryptography: A Practical Introduction to Modern Encryption $\endgroup$
    – kelalaka
    Jan 28 at 9:59
  • 1
    $\begingroup$ Another good cryptography book is Katz and Lindell's "Introduction to Modern Cryptography", and for bitcoin maybe "Grokking Bitcoin" by Rosenbaum? $\endgroup$ Jan 28 at 10:05

2 Answers 2

9
$\begingroup$

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}$$

$\endgroup$
0
8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you really much for your detailed explanation, I have been doing searches about this at got stuck at the part everyone mentioned about the condition p mod 4 = 3. I am curious about how that requirement came up in the first place? Like to make the function easier to solve or something similar? $\endgroup$
    – John Pham
    Jan 28 at 9:26
  • 1
    $\begingroup$ Yep, it makes it a lot easier. In the general case, we need to use the Tonelli-Shanks algorithm. It is still doable, of course, just a bit more complicated. $\endgroup$ Jan 28 at 10:01

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.