cryptocurrency, money, ethereum

Details of ECDSA Signatures

Leave a Comment / Cryptography / By / June 3, 2020

Ethereum Digital Signatures

In the previous post in this series, I introduced the concept of Digital Signatures. In this article, I give an outline of ECDSA, the signature algorithm that is used to secure the Bitcoin and Ethereum blockchains. This is to set the ground for the next post, where I go over how this is actually implemented in Ethereum.

The cockpit of a passenger plane is way more complex than an ECDSA signature.
ECDSA may seem complex, but not it’s not as scary as this.

ECDSA

The Original DSA Algorithm

Ethereum uses a particular digital signature scheme called ECDSA, to validate each transaction in the network. The EVM itself does not have the capability to sign, that is done by the clients. If you’re a Javascript developer, for example, web3.js gives you a method to sign. But the EVM has a method to verify a signature. That will be the topic of the next post in this series.

The ECDSA is the elliptic-curve version of the DSA algorithm, which itself belongs to the family of discrete-log based signature schemes. The basic DSA scheme works like this:

Public Parameters

p, q: prime numbers such that q is a divisor of p-1
g: a generator of an order-q group G

G: a group defined by:
    elements: integers between 1 and p
    operation: multiplication mod p

If you need refreshing your knowledge about the above, you may want to check my posts on groups, fields and elliptic curves.

Recall from the last post that before you can sign, the system has to be setup with the common parameters and that a signing key has to be generated.

In this case, this setup includes two primes that define the size of the group we will operate with. The smaller the size of the group, the easier it becomes to attack, so you want it to be large enough to defeat brute-force attacks.

In this type of groups, generators can be randomly chosen. There is not a deterministic procedure to generate an element of a group, but there are enough generators that you can pick elements at random until you find one that fits the bill.

Key Generation

Select a random element x from [1, ..., q-1]
Public verification key: y = gx mod p
Private signing key: x

Signature Generation

Input: x, m
--------------
Select a random k from [1, ..., q-1]

Define:
-------
    X = gk mod p
    r = X mod q
    e = Hash(m)
    s = k-1 * (e + xr) mod q

Return signature:
-----------------
    (r, s)

A final obserevation to add to the above is that the whole signature is re-generated if, because of the random steps, either part of the signature is equal to 0.

You might like to observe that the signature is composed of two values, r and s, which are field elements, that is, numbers from 1 to the order of G (ie, q). That is, the signature can be encoded as two numbers of size log q. The quantity log q is, therefore, the “security level” of this scheme.

Signature Verification

Inputs: m, sig
-----------------------
Obtain (r,s) from sig

Define:
-------
     e = Hash(m)
     u1 = e / s mod q
     u2 = r / s mod q
     X = gu1 yu2
     v = X mod q

Return:
-------
YES, if v == r
NO, otherwise

These definitions always look a bit scary, I know. But if you replace s by (e + xr)/k in the definition of u1 and u2, you can check that the definition of X in the Signature Verification just returns gk mod p as in the Signature Generation step. This tells us that the scheme is correct.

The Elliptic-Curve Variant (ECDSA)

The standard definition above applies to groups whose elements are integers. In practice, we can have the same security for much smaller keys if we use groups made up of Elliptic Curves points instead.

There are not many differences between these two schemes. In the end, it mostly boils down to replacing a group of integers by a group of points on an elliptic curve. The definition becomes (with some simplifications):

Public Parameters

q: a large power of 2 or an odd prime
EC: an adequate elliptic curve with N points and coefficients defined over the finite field Fq
n: the order of a large sub-group of EC such that n is prime
G: a generator for this group.

Key Generation

Select a random element d from [1, ..., n-1]
Public verification key: Q = dG
Private signing key: d

There probably seem to be more differences than there are in reality. Because the group operation over elliptic curves is usually thought of as addition, and because in the an integer field the operation is number multicplication, these groups are naturally expressed in additive and multiplicative notation respectively.

But whether we write xG or gx we still mean x group operations with the group generator.

Signature Generation

Input: d, m
------------------------------
Select a random k from [1, ..., n-1]

Define:
-------
    (x1, y1) = kG
    r = x1 mod n
    e = Hash(m)
    s = k-1 * (e + dr) mod n

Return signature:
-----------------
    (r, s)

Again, the values are discarded and the algorithm is repeated if either r or s are 0.

Remember the size of the signature in the base scheme? In this, the signature is still composed of the same two field elements, that is, two integers of size q. Now it is clearer that they are not related to group elements, as in this scheme those are points with 2 coordinates each.

What is important to notice is that, because the groups on elliptic curves are harder to attack than integer groups, we can use a much smaller value of q and therefore have much shorter signatures than in the base scheme.

Signature Verification

Inputs: m, sig
---------------------------------

Obtain (r,s) from sig

Define:
-------
     e = Hash(m)
     u1 = e / s mod n
     u2 = r / s mod n
     X = u1G + u2Q
     Parse (x1, y1) = X
     v = x1 mod n

Return:
-------
YES, if v == r
NO, otherwise

A new check is introduced in this variant. If X is the “point at infinity” of the elliptic curve, that is the group’s identity element, the verification fails.

Verification in Ethereum

I was surprised, when I started coding in Ethereum, to find out that Solidity doesn’t really offer us a way to run the VERIFY algorithm. Instead, it gives us something called ecrecover.

Calling ecrecover(<plain message>, <signature>) gives us an Ethereum address. An Ethereum address is uniquely derived from an ECDSA public key, and typically acts as a stand-in for that. In this case, this address represents a public key under which the pair (<plain message>, <signature>) is valid. To verify a signature, we obtain that address and then compare it to the address of the expected signer.

It may be just me, but this always felt the other way around and simply… well, wrong. I am even told, as a matter of folklore, I guess, that if we pass a mismatched signature and message, say ecrecover(mis_message, mis_sig) we will still get back an address for which mis_sig would be a valid signature of mis_message.

This is quite different from the standard cryptographic practice, and even possibly a bit dangerous, so what exactly is going on here?

It was basically this question that prompted me to write this series. In the next post, I will go into the murky details of ecrecover and see if my worries are justified.

Until then, enjoy, and still try to have fun coding, thinking or doing maths, while in lockdown.

Farewell.

Leave a Reply