3
$\begingroup$

I'm working on a zero knowledge proof system that uses ECC over $\mathbb{Z}_p$ (currently using NIST P-256 since mbed TLS doesn't support group operations on Curve25519, but the problem should be general). Part of this involves calculating the inverse of a group element. For some point $a=(x,y)$ I calculate

$$a^{-1}=\left(x, \text{mod-inv}(y)\right)$$

where $\text{mod-inv}$ is the modular inverse with respect to $p$, the prime of the group. This seems to be correct; I've verified that $a + a^{-1} = 0$, i.e. that performing the group operation on the two points results in the point-at-infinity. The problem is that $a^{-1}$ doesn't seem to actually be a point on the curve! For example, on NIST P-256 I have the points

$$ a = (59480773761400674036851792405749936131635847707891677548254384759310415166102, 54215024246639578077221526092518955906039351892854133302257636019166433313823),\quad a^{-1} = (59480773761400674036851792405749936131635847707891677548254384759310415166102, 112829638001096970751397729889429500563993392391887472719416027848261694765589)$$.

$a + a^{-1} = 0$ (https://i.stack.imgur.com/VTYHb.jpg), but letting $a^{-1} = (x,y)$ and $A,B$ be the appropriate constants for the curve,

$$y^2 = 4361752682281060789769969552305091818972826646482745173947303219865743305577, x^3-Ax+B = 108077544024096556861625085656772704192358526678289221948404493713765226661298$$

which means that $a^{-1}$ is not on the curve. Is this to be expected? Am I somehow calculating the inverse incorrectly? Thanks for any help!

Edit: Changed to additive notation for the group operation

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ You got it wrong: the inverse of a point $(x,y)$ is the point $(x, -y)$, not $(x, y^{-1})$ $\endgroup$
    – poncho
    Jun 9, 2015 at 19:43
  • 1
    $\begingroup$ It would make more sense if you wrote your group operation additively. $\endgroup$
    – mikeazo
    Jun 9, 2015 at 19:46
  • $\begingroup$ So what are you looking for? The second point with the same x-coordinate? Or a generic Point $P$ such that $Q+P+P^{-1}=Q$? $\endgroup$
    – SEJPM
    Jun 9, 2015 at 19:47
  • 2
    $\begingroup$ Or (to follow up Mike's comment) if you do insist on writing it multiplicatively, be consistent about it. When written multiplicatively, the group identity is written as 1, not 0. The equation $a \cdot a^{-1} = 0$ looks weird... $\endgroup$
    – poncho
    Jun 9, 2015 at 19:51

1 Answer 1

Reset to default
4
$\begingroup$

poncho has it right, I was calculating the inverse incorrectly. The inverse of a point $(x,y)$ is $(x, -y)$. It just so happens that $(x,y) + (x, y^{-1}) = 0$, but this was a red herring. Thanks!

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ I suspect the library you were using used this logic during addition: "if the x-coordinates are the same, then check the y-coordinates. If they're the same, then he's doing a doubling, if not, he's adding the inverses, and so return the PoI (aka the identity group member aka 0)". So, your code returned 0, not because the math worked out, but that's just what the logic happened to do when fed invalid input $\endgroup$
    – poncho
    Jun 9, 2015 at 19:54

Your Answer

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

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