Elliptic curves and ECDSA

ECDSA is short for Elliptic Curve Digital Signature Algorithm

The idea is that if you are going to send a message to someone, you could send the message + signature + public key to them, and the signature is computed using the private key.

The recipient could then verify the authenticity of the message with the signature and the public key

It is possible to authenticate the sender without revealing the private key.

ECDSA

• It is a digital signature scheme, based on the elliptic-curve cryptography(ECC).

• relies on the math of the cyclic groups of elliptic curves over finite fields and on the difficulty of the ECDLP problem (elliptic-curve discrete logarithm problem)

• The ECDSA sign / verify algorithm relies on EC point multiplication

• ECDSA keys and signatures are shorter than in RSA for the same security level

• 256-bit ECDSA signature has the same security strength like 3072-bit RSA signature

Elliptic curves, used in cryptography, define:

1.Generator point G, used for scalar multiplication on the curve (multiply integer by EC point), e.g. G{x = 123, y = 456}

2.Order n of the subgroup of EC points, generated by G, which defines the length of the private keys (e.g. 256 bits) e.g. n = 123123… (it’s a big prime number)

Key Generation

The ECDSA key-pair consists of:

Private key (integer): privateKey

Public key (EC point): publicKey = privateKey * G

The private key is generated as a random number in the range of [1…n-1].

• The public key is a point on the elliptic curve, calculate by the EC point multiplication:

  publicKey = privateKey * G , in other words: 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

E.g. -> for the secp256k1 curve: The private key is 256-bit integer (32 bytes) The compressed public key is 257-bit integer (~33 bytes)

🖊️ECDSA Sign

• The signing algorithm takes as an input:

  Message - msg Private key - privateKey

  👉And produces an output:

  Signature - {r, s} := r and s are pair of integers

Steps:

1.Hash the message with for example SHA-256

h = SHA-256(msg)

2.Generate securely a random number k in the range [1…n-1]

2.1 In case of deterministic-ECDSA the value of k is HMAC derived from h + privateKey

👉k derived from h + privateKey

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 * privateKey) (mod n)

4.1 The modular inverse k^(-1) (mod n) is an integer such that:

k * k^-1 = 1 (mod n)

✅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 privateKey. The proof s is by idea verifiable using the corresponding publicKey.

❕ECDSA signatures are 2 times longer than the signer's private key for the curve used during the signing process.

🔎ECDSA Verify Signature

To verify a ECDSA signature, take an input of

👉msg

👉signature {r, s} - produced by the signing algorithm

👉public key - corresponding to the signer’s private key```<br>` The output is: boolean valid || invalid signature``

🪜Steps:

👉Calculate the message hash, with the same hashing function used during signing

👉Calculate the modular inverse of the signature proof:

s1 = s^(-1) (mod n)

👉Recover the random point used during the signing:

R’ = (h * s1) * G + (r * s1) * publicKey

👉Take from R’ it’s x-coordinate:

r’ = R’ * x

👉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.

Cheatsheet 1️.The signing encodes random point R (represented by its x-coordinate only) through elliptic curve transformations using the private key and the message’s hash into a number s, which is the proof that the message signer knows the private key. The signature {r, s} cannot reveal the private key due to the difficulty of the ECDLP problem

2️.The signature verification decodes the proof number s from the signature back to its original point R, using the public key and the message’s hash and compares the x-coordinate of the recovered R with the r value from the signature