George Plotnikov

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


Elliptic curves smalltalk #2

See the new version of this article here:

Consider Diffie–Hellman key exchange.

DH uses final field. For example

user select in as a key

user select in as a key

int this case key exchange will looks: user send to user send to

their public key is = . How do they calculate it? user A takes and vice versa. there we see that for finding a key, cursed user should solve discrete logarithm task.

where here we can find an elliptic curve? we should replace exponentiation with multiplication. each participant selects some number and to summarize a point (on an elliptic curve) with itself times. the point is already known, also known that it produces big enough sub-group in elliptic curve points group. Each user sends his to the participant and keeps in secret. Consequently, a public key will be calculated as summarizing the point from the other participant with itself his times.


El-Gamal system on EC

Suppose we have the pre-defined curve and a point. Curve, as known, is over some final field. User wants to send a message to user . Assume message is also a point on a curve.

Encrypted text from to will consists of the two parts:

  1. =
  2. = + receiver:

It means anyone can encrypt and send a message, but the only receiver who has both keys can decrypt it. Real life example is the post office. You came to send a post to your aunt. You are able to put your envelope into the box, but you cannot open it.


Elliptic curve digital sign algorithm

User wants to send message to user calculates hash and for the random


,  ,  ,  ,  

User checks the sign:

Elliptic cryptography pros and cons



Common problems usually lay in the implementation:

Let’s consider another cases of using EC.

Lenstra’s Factorization

Assume we have number which we want to factorize. This algorithm works fine if we suppose has not so big prime divider. In this algorithm, we consider not the EC over final field, but the set of points which are satisfied the same equitation as an EC (coordinates are ). We take some threshold number and declare that we will find any divider lesser or equals . Calculate point which is point -times summarized with itself. It means at the end of the loop we want to calculate . Why do we need this ? If we will try to calculate the following we can find the case with illegal summarize operation. It means we found some number immutable . Probably it’s multiplicator. If true, we should take a new random EC (point) and repeat algorithm. But if it is the lesser common divider - we found ’s divider (). might not be prime. The problem causes if is a multiplication of two big primes (~ ).

Average working time:

Useful links: