Converting a point in a finite field to its real (x, y) coordinate

Question

Let curve $A = y^2 = x^3 + 3$ and curve $B = y^2 \equiv x^3 + 3 \pmod{19}$

Let $G$ be the positive y-valued point in the curve where $x = 2$

Let $r$ be a random scalar integer, for example, $r = 5$

Compute the point $G*r$ in both curves $A$ and $B$

Now, assume I give you the point $G*r$ in curve $B$, can you find what my point $G*r$ in curve $A$ is? You don't know the value for $r$, but you do know all other parameters. You can't bruteforce the curve.

Answer 1

In the question (as in rev. 3), it can be shown by enumeration that there are 12 solutions to $y^2 \equiv x^3 + 3\pmod{19}$ : $$\begin{array}{} (1,2),&(2,7),&(3,7),&(7,2),&(11,2),&(14,7)\\ (1,17),&(2,12),&(3,12),&(7,17),&(11,17),&(14,12) \end{array}$$ Thus with the neutral element $\infty$ (aka point at infinity), the order of curve $B$ is $12+1=13$. The point $B$ has the same $x=2$ coordinate on curves $A$ and $B$. We get $y=\sqrt{11}$ on $A$, and¹ $y=7$ on $B$.

Point addition $R\gets P+Q$ can go by the same formulas for $A$ and $B$, with addition, multiplication, division², and equality in the field $\mathbb R$ for $A$, the field $\mathbb F_{19}$ for $B$:

• If $P=\infty$, $R\gets Q$.
• Otherwise, if $Q=\infty$, $R\gets P$.
• Otherwise, if $x_P\ne x_Q$ $$\begin{align} \lambda&\gets\frac{y_Q-y_P}{x_Q-x_P}\\ x_R&\gets\lambda^2-x_P-x_Q\\ y_R&\gets\lambda(x_P-x_R)-y_R \end{align}$$
• Otherwise, if $P=Q$ (that is $x_P=x_Q$ and $y_P=y_Q$) $$\begin{align} \lambda&\gets\frac{3{x_P}^2}{2y_P}\\ x_R&\gets\lambda^2-2x_P\\ y_R&\gets\lambda(x_P-x_R)-y_R \end{align}$$
• Otherwise (that is $x_P=x_Q$ and $y_P\ne y_Q$), $R\gets\infty$.

In order to compute $G*5$ on each curve, we can compute $G_2\gets G+G$, $G_4\gets G_2+G_2$, $G*5\gets G_4+G$ per these formulas. Try it online!. We get $$\begin{align} G*r&=\left(\frac{60503882}{151321},-\frac{141898736429 \sqrt{11}}{58863869}\right)&\text{ on curve }A\\ &\approx(399.838,-7995.14)\\ \\ G*r&=(7,2)&\text{ on curve }B \end{align}$$

In general, we don't know how to compute $G*r$ on curve $A$ from $G*r$ on curve $B$ other than by finding $r$ first. If we could, that would³ allow finding $r$, which would solve the discrete logarithm problem on a (non-singular) elliptic curve on $\mathbb F_p$ in time polynomial w.r.t. $\log p$. That feat is widely conjectured impossible with a classical Turing machine, and the basis of the conjectured security of Elliptic Curve cryptography, e.g. on secp256k1.

---

¹ Finding a modular square root of $11$ and taking "positive" as $\in[0,9]$. Square roots in the field $\mathbb F_p$ can be efficiently computed even when prime $p$ is large, see the Tonelli–Shanks algorithm.

² Division $\frac uv$ in field $\mathbb F_{19}$ can be computed as $v^{-1}\,u$ where the modular inverse $v^{-1}$ can be found using the extended Euclidean algorithm.

³ If we get the coordinates of $G*r$ accurately enough.