? Editing: Post:21.body Save Delete Cancel
Content changed Sign & Publish new content

Ivanq's Blog

Posts about encryption, zite development and everything else you want

Follow in NewsfeedFollowing

Latest comments:

Add new post

Title

21 hours ago · 2 min read ·
3 comments
Body
Read more

Not found

Introduction into Elliptic Curve arithmetic

on Apr 28, 2019 · 5 min read

Today, let's talk about Elliptic Curve arithmetic.

Elliptic curves

First of all, what is an elliptic curve? If we're working in R\R field, we can say that an elliptic curve is defined by two real numbers aa and bb that follows the equation:

x2=y3+ax+b
x^2 = y^3 + ax + b

This form is called the Weierstrass equation.


We should also mention that this curve should be non-singular, for example:

If a=b=0a = b = 0 the curve is non-singular, and thus it's not an elliptic curve.

Interesting properties of elliptic curves

Pretend we have two different points PP and QQ both belonging to an elliptic curve. If we draw a line through them, we can see that, in some cases, it intersects the curve in 3 points (including PP and QQ), and sometimes in two points (PP and QQ themselves), but you'll never have 4 points (or more) on the same line.

What does this mean?

Let's say that, for any PP, QQ and RR belonging to the same line, P+Q+R=OP + Q + R = O.

Notice that the OO point is not really a point, but rather a special value.

We can now find some interesting properties, for example:

  1. The elliptic curve is symmetric. For example, if (x,y)(x, y) belongs to the curve, (x,y)(x, -y) will do as well. Let's define P=(x,y)-P = (x, -y) if P=(x,y)P = (x, y).

  2. If you draw a line through PP and P-P, it won't have any other intersection points. In this case, let's say that P+(P)+O=OP + (-P) + O = O.

  3. P,Q,R:P+Q+R=Q+P+R\forall P, Q, R: P + Q + R = Q + P + R

  4. P,Q:(P+Q)+R=P+(Q+R)\forall P, Q: (P + Q) + R = P + (Q + R)

  5. Since QQ and RR may be the same point, any other PP would be okay. Instead, let's say that we want such PP that it is the only other point of intersection. In fact, this means that the line is the tangent. Thus, P,Q:P+Q+Q=O    PQ is a tangent\forall P, Q: P + Q + Q = O \iff PQ \space \text{is a tangent}.

  6. Since OO may be an argument, let's say that it belongs to any line, i.e. it's a neutral element — thus, P,Q:P+Q+O=O\forall P, Q: P + Q + O = O.

  7. If we combine 5. and 6., we get that P:P+P+O=O\forall P: P + P + O = O.

ECClines.svg (680x206)

So, now we understand that OO should be a neutral element to make at least some sense.

Addition

So, why did we need this?

P+Q+R=O    P+Q=RP + Q + R = O \implies P + Q = -R

Woah!

If we say that OO is the same as a zero in real numbers, we now get an algorithm to get the sum of two points.

  1. Draw a line through PP and QQ.

  2. Intersect it with the curve and get RR.

  3. Invert RR.

Moreover, we can notice that all the usual properties apply, i.e.: P+Q=Q+PP + Q = Q + P and (P+Q)+R=P+(Q+R)(P + Q) + R = P + (Q + R).

Algebraic implementation

Instead of using geometrical interpretation which would be difficult to transform into formulas, we'll use the following rule:

Given xP,yP,xQ,yQx_P, y_P, x_Q, y_Q, we get xRx_R and yRy_R, such that P+Q=RP + Q = R.

s=yPyQxPxQxR=s2xPxQyR=yP+s(xPxR)
s = \frac{y_P - y_Q}{x_P - x_Q} \newline
x_R = s^2 - x_P - x_Q \newline
y_R = -y_P + s(x_P - x_R)

If xP=xQx_P = x_Q, i.e. ss is not defined, and yP=yQy_P = -y_Q, it's easy to notice that P+Q=OP + Q = O, and, thus, R=OR = O as well. Notice that the P=Q=OP = Q = O case is handled here as well.

If xP=xQx_P = x_Q, and yP=yQ0y_P = y_Q \neq 0, we want the tangent, thus:

s=3xP2+ayP+yQ
s = \frac{3 x_P^2 + a}{y_P + y_Q}

I won't prove this fact here, but you can notice that it gives the same results as the geometrical way.


Conclusion

An elliptic curve is defined the following way: y2=x3+ax+by^2 = x^3 + ax + b. We can define addition, such that, given two points (or zeroes) PP and QQ, we can get RR. This "addition" follows the P+Q=Q+PP + Q = Q + P and (P+Q)+R=P+(Q+R)(P + Q) + R = P + (Q + R) properties.

Why would you need this? I'll tell you the next time.

4 Comments:

user_name1 day ago
Reply
Body
leftsideon Apr 30, 2019
Reply

gitcenter: Sorry, something went wrong. Fixed now!

Great! thanks for ur kind work!

gitcenteron Apr 29, 2019
Reply

leftside: All mathematical equations seem to look raw html tags..!what's wrong?

Sorry, something went wrong. Fixed now!

leftsideon Apr 29, 2019
Reply

All mathematical equations seem to look raw html tags..!
what's wrong?

glightstaron Apr 28, 2019
Reply

even tho I don't quite understand all of the mathematical equations, this article does seem like a good round-up of what an elliptic curve is 👍

This page is a snapshot of ZeroNet. Start your own ZeroNet for complete experience. Learn More