In Elliptic Curve Addition, where does the second point come from?

Question

I have a limited understanding of elliptic curve terminology, but if you can bear with me I'd like to ask this question anyway. I'll start with what I understand...

• You do EC multiplication with the private key to get the public key.
• EC Multiplication is just EC Addition (done over and over again).
• EC Multiplication can be achieved through a combination of EC Addition and EC Double (for speed).

From the perspective of the graph:

• EC Double = draw a tangent on your current point, take the intersect, invert it.
• EC Addition = draw a line through your current point and a second point, take the intersect, invert it.

EC Double I understand -- you have your current point and you draw a tangent -- no need for any extra points on the curve to get the intersect.

But in EC Addition, if I have my current point, where does the second point on the curve come from when attempting to draw a line across the graph to find the next intersect?

Answer 1

As in Christopher's answer, in ECDSA key generation you always multiply the private key with the generator point G.

When doing addition, the second point is whatever you need to add to get what you want.

For example, if you want to find 3*G, first you do a doubling: 2*G. Then you do addition: (2*G)+G.

If you want to find 14*G, first you do some doublings:

2*G
4*G = 2*(2*G)
8*G = 2*(4*G)

Then some additions:

12*G = (8*G)+(4*G)
14*G = (12*G)+(2*G)

Not that this takes a total of 5 operations, rather than 13 as with naively adding G to itself 14 times.

Equivalently, you can do the following, with the advantage of always having to remember only the last step:

2*G
3*G = 2*G+G
6*G = 2*(3*G)
7*G = 6*G+G
14*G = 2*(7*G)

This is exactly what you do when you want to exponentiate ordinary numbers, such as modular integers:

x^2
x^3 = x^2*x
x^6 = (x^3)^2
x^7 = x^6*x
x^14 = (x^7)^2

With a total of 5 multiplications instead of 13.

Answer 2

In elliptic curve cryptography, participants need to agree on certain parameters. For example, you need to agree on which curve to use.

One of those parameters is called the base point generator, it is a point on the curve.

You do EC multiplication with the private key to get the public key

Correct, PubKey = PrivKey*G = G+G+G+... PrivKey times where G is the agreed-upon generator. Does this clarify things?

You can see its definition in SEC 2 in section 2.7.1.

Answer 3

About EC double and addition, scalar multiplcation, from a graphical ans easy point of view.

Addition 2 points: P+R = Q

Draw a line crossing these 2 points, -Q is the 3rd point crossed by the curve. Mathematically, any line crossed EC 3 times. (If P!=0, R!=0 and P!=+/-R) You don't have one point, but 2 when you perform an addition.

Double a point: 2*P = Q

This is a special case of the previous (R=P) Draw a tangent line from P and you -Q is the second point of the line crossed by the line. Mathematically, any tangent line crossed EC once. (If P!=0) You can also view that as two very close points: the common crossing line (the addition line) will become the tangent as the points come closer and closer.

Multiply a point by a scalar:

Combine addition and doubling, basic method is given by Rosenfeld's answer. There are a lot of methods with lot of variants to speed it up (NonAdjacent, Montgomery ladder, 3-basis with negative, sliding window,...).

Private key and public key:

Each curve has its own parameter and "G" is one parameter and can be see as the "unit" or the scale (like 1 in integer number).

We just use the discret logarithm problem from EC: k*G=R

k is private, R is public. R can be computed easily from k with the explanation above. But it is nearly impossible to compute or guess k from R. In Bitoin, the address "1xyz" is a base58 encoded of a hash derived from R. Something like : base58( hash( encodedR ) )

Then we use further algorithm to sign and verify. Mostly ECDSA. To make a signature you need k. To verify you need R. Sometimes for text message in the bitcoin world, R is recovered from the signature, and hash(R) is compared to the address provided (must match).

That should help you: