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

Curve $B$ is secp256k1, assume the usual parameters for that curve.

Let $k$ be any private key, and compute the corresponding public key point $[k]G$ in curve $B$.

Now, from this point $[k]G$ in curve $B$, how can we find what the point $[k]G$ in the "real" curve $A$ is? You don't know the value for $k$, but you do know all other parameters.

Point $G$ in curve $A$ is the positive $y$ solution to the curve $A$ with $x$ equal to the $x$ value of $G$ in curve $B$.

  • $\begingroup$ Use Discrete Log. I think you were asking X and wanting Y, we call it X/Y? DLog has complexity $\mathcal{O}(\sqrt{n})$ where $n$ is the group order and for this curve, it has 13 points! $\endgroup$
    – kelalaka
    Jan 22 at 8:19
  • $\begingroup$ @kelalaka I'm not exactly sure how that could be helpful. I'm asking for the equivalent $G*r$ point in the curve over all real numbers given the $G*r$ point in the curve over the finite field. $\endgroup$ Jan 22 at 8:37
  • $\begingroup$ That is scalar multiplication, then use the addition laws, with double-and-add algorithm. $\endgroup$
    – kelalaka
    Jan 22 at 8:40
  • 1
    $\begingroup$ The general answer is that you can't since the modulo operation is destructive. Since you don't know about $k$ then you don't know how many times the scalar multiplication uses the $\mod p$. There are cases that one can lift the curve $B$ and solve the DLog problem easily there, however, secp256k1 has no such known lifting. $\endgroup$
    – kelalaka
    Jan 22 at 10:33
  • 1
    $\begingroup$ I’m voting to close this question because it is cross-posted with Math. 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:08

Browse other questions tagged or ask your own question.