Blog

We have already learned about elliptic curves in simple Weierstrass form over a finite field and the group structure the points of such curve form that we can use all this information to look at some cryptography built on top of this. Going from the point negation, doubling and addition over scalar multiplication and prime order curves with no problematic points to the discrete logarithm problem and back, we show how to perform a secure key exchange using our favourite doughnuts.

Algebraic groups built on top of points of elliptic curves together with the scalar multiplication specified as repeated addition can be used as basic building blocks for asymmetric cryptography systems. The strength of these systems if derived from the toughness of the reversing the scalar multiplication operation. It is very expensive to reverse this operation and to answer a question like "how many times we have to multiply point G to get given point P". This problem is called Elliptic Curve Discrete Logarithm Problem - or ECDLP for short. In this article we show the toughness of this problem.

Last time we have shown how to perform scalar multiplication of point on elliptic curve in simple Weierstrass form over a finite field. We have also shown that all the required properties hold for all rational points of the curve - which is a good thing. The problem we have not tackled yet is the complexity of the scalar multiplication operation. Today we are about to present a method of performing fast scalar multiplication in which the complexity of the operation grows much slower than the size of the scalar.

As we have shown last time, just mapping elliptic curve in simple Weierstrass form over a finite field does not make the curve automatically practical for cryptography. Using just a few points from the whole set cannot be very secure. Today we present two important properties the curve must possess in order to be of some practical use.

Applying the scalar multiplication to points on elliptic curves over finite fields works the same way as over real numbers. The difference is that over a finite field, the operation can actually be - and it is - used for some real-world cryptography. If we look at the operation in detail, we also find some interesting features which may help or complicate things a bit when it comes to implementing such cryptography. This week we show how it works.