Cryptography based on elliptic curves

Csirmaz Laszlo <laci@degas.ceu.hu>

CEU

There is a hard-to-solve mathematical problem behind all public key cryptography system. For example, RSA uses the fact that while it is relatively simple to decide whether a number of several hundred digits is composite or not, it is beyond hope to find its prime factors. The so-called discrete logarithm problem is behind the Diffie--Hellman method. This problem can be phrased as follows: given the base and the result of an exponentiation, find the exponent. Here exponentiation is, of course, repeated multiplication, but for the multiplication we always take the remainder when dividing by a given large prime number. The problem can be worded in a more general settings. Given some kind of operation, called multiplication, among several (say 10¹⁰⁰ or so) objects. Choose a base g, an exponent n, and compute y=gⁿ. The task is to determine the exponent n, given y and g only. Elliptic curves present a mathematical way to come up with such a multiplication. It can be defined easily, computed fast, and only the general, ineffective algorithms are known for the induced discrete logarithm problem. Elliptic curves arise in algebraic geometry, maybe the most beautiful and the hardest part of mathematics. These curves are generalisations of the ones known from secondary school, such as circle, ellipse, parabola and hyperbola. The unit circle, for example, consists of all points with co-ordinates (x,y) satisfying x²+y²=1. The locus of points with y²=x³+ax+b is a typical elliptic curve. On its points we could define a multiplication, which then can be used for a public key cryptographic system as indicated above.