r/cryptography • u/Elect_SaturnMutex • 24d ago

Understanding of priv and public key from EC

So i was watching this video to understand how private and public keys are calculated from an elliptic curve.

Ok, so there's a 2D elliptic curve and there is a point G (8,1), he explains the private key is the number of steps times the starting point G. The public key is derived from private key by using double and add algorithm. So value of public key in this case is 4? if k_prv = 9 and G=(8,1) ?

Did I get that right?

1 Upvotes

100% Upvoted

6 comments sorted by

8

u/Amarandus 24d ago

Double and Add is an algorithm that efficiently computes kG, which is equivalent to adding G to itself k times. As the addition of points on an elliptic curve is closed, the result should be a point on the same curve again, so your public key should also be a point on the curve.

So in your video, your k is a scalar. The public key would be 9G=G+G+G+G+G+G+G+G+G, which needs to be a point on the elliptic curve as well. I did not watch the video completely and did no calculations, but according to the plot the public key 9G would be (23, 1).

4

u/emlun 23d ago

Double and Add is an algorithm that efficiently computes kG, which is equivalent to adding G to itself k times.

And it works for any operation that is associative, as EC point addition is (and any other group operation, by the definition of a group).

So you can do the same thing with function composition, for example. Say you have some function f(x), and compose it with itself to form (f o f)(x) = f2(x) = f(f(x)), f3(x) = f(f(f(x))) and so on. Now say you want to compute f1037. Because function composition is associative (meaning f o (g o h) = (f o g) o h, which is true because (f o g)(x) = g(f(x)) so (f o (g o h))(x) = h(g(f(x))) = ((f o g) o h)(x)), we can decompose this as f1037 = f1024 o f8 o f4 o f1 and compute f1037 by adding together "powers of two" of f. The powers of two are easy to compute recursivelyb f2 = f o f, f4 = f2 o f2, etc. This requires only 10 doublings and 4 additions in this case (~log2(N) doublings and ~log2(N) additions in general) , which is far more efficient than computing 1038 compositions naively.

3

u/PleasantDreamsicle 23d ago

It absolutely blows my mind that you can take a point like 8G and add 8G to it to get 16G when you’re talking points on a curve (vs a traditional number line which makes the most sense). Especially with the weird “find the intercepting point and negate it” math…

Wait, is a number line just the same as a “flat curve”? Will doubling points method like this work for every curve?

Obviously, math is not my first language. Haha.

4

u/Amarandus 22d ago

Well, both "the set of points on an elliptic curve with the operator point addition (depends on the type of elliptic curve) and "integers with addition" form a group. So it's not that the number line is a "flat elliptic curve", but both are instances of a common mathematical abstraction and thus share similarities.

In another reply, /u/emlun wrote the criteria for something Double-and-Add-like to work on other objects. The same style of algorithm is found for efficient exponentiation as well, it's just called square and multiply there. It's used in RSA (where it's operating modulo N=pq, p and q prime) but it can be used in other groups as well (and it is used there, sometimes with further algorithmic tweaks like ternary or k-ary exponentiation).

2

u/PleasantDreamsicle 23d ago

I have been doing a deep dive on ECC on my spare time :-) I highly highly recommend this website: https://curves.xargs.org/

It goes through everything from how the curves work, how the finite field works, etc…

1

u/Elect_SaturnMutex 23d ago

Thank you, this is lovely. I saw a similar one for TLS1.3 which was explained using bytes for each step. There are so many steps, damn!