How does this formula work $(aG + bG) = (a + b) G$ in ECDSA?

Please explain how does this formula $$(aG + bG) = (a + b) G$$ work in ECDSA?

According to the source:

$$a$$ and $$b$$ are different private keys

Suppose

$$a = 3$$

$$b = 4$$

then the public key is $$Q = aG$$ and $$W = bG$$ (secp256k1)

Q = F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9

W = E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13


Now we take the formula $$(a + b)G$$

$$(3 + 4)G$$

$$7g$$

$$c = 7$$

public key $$P = cG$$

P = 5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC


Now take the formula $$(aG + bG)$$

$$(Q + W)$$

And the amount of public keys $$(Q + W)$$ will be

DDC465F353664403A152988A8BA8662FC6EEFEEEE3076EF93B2A2732D56EC2CB


Why it turns out:

DDC465F353664403A152988A8BA8662FC6EEFEEEE3076EF93B2A2732D56EC2CB


Why is the answer of this sum not this value:

5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

• $G$, $Q$, $W$ are elliptic curve points and have two coordinates each. How come you have a single integer? How are you computing $aG$ and so on? – Conrado Nov 8 '19 at 12:02

..how does this formula $$(aG+bG) = (a+b)G$$ work in ECDSA?

Perfectly well. It follows from the definition of $$kG$$ as $$\overbrace{G+\cdots+G}^{k\text{ times}}$$, associativity and commutativity of point addition. Notice that operator $$+$$ in $$(aG+bG)$$ and $$G+\cdots+G$$ is elliptic curve point addition, while operator $$+$$ in $$(a+b)$$ is addition in $$\Bbb Z$$ (signed integers) or $$\Bbb Z_n$$ (integers modulo $$n$$, where $$n$$ is the order of $$G$$).

Be confident that $$3G+4G=7G$$ holds, and if $$Q=3G$$, $$W=4G$$, $$P=7G$$ then $$Q+W=P$$.
The issue is on what arguments the point addition of the final $$+$$ is computed.

In the question, what's shown after Q = is the X coordinate $$Q_x$$ of point $$Q$$. The Y coordinate is missing. Therefore what follows Q = does not settle between two points: $$Q$$ of coordinates $$(Q_x,Q_y)$$ and $$-Q$$ of coordinates $$(Q_x,Q'_y)$$ with $$(Q_y)^2=(Q_x)^3+7\bmod p$$ (per the equation of secp256k1) and $$Q'_y=p-Q_y$$. Same issue for $$W$$ and $$P$$.

Why is the answer of this sum not this value (..)

This value ended up being the X coordinate for $$Q-W$$ (or equivalently $$-Q+W$$) instead of $$Q+W$$ as thought, due to the above. This also is the X coordinate for the base point $$G$$, because $$Q-W=3G-4G=(3-4)G=(-1)G=-G$$.

How does this formula work (aG+bG)=(a+b)G in ECDSA?

This is due to the definition of scalar multiplication of Elliptic Curves.

$$[a]g = \overbrace{g+\cdots+g}^{{a\hbox{ - }times}}$$ $$[b]g = \overbrace{g+\cdots+g}^{{b\hbox{ - }times}}$$

then $$[a+b]g = \overbrace{g+\cdots+g}^{{a+b\hbox{ - }times}} = \overbrace{g+\cdots+g}^{{a\hbox{ - }times}} + \overbrace{g+\cdots+g}^{{b\hbox{ - }times}} = [a]g+[b]g$$

Why is the answer of this sum not this value:

The addition on Elliptic Curves is different from integers and they have a geometric meaning.

We, however, arithmetically can define the addition rules in affine coordinates as;

Let $$P=(x_1,x_2)$$ and $$Q=(x_2,y_2)$$ be two point in the elliptic curve.

1. $$P+O=O+P=P$$
2. If $$x_1 = x_2$$ and $$y_1 = - y_2$$ and $$Q =(x_2,y_2)=(x_1,−y_1)=−P$$ then $$P + (-P) = O$$
3. If $$Q \neq -P$$ then the addition $$P+Q = (x_3,y_3)$$ and the coordinate can be calculated by;

\begin{align} x_3 = & \lambda^2 -x_1 - x_2 \mod p\\ y_3 = & \lambda(x_1-x_3) -y_1 \mod p \end{align}

$$\lambda = \begin{cases} \frac{y_2-y_1}{x_2-x_1}, & \text{if P \neq Q} \\[2ex] \frac{3 x_1^2+a}{2y_1}, & \text{if P = Q} \\[2ex] \end{cases}$$

So, $$[3]P$$ can be calculated as $$([2]P)+P$$, one doubling, and one addition. This is actually a hint for the double and add algorithm. Below is a simple Python function to show this and this is the addition version of the repeated-squaring method.

def double_and_add(n, x):

result = 0
double = x

for bit in bits(n):
if bit == 1:
result += double
double *= 2

return result


Note that this addition and doubling rules are generic. According to curve and used coordinates faster versions are available.

• Please give a detailed answer on an example of how scalar multiplication of elliptic curves occurs, for example, for a = 3? with parameters secp256k1 g = Point (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8, FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141) – Rozwrcd Nov 8 '19 at 12:06
• @Rozwrcd Please see the update. – kelalaka Nov 8 '19 at 13:13