New blogpost on SIDH, a key-exchange protocol based on supersingular isogenies.

Hope you enjoy! M x

Skip to content
# Tag: elliptic

## SIDH

## Vélu’s Formulas for SIDH

## Elliptic Curves: The Basics

### Point at Infinity

### Making Points on an Elliptic Curve into a Group

### Consequence

## Elliptic Curve Cryptography

New blogpost on SIDH, a key-exchange protocol based on supersingular isogenies.

Hope you enjoy! M x

A new post is up on my website on Vélu’s formulas for Supersingular Isogeny Diffie-Hellman! Click here to read it.

Hope you enjoy! – M

Working over the rationals (or more precisely any field with characteristic 0) an **elliptic curve** is a curve given the equation

such that the discriminant, which is 4A^{3} + 27B^{2}, is non-zero. Equivalently, the polynomial on the right hand side has distinct roots, ensuring that the curve is non-singular. Though we restrict our attention to these non-singular curves we note that if the right hand side is a cubic polynomial, there are only two types of singular curves, corresponding to whether there is a double root (*node*) or triple root (*cusp*).

The point at infinity is an important point that **always** lies on an elliptic curve. For those who have studied algebraic geometry this is a familiar concept and comes from defining a projective closure of the equation defining the elliptic curve. However, informally it can be described as an idealised limiting point at the ‘end’ of each line.

If you imagine a vertical straight line, which intersects the elliptic curve at most two times.

The point at infinity is the point at which the two ends of this vertical line ‘meet’.

The reason that elliptic curves are amazing objects is because we can use geometry to make the points on the curve a group. Therefore we can use tools from algebraic number theory to study them.

This is done using the *chord and tangent process*:

We denote the point at infinity on an elliptic curve E over **Q** as O_{E}. E meets each line in 3 points, counted with multiplicity. Given two points on E, say P and Q, let R be the third point of intersection of PQ and E. Then P ⊕ Q is the third point of intersection of O_{E}R (vertical line through R) and E.

If P = Q we take the tangent at P instead of the line PQ.

Then E with the group law on points defined above, denoted by (E, ⊕), is an abelian group:

- The fact that is abelian is clear by construction
- I
**dentity:**O_{E}– this is why the point at infinity is such an important point and exists on all elliptic curves.

**Inverses:**Given a point P, let S be the point of intersection of the tangent at O_{E}and E. Then let Q be the intersection of PS and E. Then the inverse of P is defined to be Q. Note that if O_{E}is a point of inflection (point of multiplicity 3) then S = O_{E}in the above.

**Associativity:**This is much harder to prove. It can be done by identifying (E, ⊕) with a subgroup of the Picard Group, which related to something called*divisors*.

Divisors are a tool for keeping track of poles and zeroes. For example, suppose a function *g* has a zero at a point P of order 3, and a pole at another point Q of order 2, and a pole at O of order 1 (note the number of zeroes and poles are equal, as they must be for a function). Then using divisors, we can say all this concisely as follows:

**div g=3P−2Q−O**

More precisely, we can define a divisor D to be a ‘formal sum’ of points on E (meaning that we write a sum of points using a + symbol but no actual operation is defined), say

Then the **degree** of a divisor is the sum of the coefficients.

This set of divisors forms a group, Div(E), generated by the points on E. Immediately we can identify a subgroup of Div(E), namely the divisors of **degree zero** denoted Div^{0}(E).

We can also define an equivalence relation ~ on divisors: D_{1}, D_{2} ∈ Div(E) are** linearly equivalent,** written D_{1} ~ D_{2}, if exists an *f* such that **div(f) = D _{1} – D_{2}**.

We can now introduce the **Picard Group**. It is a subgroup of Div(E), defined by quotienting out by this equivalence relation

A subgroup of the Picard group is given by

We’re now ready to go back to talking about elliptic curves. The point of this discussion is that we know (Pic_{0}(E), +) is a group which has the associative property. Furthermore, we can show that we have a bijection between (E, ⊕) and (Pic_{0}(E), +) that preserves the group structure i.e. we have an isomorphism of groups. So, using this isomorphism we can identify the two groups and deduce that (E, ⊕) is also associative.

Say we started looking at points defined over **Q** (denoted by E(**Q**)). A natural question is to ask how we know that the addition or inverses of these points remains in **Q**?

We defined the group law by looking at the intersections of lines and curves. So, working through the algebra, we can get explicit equations for the addition of points and inverses. For example if we have an elliptic curve E over **Q** and a point P = (x,y) in E(**Q**), then **-P = (x, -y)**.

These explicit equations are useful because they tell us that the points do indeed remain defined over **Q**. More precisely, we find that (E(**Q**), ⊕) is a subgroup of (E, ⊕):

- The identity O
_{E}is in E(**Q**) by definition - (E(
**Q**), ⊕) is closed under addition and has inverses by the explicit formulae - Associativity and commutativity is inherited from (E, ⊕).

Note: This in fact holds for any field K, not just **Q**, but we must be a bit more careful, as the elliptic curve may not be expressible in the nice form y^{2} = x^{3} + Ax + B so the formulae are a bit messier. The reason why this is important is that we often want to consider elliptic curves over *finite fields*, something I will explore in future posts.

M x

__What are Elliptic Curves?__

An elliptic curve is a cubic curve whose solutions are confined to a region of space that is topologically equivalent to a torus (doughnut-like shape). It’s defined by an equation in the form:

where

as this ensures that the curve has no singular points (the curve is nice and smooth and doesn’t contain any sharp points or cusps).

They have shown potential as a tool for solving complicated number problems. Additionally, in the last few decades there has been a lot of research into using elliptic curves for encryption instead of RSA encryption to keep data transfer safe online.

__Elliptic Curve Cryptography__

Elliptic Curve Cryptography is an example of public key cryptography. This is when the messages are encrypted using a public key. Decryption is then only possible using a mathematical private key, which is almost impossible to determine if you only know the public key.

Elliptic Curve cryptography is based on the difficulty of solving number problems involving elliptic curves.

Bellow are some examples of elliptic curves:

For uses in cryptography a and b are required to come from special sets of numbers called finite fields (a field that contains a finite number of elements).

__Adding Points__

Let’s consider the curve

and the two points A = (2,1) and B = (-2, -1), both of which lie on the curve. Now, we want to find an answer to A = B, which should also lie on the elliptic curve.

Thus, by joining the points A and B with a straight line, we can see that it intersects the curve in one more place, point C. We then reflect this point in the x – axis and define it as point C’. Therefore,

A + B = C’.

In our example this means that

(2,1) + (-2,-1) = (1/4, -1/8)

The only situation where C’ is not equal to A + B is when B is a reflection of A in the x-axis. In this case, the line we use to define the sum is vertical and there isn’t a third point at which it meets they curve.

Below is an image to depict the different cases which may arise with different points:

It turns out that, given two points A and B on an elliptic curve, finding a number *n* such that **B = nA** can take an enormous amount of computing power, especially when *n* is large. In elliptic curve cryptography points A and B can be used as a public key and the number *n* as the private key. Anyone can encrypt a message using the publicly available public key, but only the person in possession of the private key – the number *n* – can decrypt them.

__Advantages__

Elliptic curve cryptography has some advantages over RSA cryptography, which is based on the difficulty of factorising, as fewer digits are required to create a problem of equal difficulty. Therefore data can be encoded more efficiently and rapidly than using RSA encryption.

However, no one has proved that it has to be difficult to crack elliptic curves, and in fact there may be a novel approach that is able to solve the problem in a much shorter time. Indeed many mathematicians and computer scientists are working in this field.

So what are your thoughts on elliptic curve cryptography? M x