Elliptic Curve Cryptography

 Outline:

1. Elliptic Curve Arithmetic 

2. Elliptic Curves over Real Numbers 

3. Elliptic Curve on a Zp

4. Elliptic Curve Key Exchange 

5. Security of Elliptic Curve Cryptography (ECC)

1. Elliptic Curve Arithmetic : Firstly, Elliptic curve are not ellipse 😂. They are named so because they are described by cubic equation. 

Now Let's go for the little bit background regarding the derivation : 

Suppose there is a set of balls which shown in the form of a pyramid. Let x be the height of pyramid so total number of balls that can be stored in a pyramid is - 

1^2+2^2+3^2+………..+x^2 = (x(x+1)(2x+1))/6

now fit these balls into square then 

Y^2 = (x(x+1)(2x+1))/6

2. Elliptic Curve over Real Numbers : 

Elliptic curve are not ellipse. They are so named because they are described by cubic equations, similar to those used for calculating the circumference of an ellipse. 

since we know that

Y^2 = (x(x+1)(2x+1))/6

so according to weierstrass equation :

Y^2 +axY + bY = x^3 + cx^2 + dx + e

where a, b, c, d, e are real numbers and x and y take on values in the real numbers. 

if characteristic is not equal to 2 then divide by 2 and see the below procedure. 

1. Ch !=2 

(Y+(ax/2)+(b/2))^2 = x^3 + (c + ((a^2)/4))x^2 + dx + e

==> Y^2 = x^3 + (A2')x^2 + (A4')x + A6'

2. Ch !=3

==> Y^2 = x^3 + Ax + b

Note 1: Since the characteristic of a field is that you add minimum number of times 'e' then it should be zero. or it comes out to be zero for adding minimum number of times e. 😒

2.1 Algebraic Description of Addition : 

consider an elliptic curve (as shown in Fig. 1) (symmetry w.r.t to x-axis). Let P1, P2, be the two points as shown in Fig. 1. 

so Y^2 = x^3 - x + 1

P3 = P1 + P2

Fig. 1. Elliptic Curve

2.1.1 Addition :

Consider Fig. 2, a line Y = mx + c is passed through this curve where m be the slope of line and c be the x-intercept. As we know this line cut the curve at two different points say P and Q. So addition of these points is -(P+Q) and symmetry w.r.t to x-axis can be considered as Point R = (P+Q). 

Fig. 2 : Sum of Points (When P and Q are different) 

Let P(x1,y1), Q(x2,y2), R(x3,y3)

now calculation of x3, and y3 are shown below. 

m = y2-y1/x2-x1

==> y2 = m(x2-x1) + y1 Or Y = m(x-x1) + y1

so we know Y^2 = x^3 + Ax + b

so we can write as x^3 - m^2x^2 +-------- = 0

so sum of roots = -b/a  (mathematical formula sum of roots 😁)

so x1+x2+x = m^2

so coordinates at point R can be computes as 

x3 = m^2-x1-x2 y3 = m(x1-x2)+y1

2.1.2 Doubling of a point : 

Now assume P = Q. Now we have to calculate the ordinate of third point so lets us assume that a tangent is passes through that curve (as shown in Fig. 3) 

Fig. 3: Doubling of point

So equation of Curve is

Y^2 = x^3 + Ax + b

now differentiating them we get, 

2Y(dY/dx) = 3x^2 + A

so dY/dx or m = (3x1^2 + A)/2Y1    (at point (x1,y1))

so we can write that

x3 = m^2 - x1 - x2 y3 = m(x3-x1) + y1

2.2 Geometric Description of Addition : 

Now considered the characteristic field is not 3 so the equation of elliptic curve can be written as : 

Y^2 = f(x) = x^3 + Ax + B

delf/delx(x0,y0) =  delf/dely(x0,y0) = 0

or 2y0 = -f'(x0) = 0

or f(x0) = f'(x0)

therefore, f has a double root

Y^2 = x^3 + Ax + B

for double root

x^3 + Ax + b

differentiating them 

3x^2 + A = 0

x^2 = -A/3

Also, 

x^4 + Ax^2 + bx = 0 

==> (-A/3)^2 + A(-A/3) + bx = 0

==> x = -2A^2/9B

since x^2 = -A/3

==> 3x^2 + A = 0

==> 3(2A^2/9B)^2 + A = 0

==> 4A^3 + 27b^2 = 0

for non-singularity

4A^3 + 27b^2 !=0

3. Elliptic curve over Zp : 

For elliptic curves over Zp, as with real numbers, we limit ourselves to equation of the form of given below equation, but in this case with coefficient and variables limited to Zp. 

Y^2 mod p = (x^3 + Ax + b)  mod p  { Here p is a prime number}

 

4. Elliptic Curve Key Exchange : 

Figure 4 explains all the working of Elliptic curve key exchange. 

Fig. 4: Elliptic curve key Exchange. 

Note 2 : Elliptic curve key exchange algorithm is similar to Diffie-Hellman key exchange algorithm. 😎

5. Security of Elliptic Curve Cryptography (ECC) :

The security of ECC depends on how difficult it is to determine k given kP and P. This is also referred to as the elliptic curve logarithm problem. The below table compares various algorithms by showing comparable key sizes in terms of computational efforts for cryptanalysis. 

Table I

As  we can see that a considerably smaller key size can be used for ECC compared to RSA. Furthermore, for equal key lengths, the computational effort require for ECC and RSA is comparable. Thus, there is a computational advantage to using ECC with a shorter key length than a comparably secure RSA. 

*********************************Thank-you*****************************************