George Plotnikov

Personal site and blog. Please feel free to contact me via the social networks below.

   

Elliptic curves smalltalk #1

please visit the new revision of this article https://www.georgeplotnikov.com/elliptic-curves-smalltalk-vol-1/

Factorization on the elliptic curves was my diploma subject, so I decided to write some short note simply describes that the elliptic curves idea. If I had this note at the beginning of my research, I would save a lot of time 😃

Elliptic curves uses are:

What the elliptic curves are? Simply talk - that is the set of solutions of an equation of the form

Why they are interesting and why are they use in cryptography? The first fascinating fact is that we are able to summarize two points on a curve: if we have two points on a curve (P and Q), we may associate them to the third point and to call it as their sum. To do that we should intersect P and Q. That line will cross a curve at the only one point R, which then we will reflect R from X-axis[1]. That’s it.

The problem might be if we would try to summarize a point with itself. It’s not a problem, actually: that means the line becomes the tangent curve[2].

The second problem if we will try to summarize two symmetric points. In that case we assumes the solution is a point somewhere in infinity [3].

Basically we can easily sum a points programmatically with the following steps:

p.s. other words it means this is an Abelian group over sum.

On practice, coordinates of a point are in Finite field. for example:

important note: A finite field of order q exists if and only if the order q is a prime power , basically a fields of order 17 or 239 contains just of excees of division by modulus prime number.

Example :

note: if p is 2 or 3

In the real task it uses in DL suppose we have:

need to find this is the Diffie-Hellman DL base.

DL task separates to the two:

Classic task of DL:

need to find (not nulls excees of Finite field)

ECDLP:

need to find this is

The complexity in this case - is that the group of the point on an elliptic curve might be not cyclic. There is no generatrix point there. But we can select a point on the elliptic curve use of which we are able to generate Many points on the elliptic curve. If in the cyclic group we can power the generatrix number to get others non zero elements of the field, in elliptic curve case - we cannot multiple points, but can only sum them.

count of pointer restricted by square field size plus one. As Hasse’s theorem on elliptic curves tells us - the amount of pointers is about an order of field. Consequently - if the pointer generated big enough field, need to find what P was multiplied on to get Q.

important: if P and n is known - the calculation of Q might be done quickly :

to be continued…


Useful links: