# Elliptic Curve Cryptorgraphy

This article will introduce the cryptographic system based on elliptic curve. We will go through detail as possible. Finally, we will present elliptic curve digital signature (ECDSA) aglgortihm, which is widely used in blockchain for signing transaction.

---
## 1. The group of points on elliptic curve

In this section, we define group of points on elliptic curve. The basic concept of group and can be referred to this [link](https://hackmd.io/anypMu1XSAa_B-Nv_86hrg). First, we define the ellitpic curve over $\mathbb{Z}_p$

$\textit{Definition: Elliptic Curve}$ $E$

$\textit{The elliptic curve over } \mathbb{Z}_p, \quad p>3, \textit{is the set of all paris } (x,y)\in \mathbb{Z}_p \textit{, which fulfill}$

$$y^2\equiv x^3 + a \cdot x +b \textit{ (mod } p)$$
$\textit{together with an imaginary point of infinity } \mathcal{O} \textit{, where}$
$$a,b\in\mathbb{Z}_p$$
$\textit{and the condition } 4\cdot a^3 +27\cdot b^2\neq 0 \textit{ (mod } p)$

Note : The definition of elliptic curve requires that the curve is nonsingular, which means the plot has no self-intersections or vertices, which satisfied if the discriminant of the curve $-16(4a^3+27b^2)$ is nonzero.

---

> (Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
---

Now, we are going to define the **"addition"** operation between two points on elliptic curves. In other words, given two point $P、Q\in E$ we can define another point $R\in E$ such that

$$P+Q=R$$
under the **"addition"** we defined. Furthermore, this kind of definition satisfies the definition of group.

Before we going to explicit math formula, the figure below can present the concept about **"addition"** of two points.

<p align="center">
<img width="460" height="300" src="https://i.imgur.com/lN1bVfd.png">
</p>

The explicit formula is given by

$\textit{Elliptic Curve Point Addition and Point Doubling}$

$\textit{Given }$ $P=(x_1,y_1)、Q = (x_2,y_2)$ $\textit{we define}$ $R=(x_3,y_3)$ $\textit{by}$
$$x_3\equiv s^2 - x_1 - x_2 \textit{ (mod } p)$$

$$y_3\equiv s(x_1 - x_3) - y_1 \textit{ (mod } p)$$
$\textit{where}$

$$s=\left\{
\begin{matrix}
\frac{y_2-y_1}{x_2-x_1} \textit{ (mod p); if } P\neq Q\\
\frac{3x_1^2+a}{2y_1} \textit{ (mod p); if } P= Q
\end{matrix}
\right.$$

And we define the addition of $\mathcal{O}$ and any point $P\in E$ satisfies

$$P+\mathcal{O}= P$$

In the words, $\mathcal{O}$ is the identity element in the group. Once can be check that this definition construct a group of points on elliptic curve.

---

## 2. The mathematical hard problem on elliptic curve

$\textit{Definition: Elliptic Curved Discrete Logarithm Problem (ECDLP)}$

$\textit{Given is an elliptic curve}$ $E.$ $\textit{We consider a primitive element P and another element T. The}$
$\textit{The DL problem is finding the integer d, where 1 ≤ d ≤ #E, such that:}$

$$P+P+\cdots + P = dP = T$$

Therefore, we will have the **Elliptic-curve Diffie–Hellman(ECDH)**
The following contents is from [wiki](https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman)
:::info
Let Alice's key pair be ${\displaystyle (d_{\text{A}},Q_{\text{A}})}$ and Bob's key pair be ${\displaystyle (d_{\text{B}},Q_{\text{B}})}.$

Alice computes point ${\displaystyle (x_{k},y_{k})=d_{\text{A}}\cdot Q_{\text{B}}}.$ Bob computes point ${\displaystyle(x_{k},y_{k})=d_{\text{B}}\cdot Q_{\text{A}}}.$

The shared secret is ${\displaystyle x_{k}}$ (the x coordinate of the point). Most standardized protocols based on ECDH derive a symmetric key from ${\displaystyle x_{k}}$ using some hash-based key derivation function.

The shared secret calculated by both parties is equal, because
$${\displaystyle d_{\text{A}}\cdot Q_{\text{B}}=d_{\text{A}}\cdot d_{\text{B}}\cdot G=d_{\text{B}}\cdot d_{\text{A}}\cdot G=d_{\text{B}}\cdot Q_{\text{A}}}.$$
:::

Alice->Bob: Q_A                  
Note right of Bob: d_B * Q_A
Bob->Alice: Q_B
Note left of Alice:  d_A * Q_B

---

## 3. Elliptic Curve Digital Signature Algorithm
The concept about digital signature can be referred to this [link](https://searchsecurity.techtarget.com/definition/digital-signature).

> (Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)

> (Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)

> (Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)

### Toy example

> (Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)

###### tags: `Cryptography` `密碼學` `ECC` `ECDSA`