# Finite projective planes

Given a field F, finite or infinite, you can construct a projective plane over F by starting with pairs of elements of F and adding “points at infinity,” one point for each direction.

## Motivation: Bézout’s theorem

A few days ago I mentioned Bézout’s theorem as an example of a simple theorem that rests on complex definitions. Bézout (1730–1783) stated that in general a curve of degree n and a curve of degree m intersect in nm points. There are a lot of special cases excluded by the phrase “in general” that go away when you state Bézout’s theorem in a sophisticated context.

To make Bézout’s theorem rigorous you have to work over an algebraically complete field (e.g. the complex numbers rather than the real numbers), you have to count intersections with multiplicity, and you have to add points at infinity, i.e. you have to work in a projective plane.

## Motivation: Elliptic curves

Bézout’s theorem involves infinite field ℂ, but this post is about finite projective planes. Elliptic curves over finite fields provide a motivating example of working in finite projective planes.

This blog is served over HTTPS and so serving up its pages involves public key cryptography. And depending on what protocol your browser negotiates with my server, you may be using elliptic curve cryptography to view this page.

An elliptic curve over a finite field is not an ellipse and not a curve, at least not a curve in the sense of a continuum of points. Elliptic curves over ℝ really are curves in the usual sense, but the definition is then abstracted in a way that extends to any field, including finite fields.

## Homogeneous coordinates

In order to make this idea of “points at infinity” rigorous, we have to introduce a new coordinate system. We now describe points by (equivalence classes of) triples of field elements rather than pairs of field elements. The benefit of this added complexity is that points at infinity can be handled perfectly rigorously. Often the third coordinate can be ignored, but then you pay attention to it when you need to be careful.

In homogeneous coordinates, we consider two points (x, y, z) and (x′, y′, z′) equivalent if there is a λ ≠ 0 such that

(x, y, z) = (λx′, λy′, λz′).

Also, we require that not all three coordinates are 0, i.e. (0, 0, 0) is not an element of the projective plane.

We associate a point (x, y) with the triple (x, y, 1) and all its equivalents, i.e. all triples of the form (λx, λy, λ) with λ ≠ 0.

## Points at infinity

A point at infinity is simply a point with third coordinate 0.

In the post mentioning Bézout’s theorem I said in passing that the lines y = 5 and y = 6 meet at infinity. Here’s how we can make this rigorous. The line y = 5 in the finite plane is the set of points of the form (x, 5), which embed in the projective plane as

(x, 5, 1)

and these points are equivalent to the set of points

(1, 5/x, 1/x)

Now take the limit as x → ∞ and we get (1, 0, 0). We consider this addition point to be part of the line y = 5 when the line is considered part of the projective plane. You can see that the line y = 6 contains the same point. So we can be very specific about where the lines y = 5 and y = 6 intersect: they intersect at (1, 0, 0).

You can go through a similar exercise to show that the lines y = x and y = x – 57 also intersect “at infinity” but at a different point at infinity, namely at (1, 1, 0) and its equivalents.This also shows that although the lines y = 5 and y = x both go off to infinity, they “reach” infinity at different points. The former goes to the point at infinity associated with horizontal lines and the latter goes to the point at infinity associated with 45 degree lines.

Note also that parallel lines meet at one point at infinity, not two. You might want to say, for example, that y = 5 and y = 6 meet twice, once at positive infinity and once at negative infinity. You could construct a system that works that way, but that’s not now projective planes work. Since non-zero multiples of a point are equivalent, (1, 0, 0) and (-1, 0, 0) are in the same equivalence class.

See this post for practical examples of when you might choose to have one or two points at infinity depending on your application.

## Finite projective planes

We can construct projective planes containing a finite number of points by repeating the construction above using a finite field F. Finding finite projective planes not isomorphic to one constructed this way is hard [1].

Let F be a finite field with q elements. Then q is necessarily either a prime or a power of a prime, though that fact isn’t needed here.

The points of the finite projective plane over F are the points of the finite plane over F, i.e. pairs of elements of F, and the additional “points at infinity.” We can say exactly what these points at infinity are and count them.

A point (x, y) is embedded in the projective plane as (x, y, 1) and all points in its equivalence class. So for starters we have at least q² points in the finite projective plane, one for each pair (x, y).

First consider the case x ≠ 0. Then (x, y, 1) is equivalent to (1, y/x, 1/x) and so without loss of generality we can assume x = 1 (the multiplicative identity of the field). So for each y, (1, y, 0) is a point at infinity. That gives us q more elements of the finite projective plane.

Next consider the case x = 0. Then (0, y, 0) is another point at infinity as long as y ≠ 0. It’s only one point, because all non-zero multiples of (0, 1, 0) are in the same equivalence class.

So all together we have q² + q + 1 points, represented by the following elements of their equivalence classes:

• (x, y, 0) for all x, y in F,
• (1, y, 0) for all y, and
• (0, 1, 0).

## Related posts

[1] There are for non-isomorphic finite projective planes of order 9, i.e. planes with 9² + 9 + 1 = 91 points. And there are other examples of finite projective planes not isomorphic to planes constructed as outlined here. However, so far all such planes have the same number of points as a finite projective plane constructed as above.

Since you can describe a point in the plane with two numbers, why would you choose to use three numbers? Why would you ever want to use a coordinate system with more coordinates than necessary?

## Barycentric coordinates

One way to indicate the location of a point inside a triangle is to give the distance to each of the vertices. These three distances are called barycentric coordinates. Why would you use three numbers when two would do?

Barycentric coordinates make some things much simpler. For example, the coordinates of the three vertices are (1, 0, 0), (0, 1, 0), and (0, 0, 1) for any triangle. The points inside are written as convex combinations of the vertices. The coordinates of the center of mass, the barycenter, are (1/3, 1/3, 1/3). The vertices are treated symmetrically, even if the triangle is far from symmetric.

Barycentric coordinates are useful in applications, such as computer graphics and finite element analysis, because they are relative coordinates. When a triangle moves or is rescaled, you only need to keep track of where the vertices went; the coordinates of the points inside relative to the vertices haven’t changed.

This can be generalized to more dimensions. For example, you could describe a point in a tetrahedron with four coordinates, more in higher dimensions you could describe a point in an n-simplex by the convex combination coefficients of the n vertices.

Barycentric coordinates are related to Dirichlet probability distributions. When you have n probabilities that sum to 1, you’ve got n-1 degrees of freedom. But it often simplifies things to work with n variables. As with the discussion of triangles above, the extra variable makes expressions more symmetric.

## Quaternions and rotations

A point in three dimensional space can be described with three numbers, but it’s often useful to think of the usual three coordinates as the vector part of a quaternion, a set of four numbers.

Suppose you have a point

a = (x, y, z)

and you want to rotate it by an angle θ around an axis given by a unit vector

b = (u, v, w).

You can compute the rotation by associating the point a with the quaternion

p = (0, x, y, z)

and the axis b with the quaternion

q = (cos(θ/2), sin(θ/2) u, sin(θ/2) v, sin(θ/2) w)

The image of a is then given by the quaternion

q p q-1.

This quaternion will have zero real part, and so the Euclidean coordinates are given by the vector part, the last three components.

Of course the product above is a quaternion product, which is not commutative. That’s why the q and the q-1 don’t cancel out.

Using quaternions for rotations has several advantages over using rotation matrices. First, the quaternion representation is more compact, describing a rotation with four real numbers rather than nine. Second, the quaternion calculation can be better behaved numerically. But most importantly, the quaternion approach avoids gimbal lock, a sort of singularity in representing rotations.

## Projective planes

In applications of algebra, such as elliptic curve cryptography, you often need to add “points at infinity” to make things work out. To formalize this, you add an extra coordinate. So while an elliptic curve is usually presented as an equation such as

y² = x³ + ax + b,

it’s more formally an equation in three variables

y²z = x³ + axz² + bz³.

Points in the projective plane have coordinates (x, y, z) where points are considered equivalent if they differ by a non-zero multiple, i.e. (x, y, z) is considered the same point as (λx, λy, λz) for any non-zero λ.

You can often ignore the z, choosing λ so that the z coordinate is 1. But when you need to work with the point at infinity in a uniform way, you bring out the full coordinates. Now the “point at infinity” is not some mysterious entity, but simply the point (0, 1, 0).

## Common themes

Projective coordinates, like barycentric coordinates, introduce symmetry. With the addition of an extra coordinate, the three coordinates all behave similarly, with no reason to distinguish any coordinate as special. And as with quanternion rotations, projective coordinates make singularities go away, which is consequence of symmetry.

# Elliptic curve P-384

