Multiplicative Inverse in Point Addition/Point Multiplication

Pi-Turn

4/18/24, 8:38 AM

Walkthrough the textbook content, understand that we need to compute the slope of 2 points before can compute the new point as the result of addition.

Multiplicative inverse is part of the operation in a process to find the slope, where we know Extended Euclidean Algorithm is one of the best method to be used.

However, in order to realize the Extended Euclidean Algorithm in hardware RTL, we need to consider about when the integer go very large. Initially when I model the algorithm out in RTL, everything works fine if I simply using "/" and "%" to find the quotient and remainder.

But I don't think this is practical when we dealing with large number. Could I get a hint that any techniques we can leverage to achieve more efficient Extended Euclidean Algorithm? Does Montgomery Reduction can be leveraged here? Need some enlightenment after days of stuck.

1 + 6

elliptic-curves

cryptographic-hardware

fgrieu

4/18/24, 11:17 AM

Have you studied the [Binary Extended GCD](https://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=19) (see also [note 14.64](https://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=21)) and it's [improvements](https://eprint.iacr.org/2020/972) (link fixed)? Independent note: With a proper coordinate system, computing the multiplicative inverse needs to be performed only on the final result needed for signature generation or verification, thus is not the bottleneck as it is if performed at each point addition.

Pi-Turn

4/18/24, 1:25 PM

@fgrieu, regarding the independent note "the proper coordinate system" is only refer to certain EC? means that we only can avoid for doing multiplicative inverse at every addition point with selected EC, or more refer to certain design technique?

fgrieu

4/18/24, 1:28 PM

Two popular coordinate systems that work for any curve in Weierstrass form are [Projective coordinates](https://www.hyperelliptic.org/EFD/oldefd/projective.html) and [Jacobian coordinates](https://www.hyperelliptic.org/EFD/oldefd/jacobian.html). The speed gain can be spectacular.

Pi-Turn

4/23/24, 2:38 PM

@fgrieu, based on your earlier hint. I manage to implement formula published in the explicit formula database in hardware. However, the formula is only works for the first addition and I'm not sure how to perform the subsequent in jacobian domain without converting back and forth. Would you mind to hint me a bit on this. X3 and Y3 I got is in jacobian form now but the subsequent add is to deal with the affine coordinate, so I think i must be doing something with X3 and Y3 before can reuse the same formula i used initially?

fgrieu

4/23/24, 4:17 PM

Basic idea: starting from Cartesian coordinates $x,y$ convert to Jacobian $(X,Y,Z)←(x,y,1)$. Then perform scalar multiplication by double and add using formulas [there](https://www.hyperelliptic.org/EFD/oldefd/jacobian.html) following "2007 Bernstein/Lange, 11M + 5S + 9add + 4times2:" for add and "2007 Bernstein/Lange, 1M + 8S + 1D + 10add + 2times2 + 1times3 + 1times8:" for doubling. Then convert outcome $(X',Y',Z')$ to Cartesian per $u←Z'^{-1}\bmod p$ [using EEA, BEEA, or $u←Z'^{p-2}\bmod p$ ] then $v\gets u^2$ then $(x,y)←(v\,X',u\,v\,Y')$. A few further savings are possible.

Pi-Turn

4/24/24, 8:54 AM

@frieu, thanks! I figured out my earlier problem where I was chosen the most least expensive from the explicit formula table. It make sense that I shouldn't use formula for z1=z2=1. But when proceed to only assume z2=1 formula, it don't work as well where i don't expect this will happen. Only the costly formula which involving both Z1 and Z2 in the formula only works even I always set 1 to the Z2 in subsequent addition.

Score:2

Crypto

poncho

4/18/24, 1:01 PM

The Extended Euclidean Algorithm is not the only way to compute inverses.

Another way (if $p$ is prime) is to take advantage of this identity:

$$x^{-1} = x^{p-2} \pmod p$$

(this identity also assumes $x \ne 0$, not an issue in this case).

That is, you can also compute the inverse by performing $O(\log p)$ multiplications; if you already implement multiplication modulo $p$, this may be easier for you to implement.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Multiplicative Inverse in Point Addition/Point Multiplication

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.