The Joy of Secs: Part 2

Posted by Mark Hornsby on 2019-08-08

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\Bbb{Z}_5, how can we calculate the square root of 11? By simply restating the problem as before, I.e. “what, when multiplied by itself, equals one”. The answer is trivial, 11, but don’t stop there. In normal arithmetic there is a second answer, 1-1. How do we represent this in Z5\Bbb{Z}_5? Well, using the number line concept and counting down one from 00 loops us back round to 44. Could 44 possibly be another solution? Multiplying out, 44=16=1Z54*4=16=1\in\Bbb{Z}_5, does indeed produce 11! 4\sqrt4 also has two answers in Z5\Bbb{Z}_5, namely 22 and 33. Trying 2\sqrt2 and 3\sqrt3 yields no valid answers, but comparing this with the square root operation on the integers, Z\Bbb{Z}, or real values, R\Bbb{R}, you’ll see that all negative numbers have no answer (to solve this you need to move to complex numbers, C\Complex), 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:

30Z7=131Z7=332Z7=233Z7=634Z7=435Z7=536Z7=137Z7=3... \begin{matrix} 3^0 \in \Bbb{Z}_7 = 1 \\ 3^1 \in \Bbb{Z}_7 = 3 \\ 3^2 \in \Bbb{Z}_7 = 2 \\ 3^3 \in \Bbb{Z}_7 = 6 \\ 3^4 \in \Bbb{Z}_7 = 4 \\ 3^5 \in \Bbb{Z}_7 = 5 \\ 3^6 \in \Bbb{Z}_7 = 1 \\ 3^7 \in \Bbb{Z}_7 = 3 \\ ... \end{matrix}

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 3Z73 \in \Bbb{Z}_7) is what is referred to as a primitive element. Not all values within a given field are primitive elements e.g 2Z72 \in \Bbb{Z}_7:

20Z7=121Z7=222Z7=423Z7=124Z7=2... \begin{matrix} 2^0 \in \Bbb{Z}_7 = 1 \\ 2^1 \in \Bbb{Z}_7 = 2 \\ 2^2 \in \Bbb{Z}_7 = 4 \\ 2^3 \in \Bbb{Z}_7 = 1 \\ 2^4 \in \Bbb{Z}_7 = 2 \\ ... \end{matrix}

The value 22 doesn’t generate every non-zero value in the field and so is not a primitive element of Z7\Bbb{Z}_7.

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:

logZ71=6logZ72=2logZ73=1logZ74=4logZ75=5logZ76=3 \begin{matrix} \log_{\Bbb{Z}_7}1 = 6 \\ \log_{\Bbb{Z}_7}2 = 2 \\ \log_{\Bbb{Z}_7}3 = 1 \\ \log_{\Bbb{Z}_7}4 = 4 \\ \log_{\Bbb{Z}_7}5 = 5 \\ \log_{\Bbb{Z}_7}6 = 3 \end{matrix}

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\Bbb{Z}_7, but how about if your field has nearly 22562^{256} values e.g. Z2256232977\Bbb{Z}_{2^{256}-2^{32}-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\Bbb{Z}_4 (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 \begin{array}{cccccc} \Bbb{F}_4^+ & & 0 & 1 & x & x+1 \\ \\ 0 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} \\ 1 & & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x} \\ x & & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{1} \\ x+1 & & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{0} \\ \end{array}

You’ll need to apply modular arithmetic to the coefficients (that is why x+x=2x=0x+x=2x=0) and this makes the table quite different in structure to that for addition in Z4\Bbb{Z}_4. Now the multiplication table:

F4×01xx+100000101xx+1x0xx+11x+10x+11x \begin{array}{cccccc} \Bbb{F}_4^\times & & 0 & 1 & x & x+1 \\ \\ 0 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} \\ 1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} \\ x & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{1} \\ x+1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x} \\ \end{array}

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=x2x.x=x^2, so why have we put the values 11, xx or x+1x+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 (00, 11, xx and x+1x+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+1x^2+x+1:

x×x(modx2+x+1)=x2(modx2+x+1)=x+1x(x+1)(modx2+x+1)=x2+x(modx2+x+1)=1(x+1)(x+1)(modx2+x+1)=x2+2x+1(modx2+x+1)=x \begin{alignedat}{2} x \times x \textcolor{#bfbfbf}{\pmod{x^2+x+1}} &= x^2 \textcolor{#bfbfbf}{\pmod{x^2+x+1}}& &= x+1 \\ x(x+1) \textcolor{#bfbfbf}{\pmod{x^2+x+1}} &= x^2+x \textcolor{#bfbfbf}{\pmod{x^2+x+1}}& &= 1 \\ (x+1)(x+1) \textcolor{#bfbfbf}{\pmod{x^2+x+1}} &= x^2+2x+1 \textcolor{#bfbfbf}{\pmod{x^2+x+1}}& &= x \\ \end{alignedat}

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+1x^2+x+1? This value is known as an irreducible polynomial and there is only one choice for F4\Bbb{F}_4 (or GF(4)GF(4) as it sometimes known, GF standing for Galois field). Using polynomials to construct a Finite Field works for any pkp^k, where pp is a prime number and kk is a positive integer. (In fact we’ve seen a number of samples where kk is 1 already e.g. Z2F21\Bbb{Z}_2\equiv\Bbb{F}_{2^1}. Fields with more than 222^2 elements often have multiple choices for the irreducible polynomial.) In fields of this form the value pp 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 k1k-1. To show how this works for higher values here is the multiplication table for F8\Bbb{F}_8, the field with 8 elements, using the irreducible polynomial x3+x+1x^3+x+1:

F8×01xx+1x2x2+1x2+xx2+x+1000000000101xx+1x2x2+1x2+xx2+x+1x0xx2x2+xx+11x2+x+1x2+1x+10x+1x2+xx2+1x2+x+1x21xx20x2x+1x2+x+1x2+xxx2+11x2+10x2+11x2xx2+x+1x+1x2+xx2+x0x2+xx2+x+11x2+1x+1xx2x2+x+10x2+x+1x2+1x1x2+xx2x+1 \begin{array}{cccccccccc} \Bbb{F}_8^\times & & 0 & 1 & x & x+1 & x^2 & x^2+1 & x^2+x & x^2+x+1 \\ \\ 0 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} \\ 1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x^2} & \textcolor{#bfbfbf}{x^2+1} & \textcolor{#bfbfbf}{x^2+x} & \textcolor{#bfbfbf}{x^2+x+1} \\ x & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x^2} & \textcolor{#bfbfbf}{x^2+x} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x^2+x+1} & \textcolor{#bfbfbf}{x^2+1} \\ x+1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x^2+x} & \textcolor{#bfbfbf}{x^2+1} & \textcolor{#bfbfbf}{x^2+x+1} & \textcolor{#bfbfbf}{x^2} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x} \\ x^2 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x^2} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x^2+x+1} & \textcolor{#bfbfbf}{x^2+x} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x^2+1} & \textcolor{#bfbfbf}{1} \\ x^2+1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x^2+1} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x^2} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x^2+x+1} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x^2+x} \\ x^2+x & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x^2+x} & \textcolor{#bfbfbf}{x^2+x+1} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x^2+1} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x^2} \\ x^2+x+1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x^2+x+1} & \textcolor{#bfbfbf}{x^2+1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x^2+x} & \textcolor{#bfbfbf}{x^2} & \textcolor{#bfbfbf}{x+1} \\ \end{array}

And the table for F9\Bbb{F}_9, the field of 9 elements, using irreducible polynomial x2+1x^2+1:

F32×012xx+1x+22x2x+12x+200000000001012xx+1x+22x2x+12x+220212x2x+22x+1xx+2x+1x0x2x2x+22x+21x+12x+1x+10x+12x+2x+22x12x+12xx+20x+22x+12x+21xx+12x22x02xx12x+1x+122x+2x+22x+102x+1x+2x+122x2x+2x12x+202x+2x+12x+1x2x+212x \begin{array}{ccccccccccc} \Bbb{F}_{3^2}^\times & & 0 & 1 & 2 & x & x+1 & x+2 & 2x & 2x+1 & 2x+2 \\ \\ 0 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{0} \\ 1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{2x+2} \\ 2 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{x+1} \\ x & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{2x+1} \\ x+1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{x} \\ x+2 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{2} \\ 2x & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{x+2} \\ 2x+1 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{2x} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{1} \\ 2x+2 & & \textcolor{#bfbfbf}{0} & \textcolor{#bfbfbf}{2x+2} & \textcolor{#bfbfbf}{x+1} & \textcolor{#bfbfbf}{2x+1} & \textcolor{#bfbfbf}{x} & \textcolor{#bfbfbf}{2} & \textcolor{#bfbfbf}{x+2} & \textcolor{#bfbfbf}{1} & \textcolor{#bfbfbf}{2x} \\ \end{array}

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.