4

Information Security System
(CSPC-306)
Mathematics of Cryptography
Algebraic Structures
Dr Samayveer Singh
Assistant Professor
Department of Computer Science & Engineering
National Institute Technology Jalandhar, Punjab, India
[email protected]
Copyright © 2015 by McGraw Hill Education (India) Private Limited. All rights reserved.
4-1 ALGEBRAIC STRUCTURES
Cryptography requires sets of integers and specific

operations that are defined for those sets.
The combination of the set and the operations that are

applied to the elements of the set is called an algebraic
structure.
Here, we will define three common algebraic

structures: groups, rings, and fields.
4.1 Continued
Figure 4.1 Common algebraic structure
4.1.1 Groups
A group (G) is a set of elements with a binary

operation (•) that satisfies four properties (or
axioms).
A commutative group satisfies an extra property,
commutativity:
❏ Closure:
❏ Associativity:
❏ Commutativity:
❏ Existence of identity:
❏ Existence of inverse:
4.1.1 Continued
Figure 4.2 Group
4.1.1 Groups
A commutative group, also called an abelian group, is a group in which the operator satisfies
the four properties for groups plus an extra property, commutativity.
4.1.1 Continued
A group involves a single operation, the properties
imposed on the operation allow the use of a pair of
operations as long as they are inverses of each other.
Example 4.1
The set of residue integers with the addition operator,

G = < Zn , +>,
is a commutative group. We can perform addition and
subtraction on the elements of this set without moving out of
the set. We can perform multiplication and division on the
elements of this set without moving out of the set. It is easy to
check the first three properties. The identity element is 1.
Each element has an inverse that can be found according to
the extended Euclidean algorithm.
4.1.1 Continued
Example 4.2
The set Zn* with the multiplication operator, G = <Zn*, ×>, is

also an abelian group.
Example 4.3
Let us define a set G = < {a, b, c, d}, •> and the operation as
shown in Table 4.1.
4.1.1 Continued
Example 4.4
A very interesting group is the permutation group. The set is
the set of all permutations, and the operation is composition:
applying one permutation after another.
Figure 4.3 Composition of permutation
4.1.1 Continued
Example 4.4 Continued
Table 4.2 Operation table for permutation group
4.1.1 Continued
Example 4.5
In the previous example, we showed that a set of

permutations with the composition operation is a group.
This implies that using two permutations one after another

cannot strengthen the security of a cipher, because we can
always find a permutation that can do the same job
because of the closure property.
4.1.1 Continued
 Finite Group
A group is called a finite group if the set has a finite number of
elements; otherwise, it is an infinite group.
 Order of a Group
The order of a group, |G|, is the number of elements in the
group. If the group is not finite, its order is infinite; if the group
is finite, the order is finite.
 Subgroups
A subset H of a group G is a subgroup of G if H itself is a group
with respect to the operation on G.
In other words, if G = <S, •> is a group, H = <T, • > is a group
under the same operation, and T is a nonempty subset of S,
then H is a subgroup of G.
4.1.1 Continued
Example 4.6
Is the group H = <Z10, +> a subgroup of the group G =

<Z12, +>?
Solution
The answer is no. Although H is a subset of G, the
operations defined for these two groups are different. The
operation in H is addition modulo 10; the operation in G
is addition modulo 12.
4.1.1 Continued
Cyclic Subgroups
If a subgroup of a group can be generated using

the power of an element, the subgroup is called
the cyclic subgroup.
4.1.1 Continued
Example 4.7
Four cyclic subgroups can be made from the group G = <Z6,
+>. They are H1 = <{0}, +>, H2 = <{0, 2, 4}, +>, H3 = <{0, 3},
+>, and H4 = G.
4.1.1 Continued
Example 4.8
Three cyclic subgroups can be made from the group

G = <Z10∗, ×>. G has only four elements: 1, 3, 7, and 9. The
cyclic subgroups are H1 = <{1}, ×>, H2 = <{1, 9}, ×>, and H3
= G.
4.1.1 Continued
Cyclic Groups
A cyclic group is a group that is its own cyclic
subgroup.
4.1.1 Continued
Example 4.9
Three cyclic subgroups can be made from the group

G = <Z10∗, ×>. G has only four elements: 1, 3, 7, and 9. The
cyclic subgroups are H1 = <{1}, ×>, H2 = <{1, 9}, ×>, and H3
= G.
a. The group G = <Z6, +> is a cyclic group with two

generators, g = 1 and g = 5.
b. The group G = <Z10∗, ×> is a cyclic group with two

generators, g = 3 and g = 7.
4.1.1 Continued
Lagrange’s Theorem
Assume that G is a group, and H is a subgroup of G. If

the order of G and H are |G| and |H|, respectively, then,
based on this theorem, |H| divides |G|.
Order of an Element
The order of an element a in a group, ord(a), is the
smallest integer n such that an = e. The order of an
element is the order of the cyclic group it generates.
4.1.1 Continued
Example 4.10
a. In the group G = <Z6, +>, the orders of the elements are:

ord(0) = 1, ord(1) = 6, ord(2) = 3, ord(3) = 2, ord(4) = 3,
ord(5) = 6.
b. In the group G = <Z10*, ×>, the orders of the elements are:

ord(1) = 1, ord(3) = 4, ord(7) = 4, ord(9) = 2.
4.1.2 Ring
A ring, R = <{…}, •, >, is an algebraic structure

with two operations.
Figure 4.4 Ring
4.1.2 Continued
Example 4.11
The set Z with two operations, addition and multiplication,

is a commutative ring. We show it by R = <Z, +, ×>.
Addition satisfies all of the five properties; multiplication
satisfies only three properties.
4.1.3 Field
A field, denoted by F = <{…}, •, > is a
commutative ring in which the second operation
satisfies all five properties defined for the first
operation except that the identity of the first
operation has no inverse.
Figure 4.5 Field

4.1.3 Continued
Finite Fields
Galois showed that for a field to be finite, the
number of elements should be pn, where p is a
prime and n is a positive integer.
Note
A Galois field, GF(pn), is a finite field

with pn elements.
4.1.3 Continued
GF(p) Fields
When n = 1, we have GF(p) field. This field can

be the set Zp, {0, 1, …, p − 1}, with two arithmetic
operations.
4.1.2 Continued
Example 4.12
A very common field in this category is GF(2) with the set

{0, 1} and two operations, addition and multiplication, as
shown in Figure 4.6.
Figure 4.6 GF(2) field
4.1.2 Continued
Example 4.13
We can define GF(5) on the set Z5 (5 is a prime) with
addition and multiplication operators as shown in Figure
4.7.
Figure 4.7 GF(5) field
4.1.3 Continued
Summary
Table 4.3
4-2 GF(2n) FIELDS
In cryptography, we often need to use four operations

(addition, subtraction, multiplication, and division). In
other words, we need to use fields. We can work in
GF(2n) and uses a set of 2n elements. The elements in
this set are n-bit words.
4.2.1 Polynomials
4.2.2 Using A Generator
4.2.3 Summary
4.2 Continued
Example 4.14
Let us define a GF(22) field in which the set has four 2-bit
words: {00, 01, 10, 11}. We can redefine addition and
multiplication for this field in such a way that all properties
of these operations are satisfied, as shown in Figure 4.8.
Figure 4.8 An example of GF(22) field
4.2.1 Polynomials
A polynomial of degree n − 1 is an expression

of the form
where xi is called the ith term and ai is called

coefficient of the ith term.
4.2.1 Continued
Example 4.15
Figure 4.9 show how we can represent the 8-bit word

(10011001) using a polynomials.
Figure 4.9 Representation of an 8-bit word by a polynomial
4.2.1 Continued
Example 4.16
To find the 8-bit word related to the polynomial x5 + x2 + x,

we first supply the omitted terms. Since n = 8, it means the
polynomial is of degree 7. The expanded polynomial is
This is related to the 8-bit word 00100110.
4.2.1 Continued
GF(2n) Fields
Note
Polynomials representing n-bit words

use two fields: GF(2) and GF(2n).
4.2.1 Continued
Modulus
For the sets of polynomials in GF(2n), a group of
polynomials of degree n is defined as the modulus.
Such polynomials are referred to as irreducible
polynomials.
Table 4.9 List of irreducible polynomials
4.2.1 Continued
Addition
Note
Addition and subtraction operations on

polynomials are the same operation.
4.2.1 Continued
Example 4.17
Let us do (x5 + x2 + x)  (x3 + x2 + 1) in GF(28). We use the

symbol  to show that we mean polynomial addition. The
following shows the procedure:
4.2.1 Continued
Example 4.18
There is also another short cut. Because the addition in

GF(2) means the exclusive-or (XOR) operation. So we can
exclusive-or the two words, bits by bits, to get the result. In
the previous example, x5 + x2 + x is 00100110 and x3 + x2 + 1
is 00001101. The result is 00101011 or in polynomial
notation x5 + x3 + x + 1.
4.2.1 Continued
Multliplication
1. The coefficient multiplication is done in GF(2).
2. The multiplying xi by xj results in xi+j.
3. The multiplication may create terms with degree

more than n − 1, which means the result needs to
be reduced using a modulus polynomial.
4.2.1 Continued
Example 4.19
Find the result of (x5 + x2 + x) ⊗ (x7 + x4 + x3 + x2 + x) in
GF(28) with irreducible polynomial (x8 + x4 + x3 + x + 1).
Note that we use the symbol ⊗ to show the multiplication of
two polynomials.
Solution
To find the final result, divide the polynomial of degree 12 by

the polynomial of degree 8 (the modulus) and keep only the
remainder. Figure 4.10 shows the process of division.
4.2.1 Continued
Figure 4.10 Polynomial division with coefficients in GF(2)
4.2.1 Continued
Example 4.20
In GF (24), find the inverse of (x2 + 1) modulo (x4 + x + 1).
Solution
The answer is (x3 + x + 1) as shown in Table 4.5.
Table 4.5 Euclidean algorithm for Exercise 4.20
4.2.1 Continued
Example 4.21
In GF(28), find the inverse of (x5) modulo (x8 + x4 + x3 + x + 1).
Solution
The answer is (x5 + x4 + x3 + x) as shown in Table 4.6.
Table 4.6 Euclidean algorithm for Exercise 4.21
4.2.1 Continued
Multliplication Using Computer
The computer implementation uses a better

algorithm, repeatedly multiplying a reduced
polynomial by x.
4.2.1 Continued
Example 4.22
Find the result of multiplying P1 = (x5 + x2 + x) by P2 = (x7 +
x4 + x3 + x2 + x) in GF(28) with irreducible polynomial (x8 +
x4 + x3 + x + 1) using the algorithm described above.
Solution
The process is shown in Table 4.7. We first find the partial

result of multiplying x0, x1, x2, x3, x4, and x5 by P2. Note that
although only three terms are needed, the product of xm ⊗
P2 for m from 0 to 5 because each calculation depends on the
previous result.
4.2.1 Continued
Table 4.7 An efficient algorithm
4.2.1 Continued
Example 4.23
Repeat Example 4.22 using bit patterns of size 8.
Solution
We have P1 = 000100110, P2 = 10011110, modulus =
100011010 (nine bits). We show the exclusive or operation
by .
Table 4.8 An efficient algorithm for multiplication using n-bit words
4.2.1 Continued
Example 4.24
The GF(23) field has 8 elements. We use the irreducible

polynomial (x3 + x2 + 1) and show the addition and
multiplication tables for this field. We show both 3-bit
words and the polynomials. Note that there are two
irreducible polynomials for degree 3. The other one, (x3 + x
+ 1), yields a totally different table for multiplication.
4.2.1 Continued
Table 4.9 Addition table for GF(23)
4.2.1 Continued
Table 4.10 Multiplication table for GF(23)
4.2.2 Using a Generator
Sometimes it is easier to define the elements of the

GF(2n) field using a generator.
4.2.1 Continued
Example 4.25
Generate the elements of the field GF(24) using the irreducible
polynomial ƒ(x) = x4 + x + 1.
Solution
The elements 0, g0, g1, g2, and g3 can be easily generated, because
they are the 4-bit representations of 0, 1, x2, and x3. Elements g4
through g14, which represent x4 though x14 need to be divided by
the irreducible polynomial. To avoid the polynomial division, the
relation ƒ(g) = g4 + g + 1 = 0 can be used (See next slide).
4.2.1 Continued
4.2.1 Continued
Example 4.26
The following show the results of addition and subtraction

operations:
4.2.1 Continued
Example 4.27
The following show the result of multiplication and division
operations:.
4.2.3 Summary
The finite field GF(2n) can be used to define four

operations of addition, subtraction, multiplication and
division over n-bit words. The only restriction is that
division by zero is not defined.

4

Uploaded by

Copyright:

Available Formats

4

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

4

Uploaded by

Copyright:

Available Formats

Information Security System

Cryptography requires sets of integers and specific

The combination of the set and the operations that are

Here, we will define three common algebraic

Figure 4.1 Common algebraic structure

A group (G) is a set of elements with a binary

Figure 4.2 Group

The set of residue integers with the addition operator,

The set Zn* with the multiplication operator, G = <Zn*, ×>, is

Figure 4.3 Composition of permutation

Example 4.4 Continued

Table 4.2 Operation table for permutation group

In the previous example, we showed that a set of

This implies that using two permutations one after another

Is the group H = <Z10, +> a subgroup of the group G =

If a subgroup of a group can be generated using

Three cyclic subgroups can be made from the group

Three cyclic subgroups can be made from the group

a. The group G = <Z6, +> is a cyclic group with two

b. The group G = <Z10∗, ×> is a cyclic group with two

Assume that G is a group, and H is a subgroup of G. If

a. In the group G = <Z6, +>, the orders of the elements are:

b. In the group G = <Z10*, ×>, the orders of the elements are:

A ring, R = <{…}, •, >, is an algebraic structure

Figure 4.4 Ring

The set Z with two operations, addition and multiplication,

Figure 4.5 Field

A Galois field, GF(pn), is a finite field

When n = 1, we have GF(p) field. This field can

A very common field in this category is GF(2) with the set

Figure 4.6 GF(2) field

Figure 4.7 GF(5) field

In cryptography, we often need to use four operations

Figure 4.8 An example of GF(22) field

A polynomial of degree n − 1 is an expression

where xi is called the ith term and ai is called

Figure 4.9 show how we can represent the 8-bit word

Figure 4.9 Representation of an 8-bit word by a polynomial

To find the 8-bit word related to the polynomial x5 + x2 + x,

This is related to the 8-bit word 00100110.

Polynomials representing n-bit words

Addition and subtraction operations on

Let us do (x5 + x2 + x)  (x3 + x2 + 1) in GF(28). We use the

There is also another short cut. Because the addition in

1. The coefficient multiplication is done in GF(2).

2. The multiplying xi by xj results in xi+j.

3. The multiplication may create terms with degree

To find the final result, divide the polynomial of degree 12 by

Figure 4.10 Polynomial division with coefficients in GF(2)

The answer is (x3 + x + 1) as shown in Table 4.5.

Table 4.5 Euclidean algorithm for Exercise 4.20

In GF(28), find the inverse of (x5) modulo (x8 + x4 + x3 + x + 1).

The answer is (x5 + x4 + x3 + x) as shown in Table 4.6.

Table 4.6 Euclidean algorithm for Exercise 4.21

Multliplication Using Computer

The computer implementation uses a better

The process is shown in Table 4.7. We first find the partial

Example 4.22 Continued

Table 4.7 An efficient algorithm

The GF(23) field has 8 elements. We use the irreducible