Cryptography/Elliptic curve

Elliptic curve cryptography is a type of cryptography that relies on mathematical structures known as "elliptic curves" and "finite fields". An elliptic curve is a relation of the form $y^{2}=x^{3}+ax+b$, where $a$ and $b$ are preset parameters of the curve and $x$ and $y$ are the coordinates. Any $(x,y)$ pair that satisfies the relation is said to be a point on the elliptic curve. On elliptic curve points, it is possible to define an operation known as "addition" as follows:

To add two points $P$ and $Q$, draw a line through them, and locate the third point on the curve that the line passes through; call it $R$. If $P$ and $Q$ have the same x coordinate, the line joining them will be vertical and R will not exist, so in that case we call $P+Q$ the "point at infinity". The point at infinity added to any other point is that point itself, so this point at infinity can be thought of as the elliptic curve point analogue of the number zero. Otherwise, trace a vertical line from $R$ to the point at the same x coordinate on the opposite side of the curve. This point is defined as $P+Q$. To calculate $P+P$, instead take the tangent line to the curve at $P$, extend it to $R$ and take the vertically opposite point as the answer just like in the $P+Q$ case.

Because elliptic curves are mathematical functions, we can use the tools of high-school algebra and elementary calculus to derive formulas for $P+Q$ and $P+P$. For $P+Q$, for formula is:

$m={\frac {P_{y}-Q_{y}}{P_{x}-Q_{x}}}$

$(P+Q)_{x}=m^{2}-P_{x}-Q_{x}$

$(P+Q)_{y}=P_{y}+m(R_{x}-P_{x})$


For P+P:

$m={\frac {3P_{x}^{2}+a}{2P_{y}}}$
$(P+P)_{x}=m^{2}-2*P_{x}$

$(P+P)_{y}=P_{y}+m(R_{x}-P_{x})$

Notice that the algorithm in both cases is the same: first we find the slope at $P$, then we get the x-coordinate of the answer, and then we use the slope-point formula to get the y-coordinate. From these formulas, however, we get a very surprising result: $(A+B)+C=A+(B+C)$, regardless of whether $A$, $B$ and $C$ are different or the same. Additionally, from the visual definition it is obvious that $A+B=B+A$. These facts together mean that elliptic curve points form what is known as an _abelian group_ - a structure which supports addition, and therefore by extension multiplication by integers. For example, $4A=(A+A)+(A+A)=(A+(A+A))+A=(A+(A+(A+A)))$.

It's also quite easy to multiply an elliptic curve point by very large numbers. You might think multiplying a point by a billion requires you to add it to itself a billion times, but in reality there is a much simpler algorithm:

  define multiply(P, k) {
    if (k == 0) return point_at_infinity()
    if (k == 1) return P;
    if (k % 2 == 0) return double(multiply(P,k/2))
    if (k % 2 == 1) return add(P,double(multiply(P,(k-1)/2)))
  }

Basically, instead of repeatedly adding on the original point to zero many times, the algorithm repeatedly uses doubling, cutting the size of the problem in half at every step. For $k=83$, for example, the algorithm expands to:

 83p
 add(p,double(41p))
 add(p,double(add(p,double(20p))))
 add(p,double(add(p,double(double(10p)))))
 add(p,double(add(p,double(double(double(5p))))))
 add(p,double(add(p,double(double(double(add(p,double(2p))))))))
 add(p,double(add(p,double(double(double(add(p,double(double(p)))))))))

For $k=1000000000$, the algorithm takes a mere thirty steps. This makes it possible to multiply elliptic curve numbers by extremely large numbers - numbers so large, in fact, that there are not enough atoms in the universe to actually count to them.

Finite Fields

Now, we get into the more interesting part of elliptic curve mathematics. A while ago, mathematicians discovered that the forms of addition, subtraction, multiplication and division that we use today are not the only forms that are mathematically consistent. There are in fact many other structures, some using numbers and others using more complex forms like polynomials, over which we can define the basic operations in special ways and still have a working system of algebra. The most common is "modular arithmetic". Modular addition and multiplication are just like normal addition and multiplication, except after the calculation is done you divide the result by a preset value, called the "modulus", and take only the remainder. For example, in modulo 7:

$3+6=9\equiv 2{\pmod {7}}$

and

$5*4=20\equiv 6{\pmod {7}}$

Subtraction is similar, except if the result turns out to be negative you add the modulus to force it to be positive again. Thus:

$1-2=-1\equiv 6{\pmod {7}}$

Division is more complicated to implement, but is defined through multiplication - that is, $a/b{\pmod {7}}$ is defined to be a number $c$ such that $bc\equiv a{\pmod {7}}$. It can be proven that all modular divisions have an answer and no modular divisions have multiple possible answers if and only if the modulus is prime. Thus, we generally only care about "prime fields".

So what's the point of this spooky kind of arithmetic? Basically, it's a great kind of arithmetic to do elliptic curves over. No matter how much you add or multiply points together, the coordinates of the result will always be integers in the range $[0...p-1]$, where $p$ is the modulus. The "wrap around" property also makes the structure cryptographically secure; given a normal elliptic curve, given two points $G$ and $Q=k*G$, you can figure out the value of $k$ by looking at the size of the output and using that information to zero in on a small range of possibilities. With an elliptic curve over a prime field, all points look essentially the same; they're all numbers roughly evenly distributed within the range $[0...p-1]$. The hardness of this problem, figuring out $k$ given $G$ and $k*G$, is in fact the basis of elliptic curve cryptography's security.

The two most well-known algorithms over elliptic curves are the elliptic curve Diffie–Hellman protocol and the Elliptic Curve Digital Signature Algorithm, used for encrypting and signing messages, respectively.

This page or section of the Cryptography book is a stub. You can help Wikibooks by expanding it.