Elliptic-Curves

Elliptic Curves

Prerequisites:

1. Finite Fields
2. Cyclic Groups
3. Discrete Logarithm Problem

To start with Elliptic Curve Cryptography we will first have to see various aspects involved in it. This tutorial is an attempt to help people understand Elliptic Curves better and dive deeper into the concepts as we move forward step by step. This tutorial includes implementation and explanation of the following:

1. Defining Elliptic Curves
2. Mathematics behind Elliptic Curves (painful?)
   • Point Arithmetic
     • Point Addition
     • Point Doubling
   • Scalar Multiplication
     • Double and Add algorithm
     • Montgomery Ladder [To be added]

Elliptic Curves- definition

Consider the polynomial . All the solutions of this polynomial, when plotted in a graph will look something like this:

Source: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

This polynomial has some very interesting properties and a modified version of this polynomial is used for cryptographic purposes. Elliptic Curves provide security with relatively smaller key sizes when compared to other public key systems such as RSA.

The original polynomial mentioned above is not used directly, as it is favorable to have the curve over a finite set (particularly Finite Fields) than to have it defined over real numbers, for cryptographic purposes. We will see one such popular form of the polynomial which is used as an Elliptic Curve, and can be defined over as the following:

An Elliptic Curve over with p>3, is the set of all pairs (x, y) in that satisfy , along with an arbitrary point 0, where

In this tutorial, we will first define operations on Elliptic Curve over real numbers and then formulate the same for Elliptic Curves over Finite Fields.
We will also see in the next few sections how Elliptic Curve is a better trapdoor function than other existing systems of Public Key Crypto.

Notable observations about EC polynomial

1. The curve is symmetric with respect to x-axis:
   • 
2. The curve of the polynomial intersects x-axis at exactly one point, implying that there exists only one real solution to the cubic equation:
   • 

Point Addition

In this section, we will define addition of two points lying on an Elliptic Curve. Please note that some people use a dot operator instead of referring to it as addition operation, the operator used to denote the operation could be different, but the operation is still the same.

Also, + is just a notation that we use to denote the operation that we do on two points on an Elliptic Curve, it is not really addition that we do on the two points.

Assume two points A=(x₁, y₁) and B=(x₂,y₂) lying on the curve of the polynomial . We define C(x₃, y₃) as:

We can calculate C geometrically with the help of following steps:

1. Draw a line from A to B and get a third point of intersection extending the line and on the curve.
2. Reflect the point obtained along the x-axis and on the curve. This mirrored point is point C.

To understand it better have a look at this GIF:

Source: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

Now that we have defined point addition geometrically, let us formulate the same arithmetically with the help of observations noted from geometric definition of point addition:

1. We know that A, B, C' (C' is the reflection of point C along x-axis) lie on the curve as well the line joining A=(x₁, y₁), B=(x₂,y₂). Our approach will be to first calculate the coordinates of C' and then we can simply negate the y-coordinate of C' keeping the x-coordinate as it is to get coordinates of C. We can write:
   • 
   • For (x₁, y₁), , where m is the slope of the line connecting A and B.
   • Thus, we have
     • 
   • We know that (x-x₁) and (x-x₂) are factors of the above cubic equation obtained, and also we can write from Vieta's Formula that for a polynomial P(x) defined as: , sum of the roots . Hence we can write for a cubic polynomial that which in case of our polynomial can be written as . We know x₁, x₂ and m² so we can calculate x₃ as:
     • --> Using this formula we can calculate the x-coordinate of C'
   • Now that we have the x-coordinate of C', we can use it to calculate the y-coordinate of C' as well. Note that point C does not lie on the line joining A and B, but the reflection of point C on x-axis lies on the line joining A and B ie. point C'; the x-coordinate of point C remains the same, while the y-coordinate is just negated. Since point A and C' lie on the same line, we can write:
     • 

Now that we have calculated (x, y) coordinates of C', we can write coordinates of C as:

