Elliptical curve cryptography key generation time 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!
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)