Algebra cheatsheet II

FINITE FIELDS / GALOIS FIELDS

Motivation

The Advanced Encryption Standard (AES) / Rijndael algorithm is the most widely used symmetric/private/secret key cryptographic protocol. The only feasible way of breaking it up to date is by a brute force attack. This does not include implementation flaws by the implementor and side channel attacks due to physical access of the device implementing AES.

The AES works on a block size of 16 bytes but since binary math happens on bytes/octets on a digital computer, AES  works in the finite extension field GF(28) where q=2 and m=8. More information on this in a later post.

To work in finite fields, the arithmetic is different from normal binary arithmetic as it involves modular arithmetic as read from the previous post.

Theory

A field is basically a set of numbers where addition, subtraction(additive inverse), multiplication and division(multiplicative inverse) are defined. This means that using any of these operations on the numbers will not break any mathematical properties of the oprations.

If a set of numbers is an algebraic group under both multiplication and addition, therefore the set of numbers become a field. The existence of an additive group automatically defines its inverse operation(subtraction). The same with the definition of division via the existence of a multiplicative group. Where both exist on a given set of numbers, the numbers become a field. The distributive law holds for fields. a(b+c)=ab+bc

As a field is simply a set. we define a version of a field called a finite field. A finite field is a field with a finite number of elements. The number of elements of a finite field is called the order/cardinality of the field.

A finite field is also known as a Galois field in honor of its creator, Évariste Galois

For a Finite/Galois field to exist. The order of the field must be prime.(Number of elements in the finite field must be a prime number)- A mathematical proof exists but is outside the scope of this discussion. See the error control coding book referenced.

A Finite/Galois field is summarized as GF(q), where q is a general prime number representation. The simplest finite field is the field of binary numbers {0,1} represented as GF(2).

In addition to prime field, there also exist extension fields that are extensions of prime fields. The order of an extension field is simply the prime number  raised to an integer power m>2, This is represented as GF(qm).

We use the term prime fields to differentiate GF(q) from extension fields GF(qm).

PRIME FIELD GF(q) ARITHMETIC

Example: GF(q) = GF(5) – {0,1,2,3,4} and GF(q)=GF(2) – {0,1}

This operation (prime field arithmetic) refers to a single digit of a field. For arithmetic on a tuple of digits from a field we can use field extensions GF(qm).

GF(q) ADDITION (a+b)mod q

GF(q) addition is a mod q operation.

+ 0 1
0 0 1
1 1 0

Figure: GF(2) addition. The above is the same as a binary XOR operation.

+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3

Figure: GF(5) addition.

GF(q) SUBTRACTION (a-b)mod q

GF(q) Subtraction is an additive inverse and can be represented as a + (-b) = c.

Thus b + (-b)=0 is an operation to finds the additive inverse where 0 is the additive neutral/identity element.

Example: In GF(5), 5 – 2 ≡ 5 + (-2) = 5 + 3 ≡ 8 mod 5 = 3 mod 5

Therefore additive inverse of 2 in GF(5) is 3. Addition and subtraction operations give same result if the operands are unchanged in mod 2 operation.

0 1
0 0 1
1 1 0

Figure: Modulo GF(2) subtraction. Similar to GF(2) addition.

row-column 0 1 2 3 4
0 0 4 3 2 1
1 1 0 4 3 2
2 2 1 0 4 3
3 3 2 1 0 4
4 4 3 2 1 0

Figure: GF(5) subtraction (column-row) because subtraction is non commutative unless when viewed as an additive inverse.

GF(q) MULTIPLICATION (axb)mod q

GF(q) multiplication is a mod q operation.

x 0 1
0 0 0
1 0 1

Figure: GF(2) multiplication. This is similar to a binary AND operation.

x 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

Figure: GF(5) multiplication

GF(q) MULTIPLICATIVE INVERSE axa-1=1 mod q

GF(q) division is an multiplicative inverse and can be represented as (1/b)

Thus bx(1/b)=1mod q is an operation that finds the multiplicative inverse where 1 is the multiplicative neutral/identity element.

Example: In GF(5), 5/2 ≡ 5 x (1/2)

(1/2) should be read as “the additive inverse of 2“. The value of (1/2) is not 0.5 as 0.5 is not in GF(q) as it is not an integer.

To obtain the multiplicative inverse of 2 (1/2), we obtain the value which when multiplied by 2 gives 1. This can be done via a lookup on the multiplicative table. The value is seen to be 3. Therefore multiplicative inverse of 2 in GF(5) is 3.

The multiplicative inverse of an element in GF(2) is the same as its complement via a binary NOT operation on the element.

Example: Multiplicative inverse of 1 is 0 and vice versa.

row x (1/column) 0 1
0 0 0
1 1 0

Figure: GF(2) division

Difference between prime fields and extension fields

The difference between working in a prime fields GF(q) and an extension field GF(qm) can be summarised as below with addition(Remember: q0=1 and q1=q):

GF(2) addition: 1+1=0

GF(28) addition: 11011110+11111111=00100001

GF(24) addition: 1101+1111=0010

Difference between field arithmetic and normal integer arithmetic(2’s complement arithmetic)

The difference between the above is that normal integer arithmetic does not involve modular arithmetic therefore does not wrap around.

Bit wide arithmetic

Normal binary arithmetic: 1+1 = 10 (3 in decimal)

vs

GF(2) arithmetic: 1+1 = 0 (0 in decimal)

Byte wide arithmetic

Normal binary arithmetic: 10110101+11111111 = 110110100 (436 in decimal)

vs

GF(28) arithmetic: 10110101+11111111=01001010(74 in decimal). The value never goes beyond outside the range [0, 2m-1]

Note:To implement prime field and extension fields in software, a class that abides by finite field arithmetic can be formed that has methods named add, subtract, divide, multiply.

The next post shall deal with extension field arithmetic before getting into AES cryptography.

An analysis of various cryptographic implementations shall be discussed including:

An analysis of cryptographic compliance based on NIST standards shall be made.

References

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s