From groups to QR Codes

Today, QR codes have an ubiquitous role in our every day life. They are used for holding data such as simple texts, URLs, contact information, payments, even Wifi atuhentication data. Furthermore, in industry they are used all around the logistics chain, for tracking the product process. This article aims to guide the reader from basic abstract algebra and coding theory to QR codes, which sound at first two very loosely related terms.

Before we begin

The reader is required to be somewhat familiar with some introductory abstract algebra because otherwise the article may seem to have a steep learning curve otherwise. For an introduction to abstract algebra, the reader can refer to “A book of Abstract Algebra” which is an excellent source for a beginner. A bit of familiarity with Python and some of its libraries is also required, because it will be used for the implementation. It is worth mentioning that given enough patience for the calculations and a millimetre notepad we could implement all this on paper and avoid programming, but we want to make our lives easier.

The goal of this article is to create manually from scratch a QR code for the URL of our blog: “https://cypher-punks.gitlab.io ”

Abstract Algebra

Rings

Ring : A ring consists of set $R$ equipped with two arbitary binary operations, usually denoted as $+$ and $*$, defined on the set $R$, and they’re pronounced addition and multiplication accordingly, satisfying the following axioms:

  1. $<R, +>$ is an abelian group
  2. Multiplication is assosiative. That is $\forall a,b,c \in R : a * (b * c) = (a * b) * c$
  3. Multiplication is distributive over addition. That is $$ \forall a,b,c \in R: \ a * (b + c) = a * b + a * c \ (b + c) * a = b * a + c * a $$

A ring is usually noted as $<R, +, *>$. It is also worth mentioning, that $<R, *>$ is not a group itself, because it lacks the identity and the inverse properties of a group. So a ring does not necessarily have a identity element for multiplication (which we will call unity for clarification from the additive identity element). The most common ring example is the set of integers $\mathbb{Z}$.

Similarly with groups, every ring can be described by its operations tables. For example,

$$ \begin{array}{l} \begin{array}{l|l|l|l|l|} & 0 & 1 & 2 & 3 \ \cline { 2 - 5 } 0 & 0 & 1 & 2 & 3 \ \cline { 2 - 5 } 1 & 1 & 0 & 3 & 2 \ \cline { 2 - 5 } 2 & 2 & 3 & 0 & 1 \ \cline { 2 - 5 } 3 & 3 & 2 & 1 & 0 \ \cline { 2 - 4 } & \multicolumn{4}{c}{+} \ & & \end{array}\ \begin{array}{l|l|l|l|l|} & \multicolumn{1}{l}{0} & 1 & \multicolumn{1}{l}{2} & \multicolumn{1}{l}{3} \ \cline { 2 - 5 } 0 & 0 & 0 & 0 & 0 \ \cline { 2 - 5 } 1 & 0 & 1 & 2 & 3 \ \cline { 2 - 5 } & 0 & 2 & 3 & 1 \ \cline { 2 - 5 } 3 & 0 & 3 & 1 & 2 \ \cline { 2 - 5 } & & & & \end{array} \end{array} $$

Commutative Ring : A ring $<R, +, *>$ is called commutative if multiplication is also commutative.

Unity :

Ring with unity : A ring $<R, +, *>$ is called to have a unity if there exists an identity element for the multiplication.

IMPORTANT NOTE : Modern mathematicians, define a ring as a ring with unity and call a ring without unity Rng (a ring without “i”, where i stands for “i”-dentity element).

However, this doesn’t mean anything about the existence of the multiplicative inverse of an element. Take for example the set $\mathbb{Z}$, there exists a unity, the element 1, but only two of its elements have an invserse, -1 and 1.

Subring : Let $A$ be a ring and a $B$, where $\empty \subset B \subset A$, if $B$ is closed with respect to addition, negatives (additive inverses) and multiplication, we say that $B$ is a subring of $A$. Or equivallently, if $B$ is closed with respect to subtraction and multiplication it is a subring of $A$. Of course, $B$ forms a ring itself.

Integral domain : A commutative ring $<R, +, *>$ with unity having the cancellation property

The set $\mathbb{Z}$ is an integral domain, hence and its name.

Field : A commutative ring $<R, +, *>$ with unity in which every nonzero element is inversible.

In the case of a field, both $<R,+$ and $<R, *>$ form abelian groups which are connected with the multiplication’s distributive property over addition.

The sets $\mathbb{Z, Q, R, C}$ are all rings, you can easily prove it yourself. From those only $\mathbb{Q, R, C}$ form a field, $\mathbb{Z}$ is an integral domain.

Bellow, there’s a map of the various definitions given bellow.

Ideal : A non empty subset $B$ of a ring $A$ is called an ideal of $A$ if $B$ is closed with respect to addition, negatives (or simply subtraction) and absorbs products in $A$.

Principle ideal : The set $B$ that is generated by all the multiples of a fixed element $a \in A$. It is denoted as $\langle a \rangle$

Homomorhpism :

Ring homomorphism : A ring homomorphism from a ring $A$ to a rin $B$ is a function $f : A \rightarrow B$ satisfying the identities:

$$ f(x_1 + x_2) = f(x_1) + f(x_2) \ f(x_1 x_2) = f(x_1)f(x_2) $$

For example, ring $\mathbb{Z}_4$ is isomorphic to ring $\mathbb{Z}_8$

Coset :

Quotient Ring :

Contructive proof

Fundamental Homomorphism Theorem (FHT) for Rings :

$$ \mathbb{Z}_n = \mathbb{Z}/ \langle n \rangle $$

Polynomial Rings

Polynomial Ring :

Polynomial Fields

Theorem 1 : Every ideal of $F[x]$ is principal.

Theorem 2 : The invertible elements of $F[x]$ are all the nonzero constant polynomials.

Reducible polynomial

Irreducible polynomial

Polynomial factorization into irreducible polynomials

Notice that the irreducible polynomials play the role of the primes.

Vector Space

Vector Space :

Finite Fields (Galois Fields)

Finite field : A field $<R, +, *>$, where $R$ has a finite number of elements. A finite field is equivallent to an finite integral domain.

Finite field of prime order :

Finite Field of prime power order :

Applications of Galois fields

Galois Fields are used in various fields of Computer Science, cryptography tellecommunications (coding theory as we’ll find out later) to name a few. In cryptography, GFs have major applications, elliptic curves over finite fields and popular block ciphers such as AES and DES are among them. Let’s consider the case of a byte $b$. We can either interpret it either as a binary value corresponding to a decimal number $b \in \mathbb{Z} / \langle 2^8 \rangle$, where $\mathbb{Z} / \langle 2^8 \rangle$ is a quotient ring. But we can also interpret it as an element $b \in GF(2^8)$. The reason we choose the latter interpretation is because the $GF(2^8)$ forms a field, which means it is closed with respect to addition and multiplication but most importantly that every element is inversible. In $\mathbb{Z} / \langle 2^8 \rangle$ we don’t have these properties, it only forms a ring. It is itself closed with respect to addition and multiplication, but lacks the inversibility property. If it was only for addition, because both structures form a ring, a ring is an abelian group so using either of the structures forms would be equivallent.

Coding Theory

Let’s denote the set of all binary words of length n as $\mathbb{B}^n$.

Code : A code $C$ of length $n$ consists of codewords $c_i \in \mathbb{B}^n$. It is a subset of $\mathbb{B}^n$. It consists of information positions where it holds information bits and of redundancy positions where it holds redundancy bits responsible for error detection and correction.

Group code : When the code $C$ is a subgroup of $\mathbb{B}^n$, e.g. $C < \mathbb{B}^n$

Cyclic code :

Linear code :

Codeword :

Generator Matrix :

Parity Check Matrix :

Length of code :

Weight of binary word : Is the number of 1s in the word.

Distance between two binary words : The number of positions where the words differ.

Bose-Chaudhuri-Hocquenghem codes (BCH codes)

Reed-Salomon codes (RS codes)

First we will give an example to understand the basic mechanism of the RS codes and afterwards we will elaborate further on the intuition behind them.

We need a vector space. We will use Galois Fields because they are very convinient to work with in binary arithmetic.

In our example

The Original approach

The Generator Polynomial approach

The Galois Field Fourier Transform (GFFT) apporach

QR Codes

The end of data in the symbol is signalled by the Terminator sequence 0000, appended to the data bit stream following the final mode segment. This may be omitted if the data bit stream completely fills the capacity of the symbol, or abbreviated if the remaining capacity of the symbol is less than 4 bits.

The bit streams corresponding to each mode segment shall be connected in order. The Terminator shall be appended to the complete bit stream, unless the data b5it stream completely fills the capacity of the symbol. The resulting message bit stream shall then be divided into codewords. All codewords are 8 bits in length. If the bit stream length is such that the final codeword is not exactly 8 bits in length, it shall be made 8 bits long by the addition of padding bits with binary value 0.

