Skip to content

Elliptic Curve Digital Signature Algorithm

Table of contents

Open Table of contents

What it is

The Elliptic Curve Digital Signature Algorithm (ECDSA) is a standard that’s used to generate digital signatures over arbitrary messages. Such digital signatures can then be verified by a third party in a non-interactive way.

How it works

Our example assumes that Alice wants to create a digital signature for a message mm which is then verified by Bob.

We’ll be working with the Elliptic Curve EE that is of order qq and has a generator GG. All calculations are done mod q\bmod\ q if not stated otherwise.

As a first step, Alice generates her private key aa by sampling a random value from Zq\mathbb{Z}_q. Once done, she derives the public key AA by multiplying her private key aa with the generator GG:

a$Zqa \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q A=aGA = aG

Alice then samples another, random value kk from Zq\mathbb{Z}_q that’s called the “nonce” (number used once). It’s of utmost important that this value is truly random and never reused.

Next up, the value RR is derived by multiplying kk with the generator GG:

k$Zqk \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R=kGR = kG

Given that the value RR is a point on the Elliptic Curve it has an xx- and yy-coordinate. Alice can therefore define the value rr as the xx-coordinate of RR:

r=Rxr = R_x

If r=0r = 0, Alice needs to discard kk and sample another, random nonce kk and derive RR and rr as she did before. This has to be done until r0r \ne 0.

Alice now needs to turn the message mm she wants to sign into a representation that can be “mapped onto” the Elliptic Curve EE. This can be done by hashing mm via a cryptographic hash function HH and interpreting its result as a point on the curve:

z=H(m)z = H(m)

Finally she computes the value ss:

s=k1(z+ra)s = k^{-1}(z + ra)

If s=0s = 0, Alice needs to discard kk and sample another, random nonce kk and derive RR, rr and ss as she did before. This has to be done until s0s \ne 0.

The signature for the message mm is the tuple (r,s)(r, s) which Alice can send alongside her public key AA to Bob for verification.

To verify Alice’s signature, Bob recomputes zz as z=H(m)z = H(m).

He then calculates uu, vv and RR as follows:

u=s1zu = s^{-1}z v=s1rv = s^{-1}r R=uG+vAR = uG + vA

The signature is valid if r=?Rxr \overset{?}{=} R_x.

That is, if the rr value from Alice’s signature equals the xx-coordinate of the Elliptic Curve point RR that Bob calculated as R=uG+vAR = uG + vA.

Elliptic Curve Digital Signature Algorithm

Why it works

While the ECDSA signature verification algorithm might seem daunting at first, it’s easy to see why it works if we apply some basic algebra.

First, let’s recall that zz is the hash of the message mm that’s interpreted as a point on the Elliptic Curve EE.

We can now use the ss value from the signature to isolate kk:

s=k1(z+ra)×ksk=z+ra×s1k=s1(z+ra)\begin{aligned} s &= k^{-1}(z + ra) && \mid \times k \\ sk &= z + ra && \mid \times s^{-1} \\ k &= s^{-1}(z + ra) \end{aligned}

By expanding RR and substituting kk for s1(z+ra)s^{-1}(z + ra) (as we’ve just calculated), we can see that R=kGR = kG:

R=uG+vA=uG+vaG=G(u+va)=G(s1z+s1ra)=s1G(z+ra)k=s1(z+ra)=kG\begin{aligned} R &= uG + vA \\ &= uG + vaG \\ &= G(u + va) \\ &= G(s^{-1}z + s^{-1}ra) \\ &= s^{-1}G(z + ra) && \mid k = s^{-1}(z + ra) \\ &= kG \end{aligned}

Checking the signature generation procedure above, we can verify that this Elliptic Curve point RR is the same as the one Alice derived from kk.

This implies that its xx-coordinate is equal to the rr value of the signature. The signature over the message mm is therefore valid.

A note on nonce reuse

As we’ve highlighted above, it’s of utmost importance that the nonce kk is never reused as otherwise attackers who get access to two signatures that were generated with the same nonce kk can extract the private key aa.

To see how this would work, let’s pretend that we got our hands on two such signatures (r1,s1)(r_1, s_1) and (r2,s2)(r_2, s_2).

The first thing to note is that r1=r2r_1 = r_2. This is because r1r_1 is the xx-coordinate of R=kGR = kG and given that kk is reused, r2r_2 is also the xx-coordinate of the same R=kGR = kG.

Looking at s1s_1 and s2s_2 we can subtract both from each other to extract kk as follows:

s1s2=k1(z1+ra)k1(z2+ra)=k1z1+k1rak1z2k1ra=k1z1+k1rak1z2k1ra=k1z1k1z2=k1(z1z2)×kk(s1s2)=(z1z2)×(s1s2)1k=(z1z2)(s1s2)1\begin{aligned} s_1 - s_2 &= k^{-1}(z_1 + ra) - k^{-1}(z_2 + ra) \\ &= k^{-1}z_1 + k^{-1}ra - k^{-1}z_2 - k^{-1}ra \\ &= k^{-1}z_1 \cancel{+ k^{-1}ra} - k^{-1}z_2 \cancel{- k^{-1}ra} \\ &= k^{-1}z_1 - k^{-1}z_2 \\ &= k^{-1}(z_1 - z_2) && \mid \times k \\ k(s_1 - s_2) &= (z_1 - z_2) && \mid \times (s_1 - s_2)^{-1} \\ k &= (z_1 - z_2)(s_1 - s_2)^{-1} \end{aligned}

We can now use kk to extract the private key aa from any ss:

s=k1(z+ra)×ksk=z+razskz=ra×r1r1(skz)=a\begin{aligned} s &= k^{-1}(z + ra) && \mid \times k \\ sk &= z + ra && \mid -z \\ sk - z &= ra && \mid \times r^{-1} \\ r^{-1}(sk - z) &= a \end{aligned}

To see how severe this issue really is you can take a look at the PlayStation 3 Homebrew Wikipedia Article which has a section on the infamous private key compromise in which the key was extracted exactly the way you just learned.


The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.