0
$\begingroup$

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
$\endgroup$
  • 2
    $\begingroup$ $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? $\endgroup$ – Conrado Nov 8 at 12:02
1
$\begingroup$

..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$.

$\endgroup$
0
$\begingroup$

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.

Geometric interpretation of addition on a Weierstrass curve

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Rozwrcd Nov 8 at 12:06
  • $\begingroup$ @Rozwrcd Please see the update. $\endgroup$ – kelalaka Nov 8 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.