# ECDSA

secp256k1

* Group order $\phi = 115792089237316195423570985008687907852837564279074904382605163141518161494337$ (256 bits)

* Field modulus $f = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ (256 bits)

## Faster combined scalar multiplication

One of the most expensive parts of signature verification are the elliptic curve scalar multiplications

$$
Q = u_1G + u_2P
$$
where G is the public generator point and P is the signer's public key.

Instead of computing two elliptic curve scalar multiplications, we can combine these into a single combined scalar multiplication algorithm and halve the number of elliptic curve point doublings.

Let $n$ be the number of bits in the order $\phi$ of the elliptic curve group. It works like this

>$$
\begin{aligned}
&~\mathtt{combined}\mathtt{\_double\_and\_add(}u, v, ~P\mathtt{) -> CurvePoint} ~\{\\
~&~~~~Q \leftarrow G + P \\
~&~~~~R \leftarrow \mathcal{O} \\
~&~~~~\mathtt{for} ~i \in [0, n) \\
~&~~~~~~~~R \leftarrow 2 \cdot R \\
~&~~~~~~~~\mathtt{if} ~u_i ~\wedge v_i \\
~&~~~~~~~~~~~~R \leftarrow R + Q \\
~&~~~~~~~~\mathtt{else~ if} ~u_i \\
~&~~~~~~~~~~~~R \leftarrow R + G \\
~&~~~~~~~~\mathtt{else~ if} ~v_i \\
~&~~~~~~~~~~~~R \leftarrow R + P \\
~&~~~~R \\
~&\}
\end{aligned}
$$

Total cost is:
* Additions: $3n/4 + 1$ (on average)
* Doubles: $n$

The cost of the naive algorithm, performing the scalar multiplications separately is
* Additions: $n + 1$ (on average)
* Doubles: $2(n - 1)$

## Anythings else?

### Windowing

Is it possible to do some precomputation and windowing with the combined algorithm in order to reduce the number of additions?

### GLV endomorphism

We could leverage the combined algorithm with an *endomorphism*.

Suppose there an efficient endomorphism $\zeta$, such that $\zeta(Q)$ corresponds to $\lambda Q ~~\forall \in \mathcal{E}(\mathbb{F_p})$.

We have scalar $v = v_1 + \lambda v_2$ where $v_1$ and $v_2$ are half the number of bits, i.e., $n/2$.

Perform half-sized multiplications

$$
v_1G + v_2(\zeta(G))
$$

If so, then we can use the above combined elliptic curve scalar multiplication to get costs:
* Additions: $0.375 \cdot n + 1$
* Doubles: $n/2$