ECDSA

Notation

$q$ is the order of the elliptic curve group $\mathbb{G}$.
$g$ is the generator of $\mathbb{G}$.
$.x$ refers to the x co-ordinate of a point.
Let $H_{q}: \{0,1\}^{*} \rightarrow \mathbb{Z}_{q}$ be a hash function modeled as a random oracle.

$Gen(1^{\kappa}) \rightarrow (sk, pk)$:
- Choose $sk \leftarrow \mathbb{Z}^{*}_{q}$
- Compute $pk \leftarrow g^{x}$
$Sign(sk, m) \rightarrow \sigma$:
- Choose $k \leftarrow \mathbb{Z}^{*}_{q}$
- Compute $r \leftarrow g^{k}.x \mod{q}$
- Compute $m' \leftarrow H_{q}(m)$
- Compute $s \leftarrow (k^{-1}(m' + r\cdot sk)) \mod{q}$
- Output $\sigma := (r,s)$
$Verify(pk, m, \sigma) \rightarrow \{0,1\}$:
- Compute $m' \leftarrow H_{q}(m)$
- Output $(g^{m\cdot s^{-1}}\cdot pk^{r\cdot s^{-1}}).x \mod{q} = r$
Correctness check:
- $(g^{m\cdot s^{-1}}\cdot pk^{r\cdot s^{-1}}).x \mod{q}$ is
- $g^{s^{-1}\cdot (m+ sk \cdot r)}.x \mod{q}$ is
- $g^{s^{-1}\cdot s \cdot k}.x \mod{q}$ is
- $g^{k}.x \mod{q}$ is
- $r$