1
$\begingroup$

I am currently trying to learn more about Elliptical curve crypthography and have finally started to get things working and undestanding the different pieces.

I've written a small project in C# and are currently testing it using really big numbers (the .NET BigInteger class). So far I've implemented the key generation algorithm, the point addition, doubling, encryption and decryption.

Now my problem is the key generation. The formula for generating a key is:

Q = d * G

Where Q is the public key, d is the private key and G the generator point.

If I for example want to use a 256 bit private key n would become a BigInteger with 78 numbers in it right (2^256)?

Now to calculate Q this will take a lot of time since it means I will need to perform point addition an insane number of times unless I'm not understanding something about it.

How is this accomplished in practise? Am I thinking about it in the wrong way or will I need to perform the point addition up to 2^256 times? What is the expected amount of time for modern computer to generate the key-pair?

Thank you!

Improve this question
$\endgroup$
6
  • $\begingroup$ Usually, even a naïf algorithm is OK. The key-generation algorithm is run only once. Btw it exists some way to speed up the scalar multiplication. $\endgroup$
    – ddddavidee
    Nov 25, 2014 at 9:34
  • 2
    $\begingroup$ @ddddavidee: in this case, the naive algorithm (perform $d-1$ point additions) is so expensive that it can't even be done one. $\endgroup$
    – poncho
    Nov 25, 2014 at 14:34
  • $\begingroup$ You'd use essentially the same algorithms described at Exponentiation by squaring on Wikipedia, except that the basic operation is addition instead of multiplication. This means you only need about 256 squaring and 256 multiplications. $\endgroup$
    – CodesInChaos
    Nov 25, 2014 at 17:30
  • $\begingroup$ @poncho: I agree, that was more a general comment on key generation that focused on this case, I was planning to do a survey/list on faster algorithms but your answer came before! ;-) $\endgroup$
    – ddddavidee
    Nov 26, 2014 at 8:20
  • $\begingroup$ Concerning the naive approach: If you could do it that way, then brute forcing the key in the same manner would also be possible. Double-and-add is your only choice. (and its optimizations, especially NAF and wNAF are worth looking at) $\endgroup$
    – tylo
    Nov 27, 2014 at 12:30

1 Answer 1

Reset to default
5
$\begingroup$

Now to calculate Q this will take a lot of time since it means I will need to perform point addition an insane number of times unless I'm not understanding something about it.

You're missing a point; elliptic curve point addition is associative; that is, for any three points $A, B, C$, we have:

$$(A + B) + C = A + (B+C)$$

Now, why is this a big deal? Well, we can exploit that compute $G+G+G+...+G$ surprisingly quickly.

Our first step is to compute $G+G$ (which is $2G$); that's straight-forward:

$2G = G+G$

One point addition, no improvement over the naive method. Ok, let us compute $4G = G+G+G+G$. By the associate law, that is:

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

So, we can compute $4G$ with two point additions, one to compute $2G$ and one to take $2G$ and use it to compute $4G$.

Then, to compute $8G$, that's $8G = 4G + 4G$, just one more point addition.

In general, we can compute $2^kG$ (which is $G$ added to itself $2^k$ times) using only $k$ point additions.

And, what do we do if $d$ doesn't happen to be a power of 2? Well, by adding in previous results at various steps (e.g. $5G = 4G + G$), we can accommodate those with some additional expense.

One straight-forward way to extend this to any $d$ is found here; we know more efficient methods (some of which are also on that page); however it is quite reasonable, and a good place to start.

With this technique, you can generate an elliptic curve private key in milliseconds (and, this method of computing point multiplication will also be used when you use the key to actually do something)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wow thank you very much poncho! So this is the so called double-and-add method then? So in my case the easiest way to implement this method would be to "convert" my very big private key to binary form and do the algorithm you linked to? Thanks! $\endgroup$
    – Johan O
    Nov 25, 2014 at 17:31
  • $\begingroup$ Just wanted to add that I've implemented this now and it worked beautifully! Thank you my friend :D ! $\endgroup$
    – Johan O
    Nov 27, 2014 at 10:46

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.