## ECDSA

• Curve parameters (q, FR, a, b, B, p, h) have to be agreed (e.g. asymmetric key exchange)
• message m is to be signed
1. $H(m)$ hash is any hash function
2. Select key k so that $1< k < n-1$
3. Calculate point P, $P = k * B$
4. $r = P_{x} mod{p}$ $P_{x}$ is x coordinate of point P if r=0 then select new k
##### Signature generation algorithm

Suppose Alice wants to send a signed message to Bob. Initially, the curve parameters $(q, FR, a, b, G, n, h)$ must be agreed upon. Also, Alice must have a key pair suitable for elliptic curve cryptography, consisting of a private key $d_A$ (a randomly selected integer in the interval $[1, n-1]$) and a public key $Q_A$ (where $Q_A = d_A G$). Let $L_n$ be the bit length of the group order $n$.

For Alice to sign a message $m$, she follows these steps:

# Calculate $e = \textrm{HASH}(m)$, where HASH is a cryptographic hash function, such as SHA-1, and let $z$ be the $L_n$ leftmost bits of $e$. # Select a random integer $k$ from $[1, n-1]$. # Calculate $r = x_1 \pmod{n}$, where $(x_1, y_1) = k G$. If $r = 0$, go back to step 2. # Calculate $s = k^{-1}(z + r d_A ) \pmod{n}$. If $s = 0$, go back to step 2. # The signature is the pair $(r, s)$.

When computing $s$, the string $z$ resulting from $\textrm{HASH}(m)$ shall be converted to an integer. Note that $z$ can be `greater` than $n$ but not `longer`<ref>[http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf FIPS 186-3, pp. 19 and 26]</ref>.

##### Signature verification algorithm

For Bob to authenticate Alice's signature, he must have a copy of her public key $Q_A$. If he does not trust the source of $Q_A$, he needs to validate the key ($O$ here indicates the identity element):

# Check that $Q_A$ is not equal to $O$ and its coordinates are otherwise valid # Check that $Q_A$ lies on the curve # Check that $nQ_A = O$

After that, Bob follows these steps:

# Verify that $r$ and $s$ are integers in $[1, n-1]$. If not, the signature is invalid. # Calculate $e = \textrm{HASH}(m)$, where HASH is the same function used in the signature generation. Let $z$ be the $L_n$ leftmost bits of $e$. # Calculate $w = s^{-1} \pmod{n}$. # Calculate $u_1 = zw \pmod{n}$ and $u_2 = rw \pmod{n}$. # Calculate $(x_1, y_1) = u_1 G + u_2 Q_A$. # The signature is valid if $r = x_1 \pmod{n}$, invalid otherwise.

Note that using Straus's algorithm (also known as Shamir's trick) a sum of two scalar multiplications $u_1 G + u_2 Q_A$ can be calculated faster than with two scalar multiplications.