1
$\begingroup$

Given a secp256k1 point $P$ with scalar 3 where:

$P = 3*G$

You get a point with co-ordinates: x = 112711660439710606056748659173929673102114977341539408544630613555209775888121 y = 25583027980570883691656905877401976406448868254816295069919888960541586679410 When I calculate the point $-P$, I get: x = 112711660439710606056748659173929673102114977341539408544630613555209775888121 y = 90209061256745311731914079131285931446821116410824268969537695047367247992253 Now my question is, if I take the x-coodinate above and use it in the equation: $y^2 = x^3 + 7$

Calculate rhs: $rhs = (x^3 + 7) \bmod p$

Since: $p \bmod 4 \equiv 3$

for the left hand side, we use the equation: y = pow(rhs, (p + 1) // 4, p)

From the above why do I get the y value of $-P$

I have tested this with multiple scalar values and sometimes I get the right value for y sometimes I get the value for $-y$. Does Secp256k1 randomly select values for y?

  • 1 : correct,
  • 2 : correct,
  • 3 : wrong,
  • 4 : correct,
  • 5 : wrong,
  • 6 : correct,
  • 7 : wrong,
  • 8 : wrong,
  • 9 : correct,
  • 10: correct,
$\endgroup$

1 Answer 1

1
$\begingroup$

Because the actual theorem is like this; if $p \equiv 3\pmod{4}$ then the square root of $y$ can be found as;

$$x \equiv \pm y^{(p+1)/4}\pmod{p}$$

There can be no root at all. There can be one root ( $y = 0$). In the other cases, we have two roots that are negative of each other in the modulus $p$.

The theorem doesn't say which one is the one you need. It is your job to determine this. This may create conflict as did in Bitcoin, and now Bitcoin uses Bitcoin Taproot (bip-0340) so the both cases is your private key.

$\endgroup$
5
  • $\begingroup$ A similar question but not dupe ; How to determine the prefix of a SECP256K1 compressed public key $\endgroup$
    – kelalaka
    Commented Jun 11 at 11:42
  • $\begingroup$ My thinking was that, since for -P you have to explicitly compute (n - k)*G (with an extra step), then computing P should be the first y get before going an extra step to compute -y % p. $\endgroup$
    – dred28
    Commented Jun 11 at 14:37
  • $\begingroup$ Given $P = (x,y)$ in Cartesian coordinates, finding $-P$ is easy since $-P = (x, -y)$. The point addition from an Abelian group and $P + (-P) = \mathcal{O}$. You can compute $-P = [n-k]G$, however, first, this is unnecessary if you have $P$, second you will get the $y$, too. If one has only $x$ coordinate, this is due to the fast addition chains ( Lucas ) and is commonly used in DHKE where only $x$ coordinate is used. Even in this case, there are formulas to extract the $y$ given $x(P), y(P), x([n]P)$ where $x()$ means the x-coordinate. $\endgroup$
    – kelalaka
    Commented Jun 11 at 15:44
  • $\begingroup$ Thank you for your response, appreciate a lot, this clears up a lot in the subject. $\endgroup$
    – dred28
    Commented Jun 11 at 16:38
  • $\begingroup$ It must be, $y([n]P)$, given... on the last part of the comment. $\endgroup$
    – kelalaka
    Commented Jun 11 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.