The various elliptic curves used in ellitpic curve cryptography (ECC) have different properties, and we’ve looked at several of them before. For example, Curve25519 is implemented very efficiently, and the parameters were transparently chosen. Curve1174 is interesting because it’s an Edwards curve and has a special addition formula.

This post looks at curve P-384. What’s special about this curve? It’s the elliptic curve that the NSA recommends everyone use until post-quantum methods have been standardized. It provides 192 bits of security, whereas more commonly used curves provide 128 bits.

Does the NSA recommend this method because they know how to get around it? Possibly, but they also need to recommend methods that they believe foreign governments cannot break.

The equation of the P-384 curve is

y² = x³ + ax + b

working over the field of integers modulo a prime p. We will go into each of the specific parameters ab, and p, and discuss how they were chosen.

## Modulus p

Consisting with the naming conventions for elliptic curves used in cryptography, the name “P-384” tells you that the curve is over a prime field where the prime is a 384-bit integer. Specifically, the order of the field is

p = 2384 – 2128 – 296 + 232 – 1

For a given number of bits, in this case 384, you want to pick a prime that’s relatively near the maximum size for that number of bits. In our case, our prime p is a prime near 2384 with a convenient bit pattern. (The special pattern allows implementation tricks that increase efficiency.)

Hasse’s theorem says that the number of points on a curve modulo a large prime is on the order of magnitude equal to the prime, so P-384 contains approximately 2384 points. In fact, the number of points n on the curve is

39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643

or approximately 2384 – 2190. The number n is a prime, and so it is the order of P-384 as a group.

## Linear coefficient a

According to a footnote in the standard defining P-384, FIPS PUB 186-4,

The selection a ≡ -3 for the coefficient of x was made for reasons of efficiency; see IEEE Std 1363-2000.

All the NIST elliptic curves over prime fields use a = -3 because this makes it possible to use special algorithms for elliptic curve arithmetic.

## Constant coefficient b

The curve P-384 has Weierstrass form

y² = x³ – 3x + b

where b is

27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575.

The parameter b is between 2383 and 2384 but doesn’t have any particular binary pattern:

101100110011000100101111101001111110001000111110111001111110010010011000100011100000010101101011111000111111100000101101000110010001100000011101100111000110111011111110100000010100000100010010000000110001010000001000100011110101000000010011100001110101101011000110010101100011100110001101100010100010111011010001100111010010101010000101110010001110110111010011111011000010101011101111

The specification says that b was chosen at random. How can you convince someone that you chose a parameter at random?

The standard gives a 160-bit seed s, and a hash-based algorithm that s was run through to create a 384-bit parameter c. Then b is the solution to

b² c = -27 mod p.

The algorithm going from the s to c is given in Appendix D.6 and is a sort of key-stretching algorithm. The standard cites ANS X9.62 and IEEE Standard 1363-2000 as the source of the algorithm.

If b was designed to have a back door, presumably a tremendous amount of computation had to go into reverse engineering the seed s.

Koblitz and Menezes wrote a paper in which they suggest a way that the NSA might have picked seeds that lead to weak elliptic curves, but then argue against it.

It is far-fetched to speculate that the NSA would have deliberately selected weak elliptic curves in 1997 for U.S. government usage … confident that no one else would be able to discover the weakness in these curves in the ensuing decades. Such a risky move by the NSA would have been inconsistent with the Agency’s mission.

# Isogeny-based encryption

If and when large quantum computers become practical, all currently widely deployed method for public key cryptography will break. Even the most optimistic proponents of quantum computing believe such computers are years away, maybe decades. But it also takes years, maybe decades, to develop, test, and deploy new encryption methods, and so researchers are working now to have quantum-resistant encryption methods in place by the time they are needed.

## What’s special about isogeny-based encryption?

One class of quantum-resistant encryption methods is isogeny-based encryption. This class stands out for at least a couple methods:

• it uses the shortest keys, and
• it uses the most sophisticated math.

Most post-quantum encryption schemes require much longer keys to maintain current levels of protection, two or three orders of magnitude longer. Isogeny-based encryption uses the shortest keys of any proposed post-quantum encryption methods, requiring keys roughly the same size as are currently in use.

The mathematics behind isogeny-based cryptography is deep. Even a high-level description requires quite a bit of background. I’ll take a shot at exploring the prerequisites starting with this blog post.

## Elliptic curves

Elliptic curve cryptography is widely used today, and partly for one of the reasons listed above: short keys. To achieve a level of security comparable to 128-bit AES, you need a 256-bit key using elliptic curve cryptography, but a 3072-bit key using RSA.

Quantum computers could solve the elliptic curve discrete logarithm problem efficiently, and so elliptic curve cryptography as currently practiced is not quantum resistant. Isogeny-based encryption is based on elliptic curves, but not as directly as current ECC methods. While current ECC methods perform computations on a elliptic curves, isogeny methods are based on networks of functions between elliptic curves.

## SIKE

NIST is sponsoring a competition for post-quantum encryption methods, and only one of the contestants is related to elliptic curves, and that’s SIKE. The name stands for Supersingular Isogeny Key Encapsulation. “Supersingular” describes a class of elliptic curves, and SIKE is based on isogenies between these curves.

## Future posts

This post raises a lot of questions. First and foremost, what is an isogeny? That’s the next post. And what are “supersingular” elliptic curves? I hope to go over that in a future post. Then after exploring the building blocks, where does encryption come in?

## Past posts

I’ve written several related blog posts leading up to this topic from two directions: post-quantum encryption and elliptic curves.

# All elliptic curves over fields of order 2 and 3

Introductions to elliptic curves often start by saying that elliptic curves have the form

y² = x³ + ax + b.

where 4a³ + 27b² ≠ 0. Then later they say “except over fields of characteristic 2 or 3.”

What does characteristic 2 or 3 mean? The order of a finite field is the number of elements it has. The order is always a prime or a prime power. The characteristic is that prime. So another way to phrase the exception above is to say “except over fields of order 2n or 3n.”

If we’re looking at fields not just of characteristic 2 or 3, but order 2 or 3, there can’t be that many of them. Why not just list them? That’s what I plan to do here.

## General form of elliptic curves

All elliptic curves over a finite field have the form

y² + a1xy + a3y = x³ + a2x² + a4x + a6,

even over fields of characteristic 2 or 3.

When the characteristic of the field is not 2, this can be simplified to

y² = 4x³ + b2x² + 2b4x + b6

where

b2 = a1² + 4a4,
b4 = 2a4 + a1a3, and
b6 = a3² + 4a6.

When the characteristic is at least 5, the form can be simplified further to the one at the top with just two parameters.

## General form of the discriminant

The discriminant of an elliptic curve is something like the discriminant of a quadratic equation. You have an elliptic curve if and only if it is not zero. For curves of characteristic at least five, the condition is 4a³ + 27b², but it’s more complicated for characteristic 2 and 3. To define the discriminant, we’ll need to use b2, b4, and b6 from above, and also

b8 = a1²a6 + 4a2a6a1a3a4 + a2a3² – a4².

Now we can define the discriminant Δ in terms of all the b‘s.

Δ = –b2²b8 – 8b4³ – 27b6² + 9b2b4b6.

See Handbook of Finite Fields page 423.

## Enumerating coefficients

Now we can enumerate which parameter combinations yield elliptic curves with the following Python code.

from itertools import product

def discriminant(a1, a2, a3, a4, a6):
b2 = a1**2 + 4*a4
b4 = 2*a4 + a1*a3
b6 = a3**2 + 4*a6
b8 = a1**2*a6 + 4*a2*a6 - a1*a3*a4 + a2*a3**2 - a4**2
delta = -b2**2*b8 - 8*b4**3 - 27*b6**2 + 9*b2*b4*b6
return delta

p = 2
r = range(p)
for (a1, a2, a3, a4, a6) in product(r,r,r,r,r):
if discriminant(a1, a2, a3, a4, a6)%p != 0:
print(a1, a2, a3, a4, a6)


The code above does return the values of the a‘s that yield an elliptic curve, but in some sense it returns too many. For example, there are 32 possible combinations of the a‘s when working over GF(2), the field with two elements, and 16 of these lead to elliptic curves. But some of these must lead to the same set of points because there are only 4 possible (x, y) affine points on the curve, plus the point at infinity.

Now we get into a subtle question: when are two elliptic curves the same? Can two elliptic curves have the same set of points and yet be algebraically different? Sometimes, but not usually. Lenstra and Pila [1] proved that two elliptic curves can be equal as sets but not equal as groups if and only if the curve has 5 points and the field has characteristic 2. [2]

Lenstra and Pila give the example of the two equations

y² + y = x³ + x²

and

y² + y = x³ + x

over GF(2). Both determine the same set of points, but the two curves are algebraically different because (0,0) + (0,0) equals (1,1) on the first curve and (1,0) on the second.

## Enumerating points on curves

The following Python code will enumerate the set of points on a given curve.

def on_curve(x, y, a1, a2, a3, a4, a6, p):
left = y**2 + a1*x*y + a3*y
right = x**3 + a2*x**2 + a4*x + a6
return (left - right)%p == 0

def affine_points(a1, a2, a3, a4, a6, p):
pts = set()
for x in range(p):
for y in range(p):
if on_curve(x, y, a1, a2, a3, a4, a6, p):
return pts


We can use this code, along with Lenstra and Pila’s result, to enumerate all elliptic curves of small order.

## All elliptic curves over GF(2)

Now we can list all the elliptic curves over the field with two elements.

### Curves of order 5

The two curves in the example of Lendstra and Pila are the only ones over GF(2) with five points. So the two curves of order 5 over GF(2) are

y² + y = x³ + x²
y² + y = x³ + x.

They determine the same set of points but are algebraically different.

### Curves of order 4

There are four curves of order 4.They contain different sets of points, i.e. each omits a different one of the four possible affine points.

y² + xy = x³ + 1
y² + xy = x³ + x² + x
y² + xy + y = x³ + x²
y² + xy + y = x³ + x² + x

### Curves of order 3

There are two distinct curves of order 3, each determined by two equations.

The first curve is determined by either of

y² + y = x³
y² + y = x³ + x² + x

and the second by either of

y² + xy + y = x³ + 1
y² + y = x³ + x² + x + 1

### Curves of order 2

There are 4 curves of order two; each contains a different affine point.

y² + xy + y = x³ + 1
y² + xy + y = x³ + x + 1
y² + xy = x³ + x² + 1
y² + xy = x³ + x² + x

### Curves of order 1

These are curves containing only the point at infinity

y² + y = x³ + x + 1
y² + y = x³ + x² + 1

There are no affine points because the left side is always 0 and the right side is always 1 for x and y in {0, 1}.

## All elliptic curves over GF(3)

There are too many elliptic curves over GF(3) to explore as thoroughly as we did with GF(2) above, but I can report the following results that are obtainable using the Python code above.

An elliptic curve over GF(3) contains between 1 and 7 points. Here are the number of parameter combinations that lead to each number of points.

    1:  9
2: 22
3: 26
4: 15
5: 26
6: 22
7:  9


Obviously there’s only one curve with one point, the point at infinity, so the nine coefficient combinations that lead to a curve of order 1 determine the same curve.

There are 9 distinct curves of order 2 and 12 distinct curves of order 3. All the curves of orders 4, 5, 6, and 7 are distinct.

## Related posts

[1] H. W. Lenstra, Jr and J. Pila. Does the set of points of an elliptic curve determine the group? Computational Algebra and Number Theory, 111-118.

[2] We are not considering isomorphism classes here. If two curves have a different set of points, or the same set of points but different group properties, we’re considering them different.

# Efficient modular arithmetic technique for Curve25519

Daniel Bernstein’s Curve25519 is the elliptic curve

y² = x³ + 486662x² + x

over the prime field with order p = 2255 – 19. The curve is a popular choice in elliptic curve cryptography because its design choices are transparently justified [1] and because cryptography over the curve can be implemented very efficiently. This post will concentrate on one of the tricks that makes ECC over Curve25519 so efficient.

Curve25519 was designed for fast and secure cryptography. One of the things that make it fast is the clever way Bernstein carries out arithmetic mod 2255 – 19 which he describes here.

Bernstein represents numbers mod 2255 – 19 by polynomials whose value at 1 gives the number. That alone is not remarkable, but his choice of representation seems odd until you learn why it was chosen. Each number is represented as a polynomial of the form

ui xi

where each ui is an integer multiple ki of 2⌈25.5i, and each ki is an integer between -225 and 225 inclusive.

Why this limitation on the k‘s? Pentium cache optimization. In Bernstein’s words:

Why split 255-bit integers into ten 26-bit pieces, rather than nine 29-bit pieces or eight 32-bit pieces? Answer: The coefficients of a polynomial product do not fit into the Pentium M’s fp registers if pieces are too large. The cost of handling larger coefficients outweighs the savings of handling fewer coefficients.

And why unevenly spaced powers of 2: 1, 226, 251, 277, …, 2230? Some consecutive exponents differ by 25 and some by 26. This looks sorta like a base 225 or base 226 representation, but is a mixture of both. Bernstein answers this in his paper.

Bernstein answers this question as well.

Given that there are 10 pieces, why use radix 225.5 rather than, e.g., radix 225 or radix 226? Answer: My ring R contains 2255x10 − 19, which represents 0 in Z/(2255 − 19). I will reduce polynomial products modulo 2255x10 – 19 to eliminate the coefficients of x10, x11, etc. With radix 225 , the coefficient of x10 could not be eliminated. With radix 226, coefficients would have to be multiplied by 2519 rather than just 19, and the results would not fit into an fp register.

There are a few things to unpack here.

Remember that we’re turning polynomials in to numbers by evaluating them at 1. So when x = 1, 2255x10 – 19  = p = 2255 – 19, which is the zero in the integers mod  2255 – 19.

If we were using base (radix) 225 , the largest number we could represent with a 9th degree polynomial with the restrictions above would be 2250 , so we’d need a 10th degree polynomial; we couldn’t eliminate terms containing x10.

I don’t yet see why working with radix 226 would overflow an fp register. If you do see why, please leave an explanation in the comments.

## Related posts

[1] When a cryptographic method has an unjustified parameter, it invites suspicion that the parameter was chosen to create an undocumented back door. This is not the case with Curve25519. For example, why does it use p = 2255 – 19? It’s efficient to use a prime close to a large power of 2, and this p is the closes prime to 2255. The coefficient 486662 is not immediately obvious, but Bernstein explains in his paper how it was the smallest integer that met his design criteria.

# What is an elliptic curve?

Elliptic curves are pure and applied, concrete and abstract, simple and complex.

Elliptic curves have been studied for many years by pure mathematicians with no intention to apply the results to anything outside math itself. And yet elliptic curves have become a critical part of applied cryptography.

Elliptic curves are very concrete. There are some subtleties in the definition—more on that in a moment—but they’re essentially the set of point satisfying a simple equation. And yet a lot of extremely abstract mathematics has been developed out of necessity to study these simple objects. And while the objects are in some sense simple, the questions that people naturally ask about them are far from simple.

## Preliminary definition

A preliminary definition of an elliptic curve is the set of points satisfying

y² = x³ + ax + b.

This is a theorem, not a definition, and it requires some qualifications. The values xya, and b come from some field, and that field is an important part of the definition of an elliptic curve. If that field is the real numbers, then all elliptic curves do have the form above, known as the Weierstrass form. For fields of characteristic 2 or 3, the Weierstrass form isn’t general enough. Also, we require that

4a³ + 27b² ≠ 0.

The other day I wrote about Curve1174, a particular elliptic curve used in cryptography. The points on this curve satisfy

x² + y² = 1 – 1174 x² y²

This equation does not specify an elliptic curve if we’re working over real numbers. But Curve1174 is defined over the integers modulo p = 2251 – 9. There it is an elliptic curve. It is equivalent to a curve in Weierstrass, though that’s not true when working over the reals. So whether an equation defines an elliptic curve depends on the field the constituents come from.

## Not an ellipse, not a curve

An elliptic curve is not an ellipse, and it may not be a curve in the usual sense.

There is a connection between elliptic curves and ellipses, but it’s indirect. Elliptic curves are related to the integrals you would write down to find the length of a portion of an ellipse.

Working over the real numbers, an elliptic curve is a curve in the geometric sense. Working over a finite field, an elliptic curve is a finite set of points, not a continuum. Working over the complex numbers, an elliptic curve is a two-dimensional surface. The name “curve” is extended by analogy to elliptic curves over general fields.

## Final definition

In this section we’ll give the full definition of an algebraic curve, though we’ll be deliberately vague about some of the details.

The definition of an elliptic curve is not in terms of equations of a particular form. It says an elliptic curve is a

• smooth,
• projective,
• algebraic curve,
• of genus one,
• having a specified point O.

Working over real numbers, smoothness can be specified in terms of derivatives. But that does smoothness mean working over a finite field? You take the derivative equations from the real case and extend them by analogy to other fields. You can “differentiate” polynomials in settings where you can’t take limits by defining derivatives algebraically. (The condition 4a³ + 27b² ≠ 0 above is to guarantee smoothness.)

Informally, projective means we add “points at infinity” as necessary to make things more consistent. Formally, we’re not actually working with pairs of coordinates (xy) but equivalence classes of triples of coordinates (x, yz). You can usually think in terms of pairs of values, but the extra value is there when you need it to deal with points at infinity. More on that here.

An algebraic curve is the set of points satisfying a polynomial equation.

The genus of an algebraic curve is roughly the number of holes it has. Over the complex numbers, the genus of an algebraic curve really is the number of holes. As with so many ideas in algebra, a theorem from a familiar context is taken as a definition in a more general context.

The specified point O, often the point at infinity, is the location of the identity element for the group addition. In the post on Curve1174, we go into the addition in detail, and the zero point is (0, 1).

In elliptic curve cryptography, it’s necessary to specify another point, a base point, which is the generator for a subgroup. This post gives an example, specifying the base point on secp256k1, a curve used in the implementation of Bitcoin.

# Naming elliptic curves used in cryptography

There are an infinite number of elliptic curves, but a small number that are used in elliptic curve cryptography (ECC), and these special curves have names. Apparently there are no hard and fast rules for how the names are chosen, but there are patterns.

The named elliptic curves are over a prime field, i.e. a finite field with a prime number of elements p, denoted GF(p). The number of points on the elliptic curve is on the order of p [1].

The curve names usually contain a number which is the number of bits in the binary representation of p. Let’s see how that plays out with a few named elliptic curves.

Curve name Bits in p
ANSSI FRP256v1   256
BN(2, 254) 254
brainpoolP256t1   256
251
255
Curve383187 383
E-222 222
E-382 382
E-521 521
448
M-211 221
M-383 383
M-511 511
NIST P-224 224
256
384
256

In Curve25519, p = 2255 – 19 and in Curve 383187, p = 2383 – 187. Here the number of bits in p is part of the name but another number is stuck on.

The only mystery on the list is Curve1174 where p has 251 bits. The equation for the curve is

x² + y² = 1 – 1174 y²

and so the 1174 in the name comes from a coefficient rather than from the number of bits in p.

## Edwards curves

The equation for Curve1174 doesn’t look like an elliptic curve. It doesn’t have the familiar (Weierstrass) form

y² = x³ + ax + b

It is an example of an Edwards curve, named after Harold Edwards. So are all the curves above whose names start with “E”. These curves have the form

x² + y² = 1 + d x² y².

where d is not 0 or 1. So some Edwards curves are named after their d parameter and some are named after the number of bits in p.

It’s not obvious that an Edwards curve can be changed into Weierstrass form, but apparently it’s possible; this paper goes into the details.

The advantage of Edwards curves is that the elliptic curve group addition has a simple, convenient form. Also, when d is not a square in the underlying field, there are no exceptional points to consider for group addition.

Is d = -1174 a square in the field underlying Curve1174? For that curve p = 2251 – 9, and we can use the Jacobi symbol code from earlier this week to show that d is not a square.

    p = 2**251 - 9
d = p-1174
print(jacobi(d, p))


This prints -1, indicating that d is not a square. Note that we set d to p – 1174 rather than -1174 because our code assumes the first argument is positive, and -1174 and p – 1174 are equivalent mod p.

Update: More on addition on Curve1174.

## Prefix conventions

A US government publication (FIPS PUB 186-4) mandates the following prefixes:

• P for curves over a prime field,
• B for curves over a binary field (i.e. GF(2n)), and
• K for Koblitz fields.

The ‘k’ in secp256k1 also stands for Koblitz.

The M prefix above stands for Montgomery.

## More ECC posts

[1] It is difficult to compute the exact number of points on an elliptic curve over a prime field. However, the number is roughly p ± 2√p. More precisely, Hasse’s theorem says

# A tale of two elliptic curves

A few days ago I blogged about the elliptic curve secp256k1 and its use in Bitcoin. This curve has a sibling, secp256r1. Note the “r” in the penultimate position rather than a “k”. Both are defined in SEC 2: Recommended Elliptic Curve Domain Parameters. Both are elliptic curves over a field zp where p is a 256-bit prime (though different primes for each curve).

The “k” in sepc256k1 stands for Koblitz and the “r” in sepc256r1 stands for random. A Koblitz elliptic curve has some special properties that make it possible to implement the group operation more efficiently. It is believed that there is a small security trade-off, that more “randomly” selected parameters are more secure. However, some people suspect that the random coefficients may have been selected to provide a back door.

Both elliptic curves are of the form y² = x³ + ax + b. In the Koblitz curve, we have

a = 0
b = 7


and in the random case we have

a = FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC
b = 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B


You can find the rest of the elliptic curve parameters in the SEC 2 report. For some help understanding what the parameters mean and how to decode them, see my earlier post.

The NSA recommends the random curve for government use. It is also known as NIST P-256. Or rather it did recommend P-256 as part of its Suite B of cryptography recommendations. In August 21015 the NSA announced its concern that in the future, quantum computing could render the Suite B methods insecure. As far as we know, quantum computing at scale is years, maybe decades, away. But it takes a long time to develop quality encryption methods, and so the NSA and NIST are urging people to think ahead. (Update: The NSA recommends P-384 until post quantum methods mature.)

Bitcoin chose to use the less popular Koblitz curve for the reasons mentioned above, namely efficiency and concerns over a possible back door in the random curve. Before Bitcoin, secp256k1 was not widely used.

Related post: RSA numbers and factoring

# Bitcoin key mechanism and elliptic curves over finite fields

Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) based on elliptic curve cryptography. The particular elliptic curve is known as secp256k1, which is the curve

y² = x³ + 7

over a finite field (a.k.a. Galois field) to be described shortly.

Addition on elliptic curves in the plane is defined geometrically in terms of where lines intercept the curve. We won’t go into the geometry here, except to say that it boils down to a set of equations involving real numbers. But we’re not working over real numbers; we’re working over a finite field.

## Finite field modulus

The idea is to take the equations motivated by the geometry in the plane then use those equations to define addition when you’re not working over real numbers but over a different field. In the case of secp256k1, the field is the finite field of integers mod p where

p = 2256 – 232 – 977

Here p was chosen to be relatively close to 2256. It’s not the largest prime less than 2256; there are a lot of primes between p and 2256. Other factors also went into the choice p. Note that we’re not working in the integers mod p per se; we’re working in an Abelian group whose addition law is defined by an elliptic curve over the integers mod p.

(Update: Here’s another post about secp256k1’s sister curve, secp256r1, another curve modulo a 256-bit prime, but with different structure.)

## Base point

Next, we pick a base point g on the elliptic curve. The standard defining secp256k1 says that g is

0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

in “compressed form” or

in “uncompressed form”.

The base point is a specially chosen point on the elliptic curve, and so it is a pair of numbers mod p, not a single number. How do you extract x and y from these compressed or uncompressed forms?

### Compressed form

The compressed form only gives x and you’re supposed to solve for y. The uncompressed form gives you x and y. However, the numbers are slightly encoded. In compressed form, the string either starts with “o2” or “o3” and the rest of the string is the hexadecimal representation of x. There will be two values of y satisfying

y² = x³ + 7 mod p

and the “o2” or “03” tells you which one to pick. If the compressed form starts with 02, pick the root whose least significant bit is even. And if the compressed form starts with 03, pick the root whose least significant bit is odd. (The two roots will add to p, and p is odd, so one of the roots will be even and one will be odd.)

### Uncompressed form

In either case we have

x = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

and

We can verify this with a little Python code:

    x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
assert((y*y - x*x*x - 7) % p == 0)


## Exponentiation over elliptic curve

Starting with our base point g, define kg to be g added to itself k times. Note again that the sense of “addition” here is addition in the elliptic curve, not addition in the field of integers mod p. The key to elliptic curve cryptography is that kg can be computed efficiently, but solving for k starting from the product kg cannot. You can compute kg using the fast exponentiation algorithm, but solving for k requires computing discrete logarithms. (This is the ECDLP: Elliptic Curve Discrete Logarithm Problem.)

Why is this called “exponentiation” and not “multiplication”? Arithmetic on the elliptic curve is commutative, and in commutative (i.e. Abelian) groups the group operation is usually denoted as addition. And repeated addition is called multiplication.

But in general group theory, the group operation is denoted as multiplication, and repeated application of the group operation is called  exponentiation. It’s conventional to use the general term “exponentiation” even though over an Abelian group it makes more sense to call it multiplication.

You undo exponentiation by taking logarithms, so the process of solving for k is called the discrete logarithm problem. The security of elliptic curve cryptography depends on the difficulty of computing discrete logarithms.

## Counting bits of security

The best algorithms for solving discrete logarithm problem in a group of size n currently require O(√n) operations. How big is n in our case?

The base point g was chosen to have a large order, and in fact its order is approximately 2256.  Specifically, the order of g written in hexadecimal is

n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.

This means that we get approximately 256/2 = 128 bits of security because √(2256) = 2128.