Gentle and in depth introduction to Google protocol buffers(protobufs)

Image result

I met protobufs while trying to understand how messages are sent from device to the cloud using LoRaWAN implementations such as that by TheThingsNetwok.

What protobufs is:

  • A protocol that is used to serially encode and decode structured data to be sent out a wire(usually meaning communication path from sender to receiver). It also defines the endianness of the data along the wire. It can be used to send structured data.
  • It can be used to send data across machines and ensures that the transformation will happen transparently. Example: Sending a 32 bit unsigned integer from an embedded system running C is received as the same data type on a server running node.js. Another example: Sending data between servers with different implementation languages. This avoids the need to avoid sending data as text (XML, Json).

  • Attaining operational efficiency irregardless of language implementation. This is because the implementations are optimised.
  • Optionally – A poor man’s means of attaining variable length compression(I will get to this is a bit).

A typical usage scenario is as below:

  • You have structured, formatted data that is to be sent from a sender to receiver, this can be fields made up of text.
  • You define the fields in the messages that make up the protocol between your sender and receiver(Device to Device for example) and you are aware that the protocol may expand messages and/or fields so it follows semantic versioning to take care of backward compatibility and breaking changes.
  • The sender and receiver implementations use protobuf-supported languages by google or third parties. Embedded device languages included such as C.

How to use protobufs

  1. Define the protocol messages and follow as described here
  2. Create the .proto file as above that describes the messages. This will be the input to the protobuf compiler. The protobuf compiler has backends that generates code for different languages from the same .proto file. This ensures that the same message sent from a client in C is received by a server in Golang and decoded correctly.
  3. Create code in the sender and receiver implementation languages that calls the code generated by the protobuf compiler. The files generated by the protobuf compiler are textual and readable.

In depth view of protobuf message formats

A sample structured message is passed between a sender and receiver that describes a person’s data and is described as below and as opposed to xml and Json which only represent text, this message entity contains text and integers :

message Human {

char name /*Field 1*/

uint8 age /*Field 2*/

message parents= /*Field 3*/

{

bool mother /*has father*/ /*Nested field 1 of field 3*/

bool father /*Has mother*/ /*Nested field 2 of field 3*/

}
}

Each entry in the unencoded message is called a field and messages may be nested to represent the entity to be sent. A protobuf encoding thus transforms the nested tree structure above to a one dimensional structure(buffer/queue) sent along the wire in FIFO(First in-first out) format.

The encoding is done on a per field basis and a field that has been encoded(buffer) looks as below:

The data is sent along the wire as key-value pairs, where the key informs the parser of how to reconstruct structure. The field number of each field is sent first per field.

Field key encoding

The key is defined as the section of the serialised field that uniquely identifies the payload in the nested data structure to be reconstructed at the receiver. The key and value are encoded separately.

The key has the following sub-sections:

  • Field number=defines the entry by a number in the structure. Example: Age field in the human structure is defined as 2.
  • Wiretype- Defines the encoding of the field payload data. Several field payload encodings are available as below:

The Wiretype is defined as 3 bits in the protocol buffer specification(integer 0-7), only 0-5 are occupied and 6,7 reserved for future use.

For the most common field payload encodings, varints are used. Varints apply an encoding known as Little Endian Base 128.(LEB128) .Google protobufs use an LEB128 format know as unsigned LEB128 as shown in the link above on Wikipedia.

Other encodings can be found at https://developers.google.com/protocol-buffers/docs/encoding

How protobuf compiler transforms the key field section to a buffer format

The key section of the key-value pair undergoes Varint encoding. The key of a key-value pair is defined as:

Each Varint encoding occurs as groups of 7 bits.

Google states:

Therefore:

  • Minimum number of fields that can be sent is 1. This field key is thus encoded as a byte.
  • The key for a structure with 1-15 fields whose field number/TAG is in range 1-15 is represented as 4 bits(0000-1111), The field type adds 3 bits to give 7 bits therefore this is encoded as a byte in varint encoding.
  • The key for a structure with 16-2047 fields whose field number/TAG is in range 16-2047 is represented as 11 bits.The field type adds 3 bits to give 14 bits therefore this is encoded as two bytes in varint encoding.
  • The largest number of fields than can be sent is 229-1 which gives 536,870,911 fields. The key is encoded as 5 bytes.

You can’t have structures sent over with fields numbers in the range 19000-19999 as they are reserved.

Performing variable length encoding of fields

The fields have a higher probability/explicitely required can be given ranges in the 0-15 range, this will give the key as a byte long  thus optimising bandwidth and ensuring effecient coding. of the field packet. Due to this, you will notice that messages in the proto files have the following formats with the required fields leading in the specification within that file. Example:

Be sure to have a read through the specification especially the techniques section that defines how good a fit protobufs is for you.

Designing a chip antenna keepout zone in python with Kicad

keepout

Antenna design has a lot of information for one to take in, especially if it is your first time doing it. In the process of developing networks and protocols for interconnected devices(IOT), there is an urge to miniaturise devices usually held by the notion “Smaller is better”.

A large part of creating devices involves the physical nature of a device and this includes its mechanical characteristics and its electrical characteristics. This is largely ignored usually and usually forms the barrier between creating a single device and moving on to mass production and manifests itself in engineering cost.

A part of this which is usually a dark art is Radio frequency design  and in product development it is usually in the statement “We need to make this design smaller” and antenna size plays a huge role in this depending on the area of application of a device. The steps taken to design an antenna involve the following:

1. Determining the application area of the device

I usually define areas of physical application in three broad categories:

  • Indoor
  • Semi-outdoor/indoor
  • Outdoor

Any of the above can also belong into other categories involving the actual use of device:

  • Human to machine(H2M).
  • Machine to machine(M2M).

The most difficult to design is Outdoor due to the weather elements and Human to machine due to the various use-cases the device may be used for and the need to pre-plan and manage user expectation.

2. Determining the factors affecting and constraints on antenna.

From the above high level classification, one then has to determine the effect of the immediate environment including:

  • Physical space constraints of the region the device will be present.
  • Effects of the immediate materials surrounding the device. An example of this are walls causing signal absorption, metals causing a change to the antenna field distribution and so on.
  • Movement of the device: This usually shows up as the Doppler effect and does affect satellite communication and high velocity communications.

The application use-case usually affects how the user perceives and interacts with the device especially in H2M applications. This is usually a design perspective that will directly affect the antenna design.

3. Choosing the antenna

This will be affected by expected cost, performance and look. There are two broad categories of antennas:

  • Internal antennas.
  • External antennas.

External antennas

External antennas are used for Industrial applications or non H2M applications where the shape and size doesn’t affect the user of the product. A famous type of external antenna in IOT applications is the whip antenna.Image result for whip antenna

Figure: A 3G/4G whip antenna.

A whip antenna is usually good where the device shape/size doesn’t matter and performance is a no compromise.

Internal antennas

These are usually in two types:

  • PCB antennas.
  • Chip antennas.

PCB antenna also called Trace antennas use the copper of the PCB board as the radiating element and the air and board underside as the dielectric. They are susceptible to detuning depending on the presence of metals, plastics and other PCB components nearby.

PCB antennas

https://i0.wp.com/dangerousprototypes.com/blog/wp-content/media/2013/02/2013-02-22_2311-600x409.png

Figure: PCB Antenna selection guide from Texas Instruments(TI) for the Industrial Scientific and Medical(ISM) band

The advantage of PCB antennas is zero cost but the disadvantage is that it involves lots of testing and simulation. They also may have poor efficiency if incorrectly used.

Chip antennas

https://www.proto-pic.co.uk/user/products/large/00691-03-L__62893__82521.jpg

Spark-fun NRF24L01+ transceiver with blue chip antenna.

Chip antennas are simply quarter-wave monopole antennas that require a ground plane in order to transform it to a half-wave dipole antenna. This is usually an example of an image antenna .

The Chip antenna usually contains its own ground plane and thus the PCB board it is to be mounted on needs to be clear of all copper. The removal of copper from the PCB forms what is called a keep out zone abbreviated as KOZ.

Kicad

Image result for kicad logo

Kicad is a great and free PCB design tool and I have been using it for approximately six months now after I switched over from EAGLE CAD. I can always pay the monthly eagle fee but I love community driven initiatives. Kicad being an open source project it usually leans on contributors like you and me apart from the official project contributor which is CERN(European Organization for Nuclear Research) in Europe.

Image may contain: 22 people, people smiling

Past image of my visit to CERN at the port hackathon, with Nobel Prize laureate in physics Jack Steinberger. Attribution to The Port association.

Kicad nuance

This lead me to my issue: Kicad lacks a means to precisely create keepout zones. One can always create a KOZ by moving the mouse on a grid and snapping on the coordinate plane but for antenna design, this does not suffice! Measurements need to be spot on and a mistake of a few millimeters can easily detune an antenna thus one needs to go berserk on the design and thoroughly inspect it. DO NOT TRUST THE DESIGN SO EASILY!…RECHECK

Image result for meme foaming at the mouth

 

Python to the rescue

Image result for python logo

Kicad includes a python interpreter that provides an interface to the compiled C++ codebase. This is done using SWIG http://www.swig.org/ that converts the C++ kicad code to python.

pyshell

Python usually has a dedicated folder for its python scripts and on my nix box, this is at:

$/usr/share/kicad/scripting/plugins/

The design

The specific chip antenna being designed for is the Ethertronics M620720:

M620720 Ethertronics Inc. | 939-1066-1-ND DigiKey Electronics

For design this antenna requires the following free-space tested land pattern:

land_pattern

 

Due to the effects of antenna detuning, it is recommended to leave a space for a PI(Shunt-series-shunt) matching circuit that one can use to correct the impedance matching after production. A PI circuit has a high Q level, and is suited for instantaneous narrow-band signals due to the high Q. More details of PI matching circuits can be found at Wikipedia .

PI_cct

At design time, it is best to use a 0 ohm resistor or solder bridge as the series element and do not populate(DNP) the shunt elements. The individual elements for a match can be calculated from a vector network analyser(VNA) measurement after production by plotting on a smith chart.

Creating the keepout zone

Kicad is built on the Wx C++ framework and thus kicad reuses alot of the components from Wx framework. In python this is Wxpython. The keep-out zone is a simple rectangular shape with the corner points as the elements. The coordinates should be known before hand with reference to the origin of the layout design. The coordinates in python is as Wxpoint with method attributes Wxpoint.x and Wxpoint.y .

Kicad uses a coordinate space of 1E6 units to form a milimeter thus in order to convert from millimeter from to kicad coordinate space one must multiply by 1000000. This is implemented in the method pcbnew.FromMM() .

We then form a python script file is antzone.py:


import pcbnew

def create_point(x,y):
    return pcbnew.wxPoint(pcbnew.FromMM(x),pcbnew.FromMM(y))

def insert_antenna_keepout(left_bottom_pt, left_top_pt, right_top_pt, right_bottom_pt):
    board = pcbnew.GetBoard()
    layers=[board.GetLayerName(0),board.GetLayerName(1),board.GetLayerName(2),board.GetLayerName(31)]
    for layer in layers:
        _insert_keepout(left_bottom_pt, left_top_pt, right_top_pt, right_bottom_pt, layer)
    #Refresh
    board = pcbnew.GetBoard()

def _insert_keepout(left_bottom_pt, left_top_pt, right_top_pt, right_bottom_pt, layer):
    board = pcbnew.GetBoard()
    hatch_type = pcbnew.CPolyLine.DIAGONAL_EDGE #Hatched outline
    area = board.InsertArea(-1, 0xffff, board.GetLayerID(layer), left_bottom_pt.x, left_bottom_pt.y, hatch_type)
    #coordinate of first corner (a zone cant have empty outline)
    area.SetIsKeepout(True) #Set area as KOZ
    area.SetDoNotAllowTracks(False) #Allow tracks in KOZ
    area.SetDoNotAllowVias(False) #Allow vias in KOZ
    area.SetDoNotAllowCopperPour(True) #Do not allow Copper pours in KOZ

    outline = area.Outline()

    outline.Append(left_top_pt.x, left_top_pt.y)
    outline.Append(right_top_pt.x, right_top_pt.y)
    outline.Append(right_bottom_pt.x, right_bottom_pt.y)

    area.Hatch()

To simplify the input process, we form a second script file that takes in the user coordinates:


import antzone

left_bot=antzone.create_point(160.28,78.537)
left_top=antzone.create_point(160.28,67.7)
right_top=antzone.create_point(171.78,67.7)
right_bot=antzone.create_point(171.78,78.537)

antzone.insert_antenna_keepout(left_bot,left_top,right_top,right_bot)

 

References

 

 

Fixing solid state drive(SSD) boot error

This guide may also be applied to older mechanical disk drives and may save you a trip to a data recovery center. Note: If your data is super-critical, it is always useful to have a RAID arrangement of disk drives in order to reduce the probability of disk failures.

I have a year old SSD that I have been using that suddenly stopped working after I shutdown. On booting my computer again, I was met with the error:

CANT FIND BOOT DEVICE.

To solve this error, it is good to understand how a standard computer boots and how storage devices are structured.

SOFTWARE BOOT STRUCTURE

boot

First stage bootloader: This is written by the motherboard manufacturer who namemost likely is the PC make. It checks for the hardware currently on the system and reports any problems on screen. It then checks for a second stage bootloader on a boot device such as a hard disk, flash disk, over a network.

Second stage bootloader: This is currently written by a user or OS maker. This bootloader checks for any data errors on the OS and boots the OS.

Reasons for failure

The reason for failure of a drive does not necessarily mean the device has failed but just that some part of the boot process has failed and most likely it is the data on the device read by the bootloaders. Errors can occur due to age, radiation , quantum effects and so on so at times may seem random.

To counter this hard drive manufacturers ensure that there is an error correcting code(ECC) within the boot process. Note there may be some firmware between the first and second stage bootloader that handles the SSD. The ECC may be handled by this firmware.

Solving the problem

  1. We need to ensure that the bootloader is just the problem and not the whole disk.
  2. Insert a mechanical disk and boot it to eliminate possibility of damage of the connecting cable to the storage drive.
  3. Use a USB startup disk of your operating system and boot from it. Thus you can repair the disk if the bootloader is Microsoft’s.
  4. This may be problematic if the bootloader is not microsoft’s for example if one was dual booting or running linux solely. Insert a USB startup disk of your SSD operating system, boot from it.
  5.  After (4), check the file system on the SSD, if the filesystem can be seen you can repair as a first alternative. It should be able to read windows files and linux files.
  6. If one does not have the USB or CD of your SSD OS you can use a USB pendrive with any linux OS. Try to read files from the SSD filesystem. This mysteriously solved it for me. No other operation was applied.

WROOM32 based, removable ESP32 module and associated programmer

Bitsoko-ESP32-module-v2

So we have been developing a module for the ESP32 above that we can use. Its based on the ESP WROOM32. The design are made in KICAD. The module is removable from the programmer and can be mounted on a product without soldering which is often useful for testing without having a dedicated programming section per product which increases product cost, for something that will be used once.

There is also an associated minimalistic programmer with a standard JTAG 20 pin header where one can connect a JTAG adapter for debugging. Design specifically contains no surface mount parts so should be easy to assemble without importation. The programmer can also be used as a development board.

The designs are in their initial versions but work well. Details shall be released as the project matures and bugs eliminated.

Draw timing diagrams in javascript with wavedrom

Wavedrom is a fantastic way to mock up a timing diagram. A timing diagram shows a sequence of how several signals change with time. Usually the signals are wire-line, meaning that they are electrical signals flowing through a wire. They are usually used to represent wire-line protocols such as SPI, I2C etc.

The changes are represented by single letter markers showing the state of the signal at a step in the plot. Example is a high to low transition represented as ‘pl’ among other signal changes. It is useful in describing a system of signals and may help one gain insight as to the time-relationship between signals. A tutorial may be found here.

The image below is of a timing diagram I previously constructed and associated code below:

timing_diagram

{signal:
[
{name: 'Column shift SRCLK', wave:'l.p|p.|p.|p.|p.|p.|p.|p.|l...'},
{name: 'Column data SER', wave:'x5..5..5..5..5..5..5..5..x...', data: ['ROW 0','ROW 1','ROW 2','ROW 3','ROW 4','ROW 5','ROW 6','ROW 7']},
{name: 'Column latch RCK', wave:'l.....pl.pl.pl.pl.pl.pl.pl.pl',},
{name: 'Row clock RCLK', wave:'l....pl.pl.pl.pl.pl.pl.pl.pl.',},
{name: 'Row reset RST', wave:'L...........................p'},
],
config: { hscale: 1 },
head:{text:'LED matrix timestep control',},
foot:{text:''},
}

 

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.

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://i0.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).