# ECDSA
#### Elliiptic Curve Digital Signature Algorithm
###### tags: `資安`
---
### Background Section
#### Bitcoin:
A P2P Electronic Cash System through a cryptography mailing list.
#### Double Spending
The result of successfully spending some money twice.
#### Authentication (Signature)
Let $A$(Alice), $B$(Bob) be two users of a public key system. Let $f_A$ be the encrypting transformation if someone wants to send a message to Alice. $f_B$ for Bob.

Let $P$ be Alice's signature. Alice should send
$f_Bf_A^{-1}(P)$
at the end of the message.
(Why not just $f_B(P)$?)

When Bob decrypts using $f_B^{-1}$, he will find anything becomes plain text except
$f_A^{-1}(P)$
Since Bob knows this message is from Alice, he applies $f_A$ and obtains $P$.

---
### Math Section
#### Elliptic Curve
$y^2 = x^3+ax+b$
#### Negation:
The reflection of $P$ is $-P$
$P = (x, y)$, $-P = (x, -y)$

#### Addition:
Draw a line $L$ through both of $P$, $Q$. This $L$ will intersect with point $R$.
$P+Q = -R$

#### Doubling:
Take the line $L$ to be tangent of $P$. This $L$ will intersect with point $R$.
$2P = -R$

#### Multiplication:
Using addition and doubling.
Example: $k = 23$
$kP = 2(2(2(2P)+P)+P)+P$

#### Math for your reference:
$y^2 = x^3+ax+b$
$(\alpha x+\beta)^2 =x^3 + ax + b$
$\alpha^2x^2+2\alpha\beta x+\beta^2=x^3+ax+b$
$x^3-\alpha^2x^2+ax+2\alpha\beta x+b+\beta^2$

##### Addition
$(x_1, \alpha x_1+\beta), (x_2, \alpha x_2+\beta)$
$(x-x_1)(x-x_2)(x-x_3)$
$x^3-(x_1+x_2+x_3)x^2+(x_1x_2+x_2x_3+x_1x_3)x-x_1x_2x_3$
$x_3 = \alpha^2-x_1-x_2$
$y_3 = -(\alpha x_3 +\beta)$

$\alpha = \frac{(y_2-y_1)}{(x_2-x_1)}$
$\beta=y_1-\alpha x_1$
$x_3 = (\frac{y_2-y_1}{x_2-x_1})^2-x_1-x_2$
$y_3 = -(\frac{y_2-y_1}{x_2-x_1}(x_3-x_1)+y_1)$

##### Doubling
$x^3+ax+b-y^2 = 0$
$3x^2+a-2y\frac{dy}{dx}=0$
$\alpha = \frac{dy}{dx}=\frac{3x^2+a}{2y}$
$x_3 = (\frac{3x_1^2+a}{2y_1})^2-2x_1$
$y_3 = -(\frac{3x_1^2+a}{2y_1}(x_3-x_1)+y_1)$

---
### EC on finite field
$y^2 = x^3+ax+b$ over $F_p$
$F_p =$ {$0, 1, 2, 3, ... p-1$}
Example: Take $p = 17$
$y^2=x^3+7 \pmod {17}$
$x=5, y=8$
$64 \equiv 132 \pmod {17}$
Take $G = (15, 13)$
order of $G$ is $17$
To calculate $2G$, remember
$\alpha = \frac{dy}{dx}=\frac{3x^2+a}{2y}$
$x_3 = \alpha^2-2x_1$
$y_3 = -(\alpha(x_3-x_1)+y_1)$
Note that $9^{-1}\equiv2\pmod {17}$
Instead of dividing by $2*13\equiv9\pmod {17}$, multiply by $2$

$\alpha = 3*15^2*2 \equiv 7 \pmod {17}$
$x = 7^2-2*15 \equiv 2 \pmod {17}$
$y = -(7*(2-15)+13)\equiv 10 \pmod {17}$

---
### Secp256k1
$p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$
$E: y^2 = x^3 + 7$ over $F_p$
$G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798$
$G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B82DCE28D9 59F2815B 16F81798$
order of $G$ is approximately $2^{1024}$

---

### ECDSA
#### Key Generation
$K_{pub} = K_{priv}G$
Example: Take $K_{priv} = 8$

#### Signarture Generation
To sign a message $m$
1. Select a random integer $k$, s.t. $1 \leq k \leq n-1$
2. Compute $kG = (x_1, y_1)$, convert $x_1$ to an integer $\overline x_1$
3. Compute $r = \overline x_1 \pmod {n}$
4. Compute $k^{-1} \pmod {n}$. Where $k^{-1}$ is the multiplicative inverse that satisfies $k^{-1}k\pmod{n}=1$
5. Compute a SHA-1($m$), and convert this into an integer $e$
6. Compute $s = k^{-1}(e+K_{priv}r)\pmod n$. If s = 0, go back to step 1
7. A's signature for message $m$ is $(r, s)$

#### Signature Verification
To verify a signature $(r, s)$ on $m$
1. Verify r and s are integers in interval $[1, n-1]$
2. Compute SHA-1($m$) and convert this into an integer $e$
3. Compute $w$ = $s^{-1}\pmod n$
4. Compute $u_1 = ew \pmod n$ and $u_2 = rw \pmod n$
5. Compute $X = u_1G + u_2K_{pub}$
6. If $X = O$, reject the signature. Otherwise convert the $x$ coordinate $x_1$ of $X$ to integer $\overline x_1$ and compute $v = \overline x_1 \pmod n$
7. Accept the signature iff $v = r$

#### Proof
If $(r, s)$ on $m$ was indeed generated by Alice, then
$s = k^{-1}(e+K_{priv}r)\pmod n$

Multiplying by $s^{-1}k$ gives
$k = s^{-1}(e+K_{priv}r)\pmod n$
$k = s^{-1}e+s^{-1}(K_{priv}r)\pmod n$
$k = we+wK_{priv}r\pmod n$
$k = u_1+u_2K_{priv}\pmod n$

In the verfication step we calulate
$X = u_1G+u_2K_{pub}$

Using the relation between the private and the public keys
$X = (u_1+u_2K_{priv})G$

Using $k = u_1+u_2K_{priv}\pmod n$
$X = kG$

So
$v = r$

---

### Some Questions
> 1. What about SHA-256?

SHA-256 is for generating the address, here we are simply producing a signature. Also, note that Proof of Work is also for SHA-256 not ECDSA.

> 2. Why SHA-1?

SHA-1 here is just for demonstration, you can use any hash function as long as it is secure. Now bitcoin uses SHA256(SHA256()).

> 3. Why use ECDSA and not RSA(prime numbers)?

Computations using elliptic curves use less CPU and memory.

---

### References
[An Introduction to Bitcoin, Elliptic Curves and the Mathematics of ECDSA](https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf)
[Elliptic curve cryptography](https://cryptobook.nakov.com/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc)