Elliptic Curve Digital Signature Algorithm

ECDSA (Elliptic Curve Digital Signature Algorithm) is a form of elliptic curve cryptography (ECC) that utilizes the secp256k1 curve to create public and private key pairs, as well as to generate and verify digital signatures.

What is the secp256k1 curve?

$$y^2 = x^3 + ax + b$$

All elliptic curves are derived from this general equation by varying the values of a and b. For secp256k1, the values are defined as:

$$a = 0$$

$$b = 7$$

Which results in:

$$y^2 = (x^3 + 7) \bmod p$$

Where:

$$p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$$

Here, the "256" refers to the size of the key, meaning the curve defines a finite field of 256-bit values. The coordinates lie within the range:

$$1 < (x, y) < 2^{256}$$

Where both x and y are always prime numbers.

How it works in Ethereum

A random number is generated to serve as the private key. This private key is then multiplied by the generator point to derive the public key. The public key is subsequently hashed using SHA2-256 (in Ethereum, this is keccak256), and the last 40 hexadecimal characters (i.e., 20 bytes) are used as the public address associated with that private key.

Create Key Pair

public key = private key * generator point (G);
public address = last_20_bytes(keccak256(public key));

Where:

The base point G in compressed form is:

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

And in uncompressed form:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
     483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

The order n of G and the cofactor h are:

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01

This implies that the randomly generated private key must satisfy:

1 <= private key <= n - 1

• The value of p is chosen specifically as it is the largest prime number under 2^{256}.

• The generator point G is the largest number under 2^{256} that satisfies the secp256k1 equation.

• The value n is the largest number under 2^{256} such that:

  $$n \cdot G = \text{point at infinity}$$

• The point at infinity is a special value on the curve where multiplication loops back:

  $$n \cdot G = G$$

• h = 1 means all points on the curve can be derived by repeatedly adding the generator point G to itself.

Create Signature

1. Compute the hash of the message:

   $$h = \text{keccak256(message)}$$

2. Generate a random number k in the range:

   $$1 \leq k \leq n - 1$$

3. Compute the point (x, y) = k * G. Let this point be R.

4. Calculate:

   $$r = x \mod n$$

5. Calculate:

   $$s = k^{-1} \cdot (h + r \cdot \text{privateKey}) \mod n$$

6. The signature is the pair (r, s). The v is used to indicate whether the positive or negative y value of R was used.

Verify Signature

1. Compute the modular inverse of s:

   $$s1 = s^{-1} \mod n$$

2. Compute the point:

   $$R' = (h \cdot s1) \cdot G + (r \cdot s1) \cdot \text{publicKey}$$

3. Let R' = (x, y), then:

   $$r' = x \mod n$$

4. The signature is valid if:

   $$r' == r$$

The parameter v helps identify which y value to use when reconstructing R. Since the secp256k1 curve is symmetric about the x-axis, each x has two valid y values: (x, y) and (x, n - y). v indicates which of these to use.

What types of attacks can occur?

Replay / Signature Malleability Attacks

As noted in the verification section, each signature can yield two valid (x, y) pairs: (x, y) and (x, n - y). Therefore, an attacker can take a valid signature (r, s), flip s to n - s, and send (r, n - s) with the corresponding v flipped. This creates a valid but different signature for the same message—allowing the signature to be reused.

ecrecover() Check

In Solidity’s EVM bytecode, if ecrecover() fails, it returns address(0). If a contract doesn’t check that the recovered address matches the expected signer, this could introduce a bug or vulnerability.

Mitigations

• The simplest solution: use OpenZeppelin’s ECDSA library.

Random Fact

• The last valid private key:

    ffffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140