<p>In elliptic curve cryptography, participants need to agree on certain parameters. For example, you need to agree on <em>which</em> curve to use.</p>

<p>One of those parameters is called the <em>base point generator</em>, it is a point on the curve.</p>

<blockquote>
  <p>You do EC multiplication with the private key to get the public key</p>
</blockquote>

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

<p>You can see its definition in <a href="http://www.secg.org/SEC2-Ver-1.0.pdf#page=21" rel="nofollow">SEC 2 in section 2.7.1</a>.</p>

CC BY-SA 3.0
2015-05-08T11:40:54.743Z
This is helpful (as always, Christopher), but I'm still unsure about the visual procedure of Addition on the graph. For example, if I had a private key of 2, my initial thought is to do G+G. Using EC addition, this would involve drawing a line through the curve (starting at G), using a second point to form the slope, and finally hitting a third point (the intersect). But if I'm starting at G, I don't know what is giving me the slope of the line I need to draw.
inersha
CC BY-SA 3.0
2015-05-08T15:52:55.157Z
@inersha G+G is the same as 2*G—it's an EC double operation, so (as you noted in your original question) its a tangent line at G.
Christopher Gurnee
CC BY-SA 3.0
2015-05-07T17:56:41.223Z
2015-05-07T17:56:41.223Z
Christopher Gurnee
<p>About EC double and addition, scalar multiplcation, from a graphical ans easy point of view.</p>

<p>Addition 2 points: P+R = Q </p>

<p>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.</p>

<p>Double a point: 2*P = Q</p>

<p>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.</p>

<p>Multiply a point by a scalar:</p>

<p>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,...).</p>

<p>Private key and public key:</p>

<p>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).</p>

<p>We just use the discret logarithm problem from EC: k*G=R</p>

<p>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 ) ) </p>

<p>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).</p>

<p>That should help you:
<a href="https://i.sstatic.net/N5e4s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/N5e4s.png" alt="EC computation"></a></p>

CC BY-SA 3.0
2015-08-01T23:47:25.250Z
2015-08-01T23:47:25.250Z
antonio-fr
<p>As in Christopher's answer, in ECDSA key generation you always multiply the private key with the generator point G.</p>

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

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

<p>If you want to find 14*G, first you do some doublings:</p>

<pre><code>2*G
4*G = 2*(2*G)
8*G = 2*(4*G)
</code></pre>

<p>Then some additions:</p>

<pre><code>12*G = (8*G)+(4*G)
14*G = (12*G)+(2*G)
</code></pre>

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

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

<pre><code>2*G
3*G = 2*G+G
6*G = 2*(3*G)
7*G = 6*G+G
14*G = 2*(7*G)
</code></pre>

<p>This is exactly what you do when you want to <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow">exponentiate ordinary numbers</a>, such as modular integers:</p>

<pre><code>x^2
x^3 = x^2*x
x^6 = (x^3)^2
x^7 = x^6*x
x^14 = (x^7)^2
</code></pre>

<p>With a total of 5 multiplications instead of 13.</p>

CC BY-SA 3.0
2015-05-08T11:32:10.330Z
Thank you. To solidify my understanding... | 1. Addition always involves the use of G (the generator point) along with the current point. | 2. Every Multiplication begins with a Double, as it's not possible to perform addition to get from G to 2G.
inersha
CC BY-SA 3.0
2015-05-08T13:50:42.457Z
@inersha - 1. True, overall. In the binary multiplcation variant I presented, you either do doubling or addition with G. But more generally (such as when using optimal addition chains), you can add any two arbitrary multiples of G. 2. Yes, you'll always start with doubling G. But I wouldn't say that "addition is impossible" - doubling _is_ addition (2*G = G+G), it's just that in EC addition, the formula for adding a point to itself is different than for adding distinct points.
Meni Rosenfeld
CC BY-SA 3.0
2015-05-09T02:05:04.003Z
`This is exactly what you do when you want to exponentiate ordinary numbers`: wow, this finally clicked with me! I'm extremely capable with algebraic eqns, exponents etc but the math for modular arithmetic seems so "removed" (for lack of a better term) from e non-modular varieties. I suppose it's the confusing notion that *addition* and *doubling* is actually nothing of the sort, and is moreso lingo (at least that's my understanding)
Wizard Of Ozzie
CC BY-SA 3.0
2015-05-09T13:11:36.533Z
@inersha Meni Rosenfeld's answer is excellent IMO, but I just wanted to briefly warn you that this exact method isn't used in (decent) crypto libraries. You can use faster methods if speed is your primary concern, or you can choose safer methods if reliance against side-channel attacks is your primary concern. (It's still a good answer, though!)
Christopher Gurnee
CC BY-SA 3.0
2015-05-08T08:35:14.067Z
2015-05-10T09:12:18.297Z
2015-05-10T09:12:18.297Z
Meni Rosenfeld
<p>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...</p>

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

<p>From the perspective of the graph:</p>

<ul>
<li><strong>EC Double</strong> = draw a tangent on your current point, take the intersect, invert it.</li>
<li><strong>EC Addition</strong> = draw a line through your current point and a <em>second point</em>, take the intersect, invert it.</li>
</ul>

<p>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. </p>

<p><strong>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</strong>?</p>

CC BY-SA 3.0
2015-08-02T11:52:16.197Z
Looking just at the question title, I was inclined to answer: "When adding two numbers, where does the second number come from?". You should probably clarify that you're talking about public key creation.
Pieter Wuille
<ecdsa>
In Elliptic Curve Addition, where does the second point come from?
inersha
# In Elliptic Curve Addition, where does the second point come from?

(Asked by: username_0 on 2015-05-07)

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**?

**Tags:** ecdsa

> **Comments:**
> **username_1**: Looking just at the question title, I was inclined to answer: "When adding two numbers, where does the second number come from?". You should probably clarify that you're talking about public key creation.  

---

## 3 answers

### Answer by username_4 on 2015-05-08. Score: 3 | Accepted answer

As in username_2'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](https://en.wikipedia.org/wiki/Exponentiation_by_squaring), 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.

> **Comments:**
> **username_0**: Thank you. To solidify my understanding... | 1. Addition always involves the use of G (the generator point) along with the current point. | 2. Every Multiplication begins with a Double, as it's not possible to perform addition to get from G to 2G.  
> **username_4**: @username_0 - 1. True, overall. In the binary multiplcation variant I presented, you either do doubling or addition with G. But more generally (such as when using optimal addition chains), you can add any two arbitrary multiples of G. 2. Yes, you'll always start with doubling G. But I wouldn't say that "addition is impossible" - doubling _is_ addition (2*G = G+G), it's just that in EC addition, the formula for adding a point to itself is different than for adding distinct points.  
> **username_5**: `This is exactly what you do when you want to exponentiate ordinary numbers`: wow, this finally clicked with me! I'm extremely capable with algebraic eqns, exponents etc but the math for modular arithmetic seems so "removed" (for lack of a better term) from e non-modular varieties. I suppose it's the confusing notion that *addition* and *doubling* is actually nothing of the sort, and is moreso lingo (at least that's my understanding)  
> **username_2**: @username_0 username_4 username_4's answer is excellent IMO, but I just wanted to briefly warn you that this exact method isn't used in (decent) crypto libraries. You can use faster methods if speed is your primary concern, or you can choose safer methods if reliance against side-channel attacks is your primary concern. (It's still a good answer, though!)  

---

### Answer by username_2 on 2015-05-07. Score: 3

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](http://www.secg.org/SEC2-Ver-1.0.pdf#page=21).

> **Comments:**
> **username_0**: This is helpful (as always, username_2), but I'm still unsure about the visual procedure of Addition on the graph. For example, if I had a private key of 2, my initial thought is to do G+G. Using EC addition, this would involve drawing a line through the curve (starting at G), using a second point to form the slope, and finally hitting a third point (the intersect). But if I'm starting at G, I don't know what is giving me the slope of the line I need to draw.  
> **username_2**: @username_0 G+G is the same as 2*G—it's an EC double operation, so (as you noted in your original question) its a tangent line at G.  

---

### Answer by username_3 on 2015-08-01. Score: 2

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 username_4'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:
[![EC computation](https://i.sstatic.net/N5e4s.png)](https://i.sstatic.net/N5e4s.png)


---

