Security Stuff!!
Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode

Elliptic Curve

Elliptic curve is an equation with two variables and coefficients and it is a cubic equation like the following form:
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)\)

\(\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}\)

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\)
Then P+Q = (17,20)

To double point P 2P
Let P =(3,10)
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 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})\)
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\)

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

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 1: The secret key is a pair of numbers.
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\)
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 2: User A masked the message Pm by adding (K.Pb) and nobody but user A knows k value.
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)}