Trusted answers to developer questions

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)**.

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**:$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 thegenerator point The starting point of the elliptic curve defined according to the standard being used $G$ .**Public key**:$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.

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:

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

**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$ .**Random point**:$R$ on the elliptic curve by multiplying the random number$k$ with the generator point$G$ , as follows:

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

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

The signature consists of two integer values calculated above

The signature verification algorithm takes the message and the signature

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

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

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

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

**Verify**:$r’$ with the$r$ that came as part of the signature, as follows:

We can generate the public key from the signature calculated by the ECDSA algorithm. The calculation process of public key returns

Extended ECDSA tackles this issue by adding an extra part

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

Related Courses