Elliptic Curve Cryptography - Extension Fields

• Communications
• Applied Math
• Algorithms

Quick Links

• Part 1: New book on Elliptic Curve Cryptography
• Part 2: Elliptic Curve Cryptography - Basic Math
• Part 3: Elliptic Curve Cryptography - Security Considerations
• Part 4: Elliptic Curve Cryptography - Key Exchange and Signatures
• Part 5: Elliptic Curve Cryptography - Extension Fields
• Part 6: Elliptic Curve Cryptography - Multiple Signatures

Field Extension

When my kids play games they talk about "leveling up". To get to the mathematics of pairing points over elliptic curves, we need to "level up" to extension fields from prime fields. If you've done any work with binary codes this is actually very familiar. Rather than base 2 fields, we are going to use base $p$ fields. An extension field is over $F_{p^k}$. It is defined by $p$ and an irreducible polynomial of order $k$.

Any polynomial with integer coefficients taken modulo $p$ can be reduced to an element in a finite field $F_{p^k}$ with an irreducible polynomial. As an example, let $p=53$ and $k=3$. An irreducible polynomial for $F_{53^3}$ is $y = x^3 + x + 5 \text{ mod } 53.$ If we take $x^5 + 23x^3 + x + 5$ modulo $y$ we get $48x^2 + 32x + 1$ as the remainder. I used the program Pari/gp as described in chapter 6 of Elliptic Curve Cryptography for Developers to check that.

If we multiply, add, subtract, or divide any two polynomials in a field, the result is always reduced by the irreducible polynomial. For cryptographic purposes we want the coefficients to be huge, as in 256 to 512 bits each. So using a computer for all the computations is a basic requirement. If a fixed field size is decided upon,  an FPGA can easily do the job. 

As discussed in previous parts of this series, the formula for an elliptic curve over large finite fields is $$y^2 = x^3 + a x + b.$$ The same formula applies over extension fields. For use with cryptographic functions, we normally take the coefficients $a$ and $b$ to be constants, and not polynomials. When the values of $x$ and $y$ are polynomials then the curve is over the field $F_{p^k}$.

For any polynomial $x$, there may not be a solution for $y^2$. That is, we can't factor the polynomial $x^3 + a x + b$ into two equal terms. That value of $x$ is not on the curve. Computing square roots of polynomials is a neat trick - see chapter 12 in Elliptic Curve Cryptography for Developers to see how it's done.

Elliptic curves over extension fields have some amazing properties. One of those properties is the existence of independent cyclic sets of points. Even more amazing is the structure of those sets - the number of points on the smaller set will divide into the number of points on the larger set. That means both sets have some similar factors. For cryptographic use, we want those sets to be a combination of small factors and one really huge prime. A lot of mathematicians have spent a long time finding algorithms which work to find such elliptic curves.

Point pairing

The arithmetic of adding points over an elliptic curve applies just as well to points on a field extension as to points over a prime field. When we talk about multiplication on an elliptic curve we mean the addition of a point to itself many times.The result is another point on the curve. The next "level up" is point pairing. This operation takes two points on an elliptic curve which have similar order and computes an $n^{th}$ root of unity modulo the irreducible polynomial. The result is not a point on the curve, it is just an element in $F_{p^k}$.

There are quite a few formulas used for pairings. They give different results for the same inputs, but overall have the same behavior. The general behavior is $$e(P, Q) = \mu_n$$where P and Q are points on an extension curve of order $n$ and $\mu_n$ is an $n^{th}$ root of unity in the extension field $F_{p^k}.$ That means $(\mu_n)^n = 1$ when computed with the irreducible polynomial defining the extension field.

The interesting and useful property of point pairing is that $$e(a P, Q) = e(P, Q)^a.$$We also have $$e(P, b Q) = e(P, Q)^b.$$We can go backwards too and swap things around$$e(P, Q)^a = e(P, a Q).$$Combining all these things together we can have $$e(a P, b Q) = e(P, Q)^{a b} = e(b P, a Q) = e(a b P, Q) = e(P, a b Q).$$

These properties are useful for verification. The values $a$ and $b$ can be private keys or random throw away values. Knowing the points $P$, $a P$, $Q$, and $b Q$ hides the values of $a$ and $b$ assuming the field size is large enough. 

The actual computation for a particular version of point pairing involves the use of a function which uses a third point on the curve as a reference. This point divides out after all is said and done, so it does not matter which point is chosen on the curve. But careful analysis will show some points are far more efficient to use than others because they may have a zero value for $x$. That drops out some terms which can speed up computation without changing the security.

In chapter 14 of Elliptic Curve Cryptography for Developers I explain how to find good curves over field extensions. This is not simple, but it is straight forward. In chapter 15 I go into the details of how to compute the basic pairing function. Again, not simple but straight forward. Specific pairings using that function are shown in chapters 16 and 17. Those are simple! But it takes a lot of work to "level up" to the point where "simple" is true.

Sign in