Padding bits shall be added after the final bit (least significant bit) of the data stream. The message bit stream shall then be extended to fill the data capacity of the symbol corresponding to the Version and Error Correction Level, as defined in Tables 7 to 11, by the addition of the Pad Codewords 11101100 and 00010001 alternately.

The resulting series of codewords, the data codeword sequence, is then processed as described in 8.5 to add error correction codewords to the message. In certain versions of symbol, it may be necessary to add 3, 4 or 7 Remainder Bits (all zeros) to the end of the message in order exactly to fill the symbol capacity (see Table 1).

Let me remind you our goal. It is to manually create a QR code for the URL : “https://cypher-punks.gitlab.io ”. It has 30 alphabetical characters legth.

We view a QR code as a matrix where each cell is called a module. Each module position is defined by its row and column coordinates (i,j) where i designates the row (counting from the top downwords) and j designates the column (counting from left to right) such that module (0,0) is located in at the upper left corner.

QR code scheme as you probably have noticed has many variants. The specification we are following has divides it into two vartiants :

  1. QR Code with full range of capabilities including error detection and detection and maximum data capacity. Its’ size ranges from 21x21 modules to 177x177 modules.
  2. Micro QR Code with reduced overhead but some restrictions on data capacity but with none capabilities when it comes to error correction, it only supports error detection. Its’ size ranges from 11x11 modules to 17x17 modules.

In this article, we will not further refer to Micro QR Code or any of its attributes. The reader can refer to the ISO IEC 18004 2015 for further reading.

Mode indicator: 4-bit identifier indicating in which mode the following data sequence is encoded

Encode prodecure overview

  1. Data analysis
    1. Select the smallest QR code version that will accomondate the data.
    2. Select required Error Detection and Correction Level.
    3. Select symbol version.
  2. Data encoding
    1. Convert data characters into a bit stream in accordance with the rules for the mode in force.
    2. Add a terminator at the end of the data sequence.
    3. Split the resulting bit stream in 8-bit codewords.
    4. Add Pad Characters as necessary to fill teh number of data codewords required by the version you have chose.
  3. Error correction coding
    1. Divide the codeword sequence into the required number of blocks to enable the error correction algotihms to be processed. Generate the error correction codewords for each block and append the error correction codewords to the end of the data codeword sequence.
  4. Structure final message Interleave the data and error correction codewords from each block as described and add remainder bits as necessary.
  5. Module placement Place the codeword modules in the matrix along with the finder, timing allignment patterns and separators.
  6. Data masking There are eight mask patterns that you can use to change the outputted matrix. Each mask pattern changes the bits according to their coordinates in the QR matrix. The purpose of a mask pattern is to make the QR code easier for a QR scanner to read.
  7. Format and version information Generate the corresponding format and version information and append them to the symbol.

Data analysis

After consulting, Table 7 and Table 2 of the ISO. We decided that we will use QR 2-L, which is a 57x57 modules matrix which allows 7% recovery of the symbol codewords.

Data encoding

The specification makes available plenty of data encoding techniques. More specifically the following :

  1. Numeric mode for encoding decimal digits (0-9), with coding density 10-bits/3-characters
  2. Alphanumeric mode for encoding only the 26 capital characters of the English alphabet (A-Z) as well ass the symbols (SP, $, %, *, +, -, ., /, :) with code density 11-bits/2-characters
  3. Byte mode, where the 8-bit representation of each character as specified in ISO/IEC 8859 can be used, of course with code density 8-bits/1-character.
  4. Kanji mode, which encodes Kanji characters in acordance with the Shift JIS system based on JIS X 0208. Each two-byte character is compacted to a 13-bit binary word, which results to 1-characters/13-bits code density.
  5. Extened Channel Interpretation (ECI) mode. ECI could by a whole article on its own. It is a transparent protocol used on barcodes to transfer additional interpretation information about the inteded interpretation of the message contained within the barcode. It’s used majorly for adding implicit information about barcode messages that are in various usually unsupported character sets such as Japanese or Arabic.
  6. Structured Append mode, which is used to aid the process of splitting a big data stream into more than one smaller QR codes so the original data stream can be reconstructed from them. You can think of a shipping package that doesn’t have space to fit a big square QR code but has plenty of vertical or horizontal rectangle space that fit more that one smallers squares QR codes.
  7. FNC1 mode

All the above modes can be used in combination in a single QR Code matrix, of course with the appropriate formatting.

For our purpose we will use Byte mode. So we will focus on this one.

Byte encoding

According to ISO, for a given byte sequence the length $B$ of the bit stream is calculated from this formula:

$$ B = M + C + 8D $$

where:

B = number the of bits in the bit stream M = number of bits in mode indicator We use Byte mode with QR version 2-L which has 0100 as mode indicator = 4 C = number of bits in character count indicator. We use QR vesion 2-L which has 16 bits of character count indicator = 16 D = number of input data characters. Our string has 30 characters length = 30

So we have B = 4 + 16 + 30*8 = 260 bits of data stream

For each QR Error Correction level and Version the generator polynomial is the product of the fist degree polynomials $(x-α^0), (x-α^1), \dots, (x-2^{α-1})$, where $α=2$, which is the primitive element of $GF(2^8)$ and $n$ is the Error Correction Codewords per Block. For 2-L, $n=7$, so the generator polynomial is $\Pi_{i=0}^{10} x-2^i = $.

Error correction coding

p is the number of misdecode protection codewords, e is the number of erasures d is the number of erro correction codewords, and t is the number of errors.

$e +2t \le d - p$

We split the data codewords into groups, for 2-L we only need one group.

The error correction codewords can correct two types of erroneous codewords:

  1. Erasues, erroneous codewords at known locations, for example an unscanned or undecodable symbol character.
  2. Errors, erroneous codewords at unknown locations, for example a misdecoded symbol character.

Depending on the Version and Error Correction Level, the data codeword sequence shall be subdivided into one or more blocks, to each of which the error correction algorithm shall be applied separately.

The choice of QR version 2-L we have made

Structure final message

Before continue, we have to check that the total number of codewords in the message are equal to the total number of codewords that are capable of being represented in the symbol. For 2-L the total number of codewords is 44, 34 data codewords and 10 error correction codewords.

Then we follow these steps:

  1. We divide the data codeword sequence into n blocks, where $n=$
  3. Assemble the final sequence by taking data and error correction codewords from each block in turn, e.g. data block 1; codeword 1, …, etc.

Our sample message starts with 0100 (hex 4), indicating that there are 8 bits per character. The next 8 bits (hex 0d) are the length field, 13 in decimal notation. The bits after that can be rearranged in bytes representing the actual characters of the messageː 27 54 77 61 73 20 62 72 69 6c 6c 69 67, and additionally 0e c. The first two, hex 27 and 54 are the ASCII codes for apostrophe and T. The whole message is “‘Twas billig” (from w:Jabberwocky#Lexicon).

After the last of the data bits is another 4-bit mode indicator. It can be different from the first one, allowing different encodings to be mixed within the same QR symbol. When there is no more data to store, the special end-of-message code 0000 is given. (Note that the standard allows the end-of-message code to be omitted if it wouldn’t fit in the available number of data bytes.)

Module placement


Data masking

The purpose of data masking is making it easier the reading of the code. Take for example the case of 8 white sequential modules of the same colour, this could confuse the reader and read them as 7 or 9 sequential same colour modules. We want to make reading as fast and as accurate as possible even with the cheapest hardware.

There are Each mask pattern uses a formula to determine whether or not to change the color of the current bit. You put the coordinates of the current bit into the formula, and if the result is 0, you use the opposite bit at that coordinate. For example, if the bit for coordinate (0,3) is 1, and the formula is equal to 0 for that coordinate, then you put a 0 at (0,3) instead of a 1.

Mask patterns must ONLY be applied to data modules and error correction modules. In other words, we don’t mask function patterns (finder patterns, timing patterns, separators, alignment patterns) and reserved areas (format information area, version information area), we only mask data and error correction modules.

Format and version information

We are done with the maths! Let’s write the code!

Designing a QR code

Extra : Relationship of RS codes to Shamir Secret Sharing

Bibliography

[1] Charles C. Pinter, A Book of Abstract Algebra, Second Edition

[2] ISO/IEc 18004, Third Edition, Information technology - Automatic identification and data capture techniques - QR code barcode symbology specification

[3] James Westall, James Martin, An Introduction to Galois Fields and Reed-Solomon Coding

[4] Robert J. McEliece, Finite Fields for Computer Scientists and Engineers

RFID Tags & Security Issues