Elliptic curves (sum and multiply)

Question

I was wondering if someone could give me some resources on elliptic curve cryptography. Specifically I need to know how to do something like:

$y^2=x^3-x+1$ compute $(0,1)⊕(1,1)$ or

$y^2=x^3+x^2-x$ compute $2*(-1,1)$

I can't seem to find anything that explains how to do things like this online

$y^2=x^3-x+1$ compute

$(0,1)⊕(1,1) =(-1,-1)$

$(-1,-1)⊕(1,1) =(1,-3)$

$(1,-1)⊕(3,5) =(5,-11)$

$2*(3,5)=(-6,-5)$

Answer 1

For the first one, find the equation of the line through the two given points: It is $y=1$. Find the three intersection between this line and the curve. Substituting in $y=1$ in the curve equation and simplifying gives $x^3-x=0$, with the three solutions $x=0$, $x=1$, and $x=-1$. (If the equation had been any harder, you could have simplified it by dividing by $x(x-1)$, since you already know that $x=0$ and $x=1$ are solutions.) The new solution is $x=-1$, so the third point on the curve and the line is $(-1,1)$. Now flip the $y$ coordinate to get the answer $(-1,-1)$.

See? It's easy, you don't need any textbook for this. For the second one, note that you're asked to produce the sum of $(-1,1)$ with itself.

What you do need textbooks for, is to understand the theory of elliptic curves. See the answer by Ferra for some possible ones. There will be many more.

Answer 2

You don't need a text on cryptography, these are elementary facts that you find on every elliptic curves text. For example, check J.Silverman's "The arithmetic of elliptic curves" or Washington's "Elliptic curves: number theory and cryptography".

Answer 3

See Harald Hanche-Olsen for most of the solution.
When the two points are the same, there are lots of lines through them. You need the line that is tangent to the curve at that point.
Differentiate the equation to find the slope of the tangent $$ 2y\frac{dy}{dx}=3x^2+2x-1$$ and, oddly enough, the slope of the line $dy/dx$ is zero again, and the line is $y=1$ again. $x^3+x^2-x-1=(x+1)^2(x-1)$ so the third point is $(1,1)$. Flip the $y$-coordinate and $2(-1,1)=(1,-1)$

Answer 4

There are formulae for these operations: http://en.m.wikipedia.org/wiki/Elliptic_curve_point_multiplication. Simply fill in the formulae to get the answers.

Answer 5

To add together two points on an elliptic curve we calculate the line between the two points, $P$, and $Q$, and find the point, $-R$, where this line crosses the curve for a third time. We reflect this point in the $x$ axis to obtain the point $R=P\oplus Q$

Point Addition

When we have two distinct points, $P$ and $Q$, we can add them together to obtain a point $R=P\oplus Q$

We can calculate $R=\left(x_{R},y_{R}\right)$ as follows:

Given $P=\left(x_{P},y_{P}\right)$ and $Q=\left(x_{Q},y_{Q}\right) $, first calculate $$s=\frac{y_{P}-y_{Q}}{x_{P}-x_{Q}}$$

Then we can say that $$x_{R} =s^{2}-\left(x_{P}+x_{Q}\right)$$ $$y_{R} =s\left(x_{P}-x_{R}\right)-y_{P}$$

Point Doubling

To double a point $P$ we calculate the tangent at that point and calculate $R=P\oplus P$

We can calculate $R=\left(x_{R},y_{R}\right)$ as follows:

Given $P=\left(x_{P},y_{P}\right)$ and $Q=\left(x_{Q},y_{Q}\right) $, first calculate $$s=\frac{3x_{P}^{2}+a}{2y_{P}}$$

where $y^{2}=x^{3}+ax+b$ is the equation of the curve

Then we can say that $$x_{R} =s^{2}-2x_{P}$$ $$y_{R} =s\left(x_{P}-x_{R}\right)-y_{P}$$

If there is no such point $R$ then we take $P+P=-P$ i.e. we take the point opposite $P$ to be equal to $2P $

Vertical Points

When adding vertical points, we will obtain a value of $\mathcal{O}$, the point at $\infty$

$P+Q=\mathcal{O}$ if $x_{P}=x_{Q} $

$P+P=\mathcal{O}$ if $y_{P}=0 $

Scalar Multiplication of Points

We can calculate $k*P$ for an integer $k$ and a point on the curve $P=\left(x_{P},y_{P}\right)$ by computing $\underset{k\text{ times}}{\underbrace{P+P+\cdots+P}} $