Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  fgrieu Apr 13 '12 at 5:13
    
Sorry, NISTs-192..521 with exp. multiplying algorithm sounds not much promising; –  ted Apr 13 '12 at 5:30
2  
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. –  MartinSuecia Apr 13 '12 at 8:15

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
An awesome answer but nothing from X9.62 about point multiplication by number. Still thank you. Cannot upvote for now. –  ted Apr 13 '12 at 5:45
    
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. –  MartinSuecia Apr 13 '12 at 8:03
    
@MartinSuecia, may i ask to receive this page by email? Thank you. –  ted Apr 13 '12 at 8:59
1  
@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 –  MartinSuecia Apr 13 '12 at 9:04
    
@MartinSuecia, Thank you –  ted Apr 14 '12 at 9:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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