Learning Cryptography, Part 1: Finite Fields

This is Episode 1 in the Learning Cryptography series.

Background

Loopring is creating a new “Learning Cryptography” series to educate the wider crypto community about this fascinating field. This series will begin from the basics, and work its way up to the advanced tools that make our scalable 3.0 DEX protocol — which utilizes zero-knowledge proofs — possible.

Introduction

For many developers like myself, understanding cryptography feels like a dark art/magic. It’s not that we find math hard, in fact, many of us probably excelled in it in high school/college courses.

The problem lies with the fact that there’s no resource which balances the mathematics and presentation of ideas in an easy-to-understand manner. Facing this problem first hand, I decided to start this series to consolidate my learning, but also help various developers in their journey of understanding cryptography.

After reading through enough of these articles you should be able to understand and grasp more complicated cryptographic primitives in detail such as zero-knowledge proofs, threshold relay signatures and more.

Mathematical notations will gradually be introduced but pictures and repeated explanations will be present so you should hopefully be able to follow along!

Finite Fields

Finite Fields, also known as Galois Fields, are cornerstones for understanding any cryptography. A field can be defined as a set of numbers that we can add, subtract, multiply and divide together and only ever end up with a result that exists in our set of numbers. This is particularly useful for crypto as we can deal with a limited set of extremely large numbers.

To have a finite field you need the following properties (the dot symbol · denotes the remainder after multiplying/adding two elements):

• Closed — any operation performed with elements from the set returns an element contained in the original set.
• Associative — if you have (a· b) ·c, it’s the same as a ·(b ·c)
• Identity — there exists a neutral element (usually 1) such that a · 1 = a
• Inverse — within the set there’s another element such that a · (a)^-1= 1
• Commutative — the order of operations doesn’t matter: a · b = b · a

The most crucial property of a finite field is that it has p^m elements where p is a prime number and m is whatever you choose. A finite field with 11 elements can be defined as GF(11^1). A finite field with 256 elements would be written as GF(2^8). You can’t have a finite field with 12 elements since you’d have to write it as 2^2 * 3 which breaks the convention of p^m.

With our notation of GF(p^m):

• If m = 1 then we get prime fields
• If m > 1 then we get extension fields. This is a key point as it links to what we’re going to do with elliptic curves down the line. When m = 2 we get plenty of super interesting results as well.

Prime Field Arithmetic

The notation GF(p) means we have a finite field with the integers {0, … , p-1}. Suppose we have GF(5), our initial set will be {0, 1, 2, 3, 4}. Let’s put this into practice by trying out different operations. Any operations we do below should return 0, 1, 2, 3 or 4 (closure property).

Addition:

(3 + 4) mod 5 = 2
(1 + 4) mod 5 = 0
(1 + 2) mod 5 = 3

Subtraction:

(4 - 0) mod 5 = 4
(4 - 2) mod 5 = 2
(3 - 0) mod 5 = 1

Multiplication:

(0 * 4) mod 5 = 0
(2 * 4) mod 5 = 3
(3 * 4) mod 5 = 2

Division/Inversion:

(4 * 4) mod 5 = 1
(3 * 2) mod 5 = 1
(2 * 3) mod 5 = 1
(1 * 1) mod 5 = 1
(0 * ?) mod 5 = 1 // this doesn’t exist!
GCD(0, 5) = undefined!

It seemed like our finite field was coming along perfectly until we came across the identity for 0. So what do we do? Eliminate it and represent our field as F11* rather than F11. When referring to finite fields as F* it means 0 is not included as part of the set.

Extension Fields

Unlike finite fields, whose elements are integers, extension fields’ elements are polynomials. Extension fields = GF(2^m) where m > 1

These polynomials take the form of:

To make it less cryptic, let’s use the example of GF(2^3) which will result in the equation form:

GF(2^3) = GF(8) which means there’ll be a total of 8 elements in this set.

If we write out the elements they’ll have the following values for (a2,a1,a0) where a1, a2 or a0 can only ever be 0 or 1.

(a2, a1, a0)
(0, 0, 0) = 0
(0, 0, 1) = 1
(0, 1, 0) = x
(1, 0, 0) = x²
(0, 1, 1) = x+1
(1, 1, 0) = x²+x
(1, 0, 1) = x²+1
(1, 1, 1) = x²+x+1

Putting it all together, GF(2^3) = {0, 1, x, x², x+1, x²+x, x²+1, x²+x+1}

Although this form looks much different from our integers, we can still do our addition, subtraction, multiplication, and division and return an element in our set.

To keep it short and simple let’s addx²+1 andx²+x+1which gives us:

(1+1)x²+x+(1+1)

Since 1 + 1 mod 2 = 0, our equation simplifies to x which is contained in our original set!

Let’s try another example but a little bit harder.

A · B = (x²+1)(x²+x+1)
= x⁴+x³+x²+x²+1
= x⁴+x³+(1+1)x²+1
= x⁴+x³+1

Unfortunately, x⁴+x³+1 doesn’t exist in our finite field. So what do we do? Cue irreducible polynomials which are defined as polynomials which can’t be broken down into smaller polynomials (from the power of original polynomial).

In the case of GF(2^3) our irreducible polynomial is x³+x+1. If we divide x⁴+ x³+1 with our irreducible prime, we ultimately getx²+x which exists in our set — yay!

Closing

It seems quite mundane to go over such a basic concept in detail, but without doing so it can lead to difficulty understanding more advanced concepts down the line, especially when it comes to the generalized discrete logarithm problem and elliptic curve cryptography!

About Loopring

Loopring is a decentralized exchange protocol utilizing zkSNARKs to bring highly scalable, non-custodial trading to the masses. You can sign up for our bi-weekly update, and learn more at:

⭑ Twitter: twitter.com/loopringorg
⭑ Reddit: reddit.com/r/loopringorg
⭑ Telegram: t.me/loopring_en & t.me/loopringfans (Chinese)
⭑ Discord: discord.gg/KkYccYp
⭑ GitHub: https://github.com/Loopring
⭑ Kakao: open.kakao.com/o/gJbSZdF (Korean)