6
$\begingroup$

I'm currently trying to implement ecdsa and the first problem i met --
multiply an elliptic curve point by a number.

As far as i understand X9.62 gives some recommendation for doing it but i haven't managed to find anything.
It would be great to see some program like algorithm.

P.S.
Any help is appreciated. Sorry for my English and thanks.

|improve this question
$\endgroup$
  • $\begingroup$ Once you can add two points, multiplication by a number follows. The simplest algorithm to multiply by n>0 uses n-1 additions, much like 3*19 is 19+19+19. This can be made O(Log(n)) by methods analog to these for exponentiation. $\endgroup$ – fgrieu Apr 13 '12 at 5:13
  • $\begingroup$ Sorry, NISTs-192..521 with exp. multiplying algorithm sounds not much promising; $\endgroup$ – ted Apr 13 '12 at 5:30
  • 2
    $\begingroup$ I think you need to understand the idea about groups, and that "exponentiation" (when the group operation is called multiplication) and "multiplication by number" (when the group operation is called addition - as is the case for Elliptic Curve groups) are actually exactly the same thing. $\endgroup$ – MartinSuecia Apr 13 '12 at 8:15
7
$\begingroup$

Well, you understand that Elliptic Curves define an operation on points we denote as +; that is, if $A$ and $B$ are two (not necessarily distinct) points, then $A+B$ is a third point (which will be distinct unless either $A$ or $B$ are the 'point-at-infinity'). If $A$ and $B$ are the same, the operation is usually called doubling instead of addition.

Now, by "multiplying an elliptic curve point by a number" (or point multiplication), what we mean is adding the point to itself the specified number of times. That is:

$\displaylines{kG =}{\underbrace{G + G + G + ... + G}}$

where exactly k $G$'s are added together.

Now, the naive implementation is just to perform $k-1$ point additions; however, because the integers we're multiplying by are huge, this is not practical.

However, point addition is associative (that is, $(A+B)+C = A+(B+C)$, that means that we can use less than $k-1$ additions; for example, to compute $8G$, we can note that:

$2G = G + G$

$4G = G + G + G + G = (G + G) + (G + G) = 2G + 2G$

$8G = 4G + 4G$

and hence we've computed $8G$ using only three additions.

One straight-forward (decent, but nonoptimal) method to do this (assuming, of course, that you have already implemented the Elliptic Curve addition function) is to use the binary addition method; just note that the Wiki article talks about 'multiplication', while you're doing addition; that is merely a difference in syntax.

|improve this answer
$\endgroup$
  • $\begingroup$ An awesome answer but nothing from X9.62 about point multiplication by number. Still thank you. Cannot upvote for now. $\endgroup$ – ted Apr 13 '12 at 5:45
  • $\begingroup$ Page 91 in ANSI X9.62 defines and describes a way to perform point multiplication (they call it scalar multiplication). This is slightly different from ponchos method, choose whichever one you want. $\endgroup$ – MartinSuecia Apr 13 '12 at 8:03
  • $\begingroup$ @MartinSuecia, may i ask to receive this page by email? Thank you. $\endgroup$ – ted Apr 13 '12 at 8:59
  • 1
    $\begingroup$ @Ted: The page is included in X9.62 2005 version, which can be bought by ANSI. Wikipedia gives enough to understand and implement point multiplication though: en.wikipedia.org/wiki/Elliptic_curve_point_multiplication $\endgroup$ – MartinSuecia Apr 13 '12 at 9:04
  • $\begingroup$ This answer would be improved if it didn't leave it up to the reader to figure out how to use the binary method for exponentiation to do multiplication. While the answer's author may find it trivial to understand how to adapt the algorithm from exponentiation to multiplication, it is not necessarily as obvious to the reader of this answer. $\endgroup$ – Micah Zoltu Aug 30 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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