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:

Bitcoin
SSH
TLS
Citizen Card (Austria)

What the elliptic curves are? Simply talk - that is the set of solutions of an equation of the form $Y^{2}=X^{3}+AX+B$

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 $\varnothing$ [3].

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

$P_{1}=(x_{1},y_{1}) P_{2}=(x_{2}, y_{2})$
suppose both points are not a $\varnothing$
- line, intersected ,
- $\lambda =(y_{2}-y_{1})/(x_{2}-x_{1})$ or
- $\lambda =(3x_{1}^{2}+A)/(2y_{1})$
- $\nu = y_{1} - \lambda x_{1}$
substitute $Y = \lambda X + \nu$ into line equtation
- $x_{3}= \lambda ^{2} - x_{1} - x_{2}, y_{3} = \lambda (x_{1} - x_{3})-y_{1}$
as you see, we event don’t need to resolve cubic equitation 😃 Now, lets clarify the definition of the elliptic curves: $Y^{2}=X^{3}+AX+B, 3A^{3}+27B^{2}\neq \varnothing$ , plus the addition point $\varnothing$

This kind of summarizing is very useful and looks similar to sum the numbers:
$(P\oplus Q)\oplus R=P \oplus (Q \oplus R)$
$P \oplus \varnothing = \varnothing \oplus P$
$P \oplus -P = \varnothing$
$P \oplus Q = Q \oplus P$

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:

Real number
Complex number
Finite fields $F_{p}$ and $F_{p^t}$

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

Example $F_{p}$ :

$Y^{2}=X^{3}+AX+B$
replace R with $F_{p}$ , $p=q^{t}$ , $q \neq 2,3$
over
- $(1,1) \in E, (4,1) \notin E$
use the previous algotithm

note: if p is 2 or 3

$p=2^{t}$
- $Y^{2}+CY=X^{3}+AX+B$ or
- $Y^{2}+CXY=X^{3}+AX^{2}+B$
$p=3^{t}$
- $Y^{2}=X^{3}+AX^{2}+BX+C$

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

$G=\{g,g^{2},...,g^{n-1},g^{n}=e\}$ - circle group (all elements are the power one of the element in this group)
$h \in G$

need to find $x, g^{x}=h$ this is the Diffie-Hellman DL base.

DL task separates to the two:

Classic task of DL:

p - Prime
$g,h \in Z$

need to find $g^{x} \equiv \mod p$ (not nulls excees of Finite field)

ECDLP:

E - elliptic curve
$P,Q \in E(F_{p})$

need to find $n,nP=Q$ this is $n = log_{P} Q$

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.

$nP=mP$ $\varnothing = (m-n)P = P+...m...+P-P...n...P$ 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 $O(\sqrt p)$ : $5P=(P+P)+(P+P)+P$

to be continued…

Useful links: