# Elliptic Curve

[比較](https://ithelp.ithome.com.tw/articles/10251031)

## Graph

$y^2 = x^3 + ax + b$

* [Elliptic Curve](https://www.geogebra.org/m/xDFZT5F6)
* [Elliptic Curve Algebra](https://www.geogebra.org/m/GCrVzWCV)
* [Addition](https://www.geogebra.org/m/BcPvTBCh)

## Over $\mathbb{F}_p$


$y^2 = x^3 - 7x + 10$

19, 97, 127, 487


11 % 2 = 1

https://andrea.corbellini.name/ecc/interactive/modk-add.html

## Algorithm

* Addition and Scalar multiplication (discrete logarithm problem)
* [Extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)
* [Schoof's algorithm](https://en.wikipedia.org/wiki/Schoof%27s_algorithm)
* Find Base Point and Order of subgroup
* [Verifiably Random Curves and Base Point Generators](http://www.secg.org/sec1-v2.pdf)

## ECDH (Elliptic curve Diffie-Hellman)

* [Diffie-Hellman problem](https://www.youtube.com/watch?v=YEBfamv-_do#t=02m37s)


[youtube](https://www.youtube.com/watch?v=YEBfamv-_do#t=02m37s)

## ECDSA (Elliptic Curve Digital Signature Algorithm)


Alice 如何生成 $(r,s)$：

1. 隨機找一個小於 subgroup 的 order $n$ 的數 $k$（first secret，PS 3 case），計算 $P = kG$（$G$ 是 subgroup 的 base point）
2. $r = x_P \text{ mod } n$（不可為 $0$）
3. $s = k^{-1}(z + r d_A) \text{ mod } n$

Bob 如何驗證 $(r,s)$：

1. $u_1 = s^{-1} z\text{ mod } n$
2. $u_2 = s^{-1} r\text{ mod } n$
3. $P = u_1 G + u_2 H_A\text{ mod } n$
4. 驗證 $r ?= x_P\text{ mod } n$

## Ref

* [Elliptic Curve Cryptography: a gentle introduction](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/)