# ECDSA: Elliptic Curve Signatures

The [**ECDSA**](https://en.wikipedia.org/wiki/Elliptic\_Curve\_Digital\_Signature\_Algorithm) (Elliptic Curve Digital Signature Algorithm) is a cryptographically secure **digital signature scheme**, based on the elliptic-curve cryptography ([**ECC**](../asymmetric-key-ciphers/elliptic-curve-cryptography-ecc.md)). **ECDSA** relies on the math of the **cyclic groups of elliptic curves over finite fields** and on the difficulty of the [**ECDLP problem**](https://en.wikipedia.org/wiki/Elliptic-curve\_cryptography#Rationale) (elliptic-curve discrete logarithm problem). The [**ECDSA sign / verify**](https://en.wikipedia.org/wiki/Elliptic\_Curve\_Digital\_Signature\_Algorithm) algorithm relies on EC point multiplication and works as described below. ECDSA keys and signatures are shorter than in RSA for the same security level. A 256-bit ECDSA signature has the same security strength like 3072-bit RSA signature.

**ECDSA** uses [cryptographic **elliptic curves** (EC)](../asymmetric-key-ciphers/elliptic-curve-cryptography-ecc.md) over finite fields in the classical Weierstrass form. These curves are described by their **EC domain parameters**, specified by various cryptographic standards such as [**SECG: SEC 2**](http://www.secg.org/sec2-v2.pdf) and [**Brainpool (RFC 5639)**](https://tools.ietf.org/html/rfc5639). Elliptic curves, used in cryptography, define:

* **Generator point** **G**, used for scalar multiplication on the curve (multiply integer by EC point)
* **Order** _**n**_ of the subgroup of EC points, generated by **G**, which defines the length of the private keys (e.g. 256 bits)

For example, the 256-bit elliptic curve `secp256k1` has:

* Order _**n**_ = 115792089237316195423570985008687907852837564279074904382605163141518161494337 (prime number)
* Generator point **G** {_**x**_ = 55066263022277343669578718895168534326250603453777594175500187360389116729240, _**y**_ = 32670510020758816978083085130507043184471273380659243275938904335757337482424}

## Key Generation

The **ECDSA key-pair** consists of:

* **private key** (integer): _**privKey**_
* **public key** (EC point): _**pubKey**_ = _**privKey**_ \* **G**

The **private key** is generated as a **random integer** in the range \[0..._**n**_-1]. The public key _**pubKey**_ is a point on the elliptic curve, calculated by the EC point multiplication: _**pubKey**_ = _**privKey**_ \* **G** (the private key, multiplied by the generator point **G**).

The public key EC point {_**x**_, _**y**_} can be **compressed** to just one of the coordinates + 1 bit (parity). For the `secp256k1` curve, the private key is 256-bit integer (32 bytes) and the compressed public key is 257-bit integer (\~ 33 bytes).

## ECDSA Sign

The ECDSA signing algorithm ([**RFC 6979**](https://tools.ietf.org/html/rfc6979#section-3.2)) takes as input a message _**msg**_ \*\*\*\*+ a private key _**privKey**_ \*\*\*\*and produces as output a **signature**, which consists of pair of integers {_**r**_, _**s**_}. The **ECDSA signing** algorithm is based on the [**ElGamal signature scheme**](https://en.wikipedia.org/wiki/ElGamal\_signature\_scheme) and works as follows (with minor simplifications):

1. Calculate the message **hash**, using a cryptographic hash function like SHA-256: _**h**_ = hash(_**msg**_)
2. Generate securely a **random** number _**k**_ in the range \[1.._**n**_-1]
   * In case of **deterministic-ECDSA**, the value _**k**_ is HMAC-derived from _**h**_ + _**privKey**_ (see [RFC 6979](https://tools.ietf.org/html/rfc6979#section-3.2))
3. Calculate the random point _**R**_ = _**k**_ \* **G** and take its x-coordinate: _**r**_ = _**R**_**.x**
4. Calculate the signature proof: _**s**_ = $$k^{-1} * (h + r * privKey) \pmod n$$
   * The modular inverse $$k^{-1} \pmod n$$ is an integer, such that $$k * k^{-1} \equiv 1 \pmod n$$
5. Return the **signature** {_**r**_, _**s**_}.

The calculated **signature** {_**r**_, _**s**_} is a pair of integers, each in the range \[1..._**n**_-1]. It encodes the random point _**R**_ = _**k**_ \* **G**, along with a proof _**s**_, confirming that the signer knows the message _**h**_ and the private key _**privKey**_. The proof _**s**_ is by idea verifiable using the corresponding _**pubKey**_.

**ECDSA signatures** are **2 times longer** than the signer's **private key** for the curve used during the signing process. For example, for 256-bit elliptic curves (like `secp256k1`) the ECDSA signature is 512 bits (64 bytes) and for 521-bit curves (like `secp521r1`) the signature is 1042 bits.

## ECDSA Verify Signature

The algorithm to **verify a ECDSA signature** takes as input the signed message _**msg**_ + the signature {_**r**_, _**s**_} produced from the signing algorithm + the public key _**pubKey**_, corresponding to the signer's private key. The output is boolean value: _**valid**_ or _**invalid**_ signature. The **ECDSA signature verify** algorithm works as follows (with minor simplifications):

1. Calculate the message **hash**, with the same cryptographic hash function used during the signing: _**h**_ = hash(_**msg**_)
2. Calculate the modular inverse of the signature proof: _**s1**_ = $$s^{-1} \pmod n$$
3. Recover the random point used during the signing: _**R'**_ = (_**h**_ \* **s1**) \* **G** + (_**r**_ \* _**s1**_) \* _**pubKey**_
4. Take from _**R'**_ its x-coordinate: _**r'**_ = _**R'**_**.x**
5. Calculate the signature validation **result** by comparing whether _**r'**_ == _**r**_

The general idea of the signature verification is to **recover the point** _**R'**_ using the public key and check whether it is same point _**R**_, generated randomly during the signing process.

## How Does it Work?

The **ECDSA signature** {_**r**_, _**s**_} has the following simple explanation:

* The signing **signing** encodes a random point _**R**_ (represented by its x-coordinate only) through elliptic-curve transformations using the private key _**privKey**_ and the message hash _**h**_ into a number _**s**_, which is the **proof** that the message signer knows the private key _**privKey**_. The signature {_**r**_, _**s**_} cannot reveal the private key due to the difficulty of the **ECDLP problem**.
* The **signature verification** decodes the proof number _**s**_ from the signature back to its original point _**R**_, using the public key _**pubKey**_ and the message hash _**h**_ and compares the x-coordinate of the recovered _**R**_ with the _**r**_ value from the signature.

## The Math behind the ECDSA Sign / Verify

Read this section **only if you like math**. Most developer may skip it.

How does the above sign / verify scheme work? It is not obvious, but let's play a bit with the equations.

The equation behind the recovering of the point _**R'**_, calculated during the **signature verification**, can be transformed by replacing the _**pubKey**_ with _**privKey**_ \* **G** as follows:

_**R'**_ = (_**h**_ \* _**s1**_) \* **G** + (_**r**_ \* _**s1**_) \* _**pubKey**_ =\
_\*\*\*\*_ = (_**h**_ \* _**s1**_) \* **G** + (_**r**_ \* _**s1**_) \* _**privKey \***_ **G** _\*\*\*\*_=\
_\*\*\*\*_ = (_**h**_ + _**r**_ \* _**privKey**_) _**\* s1 \***_ **G**

If we take the number _**s**_ = $$k^{-1} * (h + r * privKey) \pmod n$$**,** calculated during the signing process, we can calculate _**s1**_ = $$s^{-1} \pmod n$$ like this:

_**s1**_ = $$s^{-1} \pmod n$$ =\
\= $$(k^{-1} * (h + r * privKey))^{-1} \pmod n$$ =\
\= $$k * (h + r * privKey)^{-1} \pmod n$$

Now, replace _**s1**_ in the point _**R'**_.

_**R'**_ = (_**h**_ + _**r**_ \* _**privKey**_) _**\* s1 \***_ **G** =\
\= $$(h + r * privKey) * k * (h + r * privKey)^{-1} \pmod n$$ _**\***_ **G** =\
_\*\*\*\*_ = **k** \* **G**

The final step is to **compare** the **point** _**R'**_ (decoded by the _**pubKey**_) with the **point** _**R**_ (encoded by the _**privKey**_). The algorithm in fact compares only the x-coordinates of _**R'**_ and _**R**_: the integers _**r'**_ and _**r**_.

It is expected that _**r'**_ == _**r**_ if the signature is **valid** and _**r'**_ ≠ _**r**_ if the signature or the message or the public key is incorrect.

## ECDSA: Public Key Recovery from Signature

It is important to know that the **ECDSA signature scheme** allows the **public key to be recovered** from the signed **message** together with the **signature**. The recovery process is based on some **mathematical computations** (described in the [**SECG: SEC 1**](http://www.secg.org/sec1-v2.pdf) standard) and returns 0, 1 or 2 possible EC points that are valid **public keys**, corresponding to the signature. To avoid this ambiguity, some ECDSA implementations add one additional bit _**v**_ to the signature during the signing process and it takes the form {_**r**_, _**s, v**_}. From this extended ECDSA signature {_**r**_, _**s**_, _**v**_} + the signed **message**, the signer's public key can be restored with confidence.

The **public key recovery from the ECDSA signature** is very useful in bandwidth constrained or storage constrained environments (such as blockchain systems), when transmission or storage of the public keys cannot be afforded. For example, the Ethereum blockchain uses extended signatures {_**r**_, _**s**_, _**v**_} for the signed transactions on the chain to save storage and bandwidth.

Public key recovery is possible for signatures, based on the **ElGamal signature scheme** (such as DSA and ECDSA).
