In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.

As with elliptic-curve cryptography in general, the bit size of the private key believed to be needed for ECDSA is about twice the size of the security level, in bits. For example, at a security level of 80 bits—meaning an attacker requires a maximum of about ${\displaystyle 2^{80}}$ operations to find the private key—the size of an ECDSA private key would be 160 bits. On the other hand, the signature size is the same for both DSA and ECDSA: approximately ${\displaystyle 4t}$ bits, where ${\displaystyle t}$ is the exponent in the formula ${\displaystyle 2^{t}}$, that is, about 320 bits for a security level of 80 bits, which is equivalent to ${\displaystyle 2^{80}}$ operations.

Suppose Alice wants to send a signed message to Bob. Initially, they must agree on the curve parameters ${\displaystyle ({\textrm {CURVE}},G,n)}$. In addition to the field and equation of the curve, we need ${\displaystyle G}$, a base point of prime order on the curve; ${\displaystyle n}$ is the additive order of the point ${\displaystyle G}$.

The order ${\displaystyle n}$ of the base point ${\displaystyle G}$ must be prime. Indeed, we assume that every nonzero element of the ring ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ is invertible, so that ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ must be a field. It implies that ${\displaystyle n}$ must be prime (cf. Bézout's identity).

Alice creates a key pair, consisting of a private key integer ${\displaystyle d_{A}}$, randomly selected in the interval ${\displaystyle [1,n-1]}$; and a public key curve point ${\displaystyle Q_{A}=d_{A}\times G}$. We use ${\displaystyle \times }$ to denote elliptic curve point multiplication by a scalar.

For Alice to sign a message ${\displaystyle m}$, she follows these steps:

As the standard notes, it is not only required for ${\displaystyle k}$ to be secret, but it is also crucial to select different ${\displaystyle k}$ for different signatures. Otherwise, the equation in step 6 can be solved for ${\displaystyle d_{A}}$, the private key: given two signatures ${\displaystyle (r,s)}$ and ${\displaystyle (r,s')}$, employing the same unknown ${\displaystyle k}$ for different known messages ${\displaystyle m}$ and ${\displaystyle m'}$, an attacker can calculate ${\displaystyle z}$ and ${\displaystyle z'}$, and since ${\displaystyle s-s'=k^{-1}(z-z')}$ (all operations in this paragraph are done modulo ${\displaystyle n}$) the attacker can find ${\displaystyle k={\frac {z-z'}{s-s'}}}$. Since ${\displaystyle s=k^{-1}(z+rd_{A})}$, the attacker can now calculate the private key ${\displaystyle d_{A}={\frac {sk-z}{r}}}$.

This implementation failure was used, for example, to extract the signing key used for the PlayStation 3 gaming-console.