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.

An overview of software defined radio

Wikipedia defines software radio as Software-defined radio (SDR) as a radio communication system where majority of the radio components such as amplifiers, mixers, filters among others have been implemented in software instead of hardware. This means that these part of a radio system are in software code instead of something physical.

To quickly understand how a software defined radio works, imagine the sound card on a computer. It converts sound from analog(continuous time) to discrete samples. After that, you can record(store) the sound samples in various formats such as .wav, .mp3 and so on. It also allows one to apply filters to the sound thus one can also mix sounds and perform many other effects. The act of applying the effects is called digital signal processing(DSP). So when you hear a DJ on the radio, he is doing nothing more than math on sound samples and you like the effects.

There is main drivers for the development of SDR:

  1. Digital signal processing(DSP). When you are applying filters to sound and so on, that is DSP. It is just applying mathematics to samples to realise an effect.
  2. Moore’s law– The growth of transistors that can be packaged in a chip at a given cost grows exponentially. This increases the computational speed, but of late this has hit diminishing returns so multi-core processing systems are more popular.

To further understand how a software defined radio works, let us look at how WIFI works based on its OSI (Open systems interconnect) model.

File:Osi-model.png - Wikipedia, the free encyclopedia

The OSI model

The physical layer defines our layer of interest when working in this. Examples of how this layer works:

  • In WIFI, the physical layer defines how the bits are converted to wireless signals from sender to receiver.
  • In ethernet, the physical layer defines how the bits are converted to electrical signals that travel down an ethernet cable between sender and receiver.
  • in USB, the physical layer defines how the bits are converted to and from USB signals that travel down a USB cable, from a host to device or vice versa.

The image below shows an example system block diagram of a software defined radio from XILINX:

https://i1.wp.com/www.ti.com/graphics/blockdiagram/blockdiagram_images/6091.gif

SDR system block diagram

The antenna is on the far left. The upper section is the input path and it defines the receive section of the system. It consists of an analog to digital converter(converts signals to bits). The lower section is the transmit section of the system(converts bits to signals).

THE FUN  STUFF

GitHub - mossmann/hackrf: low cost software radio platform

Hackrf SDR platform (1MHz-6GHz)

You can imagine you are an engineer who has been asked to develop a wireless system and you want to check that it works, how do you check wireless signals???

  • You either use a dedicated radio that  can tune to the wireless frequency you want. The radio will most likely convert the wireless signal to information. Example: If you want to check that you have a wifi signal, you take your phone and it gives you this information.
  • You can use a software defined radio that you can tune into the wireless frequency range and inspect that there is the desired signal.

Understanding how communication happens

shows a typical system diagram of a modern digital communications ...

The communication model

To use a software defined radio: Connect the SDR to your computer and tune  to your frequency of interest. Obtain the  modulation from the data and convert it into bits/information. This is done usually in C++ or Python using the software framework gnuradio companion.

Screenshot_2016-12-17_21-10-11

A GNU-radio wireless capture session

Then one saves a recording and writes a software decoder to decode the signal usually in python or C++.

Example 1: vehicle wireless key signal(Digital)

An example of this is below when one presses a wireless key to open a car, you want to check that it works.

keyfob_unfiltered

A spectrogram. The horizontal axis is frequency, vertical is time.

To clearly see the signal sent to the car to unlock, we need to zoom and filter the signal. The brighter the  parts of the image, the more power there is thus giving an indication of information being sent. The rest of the image is just background noise power.

We thus isolate the lower power section which represents background noise and we obtain our signal to the car.

keyfob_color_plot

As can be seen, It can be seen that the power shifts between two frequencies thus one frequency represents a binary 1 and the other represents a binary 0. This sequence of 1s and 0s is binary data.

If we remember our definition of the physical layer, The physical layer defines how bits are encoded into physical signals. In this case, this case a binary 1 is encoded into frequency F1 and binary zero is encoded into frequency F2. This encoding is called modulation. This specific modulation is called BFSK(Binary frequency shift keying). The carrier frequency is generated usually by an oscillator on the wireless key and modulated by the data.

NOTE: A software defined radio can even demodulate the signal to give you the actual message. It is not enough to use the above system to open cars as the wireless key signal is pseudorandom nature as a rolling key(constantly changing under an algorithm) is XOR’d with the message. Once the car system receives the message, it XOR’s the message with the key to obtain the actual command message from the wireless key. More details of this can be studied in stream ciphers in cryptography. It relies on synchronizing the receiver and transmitter in order not to xor with the wrong key.

Example 2: FM capture(Analog)

FM means frequency modulation, it encodes low frequency information such as voice on a higher frequency wave called a carrier signal. The carrier signals in Kenya are standardised by the Communications authority from 88MHz-108MHz.

Animation of audio, AM and FM signals

Frequency vs amplitude modulation

 

To inspect this on the local FM band, we tune and we check the power across the frequency bands to obtain the following signals which confirm Frequency modulation. I remember there was a talk show at the moment this was captured.

FM modulation on the FM frequency bands.

 

 

SDR is thus an important tool for wireless designers, wireless researchers and hobbyists. This concludes the overview of software defined radio(SDR).

A brief introduction to unit testing in C with unity

Unit testing is the practice of testing different components of a code where the different components can be taken as independent entities that only interact in order to realize full functionality.

Usually when developing embedded code there is code under test and production code. Production code is code that will be released while code under test is code that is being tested, prior to release or probably as an experimental feature that may never see the light of day.

An effect of not testing code is an unpredictable behavior given an unforeseen input by the author. An example of such is a technique called fuzzing where random input is fed to an executable or code until it fails. Such a scenario would then be used to exploit an unforeseen vulnerability. More details in this Chaos Communications congress talk.

So how do you protect against that which you do not know?

Enter Unity. Unity is a C framework that is composed of C macros that checks(asserts) whether a given code under a given stimuli(input), gives an expected output. It is usually a test of code behavior under different scenarios. The code therefore should be deterministic.

Unity is meant for code that is incrementally tested  along its development as opposed to the traditional code development cycle where code is tested after development. This ensures code is tested even before it is refactored. Usage of unity is basically composed of 3 parts:

  • Test code– Code that is used to test the code under development.
  • Test caseTest code that checks result of code execution against the expected behavior.(Example: Input X should give input Y. If not, test failed).
  • Test fixture– A set of test cases that does the same as above but under different scenarios. It is grouped under a single entity. (Example: The code should behave this way for inputs X,Y or Z)

A more detailed use case of unity shall be given in a later post.