ECDSA (Elliptical Curve Digital Signature Algorithm) uses [[Knowledge Base/Cryptography/Elliptical Curve Cryptography/! Overview|! Overview]] to implement [[DSA]] (Digital Signature Algorithm). This is used to verify the authenticity and integrity of messages. # Components ECDSA uses the following components: * **Private key:** An integer ($d$) in the range of $[1, n - 1]$, where $n$ is the curve order. * **Public key:** A point defined by $Q = d \times G$, where $G$ is the curve's base point. * **Hash function:** This is used to produce the message digest. * **Curve parameters:** P-256, SECP256K1, SECP384R1, or another standard vetted curve. # Signing Given a message $m$ and private key $d$: 1. Compute $e = HASH(m)$ and reduce to integer $z$ (bit-length $\le$ curve order). 2. Pick a random $k$ in $[1, n - 1]$. _This must be unique per signature_. 3. Compute point $(x_1, y_1) = k \times G$. Set $r = x_1 \mod n$. If $r = 0$, restart. 4. Compute $s = k^{-1} \times (z + r \times d) \mod n$. If $s = 0$, restart. 5. Resulting pair $(r, s)$ is the signature. $k$ must be private and unguessable and should never be reused, or the whole private key is compromised. # Verification Given $m$, signature $(r, s)$, and public key $Q$: 1. Check if $1 \le r, s < n$. If not, reject the signature. 2. Compute $e = HASH(m)$ and reduce to $z$. 3. Compute $w = s^{-1} \mod n$. 4. Compute $u_1 = z \times w \mod n$. 5. Compute $u_2 = r \times w \mod n$. 6. Compute $(x_1, y_1) = u_1 \times G + u_2 \times Q$. 7. If $r = x_1 \mod n$, the signature is valid.