Elliptic Curve Digital Signature Algorithm

Open Table of contents

What it is
How it works
Why it works
A note on nonce reuse
References

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 $m$ which is then verified by Bob.

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

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

a \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

A = aG

Alice then samples another, random value $k$ from $\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 $R$ is derived by multiplying $k$ with the generator $G$ :

k \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

R = kG

Given that the value $R$ is a point on the Elliptic Curve it has an $x$ - and $y$ -coordinate. Alice can therefore define the value $r$ as the $x$ -coordinate of $R$ :

r = R_x

If $r = 0$ , Alice needs to discard $k$ and sample another, random nonce $k$ and derive $R$ and $r$ as she did before. This has to be done until $r \ne 0$ .

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

z = H(m)

Finally she computes the value $s$ :

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

If $s = 0$ , Alice needs to discard $k$ and sample another, random nonce $k$ and derive $R$ , $r$ and $s$ as she did before. This has to be done until $s \ne 0$ .

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

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

He then calculates $u$ , $v$ and $R$ as follows:

u = s^{-1}z

v = s^{-1}r

R = uG + vA

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

That is, if the $r$ value from Alice’s signature equals the $x$ -coordinate of the Elliptic Curve point $R$ that Bob calculated as $R = 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 $z$ is the hash of the message $m$ that’s interpreted as a point on the Elliptic Curve $E$ .

We can now use the $s$ value from the signature to isolate $k$ :

\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 $R$ and substituting $k$ for $s^{-1}(z + ra)$ (as we’ve just calculated), we can see that $R = 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 $R$ is the same as the one Alice derived from $k$ .

This implies that its $x$ -coordinate is equal to the $r$ value of the signature. The signature over the message $m$ is therefore valid.

A note on nonce reuse

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

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

The first thing to note is that $r_1 = r_2$ . This is because $r_1$ is the $x$ -coordinate of $R = kG$ and given that $k$ is reused, $r_2$ is also the $x$ -coordinate of the same $R = kG$ .

Looking at $s_1$ and $s_2$ we can subtract both from each other to extract $k$ as follows:

\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 $k$ to extract the private key $a$ from any $s$ :

\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.

References

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.