Be a crypto hero in the market by logging in

Don't you have an account? Sign in

Token price

  • BTC

    10,244,649.3KRW

    1.9%

  • ETH

    194,317.0KRW

    3.5%

  • XRP

    270.7KRW

    2.9%

  • BCH

    392,925.2KRW

    5.9%

  • BSV

    346,322.8KRW

    -3.6%

  • USDT

    1,160.5KRW

    0.1%

  • EOS

    4,450.2KRW

    4.9%

  • LTC

    54,759.1KRW

    -0.5%

  • BNB

    20,450.5KRW

    4.6%

  • ETC

    11,737.6KRW

    28.7%

  • TRX

    20.0KRW

    3.8%

  • XMR

    76,120.8KRW

    1.7%

  • XLM

    65.6KRW

    6.2%

  • ADA

    49.5KRW

    5.2%

  • DASH

    137,815.7KRW

    -3.4%

  • XTZ

    1,752.7KRW

    13.8%

  • ATOM

    5,660.8KRW

    12.1%

  • NEO

    13,217.2KRW

    4.4%

  • HT

    3,742.1KRW

    1.4%

  • HEDG

    2,628.6KRW

    0.6%

  • MKR

    582,868.9KRW

    -1.7%

  • ZEC

    61,478.1KRW

    7.5%

  • ONT

    801.6KRW

    3.8%

  • USDC

    1,162.5KRW

    0.0%

  • VET

    7.3KRW

    8.4%

  • XEM

    45.1KRW

    8.6%

  • BAT

    259.2KRW

    2.7%

  • DOGE

    2.7KRW

    2.0%

  • PAX

    1,167.2KRW

    0.4%

  • BTG

    14,561.2KRW

    -4.3%

  • DCR

    23,466.9KRW

    -6.5%

  • QTUM

    2,296.5KRW

    5.5%

  • INB

    573.4KRW

    2.3%

  • REP

    18,219.2KRW

    -9.0%

  • ZRX

    288.5KRW

    2.6%

  • RVN

    32.3KRW

    10.4%

  • LINK

    485.1KRW

    2.0%

  • TUSD

    1,164.3KRW

    0.1%

  • BCD

    792.5KRW

    -2.5%

  • ALGO

    283.0KRW

    2.0%

  • CNX

    2,514.6KRW

    1.2%

  • XIN

    276,337.6KRW

    5.3%

  • XIN

    276,337.6KRW

    5.3%

  • OMG

    910.3KRW

    3.3%

  • NANO

    811.8KRW

    4.6%

  • THETA

    123.1KRW

    5.1%

  • KCS

    1,269.2KRW

    0.1%

  • WAVES

    1,018.4KRW

    1.4%

  • LSK

    839.5KRW

    10.8%

  • DGB

    7.9KRW

    4.3%

  • BTM

    99.8KRW

    4.0%

  • BTM

    99.8KRW

    4.0%

  • MONA

    1,430.4KRW

    18.8%

  • ICX

    175.5KRW

    8.5%

  • KMD

    761.5KRW

    8.8%

  • MCO

    5,665.0KRW

    3.4%

  • IOST

    6.8KRW

    5.2%

  • HC

    1,720.2KRW

    4.5%

  • SC

    1.8KRW

    1.4%

  • XVG

    4.6KRW

    1.8%

  • ENJ

    90.5KRW

    -0.8%

  • NEXO

    124.0KRW

    10.9%

  • ABBC

    123.9KRW

    0.4%

  • BCN

    0.4KRW

    6.2%

  • ZIL

    6.1KRW

    4.4%

  • BTS

    21.8KRW

    5.4%

  • STEEM

    164.1KRW

    0.7%

  • AE

    190.3KRW

    5.0%

  • XZC

    5,877.5KRW

    -0.9%

  • MATIC

    21.2KRW

    16.3%

  • ARDR

    52.3KRW

    8.3%

  • QNT

    4,060.1KRW

    7.1%

  • ETN

    4.7KRW

    -0.0%

  • MANA

    43.2KRW

    0.9%

  • SNT

    12.1KRW

    4.0%

  • DAI

    1,164.7KRW

    0.4%

  • NPXS

    0.2KRW

    3.1%

  • TOMO

    562.2KRW

    4.4%

  • GNT

    38.8KRW

    0.9%

  • MAID

    84.0KRW

    -4.8%

  • STRAT

    380.7KRW

    5.7%

  • ELF

    68.8KRW

    2.5%

  • ELA

    1,836.4KRW

    0.7%

  • FET

    47.6KRW

    4.0%

  • AION

    76.7KRW

    6.0%

  • LRC

    28.9KRW

    4.3%

  • TRUE

    310.9KRW

    4.6%

  • RDD

    0.8KRW

    -0.5%

  • WAX

    22.9KRW

    1.7%

  • WTC

    527.6KRW

    -2.6%

  • LAMB

    32.4KRW

    2.7%

  • FCT

    2,479.9KRW

    5.7%

  • PPT

    401.1KRW

    3.6%

  • ARK

    176.7KRW

    4.7%

  • POWR

    48.0KRW

    1.2%

  • R

    41.6KRW

    0.7%

  • ANT

    645.5KRW

    -1.1%

  • LOOM

    20.2KRW

    -1.0%

  • PAI

    12.9KRW

    4.8%

  • PAI

    12.9KRW

    4.8%

  • BNT

    257.6KRW

    1.4%

  • DENT

    0.2KRW

    14.3%

  • PIVX

    301.5KRW

    -2.0%

  • OCEAN

    46.5KRW

    3.5%

  • MOAC

    259.9KRW

    -2.4%

  • ABT

    162.1KRW

    3.6%

  • CET

    17.2KRW

    3.0%

  • ODE

    59.3KRW

    1.3%

  • TTC

    33.0KRW

    -0.2%

  • AOA

    1.9KRW

    3.9%

  • POLY

    21.7KRW

    1.4%

  • PAY

    47.6KRW

    4.0%

  • REPO

    59.8KRW

    3.0%

  • MBL

    1.7KRW

    4.5%

  • BORA

    9.5KRW

    2.2%

  • CPT

    1.9KRW

    1.5%

  • BCV

    6.2KRW

    -2.3%

  • BAAS

    1.1KRW

    2.1%

  • COSM

    7.6KRW

    1.4%

  • GUSD

    1,151.6KRW

    -0.3%

  • FLETA

    9.2KRW

    1.5%

  • FNB

    2.2KRW

    5.2%

  • UPP

    11.0KRW

    -5.1%

  • HUM

    6.7KRW

    -1.4%

  • EOSC

    3.3KRW

    1.2%

  • AERGO

    30.2KRW

    3.1%

  • MVL

    0.4KRW

    -1.9%

  • DCC

    0.9KRW

    0.1%

  • LKY

    48.6KRW

    0.1%

  • eDEL

    2.4KRW

    -0.7%

  • RBG

    0.7KRW

    -13.5%

  • VRA

    0.5KRW

    -2.0%

  • ABL

    7.0KRW

    -8.9%

  • TEMCO

    0.5KRW

    -3.9%

  • AID

    3.0KRW

    -8.3%

  • MEETONE

    0.7KRW

    8.4%

  • AMON

    2.1KRW

    9.1%

  • PXL

    21.8KRW

    2.3%

  • AKRO

    0.8KRW

    -5.8%

  • XRA

    7.8KRW

    0.2%

  • WET

    4.0KRW

    1.8%

  • HORUS

    0.7KRW

    42.5%

  • CLB

    1.2KRW

    -15.8%

  • RBTC

    10,087,250.7KRW

    6.4%

  • WIKEN

    1.6KRW

    6.4%

  • NEWS

    1.7KRW

    45.9%

  • PTON

    0.0KRW

    41.8%

  • SEAL

    0.7KRW

    -7.6%

  • PUB

    0.2KRW

    -21.1%

  • NPER

    3.4KRW

    0.1%

  • KARMA

    0.0KRW

    1.2%

  • PUT

    1.4KRW

    -0.7%

  • CCH

    0.0KRW

    0.0%

  • KNT

    0.0KRW

    -44.1%

  • APIX

    0.6KRW

    0.1%

  • IQ

    3.4KRW

    2.0%

  • BLACK

    0.5KRW

    21.3%

  • RCD

    3.0KRW

    --%

  • MCC

    4.4KRW

    0.1%

  • INC

    0.4KRW

    43.6%

  • BZKY

    0.3KRW

    0.1%

  • CRE

    1.5KRW

    -3.0%

Community

Learning Cryptography: Finite Fields

Loopring | 06.19| 392

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 utilises 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 notation 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 doughnut 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¹). A finite field with 256 elements would be written as GF(28). You can’t have a finite field with 12 elements since you’d have to write it as 22 * 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(2m) where m > 1

These polynomials take the form of:

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

GF(23) = 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(23) = {0, 1, x, x², x +1, x²+x, x²+1, x²+x+1}

Although this form looks much different to 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 add x²+1 and x²+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(23) our irreducible polynomial is x³+x+1. If we divide x⁴+x³+1 with our irreducible prime we ultimately get x²+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)


Learning Cryptography: Finite Fields was originally published in Loopring Protocol on Medium, where people are continuing the conversation by highlighting and responding to this story.

Comment 0

delete

Are you sure you want to delete this post?