What is the Elliptic Curve Digital Signature Algorithm?

The Elliptic Curve Digital Signature Algorithm (ECDSA) is a digital signature algorithm (DSA). ECDSA relies on elliptic curves defined over a finite field to generate and verify signatures. The underlying elliptic curves make the signing process more efficient and secure, as the process relies on the complexity of the elliptic-curve discrete logarithm problem (ECDLP).

Key generation

We generate asymmetric keys using the key agreement algorithms that elliptic curve cryptography provides. Elliptic-curve Diffie–Hellman (ECDH) is a widely used key agreement algorithm. The process of public-private key generation in ECDH as follows:

• Private key: The private key is a randomly selected number $n_p$ such that $n_p$ is in the interval 1 to $n_o$- 1, where $n_o$ is the order of the subgroup of the elliptic curve points, generated by the generator pointThe starting point of the elliptic curve defined according to the standard being used $G$.
• Public key: The public key is given as $P = n_pG$, where $n_p$ is the private key selected randomly above, $G$ is the generator point of the elliptic curve, and $P$ is the public key.

Note: To learn more about the ECDH, we can click here.

Signature generation

The signature generation algorithm is based on the ElGamal signature scheme. It takes the private key of the sender and the message to be sent as input, and generates the signature as output. The working of the algorithm is as follows:

1. Message hash: We calculate the hash $h$ of the message $m$ using hash functions like MD-5, SHA-256, and Keccak-256, as follows:

2. Random number: We choose a random number $k$, ranging from $1$ to $n-1$, where $n$ is a prime number that represents the order of the subgroup of elliptic curve points generated by the generator point $G$.
3. Random point: We calculate the random point $R$ on the elliptic curve by multiplying the random number $k$ with the generator point $G$, as follows:

4. $x$-coordinate: We select the $x$-coordinate of the random point generated above, as follows:

5. Signature proof: We apply the following equation to calculate the signature proof $s$, as follows:

The signature consists of two integer values calculated above $r$ and $s$.

Signature verification

The signature verification algorithm takes the message and the signature $r,\,s$ as input, and returns a boolean value representing whether the signature is verified. The signature verification algorithm works as follows:

1. Message hash: We calculate the hash $h$ of the message $m$ using the same hash function that was we used during the signature generation, as follows:

2. Modular inverse: We calculate the modular inverse of the signature, as follows:

3. Random point: We recalculate the random point $R’$ as in the signature generation process, where $P$ is the public key of the sender, as follows:

4. $x$-coordinate: We get the $x$-coordinate of the recalculated random point, as follows:

5. Verify: We verify the result by matching the recently calculated $r’$ with the $r$ that came as part of the signature, as follows:

Extended ECDSA

We can generate the public key from the signature calculated by the ECDSA algorithm. The calculation process of public key returns $0$, $1$, or $2$ points on the elliptic curve that represent the public key against the signature. However, this creates ambiguity.

Extended ECDSA tackles this issue by adding an extra part $v$to the signature, making the signature $\{r, s, v\}$. This allows us to calculate the public key with greater guarantee. The extended ECDSA not only removes ambiguity, but also has more uses.

Uses of extended ECDSA

Extended ECDSA implementation is particularly useful in storage or bandwidth constraint environments. In situations where it is difficult or expensive to store or transmit public keys, we can use extended ECDSA.

Blockchain is an environment limited on bandwidth and storage. By using extended ECDSA, it avoids transmitting or storing the public key. Ethereum uses it to sign transactions.

Note: To learn how to create a digital signature in Python, we can click here.