Notice that we added (mod p) in calculation as our curve is defined over the Finite Field and not over Real Numbers

You can find an implementation of the above discussed method in python here: ellipticcurve.py and in sage here(lesser lines of code): ellipticcurve.sage

Point Doubling

Point Doubling is similar to Point Addition, just that the formula for calculating slope is different, rest of the formulae for getting the coordinates of x₃ and y₃ are the same. We will first define point doubling geometrically and then define it arithmetically. Please note here doubling is just a notation, the operation that takes place on point lying on the curve is very different from normal doubling.

Consider a point P=(x₃, y₃) that we want to double. We can calculate 2P with the help of following steps:

1. Draw a tangent on the curve through P and obtain a second point of intersection between the curve and the line.
2. Reflect the point obtained along the x-axis and on the curve. This mirrored point is 2P.

We can also understand it using Point Addition: Consider addition two points P and Q on an Elliptic Curve, as Q approaches P, the line joining the two points to add these points approaches closer and as Q becomes very very close to P, the line becomes a tangent at point P.

Formula for slope will be different, as we have only one point on the curve and we want to compute the slope of its tangent, let us see how we can do it:

1. We know that . Differentiating both sides of this equation with respect to x, we get:
2. 
3. Thus, with the given point (x₁, y₁), we can write m as:
   • , where m is slope of the tangent passing through the point P

Arithmetically, we can express coordinates of 2P as:

Here m is the slope of the tangent passing through P

You can find an implementation of the above method in python here: ellipticcurve.py and in sage here(lesser lines of code): ellipticcurve.sage

Scalar Multiplication

There are two algorithms for implementing scalar multiplication in Elliptic Curves:

1. Double and Add algorithm
2. Montgomery Ladder

We will see how to implement each algorithm and also discuss why Montgomery ladder is preferred over Double and Add algorithm.

Double and Add Algorithm

This is a very simple algorithm for multiplication of a point with a scalar. Let us try to first understand multiplication of two scalars a and b using double and add, and then apply the same logic for points on an Elliptic Curve.
Suppose you want to multiply 5 = (101)₂ by 11 = (1011)₂

1. We can write: 5*11 = 5 * (1*2⁰ + 1*2¹ + 0*2² + 1*2³)
   • 5*11 = 5*1*2⁰ + 5*1*2¹ + 5*0*2² + 5*1*2³
2. For each term starting from the left, corresponding bit of b (ie equal to 11 in our example) is multiplied with a*2ⁱ, where i = 0,...,n (n is number of bits of b minus 1)
   • All the terms are then added together to give the result

Let us implement this algorithm for multiplying two scalars a and b:

def doubleandadd(a, b):
    res = 0
    addend = a
    for i in bin(b)[2:][::-1]:
        if i == "1":
            res = res + addend
        addend *= 2
    return res

We can apply the same for Elliptic Curves, the only difference is that instead of a we have a point P lying on an Elliptic Curve E:

from sage.all import *
# Declaring parameters of Elliptic Curve
# Select appropriate values of p, a, b

# Declaring a Weierstrass Curve
E = EllipticCurve(GF(p), [a, b])

def doubleandadd(E, P, b):
    # P is a point on the Elliptic Curve E

    # (0:1:0) are projective coordinates of arbitrary point at infinity
    res = E((0, 1, 0))
    addend = P
    for i in bin(b)[2:][::-1]:
        if i == "1":
            res = res + addend
        addend = addend * 2
    return res

Projective coordinates of points on Elliptic Curves

Resources

There are some pretty cool resources on ECC which you can refer:

1. Andrea Corbellini- Gentle Introduction to Elliptic Curves
2. Andrea Corbellini- Finite Fields and Discrete Logarithms
3. Nick Sullivan- Primer on Elliptic Curves
4. Introduction to Cryptography by Christof Paar- Introduction to Elliptic Curves
5. Introduction to Cryptography by Christof Paar- Elliptic Curve Cryptography

References

1. Picture/GIF reference: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/