Elliptic curve is an equation with two variables and coefficients and it is a cubic equation like the following form:

\(y^{2}+axy+by=x^{3}+cx^{2}+dx+e\)

\(y^{2}=x^{3}\)

Let's plot \(y^{2}=x^{3}+ax+b\) with set of points E(a,b) = E(1,1)

Addition Over Elliptic curve :

First we have element called O (zero point or point of infinity) and we have a rule in geometric tearm "If 3 points on an elliptic curve lie on a straight line, their sum is O."

We can drive some rules from this rule :

1- For any point P on elliptic curve P+O=P.

2- The negative of point P with the same X coordinate, so if P=(x,y) then -P=(x,-y).

3- To add two points P and Q,draw a straight line between them and the third intersection point with curve is -R, then these three points P+Q=-R and the positive value of P+Q is the mirror image of the third point.

If the line between P and Q is tangent to the curve then R=P or R=Q.

4- To double point P,draw the tangent line and find the intersection point S then 2P=-S.

Algebraic addition over Elliptic curve :

1- To add two points \(P({X}_{p},{Y}_{p}) \ Q({X}_{q},{Y}_{q})\), then the slope of the line that join them \(\Delta = \frac{{Y}_{q}-{Y}_{p}} {{X}_{q}-{Y}_{p}}\)

Then we can express R (which R= P+Q)

\({X}_{r} = \Delta ^{2} - {X}_{p}-{X}_{q}\)

\({Y}_{r} = -{Y}_{p}+\Delta({X}_{p}-{X}_{r})\)

2- To double point P P+P=2P = R

\({X}_{r} =(\frac{3{X}_{p}^{2}+a}{2{Y}_{p}})^{2}-2{X}_{p}\)

\({Y}_{p} =(\frac{3{x}_{p}^{2}+a} {2{Y}_{p}})({X}_{p}-{X}{r})-{Y}_{p}\)

Elliptic Curve over finite field :

Elliptic Curve over finite field is using elliptic curve in which variables and coefficients are all restricted to elements of finite field.

Prime Curve over Zp :

Prime Curve is using a cubic equation in which the variables and coefficients take value from 0 to P-1.

Equation of elliptic curve over Zp :

\(y^{2} mod(p)=(x^{3}+ax+b) mod(p)\)

The rules for addition over \({E}_{p}(a,b)\):

1- If \(P({X}_{p},{Y}_{p}) \ then \ -P({X}_{p},{-Y}_{p})\).

2- To add two points \(P({X}_{p},{Y}_{p}) \ and \ Q ({X}_{q},{Y}_{q}) \ R= P+Q\)

Then R =

\({X}_{r}=(\lambda^{2}-{X}_{p}-{X}_{q})mod(p)\)

\({Y}_{r}=(\lambda({X}_{p}-{X}_{r})-{Y}_{p})mod(p)\)

\(\lambda = \begin{cases}(\frac{{}{Y}_{q}-{Y}_{p}}{{X}_{q}-{X}_{p}})mod(p)) & if\ p\neq q \\ \\

(\frac{3{X}_{p}^{2}+a}{2{Y}_{p}})mod(p) & \text if \ p=q (double\ point\ p) \end{cases}\)

For example :

Let P=(3,10) Q=(9,7) in \({E}_{23}(1,1)\)

\(\lambda=\frac{7-10}{9-3}mod(23)\ =\frac{-1}{2}mod(23)=11\)

