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!

$\endgroup$
  • $\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 '14 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 '14 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 '14 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 '14 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 '14 at 12:30
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)

$\endgroup$
  • $\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 '14 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 '14 at 10:46

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.