One of the most widely deployed asymmetric cryptographic algorithms used today (driven by the popularity of blockchain technology) is based on elliptic curves over finite fields. Like all good engineers I struggled to just accept how they work. I needed to dig deeper to better understand the mathematics and in doing so decided to share my experience ...
This is part 2 in a series. You can also read part 1 about the basics of Finite Fields and part 3 which covers calculations on elliptic curves.
In part 1 we learnt the basics of Finite Field maths and showed how to calculate 4 basic operations. We can now start to look at how to handle more complex operations. For example, taking Z5, how can we calculate the square root of 1? By simply restating the problem as before, I.e. “what, when multiplied by itself, equals one”. The answer is trivial, 1, but don’t stop there. In normal arithmetic there is a second answer, −1. How do we represent this in Z5? Well, using the number line concept and counting down one from 0 loops us back round to 4. Could 4 possibly be another solution? Multiplying out, 4∗4=16=1∈Z5, does indeed produce 1! 4 also has two answers in Z5, namely 2 and 3. Trying 2 and 3 yields no valid answers, but comparing this with the square root operation on the integers, Z, or real values, R, you’ll see that all negative numbers have no answer (to solve this you need to move to complex numbers, C), so they are all quite similar in that regard.
Moving on, we can calculate powers by simply applying repeated multiplication and modulo operations e.g:
Notice how as the powers increase we generate each non-zero element of the field. Once each value has been generated once, the sequence starts again and this repeats ad infinitum. This feature (in this case of the value 3∈Z7) is what is referred to as a primitive element. Not all values within a given field are primitive elements e.g 2∈Z7:
20∈Z7=121∈Z7=222∈Z7=423∈Z7=124∈Z7=2...
The value 2 doesn’t generate every non-zero value in the field and so is not a primitive element of Z7.
The inverse operation of the power operator is the logarithm. As before, we can use the list of values of successive powers to calculate the logarithm:
The sequence of values here is quite unpredictable, it would be hard to solve for any given value unless we’d written out the table of values like this. It’s pretty easy to do this for Z7, but how about if your field has nearly 2256 values e.g. Z2256−232−977? (This is the field used by the secp256k1 curve as we’ll see later).
It is this challenge, calculating the discrete logarithm in a large finite field, that allows it to be used in cryptography. It is relatively easy to calculate the power, but given a value it is very hard to find the logarithm. This is what is known as a ‘trapdoor’ function and this particular problem is known as the Discrete Logarithm Problem.
Both the elliptic curves that we are looking at as part of this series have prime orders (detailed later on), so we could stop here (feel free to skip straight to part 3), but it is worth understanding that there is another type of finite field that is used by some elliptic curves (sect... curves, not secp...). The simplest example of this type of field has 4 elements, but we already deteremined that it’s not Z4 (integers modulo 4). For these type of fields we need to start using something a little more powerful than just the integers, here we will introduce polynomials as some of the values in our field:
F4+01xx+1001xx+1110x+1xxxx+101x+1x+1x10
You’ll need to apply modular arithmetic to the coefficients (that is why x+x=2x=0) and this makes the table quite different in structure to that for addition in Z4. Now the multiplication table:
F4×01xx+100000101xx+1x0xx+11x+10x+11x
12 of the values in this table should be somewhat obvious to you, but what about the 4 values in the lower right quadrant? x.x=x2, so why have we put the values 1, x or x+1 here? In the same way we apply modular arithmetic to integers, we need to apply a similar principal to polynomials. When our result does not lie within the original field (0, 1, x and x+1) we need to divide by some value and take the remainder. You'll need to understand polynomial division for this (or you can just reapeatedly subtract until the result is in the original finite field). The value we divide by here is x2+x+1:
As you can see the remainder in each equation lies within our original field. More importantly the values in the multiplication table (excluding the first row of zeros) are all unique in each row. This validates that this field is indeed a finite field.
What leads us to divide by x2+x+1? This value is known as an irreducible polynomial and there is only one choice for F4 (or GF(4) as it sometimes known, GF standing for Galois field). Using polynomials to construct a Finite Field works for any pk, where p is a prime number and k is a positive integer. (In fact we’ve seen a number of samples where k is 1 already e.g. Z2≡F21. Fields with more than 22 elements often have multiple choices for the irreducible polynomial.) In fields of this form the value p is referred to as the characteristic. It is this value that is used for modular arithmetic on the polynomial coefficients. The maximum power used in the polynomial will be k−1. To show how this works for higher values here is the multiplication table for F8, the field with 8 elements, using the irreducible polynomial x3+x+1:
You can review the SEC 2: Recommended Elliptic Curve Domain Parameters document for other curves that are defined over finite fields of characteristic 2. Lets leave the topic of finite fields and return to our discussion of elliptic curves in part 3.