ECDSA sign

The ECDSA signing algorithm (RFC 6979) 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 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)

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.

Source