1
$\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$
6
  • 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 '20 at 5:34
  • $\begingroup$ Thanks for pointing to the right direction. The key part is an efficient algorithm to compute the modular square root, namely the Tonelli–Shanks algorithm, which I didn't know and I was asking for, and which I know now. If time permits I can make an answer my own. $\endgroup$ – aafulei Jul 22 '20 at 7:13
  • $\begingroup$ Note that the linked strategy requires an extra byte (or rather 2 bit) of information as there are two possible $y$ values for each $x$. $\endgroup$ – SEJPM Jul 22 '20 at 10:22
  • $\begingroup$ In the compression form, the value of $g$ starts with 02 or 03, '02' tells to select the root whose least significant bit is even, and versa. $\endgroup$ – kelalaka Jul 22 '20 at 14:40
  • 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$ – dave_thompson_085 Jul 22 '20 at 23:44
6
$\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

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.