Elliptic Curve DSA (ECDSA)
The Elliptic Curve Digital Signature Algorithm (ECDSA) is a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.
Basics
Parameters
| Name | Description |
|---|---|
| CURVE | The elliptic curve field and equation used |
| \(G\) | A point on the curve that generates a subgroup of large prime order n |
| \(n\) | Integer order of \(G\), means that \(nG=\mathcal{O}\), where \(\mathcal{O}\) is the identity element |
| \(d_{A}\) | The private key (randomly selected) |
| \(Q_{A}\) | The public key \(d_{A}\times G\) (calculated by elliptic curve) |
| \(m\) | The message to send |
Public key recovery
Given a message \(m\) and a signature \((r,s)\) on that message, one can (potentially) recover the associated public key as follows.
- Verify that \(r\) and \(s\) are integers in \([1,n-1]\). If not, the signature is invalid.
- Calculate a curve point \(R=(x_{1},y_{1})\) where \(x_{1} = r + kn < p \; | \; \forall k \in \mathbb{N}\).
- Calculate \(e={\textrm {HASH}}(m)\), using the same function used during signature generation.
- Let \(z\) be the \(L_{n}\) leftmost bits of \(e\).
- Calculate \(u_{1}=-zr^{-1}\,{\bmod {\,}}n\) and \(u_{2}=sr^{-1}\,{\bmod {\,}}n\).
- Calculate the curve point \(Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R\).
Attacks
Nonce reuse
Insecure nonce
Message not hashes
Resources
Last updated on