## Elliptic Curve Digital Signature Algorithm (ECDSA) ECDSA is a variant of [Digital Signature Algorithm](https://en.wikipedia.org/wiki/Digital_Signature_Algorithm) which uses Elliptic Curve Cryptography. ### Procedure to generate signature For a Given curve and it's parameters, $(\text{CURVE}, G, n)$, where $nG = O$ where $O$ is identity element and $n$ is prime. This is required so that every element in $\mathbb{Z/nZ}$ except $0$ is invertible. Assume a key-pair $(d_A, Q_A)$ where $d_A$ is the private key and $Q_A = d_AG$ is the public key. * $d_A \in [1, n-1]$. * Find the public key curve point $Q_A = d_AG$. 1. Calculate $e = \text{HASH}(m)$, where $\text{HASH}$ is a Cryptographic hash function such as SHA-2 and $m$ is the message. 2. $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bitlength of $n$. 3. Select a Random number $k \in [1, n-1]$. 4. Find $(x_1, y_1) = kG$. 5. Find $r = x_1 \pmod{n}$. If $ r=0$, go back to step 3. 6. Find $s = k^{-1}(z + rd_A) \mod{n}$. If $s = 0$, go back to step 3. 7. The signature is $(r, s)$. Note that $z$ can be greater than $n$ but can't be longer in number of bits. The calculated hash $e$ needs to be converted to an integer. There is a consideration on selection of $k$, which is written later in the text. ### Verification of the signature * Check $Q_A$, the public part, is not $O$, identity element and also lies on the curve. * Check $nQ_A = O$. 1. Verify $r, s \in [1, n-1]$. 2. Calculate $e=\text{HASH}(m)$ using the same function. 3. $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bit length of $n$. 4. Find $w = s^{-1} \pmod{n}$. 5. Find $u_1 = zw \pmod{n}$, $u_2 = rw \pmod{n}$. 6. Calculate $(x_1, y_1) = u_1G + u_2Q_A$, if $(x_1, y_1) = O$, signature is invalid. 7. The signature is valid if $r \equiv x_1 \pmod{n}$. ### Why does the signature work $$ \begin{align} w &= s^{-1} \pmod{n} \\ u_1 &= zs^{-1} \pmod{n} \\ u_2 &= rs^{-1} \pmod{n} \\ C &= u_1G + u_2Q_A \\ &= u_1G + u_2d_AG \enspace \text{since} \enspace Q_A = d_AG\\ &= (u_1 + u_2d_A)G \\ &= (z + rd_A)s^{-1} \times G \\ &= (z + rd_A)((z + rd_A)^{-1} (k^{-1})^{-1}) \times G \\ &= kG \end{align} $$ since $r = kG$ in the signature phase, if we compare the final point $C(x, y)$ to $r$ and if $r = C_x$, the signature is valid. --- ### Retrieving Private key from faulty Signatures ([Sony PS](https://www.engadget.com/2010/12/29/hackers-obtain-ps3-private-cryptography-key-due-to-epic-programm/)) Going back to selection $k$, $k$ needs to be private and also it is recommended to select a random $k$ for each and every signature. The reason being. If we take the same $k$ for all signatures but different messages, we will have the same $r$ as $r = kG$.Which means $r_1 = r_2$. $$ \begin{align} (ks - z)r^{-1} &\equiv d_A \pmod{n} \\ (ks_1 - z_1)r^{-1} &\equiv (ks_2 - z_2)r^{-1} \pmod{n} \\ (ks_1 - z_1) &\equiv (ks_2 - z_2) \pmod{n} \\ k(s_1 - s_2) &\equiv z_1 - z_2 \pmod{n} \\ k &\equiv \frac{z_1 - z_2}{s_1 - s_2} \pmod{n} \end{align} $$ Now, once we have $k$, using equation $(10)$, $d_A$ can be evaluated.