2

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.

  • 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$. – Lubin Jan 22 '21 at 04:14
  • @Lubin its just curiosity. I've also changed the curve which now leads to a group of prime order n=13. –  Jan 22 '21 at 07:41
  • 1
    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. – Jyrki Lahtonen Jan 22 '21 at 07:47
  • @JyrkiLahtonen I hope the edit helps. –  Jan 22 '21 at 08:04
  • Improved, sure. Thanks! There are still a few obstacles. By your specification $y=\sqrt{11}$. In the field $\Bbb{F}_{19}$ we can then have $y=\pm7$, but there is no unique way to say which it should be. Remember that in finite fields we do not have any kind of notions of positive or larger than. More generally, there is no general way to relate a point $(x,y)\in\Bbb{R}^2$ to a point over a finite field. What is usually done is that we have a suitable subfield $K$ of $\Bbb{R}$ that is also a finite extension of $\Bbb{Q}$. – Jyrki Lahtonen Jan 22 '21 at 08:49
  • (cont'd) Then we concentrate on those points that have coordinates in the subfield $K$. More often than not (not 100 per cent about this, corrections welcome), we assume that $x,y$ are algebraic integers of $K$. Here the choice $K=\Bbb{Q}(\sqrt{11})$ works just fine, and $(x,y)=(2,\sqrt{11})\in K^2$. To associate with such a point a point with coordinates in a finite field of characteristic $19$ we do the following. We pick a prime ideal $\mathfrak{p}$ of the ring of integers $\mathcal{O}_K$ such that $19\in\mathfrak{p}$. – Jyrki Lahtonen Jan 22 '21 at 08:54
  • (cont'd) Then the quotient ring $F=\mathcal{O}_K/\mathfrak{p}$ will be a finite field of characteristic $19$ as required. As $x,y$ are assumed to be elements of $\mathcal{O}_K$, their cosets in $F$ are well defined. Furthermore, if $(x,y)$ is on curve $A$, the image $(x+\mathfrak{p},y+\mathfrak{p})$ will be on curve $B$, because the projection map is a homomorphism of rings. – Jyrki Lahtonen Jan 22 '21 at 08:56
  • (cont'd) With that (known as reduction modulo $\mathfrak{p}$) preliminary out of the way we, at least, have a way of relating some points on $A$ with points on $B$. This relation actually preserves the group operation of the elliptic curves. So if $P$ is a point (with coordinates in $K$) on curve $A$, and $\overline{P}$ is its image on curve $B$, we have the rule $\overline{rP}=r\overline{P}$. – Jyrki Lahtonen Jan 22 '21 at 08:59
  • 2
    (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_1G$ 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}$. – Jyrki Lahtonen Jan 22 '21 at 09:04
  • (cont'd) It may well turn out that there is a unique (or only relatively few) such point with coordinates in $\mathcal{O}_K$. But I'm not sure we can do all of the above? Even if forgetting about the uncertainty in $r$. For example, the calculation of $r*G$ often takes us outside of $\mathcal{O}_K$. We can switch to projective coordinates, but at some point the non-uniqueness of $r$ will ruin the day. – Jyrki Lahtonen Jan 22 '21 at 09:09
  • While typing all of the above I did realize that there is an interesting lifting property that can possibly be solved. I'm still fairly sure that the non-uniqueness of $r$ will ruin this, for example, as an attack on the related DLP. – Jyrki Lahtonen Jan 22 '21 at 09:11
  • @JyrkiLahtonen. Wow. First of all, thank you for developing so much your answer. I get what you mean by the non-uniqueness of $r$, but what if we only try to solve for the smallest positive $r$ integer and ignore all the other solutions? Could we convert this way points from curve $B$ to the corresponding lowest $G*r$ point in curve $A$? –  Jan 22 '21 at 10:02
  • 2
    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? – kelalaka Jan 22 '21 at 16:05

1 Answers1

0

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.

fgrieu
  • 1,758