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

18 thoughts on “Elliptic Curve Algorithm (ECC)”

  1. Hi, i believe that i noticed you visited my website thus i got here to go back thewant?.I?m attempting to find issues to enhance my website!I suppose its ok to use some of your ideas!!| Hi there, just became alert to your blog through Google, and found that it is really informative. I am gonna watch out for brussels. I will appreciate if you continue this in future. Many people will be benefited from your writing. Cheers!|

  2. I just want to mention I’m new to blogging and honestly liked your blog. Almost certainly I’m likely to bookmark your blog post . You amazingly come with wonderful writings. Thanks for sharing with us your web page.

  3. For the reason that the admin of this website is working,
    no hesitation very soon it will be well-known, due to its feature
    contents.

  4. magnificent post, very informative. I wonder why the other specialists of this sector do not notice this. You must continue your writing. I am sure, you’ve a great readers’ base already!

  5. whoah this weblog is great i really like studying your articles. Keep up the good paintings! You realize, a lot of people are searching round for this info, you could aid them greatly.

  6. I am usually to running a blog and i actually recognize your content. The article has really peaks my interest. I am going to bookmark your site and keep checking for new information.

  7. excellent issues altogether, you just won a new reader. What could you recommend about your post that you made a few days ago? Any sure?

  8. I’m impressed, I must say. Seldom do I encounter a blog that’s equally educative and entertaining, and let me tell you,
    you have hit the nail on the head. The problem is an issue that too few folks are speaking intelligently about. I’m very happy that I came across this in my hunt for something regarding this.

  9. This is very interesting, You’re a very skilled blogger.
    I’ve joined your RSS feed and look forward to seeking more of your excellent post.
    Also, I have shared your website in my social networks!

  10. Hi! I was reading your blog for the first time on my phone and wanted to say I really liked it. I thought I’d share a website too. You can learn about who was I in my past life there. Check it out if you’re interested. Thanks!!

Leave a Reply

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