Algebra cheatsheet III

Extension fields part I

Motivation

Extension fields is the mathematics involved in two example cases:

  • When you burn data on a disk. The data can then be retrieved when read even when there are scratches on the disc. Even if there are errors on the disc when read due to the scratches, some algorithm called an error correcting code shall correct the errors for you up to a certain limit, beyond which the disc is corrupted. This algorithm/code called a BCH code works in the binary extension field GF(2m) to accomplish this.
  • When you want to skype, only the caller and receiver receiver the video streams from the webcam from both ends. This is called encryption and decryption and is a branch of mathematics/engineering known as cryptography. The cryptographic code that accomplishes this, known as AES works in the binary extension field GF(2m).

crypto system definition

A system that can perform encryption and decryption is known as a cryptographic system/cryptosystem.

cryptographic protocol definition

There is a difference between a cryptosystem and a cryptographic protocol is that while a crypto system deals with encryption and decryption, a crypto protocol may deal with several crypto systems in a given use case scenario. According to Wikipedia, as it is tied toa scenario, the crypto protocol has to provide a majority of the following:

  1. Key agreement/establishment between communicating parties.
  2. Communicating entity authentication.
  3. Secure application level data transport
  4. Non repudiation methods, mostly through digital signatures.
  5. secret sharing methods
  6. symmetric encryption and/or public key/multi party encryption. The use of both is called a mixed encrypton scheme.

Example: Transport layer security(TLS) which ensures secure communication over the web. It involves: An authentication mechanism through the use of X.509 certificates and key exchange grouped into one operation known as a TLS handshake. It also provides secure application level data transport after the handshake. It thus accomplishes 5 out of 6 of the above objectives of a crypto protocal.

More about cryptosystems

Encryption– A means of hiding information(plain text) so that even if it is intercepted its secrets can’t be known. The form in which it is hidden in is called cipher text. Therefore encryption is a transformation of plain text to cipher text.

encryption

Decryption– A means of unhiding information so that the secret_systems can be known. Therefore decryption is a transformation of cipher text to plain text.

decryption_wo_key

A key is  thus introduced to ensure only the people needed to read  the message can do so. This also allows the cryptographic system to be publicly available to be tested without worrying about the key. The flaws of the cryptographic system can then be corrected which leads to even stronger security. Even an attacker of the system may know details of the system itself but decryption would be infeasible without the key which is ideally only known to the sender and receiver.

Any cryptographic  system thus comprises of 3 parts:

  • The plain text
  • The key
  • The cipher text

An attack on a cryptographic system is taken as an attack on any of the above 3 individually or through the interrelationships between them. It is thus important to decouple the three as much as possible in an encryption system.

crypto_relationships

According to Claude Shannon, there are two primitive operations upon which reliable encryption algorithms can be built:

  • Confusion – The relationship between key and cipher text is obscured. This is commonly implemented in substitution operations(S – boxes from a system view perspective).
  • Diffusion – The effect of a plain text element should be spread out all through the cipher text. The goal is to hide the statistical properties of the plain text so that it is not evident by looking/peeking at the cipher text.

The only thing Shannon did not talk about is the plain text – key relationship. Since both are inputs to a cryptographic system, it is best that they are decoupled as much as possible with the key being as random as possible at the input, but shared between the sending and receiving parties. This generation of the key is classified under “key generation techniques”.

To understand how an attacker can attack a general encryption system, we thus look at the different ways the attacks can happen in 4 ways:

  • Cipher text only attack – The attacker has  the some cipher text and thus needs to find a) The key if he/she is interested in decrypting subsequent messages b) The plain text if he /she is interested in the current plain text. This would most likely be due to some habit developed by the encrypter that would indicate where the interesting parts of the cipher text are. To do a) and b), the feasible option would be a brute force attack where the attacker would go through every feasible key combination till the plain text makes sense. The remedy would be to use a large key space till the in-feasibility / investment into such an attack is much greater than the gain from obtaining the cipher text. This can be viewed in terms of time or resources.
  • Known plain text attack – Attacker has access to parts of the plain text and the corresponding cipher text.
  • Chosen plain text attack – An attacker has access to a given plain text and corresponding cipher text of his/her choice.
  • Chosen cipher text attack – The attacker can decrypt parts of the plain text but does not know the whole decryption key.

The Advanced encryption standard (AES) as a cryptosystem.

NOTE: AES can be viewed as both a cryptographic system and a cryptographic standard.

The advanced encryption standard(AES) is a type of private key/symmetric encryption where the sender and receiver use a pre shared key to determine the contents of the message.

It is published as a Federal Information Processing Standards Publication 197 (FIPS PUB 197). The actual publication dated November 26 2001 can be found here

In a symmetric encryption scheme, the sender, say Alice, may encrypt the message into a non understandable text called cipher text to Bob, who then uses the same key to decrypt the cipher text and obtain the message sent.

The AES encryption block diagram looks as below:

AES_block-1

In order to understand a sample use of extension fields GF(qm) where in this case q=2, as the data is usually binary in nature, we thus need to look deeper in the AES encryption block above.

https://i2.wp.com/slideplayer.com/slide/6636376/23/images/10/AES+Round+Stallings+Fig+5-3..jpg

Each pass pass through the AES algorithm by a given data block is called a round. The number of rounds per 16 byte block is a function of the key length with:

  • 128 bits having 10 rounds per block.
  • 192 bits having 12 rounds per block.
  • 256 bits having 14 rounds per block.

The path the data follows in the AES encryption block is known as the data path. It represents the continuous changes the data undergoes. The data path at a given point is also known as the state.

Within a round there, all layers layers that work on all  128 bits of the 16 byte data block. There exists 3 layers. Each of the 3 layers work repeatedly on the data in successive procedures known as rounds.

The various layers in a round include:

  • Key addition layer – A 128 bit round key is derived from the main key then XOR’ed with the data path. The function that derives the round keys from the main key is known as a key schedule. The extension field operation involved here is GF(2m) addition.
  • Byte substitution/ sub bytes layer – Each byte in the state is  transformed by the use of lookup tables with special math properties. This causes confusion where the relation between the key and cipher text is hidden. This is usually a non linear transformation. The extension field operation involved here is GF(2m) inversion.
  • Diffusion layer shift rows sub layer –  This layer treats the 16 bytes as a concatenated block of 4, 4 byte blocks. It then cyclically right shifts each byte by various amounts. This shall be shown later. The is no extension field operation here, just computational right shift instructions.
  • Diffusion layer mix columns sub layerThe extension field operation involved here is GF(2m) multiplication.

The next post shall go through the various extension field operations and how they relate to AES in depth in order to gain an intuition.

The post after next will go through an encryption and decryption operation manually on a sample 16 byte block while referencing code from libsodium / mbedTLS (C library) from start to finish. The result will then be verified using the python cryptographic library pycrypto.

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

Algebra cheatsheet I

This algebra reference is important for cryptography and error control coding.

1. NUMBER SETS

  • set natural Natural numbers {1,2,3,…}- Does not include infinity as it is not a valid number.
  • Prime numbers– A subset of natural numbers that has no lower order factors except 1. See link
  • set integerIntegers {… , -3, -2, -1, 0, 1, 2, 3, …}- Negative and positive whole numbers including zero.
  • set rational Rational numbers. The result of a division operation of any two integers but without zero as the denominator. Could also be thought of as numbers that can be represented as a fraction(ratio of two integers).
  • Irrational numbers. A number that can’t be represented as a ratio of two integers exactly, without zero as the denominator.(NOT rational)
  • set real Real numbers. Includes all rational and irrational numbers thus  Natural numbers, integers, rational numbers, irrational numbers.
  • set imaginary Imaginary numbers. See link
  • set complex complex numbers. A combination of real and imaginary numbers. Example: 3+4i, -16.5+4.3i

 

number sets

Mathematical number set venn diagram. Source: http://www.mathsisfun.com/sets/number-types.html

2. MODULAR ARITHMETIC

STEP 1

If we have A, R, M which belong to the set of integers, and m>0:

A ≡ R mod M ≡ QM + R

Where R is the reminder, Q is the quotient, M is the divider, A is the unreduced number.

This means that an integer “A” can be reduced to R in a modulo “M” operation.

STEP2

Due to different quotients giving different reminders, another constraint is added to the reminder.

0 ≤ R ≤ M-1

Example(Modulo 9 addition):

(16+7) mod 9=23 mod 9

Without the step 2 constraint on the reminder, the following reminders are valid:

For the following set of Q{…, -1, 0, 1, 2, 3, …} gives this set of R {…, 32, 23, 14, 5, -4, …}

If we apply the step 2 constraint, the valid value of the modulo addition is 5 as 0 ≤ 5 ≤ 8

Python code

Calling the python interpreter on the command line

>>> #Compute the modulo of an integer with python's modulo operator
... -1%5
4
>>> #Trial of the example above
... (16+7)%9
5

3. ALGEBRAIC GROUP(or simply group)

A group is a mathematical entity that describes  a set of elements, say G that is generally defined with certain properties under a hypothetical binary operation •  . the general operation •  combines any two elements of G to give a result. (a•b=c)

PROPERTIES OF GROUPS

  1. The result of the binary operation “•” with the elements of G is closed, This  means that the result will still be in the set of elements G.
  2. The operation on elements of the group is associative.(a•b)•c=a•(b•c)
  3. There is an element “e” in G called the neutral/identity element of the set G under the binary operation “•”.
  4. Every element in the group G has an inverse under the operation. The following relation thus automatically holds. For ∀ a∈G, a•a-1=e,where e is the identity element of the group.
  5. If the group is commutative under the operation, the group is known as an abelian group.