Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

blockchain
cryptography
digital signature
ecdsa

What is the Elliptic Curve Digital Signature Algorithm?

Muhammad Zubair

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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 npn_p such that npn_p is in the interval 1 to non_o- 1, where non_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 GG.
  • Public key: The public key is given as P=npGP = n_pG, where npn_p is the private key selected randomly above, GG is the generator point of the elliptic curve, and PP 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 hh of the message mm using hash functions like MD-5, SHA-256, and Keccak-256, as follows:
  1. Random number: We choose a random number kk, ranging from 11 to n1n-1, where nn is a prime number that represents the order of the subgroup of elliptic curve points generated by the generator point GG.
  2. Random point: We calculate the random point RR on the elliptic curve by multiplying the random number kk with the generator point GG, as follows:
  1. xx-coordinate: We select the xx-coordinate of the random point generated above, as follows:
  1. Signature proof: We apply the following equation to calculate the signature proof ss, as follows:

The signature consists of two integer values calculated above rr and ss.

Signature verification

The signature verification algorithm takes the message and the signature r,sr,\,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 hh of the message mm using the same hash function that was we used during the signature generation, as follows:
  1. Modular inverse: We calculate the modular inverse of the signature, as follows:
  1. Random point: We recalculate the random point RR’ as in the signature generation process, where PP is the public key of the sender, as follows:
  1. xx-coordinate: We get the xx-coordinate of the recalculated random point, as follows:
  1. Verify: We verify the result by matching the recently calculated rr’ with the rr 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 00, 11, or 22 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 vvto the signature, making the signature {r,s,v}\{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.

RELATED TAGS

blockchain
cryptography
digital signature
ecdsa

CONTRIBUTOR

Muhammad Zubair
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring