2
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ You should tell us exactly what the original problem was that led you to this question. Beyond that, there’s a problem, ’cause there is no “the” point in characteristic zero that will correspond to a point with coordinates in $\Bbb Z/16\Bbb Z$. $\endgroup$
    – Lubin
    Jan 22 at 4:14
  • $\begingroup$ @Lubin its just curiosity. I've also changed the curve which now leads to a group of prime order n=13. $\endgroup$
    – user306666
    Jan 22 at 7:41
  • 1
    $\begingroup$ I am puzzled by this question. If the coordinates of a point $(x,y)$ are in a finite field, then they are elements of that finite field. They are not real numbers at all. $\endgroup$ Jan 22 at 7:47
  • 2
    $\begingroup$ (cont'd) And I can finally describe why the question is not too well defined. You see, the point $\overline{G}$ on curve $B$ has a finite order, say $\ell$. Meaning that knowing $r*\overline{G}$ does not specify $r$. We have $$r_1*\overline{G}=r_2*\overline{G}$$ whenever $r_1\equiv r_2\pmod{\ell}$. But, more often than not, the points $r_1*G$ and $r_2*G$ are distinct. Basically I am saying that there are infinitely many points on $A$ that become a given point of $B$ when they are reduced modulo $\mathfrak{p}$. $\endgroup$ Jan 22 at 9:04
  • 2
    $\begingroup$ Cross-Posted with Crytpgraphy. This is not considered good in Is cross-posting a question on multiple Stack Exchange sites permitted if the question is on-topic for each site? $\endgroup$
    – kelalaka
    Jan 22 at 16:05
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy