Be a crypto hero in the market by logging in

Don't you have an account? Sign in

Token price

  • BTC

    8,458,266.3KRW

    1.5%

  • ETH

    179,778.3KRW

    2.9%

  • XRP

    224.3KRW

    1.0%

  • USDT

    1,240.2KRW

    0.0%

  • BCH

    294,801.5KRW

    1.4%

  • BSV

    221,140.1KRW

    1.1%

  • LTC

    54,759.1KRW

    -0.5%

  • EOS

    2,921.9KRW

    1.7%

  • BNB

    17,209.6KRW

    4.2%

  • XTZ

    2,096.9KRW

    1.2%

  • XMR

    66,622.8KRW

    2.1%

  • XLM

    51.8KRW

    1.3%

  • HT

    4,612.2KRW

    5.2%

  • ADA

    40.1KRW

    0.5%

  • TRX

    14.8KRW

    0.7%

  • USDC

    1,237.5KRW

    -0.1%

  • CRO

    60.0KRW

    1.9%

  • DASH

    84,632.5KRW

    0.9%

  • ETC

    6,389.7KRW

    1.5%

  • NEO

    8,881.5KRW

    2.8%

  • HEDG

    2,160.7KRW

    1.8%

  • ATOM

    2,533.4KRW

    3.2%

  • XEM

    47.5KRW

    2.1%

  • MKR

    405,140.6KRW

    9.2%

  • ZEC

    41,308.8KRW

    2.8%

  • ONT

    486.0KRW

    3.2%

  • PAX

    1,237.4KRW

    -0.1%

  • DOGE

    2.3KRW

    1.4%

  • BAT

    184.2KRW

    2.8%

  • ELAC

    403.0KRW

    1.2%

  • VET

    4.0KRW

    0.8%

  • LINK

    485.1KRW

    2.0%

  • TUSD

    1,235.6KRW

    -0.0%

  • HBAR

    41.4KRW

    -0.0%

  • BTG

    9,088.9KRW

    -0.3%

  • DCR

    14,752.2KRW

    2.4%

  • ICX

    295.4KRW

    0.0%

  • QTUM

    1,595.2KRW

    2.3%

  • ALGO

    225.4KRW

    14.0%

  • LSK

    1,212.0KRW

    0.6%

  • INB

    392.0KRW

    1.0%

  • REP

    12,222.9KRW

    1.4%

  • ZRX

    194.0KRW

    1.0%

  • WAVES

    1,183.1KRW

    0.1%

  • CNX

    2,122.4KRW

    1.7%

  • BCD

    608.5KRW

    2.0%

  • RVN

    19.3KRW

    1.1%

  • XIN

    204,714.4KRW

    -1.0%

  • XIN

    204,714.4KRW

    -1.0%

  • NANO

    753.9KRW

    10.4%

  • ENJ

    121.6KRW

    8.9%

  • MONA

    1,500.4KRW

    0.8%

  • MCO

    6,224.2KRW

    2.0%

  • KCS

    1,177.8KRW

    1.8%

  • OMG

    687.1KRW

    1.4%

  • DGB

    6.8KRW

    3.6%

  • THETA

    100.6KRW

    7.2%

  • STEEM

    221.6KRW

    -5.3%

  • NEXO

    140.0KRW

    2.5%

  • QNT

    6,066.9KRW

    -4.8%

  • SC

    1.7KRW

    5.7%

  • BTM

    71.9KRW

    2.1%

  • BTM

    71.9KRW

    2.1%

  • SNT

    20.5KRW

    -5.1%

  • ABBC

    119.6KRW

    1.8%

  • VSYS

    33.7KRW

    13.7%

  • KMD

    510.3KRW

    -13.2%

  • BTS

    21.9KRW

    3.7%

  • SXP

    941.4KRW

    -4.2%

  • HC

    1,253.5KRW

    1.8%

  • BCN

    0.3KRW

    12.8%

  • XVG

    3.2KRW

    1.5%

  • ZIL

    5.1KRW

    3.2%

  • INS

    1,232.6KRW

    2.4%

  • IOST

    4.0KRW

    1.9%

  • ELF

    83.3KRW

    5.7%

  • GNT

    44.1KRW

    0.4%

  • ARDR

    41.0KRW

    1.5%

  • WAX

    36.5KRW

    -0.4%

  • MATIC

    14.4KRW

    1.3%

  • XZC

    3,966.8KRW

    2.4%

  • CHZ

    8.5KRW

    2.6%

  • AE

    125.9KRW

    2.2%

  • RIF

    63.0KRW

    3.2%

  • LRC

    34.8KRW

    0.4%

  • STRAT

    346.7KRW

    -0.1%

  • MANA

    32.5KRW

    1.1%

  • NPXS

    0.1KRW

    2.9%

  • AION

    80.0KRW

    0.2%

  • ANT

    924.0KRW

    -2.4%

  • POWR

    69.5KRW

    -0.2%

  • MAID

    64.0KRW

    0.6%

  • TRUE

    345.6KRW

    1.6%

  • ELA

    1,468.8KRW

    5.8%

  • CTXC

    105.7KRW

    -9.9%

  • ETN

    2.6KRW

    -1.0%

  • ORBS

    12.2KRW

    1.0%

  • RDD

    0.8KRW

    8.0%

  • ARK

    199.2KRW

    0.8%

  • PAI

    16.2KRW

    1.7%

  • PAI

    16.2KRW

    1.7%

  • OCEAN

    67.1KRW

    14.9%

  • GRIN

    606.6KRW

    4.4%

  • TOMO

    328.5KRW

    0.7%

  • WTC

    293.6KRW

    3.9%

  • WAN

    164.8KRW

    0.4%

  • BORA

    30.2KRW

    7.9%

  • BEAM

    334.7KRW

    3.2%

  • FCT

    2,170.5KRW

    -2.1%

  • NAS

    342.7KRW

    4.4%

  • DAI

    1,256.3KRW

    1.3%

  • LOOM

    18.2KRW

    0.9%

  • PIVX

    305.4KRW

    -1.1%

  • CVC

    24.8KRW

    3.8%

  • QASH

    46.8KRW

    2.9%

  • IGNIS

    21.0KRW

    -0.9%

  • BNT

    229.5KRW

    1.3%

  • GRS

    199.2KRW

    -0.3%

  • PPT

    277.5KRW

    2.0%

  • DAD

    223.7KRW

    2.7%

  • FET

    18.4KRW

    2.0%

  • LAMB

    19.0KRW

    21.7%

  • NXS

    188.6KRW

    2.4%

  • POLY

    24.3KRW

    2.1%

  • MOAC

    190.4KRW

    -0.3%

  • DENT

    0.1KRW

    0.5%

  • TTC

    25.3KRW

    -0.9%

  • AOA

    1.6KRW

    0.7%

  • ODE

    45.4KRW

    1.6%

  • ABT

    99.8KRW

    7.1%

  • MBL

    1.7KRW

    2.3%

  • GO

    9.5KRW

    5.7%

  • CET

    11.6KRW

    0.6%

  • SYM

    124.2KRW

    3.1%

  • GTO

    11.9KRW

    0.8%

  • CPT

    2.4KRW

    --%

  • CELR

    2.0KRW

    -0.4%

  • REPO

    67.5KRW

    41.1%

  • COSM

    10.9KRW

    0.5%

  • ANKR

    1.8KRW

    2.1%

  • FTM

    4.0KRW

    1.2%

  • GUSD

    1,246.0KRW

    1.1%

  • AERGO

    26.5KRW

    3.8%

  • MOC

    18.6KRW

    0.9%

  • NAV

    97.5KRW

    0.0%

  • R

    13.1KRW

    0.0%

  • FLETA

    6.8KRW

    2.2%

  • SOC

    3.8KRW

    4.7%

  • UPP

    16.0KRW

    1.2%

  • PAY

    37.8KRW

    6.5%

  • BCV

    5.1KRW

    2.9%

  • TROY

    2.4KRW

    1.2%

  • AMO

    0.3KRW

    0.6%

  • MIX

    2.0KRW

    0.7%

  • APIX

    0.6KRW

    2.4%

  • FNB

    1.6KRW

    2.4%

  • RFR

    0.7KRW

    -0.7%

  • PROM

    604.9KRW

    0.8%

  • BAAS

    0.6KRW

    -7.5%

  • HUM

    6.2KRW

    6.8%

  • DCC

    0.9KRW

    --%

  • PRO

    54.1KRW

    3.7%

  • EOSC

    2.5KRW

    7.8%

  • MVL

    0.3KRW

    0.2%

  • eDEL

    2.4KRW

    -0.7%

  • RBG

    0.7KRW

    1.4%

  • ABL

    8.1KRW

    3.4%

  • VRA

    0.5KRW

    5.8%

  • BWX

    46.3KRW

    -7.0%

  • AKRO

    1.7KRW

    31.8%

  • EGG

    4.4KRW

    5.9%

  • AIDUS

    3.9KRW

    -6.5%

  • XST

    44.3KRW

    -0.5%

  • LYM

    1.7KRW

    7.2%

  • RBTC

    8,333,903.1KRW

    1.6%

  • KARMA

    0.2KRW

    25.5%

  • CLB

    1.9KRW

    0.5%

  • NGC

    13.7KRW

    11.0%

  • PXL

    26.3KRW

    -0.0%

  • PTON

    0.1KRW

    -2.3%

  • UBEX

    0.3KRW

    0.5%

  • LKY

    17.9KRW

    --%

  • YEED

    0.2KRW

    3.5%

  • ISR

    4.1KRW

    10.9%

  • CLR

    5.5KRW

    5.8%

  • TEMCO

    0.2KRW

    -2.5%

  • WET

    4.3KRW

    0.6%

  • AMON

    0.9KRW

    -0.9%

  • MEETONE

    0.3KRW

    2.3%

  • FREE

    0.0KRW

    4.5%

  • ZPR

    0.4KRW

    22.7%

  • XRA

    5.6KRW

    --%

  • ADT

    0.7KRW

    -85.3%

  • QDAO

    6,347.2KRW

    1.6%

  • BBC

    0.9KRW

    16.7%

  • NEWS

    1.5KRW

    17.0%

  • WIKEN

    0.9KRW

    -8.8%

  • NPER

    3.6KRW

    --%

  • IQ

    49.0KRW

    5.7%

  • HORUS

    0.2KRW

    -37.5%

  • PUB

    0.1KRW

    -24.8%

  • SEAL

    0.2KRW

    --%

  • VANTA

    0.1KRW

    5.3%

  • STAR

    0.5KRW

    -11.3%

  • PUT

    2.0KRW

    4.6%

  • CCH

    0.0KRW

    --%

  • KNT

    0.0KRW

    -8.0%

  • DRM

    8.9KRW

    100.4%

  • UOS

    1.1KRW

    62.8%

  • BLACK

    0.3KRW

    0.9%

  • RCD

    3.0KRW

    --%

  • MCC

    3.6KRW

    --%

  • INC

    0.1KRW

    -14.8%

  • BZKY

    0.0KRW

    --%

  • CRE

    0.8KRW

    6.9%

Community

Learning Cryptography: Finite Fields

Loopring | 06.19| 447

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?