Elliptic Curve Algorithm (ECC)

ECC operations and performance

Elliptic curves (ECC) are a plane algebraic curve with the form:

    \[y^2=x^3+ax+b \]

General definition

    \[y^2=x^3-px-q\]

where p and q are elements such that x^3-px-q does not have double root.

ECC as a group

The curve is symmetrical about the x-axis, so given point P, we can take -P.

if P and Q are two points on the curve, P+Q operation is defined as the intersection point of the line PQ, it generates a third point R, then we take -R.

Homogeneous coordinates

Point at infinity, \textit{O}, [0:1:0]


Operations

  • Inverse

P=(P_x,P_Y) \implies -P=(P_x,-P_y)

 

  • Addition

Case 1: x_p\neq x_q

R is the inverse of the intersection of the line PQ with the elliptic curve. Let S be -R.\\
PQ‘s slope:

    \[ \lambda=\frac{y_p-y_q}{x_p-x_q} \]

Points of intersection:

    \[ \left\{ \begin{array}{ll} y=y_p+\lambda(x-x_p)\\ y^2=x^3+ax+b\\ \end{array} \right. \]

We substitute the first into the second equation to get:

    \[ x^3-\lambda^2x^2+(a+2\lambda^2x_p-2\lambda y_p)x+a-(\lambda x_p-y_p)^2=0 \]

The three solutions to that cubic equation give the x-coordinate x_p,x_q,x_s of the three points of intersection of the line with the curve.\\
From Vieta’s first formula, we see the sum of those x-coordinates in \lambda^2 so that x_p+x_q+x_s=\lambda^2. When we reflect S over the x-axis, the x-coordinate does not change, so x_r=x_s. Thus,

    \[x_r=\lambda^2 -x_p-x_q \]

Using the equation of the line,

    \[y=y_p+\lambda(x_s-x_p) \]

When we reflect S over the x-axis, the sign of the y-coordinate changes (y_r=-y_s)

    \[ y_r=\lambda(x_p-x_r)-y_p \]

Case 2: y_p=y_q=0

    \[R=\textit{O} \]

Case 3: y_p=-y_q\neq 0

    \[R=\textit{O} \]

  • Duplicate

We need to calculate the slope (\lambda) at a point

    \[\frac{dy^2}{x}=3x^2+a \]

    \[\lambda=\frac{dy}{dx}=\frac{3x^2+a}{y} \]

We can use use the equation we have deduced before:

    \[ x_r=\lambda^2-2x_p \]

    \[ y_r=\lambda(x_p-x_r)-y_p \]

 

RSA Algorithm and C++ implementation

3 thoughts on “Elliptic Curve Algorithm (ECC)”

Leave a Reply

Your email address will not be published. Required fields are marked *