Blog

After slightly going astray from the elliptically curved path on our favorite doughnuts, we return from the realm of electronic mail to much more interesting world of mathematics. Today, our effort to explain elliptic curves in simple Weierstrass form and their usage should reach its second culmination. With Diffie-Hellman key exchange explained, the only part that is missing is some digital signature scheme. So please read on to find the beauty of the Elliptic Curve Digital Signature Algorithm beast.

Last week we have discussed something rather boring - casual email communication and the security implications (or more like the lack of security) of using it. We have just re-phrased the well-known fact that casual email communication is far from secure with respect to confidentiality, integrity and authenticity. Today we are about to present a widely used class of solutions that make Eve's life harder, but I am afraid that today is not the day I can present you with ultimate solution to email communication security. But as you probably know, security is a gradual process rather than a product - a silver bullet - that solves all your problems. Read on for our gradual approach.

After ranting about elliptic curves for more than three months, it is probably the time to pause for awhile and think where the encryption based on elliptic curves of some kind might be really needed. Although many people might disagree, for some of us, liberating the communication between people is the most important thing the Internet brought. And although the generic data communication by transferring data packets over the network do not provide much convenience to an ordinary human being, if we look at some real human-to-human communication on the Internet, the email fits in really well. It has its quirks - but what does not?

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.