Elliptic Curve Cryptography — Part 1

Introduction

Elliptic curve cryptography (ECC) is an asymmetric cryptographic technique which uses the algebraic properties of elliptic curves for the secure transmission of messages. All formalities aside, I will be explaining ECC in layman’s terms and I hope this ECC series will be helping you to grasp the concepts in an easy way.

Why ECC?

The most important part is to understand why we need something before we start to learn about it. The main motive to use ECC is that it gives the same security as RSA or any other cryptographic system with a lesser key size. As you can see below, ECC with 160 bit key size has the same strength as RSA with 1024 bit key size. Just imagine the computational cost savings!

ECC and Finite fields

For cryptographic uses, we will be using elliptic curves defined over a finite field. Confused? Don’t be. Let me explain you about finite field.

A field is basically a set of elements with two binary operations ‘+’ and ‘×’. A field will have the following properties:

1. (F,+) will be an abelian group.
2. (F∗,×) will be an abelian group where F∗=F-{0}. (i.e. All elements in F except zero)
3. Operation × distributes over +.

Incase you are confused about what an abelian group is, please refer this. Also, a finite field is a field with finite number of elements. Obviously!

Moving on, the elliptic curve used in cryptography can be defined over 2 types of fields.

1. Fields of the form Fpwhere p is a prime number.
2. Fields of the form F2^m .

Elliptic curve in field Fp

Field Fp = {0,1,2,…,p-1}. For example F5contains the elements {0,1,2,3,4}. The operations in a field such as Fp will be as follows:

1. Addition: a+b = (a+b) mod p, where a,b ∈ Fp
2. Subtraction: a-b = (a-b) mod p, where a,b ∈ Fp
3. Multiplication: a*b = (a*b) mod p, where a,b ∈ Fp
4. Division: a/b = (a* (inv b)) mod p, where (inv b) is the inverse of b with respect to p and a,b ∈ Fp

Please note that “mod p” operation equals to the remainder obtained after dividing with p. Therefore the result will be in the set {0,1,…,p-1}.

Also, the inverse of an element b in Fp is another element c in Fp such that (b*c) mod p = 1.

Elliptic curve in field F2^m

This field consists of elements of the form

which is basically any polynomial with degree less than m and coefficients ∈ {0,1}. i.e. All coefficients am-1,am-2,upto a0 is either 1 or 0. The operations in such a field will be as follows:

1. Addition: For two polynomials a(x) and b(x), add their corresponding coefficients mod 2. This is nothing but the XOR operation.
2. Subtraction: For two polynomials a(x) and b(x), subtract their corresponding coefficients mod 2. This is also the XOR operation. So, addition and subtraction is the same in modulo 2.
3. Multiplication: For two polynomials a(x) and b(x), multiply them mod c(x) where c(x) is an irreducible polynomial with degree m. Irreducible polynomial is analogous to prime number. A polynomial c(x) is said to be irreducible in a field F iff the polynomial can’t be factored to 2 or more non-constant polynomials.
4. Division: For two polynomials a(x) and b(x), multiply a(x) and (inv b(x)) mod c(x) where c(x) is an irreducible polynomial with degree m. (inv b(x)) is the inverse of polynomial b(x) with respect to c(x).

Conclusion

So in this session, we learned about the foundation level of ECC. The fields on which an elliptic curve is defined and the operations in the corresponding fields. In the next part, we will be learning about the second level of ECC — The real elliptic curve, point operations and its properties. See you soon!