\({X}_{r}=(11^{2}-3-9)mod(23=13\)

\({Y}_{r}=(11(3-17)-10)mod(23)=20\)

Then P+Q = (17,20)

To double point P 2P

For example :

Let P =(3,10)

\(\lambda=(\frac{3(3^{2})+1}{2*10})mod(23)=6\)

\({X}_{r}=(6^{2}-3-3)mod(23)=7\)

\({Y}_{r}=(6(3-7)-10)mod(23)=12\)

Then 2P = (7,12)

Elliptic curve over \(GF(2^{m})\) :

\(GF(2^{m})\) consists of \(2^{m}\) elements with addition and multiplication can be defined over polynomials, which variables and coefficients are elements of \(GF(2^{m})\).

The cubic equation for cryptographic applications for elliptic curve can take the following form :

\(y^{2}+xy= x^{3}+ax^{2}+b\)

For Example :

For g = 0010

\(y^{2}+xy=x^{3}+g^{4}x^{2}+1 \ \ \ where \ a=g^{4} ,b=g^{0}\)

\(a= g^{4}, b = 1\) and points that satisfies this equation \((g^{5},g^{3})\)

\(=(9^{3})^{2}+(9^{5})(9^{3})=(9^{5})^{3}+(9^{4})(9^{5})^{2}+1\)

\(=9^{6}+9^{8}=9^{15}+9^{14}+1\)

1100+0101 = 0001+1001+0001

1001 = 1001

The rules of addition over \(GF(2^{m})\) :

1- If \(P({X}_{p},{Y}_{p}) and Q({X}_{q},{Y}_{q}) R = P+Q\)

Then

\({X}_{r}=\lambda^{2}+\lambda+{X}_{p}+{X}_{q}+a\)

\({Y}_{r}=\lambda({X}_{p}+{X}_{r})+{X}_{r}+{Y}_{p}\)

\(\lambda=(\frac{{Y}_{q}+{Y}_{p}}{{X}_{q}+{X}_{p}})\)

2- If \(P({X}_{p},{Y}_{p}) R = 2P\)

\({X}_{r}=\lambda^{2}+\lambda+a\)

\({Y}_{r}={X}_{p}^{2}+(\lambda+{X}_{p})\)

\(\lambda={X}_{p}+\frac{{Y}_{p}}{{X}_{p}}\)

Key exchange using elliptic curve:

First choose a large integer q OR a prime number P or integer of form \(2^{m}\)

Then choose base point \(G =({x}_{1},{x}_{2})\) in Ep(a,b) whose order is a very large value n, The order n of point G is the smallest positive integer n such that nG=0.

The Key exchange can be done by the following:

1- User A select an integer \({n}_{A}\) less than n , This is A's private key, then compute public key \({P}_{a}={n}_{A} * G\)

2- User B select \({n}_{B}\) and compute the public key \({P}_{b}\)

3- User A compute the secret key \(K={n}_{A} * {P}_{b}\)

4- User B compute the secret key \(K={n}_{B} * {P}_{a}\)

Note : The secret key is a pair of numbers.

For Example:

P=211 in Ep(0,-4)

The equation \(y^{2} = x^{3} - 4\)

G = (2,2)

A's private key \({n}_{A}=121\)

B's private key \({n}_{B}=203\)

Then

A's public key \({P}_{a}={n}_{A} * G = 121(2,2) = (115,48)\)

B's public key \({P}_{b}={n}_{B} * G = 203(2,2) = (130,203)\)

A's secret key \(K={n}_{A} * {P}_{b} = 121(130,203) = (161,69)\)

B's secret key \(K={n}_{B} * {P}_{a} = 203(115,48) = (161,69)\)

Then the shared key k = (161,69)

Elliptic Curve encryption algorithm :

First we have to encode the message to be sent as x and y coordinates, and it is not easy because not all points are in \({E}_{p}(a,b)\).

As with the key exchange

- Choose a point G

- User A select a private key \({n}_{A}\)

- User A calculate the public key \({P}_{a}={n}_{A} * G\)

To send a message Pm to User B, User A choose a random integer K and then produce the ciphertext Cm by the following:

\({C}_{m} = (KG.{P}_{m} + K{P}_{b})\)

Note : User A masked the message Pm by adding (K.Pb) and nobody but user A knows k value.

For Example :

P=751 in \({E}_{p}(-1,188)\)

The equation \(y^{2} = x^{3} -x + 188\)

G=(0,376) Pm = (562,201)

User A choose k=386

\({P}_{b} = (201,5)\)

Then K.G = 386(0,376) = (676,558)

\({P}_{m} + K,{P}_{b}\)

(562,201) + 386(201,5) = (385,328)

Then the ciphertext Cm

Cm = {(676,558),(385,328)}