Cryptograph
y and
Network
Security
Seventh Edition, Global Edition
by William Stallings
© 2017 Pearson Education, Ltd., All rights reserved.
Chapter 5
Finite Fields
© 2017 Pearson Education, Ltd., All rights reserved.
© 2017 Pearson Education, Ltd., All rights reserved.
Groups
• A set of elements with a binary operation denoted by that
associates to each ordered pair (a,b) of elements in G an
element (a b ) in G , such that the following axioms are
obeyed:
• (A1) Closure:
• If a and b belong to G, then a b is also in G
• (A2) Associative:
• a (b c) = (a b) c for all a, b, c in G
• (A3) Identity element:
• There is an element e in G such that a e = e a = a for all a in G
• (A4) Inverse element:
• For each a in G, there is an element a1 in G such that aa1 = a1 a =
e
• (A5) Commutative:
• a b = b a for all a, b in G
© 2017 Pearson Education, Ltd., All rights reserved.
Cyclic Group
• Exponentiation is defined within a group as a
repeated application of the group operator, so that
a3 = aaa
• We define a0 = e as the identity element, and
a-n = (a’)n , where a’ is the inverse element of a
within the group
• A group G is cyclic if every element of G is a power
ak (k is an integer) of a fixed element a € G
• The element a is said to generate the group G or to
be a generator of G
• A cyclic group is always abelian and may be finite or
infinite
© 2017 Pearson Education, Ltd., All rights reserved.
Rings
• A ring R , sometimes denoted by {R , + , * }, is a set of elements with two
binary operations, called addition and multiplication, such that for all a , b , c in
R the following axioms are obeyed:
(A1–A5)
R is an abelian group with respect to addition; that is, R satisfies axioms A1
through A5. For the case of an additive group, we denote the identity element as
0 and the inverse of a as –a
(M1) Closure under multiplication:
If a and b belong to R , then ab is also in R
(M2) Associativity of multiplication:
a (bc ) = (ab)c for all a , b , c in R
(M3) Distributive laws:
a (b + c ) = ab + ac for all a , b , c in R
(a + b )c = ac + bc for all a , b , c in R
• In essence, a ring is a set in which we can do addition, subtraction [a - b = a +
© 2017 Pearson Education, Ltd., All rights reserved.
(-b )], and multiplication without leaving the set
Rings (cont.)
• A ring is said to be commutative if it satisfies the
following additional condition:
(M4) Commutativity of multiplication:
ab = ba for all a, b in R
• An integral domain is a commutative ring that
obeys the following axioms.
(M5) Multiplicative identity:
There is an element 1 in R such that a1 = 1a =
a for all a in R
(M6) No zero divisors:
If a , b in R and ab = 0, then either a = 0 or b
= 0
© 2017 Pearson Education, Ltd., All rights reserved.
Fields
• A field F , sometimes denoted by {F, +,* }, is a set of elements
with two binary operations, called addition and multiplication, such
that for all a, b, c in F the following axioms are obeyed:
(A1–M6)
F is an integral domain; that is, F satisfies axioms A1 through A5 and M1
through M6
(M7) Multiplicative inverse:
For each a in F, except 0, there is an element a-1 in F such that aa-1 = (a-1 )a
= 1
• In essence, a field is a set in which we can do addition, subtraction,
multiplication, and division without leaving the set. Division is
defined with the
Familiar following
examples rule:
of fields are a /brational
the = a (b-1numbers,
) the real
numbers, and the complex numbers. Note that the set of all
integers is not a field, because not every element of the set has a
multiplicative inverse.
© 2017 Pearson Education, Ltd., All rights reserved.
© 2017 Pearson Education, Ltd., All rights reserved.
© 2017 Pearson Education, Ltd., All rights reserved.
Finite Fields of the Form
GF(p)
• Finite fields play a crucial role in many
cryptographic algorithms
• It can be shown that the order of a
finite field must be a power of a prime
pn, where n is a positive integer
• The finite field of order pn is generally
written GF(pn )
• GF stands for Galois field, in honor of
the mathematician who first studied
finite fields
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.1(a)
(a) Addition modulo 8
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.1(b)
(b) Multiplication modulo 8
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.1(c)
(c) Additive and multiplicative
inverses modulo 8
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.1(d)
(d) Addition modulo 7
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.1(e)
(e) Multiplication modulo 7
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.1(f)
(f) Additive and multiplicative
inverses modulo 7
© 2017 Pearson Education, Ltd., All rights reserved.
have shown • 1. GF(p) consists of p
how to elements
construct a • 2. The binary operations +
and * are defined over the
finite field of set. The operations of
order p, where addition, subtraction,
multiplication, and division
p is prime. can be performed without
leaving the set. Each
element of the set other
than 0 has a multiplicative
GF(p) is inverse
defined with • We have shown that the
the following elements of GF(p) are the
integers {0, 1, . . . , p – 1}
properties: and that the arithmetic
operations are addition
and multiplication mod p
© 2017 Pearson Education, Ltd., All rights reserved.
© 2017 Pearson Education, Ltd., All rights reserved.
© 2017 Pearson Education, Ltd., All rights reserved.
Polynomial Arithmetic
With Coefficients in Zp
• If each distinct polynomial is considered to be an
element of the set, then that set is a ring
• When polynomial arithmetic is performed on
polynomials over a field, then division is possible
• Note: this does not mean that exact division is
possible
• If we attempt to perform polynomial division over a
coefficient set that is not a field, we find that
division is not always defined
• Even if the coefficient set is a field, polynomial division
is not necessarily exact
• With the understanding that remainders are allowed,
we can say that polynomial division is possible if the
coefficient set is a field
© 2017 Pearson Education, Ltd., All rights reserved.
Polynomial Division
• We can write any polynomial in the form:
f(x) = q(x) g(x) + r(x)
• r(x) can be interpreted as being a remainder
• So r(x) = f(x) mod g(x)
• If there is no remainder we can say g(x) divides f(x)
• Written as g(x) | f(x)
• We can say that g(x) is a factor of f(x)
• Or g(x) is a divisor of f(x)
• A polynomial f(x) over a field F is called irreducible if
and only if f(x) cannot be expressed as a product of two
polynomials, both over F, and both of degree lower than
that of f(x)
• An irreducible polynomial is also called a prime
polynomial
© 2017 Pearson Education, Ltd., All rights reserved.
Example of
Polynomial
Arithmetic
Over GF(2)
(Figure 5.6 can be found on
page 137 in the textbook)
© 2017 Pearson Education, Ltd., All rights reserved.
Polynomial GCD
• The polynomial c(x) is said to be the greatest
common divisor of a(x) and b(x) if the following are
true:
• c(x) divides both a(x) and b(x)
• Any divisor of a(x) and b(x) is a divisor of c(x)
• An equivalent definition is:
• gcd[a(x), b(x)] is the polynomial of maximum degree
that divides both a(x) and b(x)
• The Euclidean algorithm can be extended to find
the greatest common divisor of two polynomials
whose coefficients are elements of a field
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.2(a)
Arithmetic in GF(2 )
3
(a) Addition
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.2(b)
Arithmetic in GF(2 )
3
(b) Multiplication
© 2017 Pearson Education, Ltd., All rights reserved.
Table
5.2(c)
Arithmetic
in GF(23)
(c) Additive and multiplicative inverses
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.3 (page 144 in
textbook)
Polynomial Arithmetic Modulo (x3 + x + 1)
(a) Addition
(b) Multiplication
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.4
Extended Euclid [(x8 + x4 + x3 + x + 1), (x7 + x + 1)]
(Table 5.4 can be found on page 146 in textbook)
© 2017 Pearson Education, Ltd., All rights reserved.
Computational
Considerations
• Since coefficients are 0 or 1, they can
represent any such polynomial as a bit
string
• Addition becomes XOR of these bit
strings
• Multiplication is shift and XOR
• cf long-hand multiplication
• Modulo reduction is done by
repeatedly substituting highest power
© 2017 Pearson Education, Ltd., All rights reserved.
Using a Generator
• A generator g of a finite field F of order q
(contains q elements) is an element whose
first q-1 powers generate all the nonzero
elements of F
• The elements of F consist of 0, g0, g1, . . . ., gq-2
• Consider a field F defined by a polynomial fx
• An element b contained in F is called a root
of the polynomial if f(b) = 0
• Finally, it can be shown that a root g of an
irreducible polynomial is a generator of the
finite field defined on that polynomial
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.5
Generator for GF(23) using x3 +
x+1
© 2017 Pearson Education, Ltd., All rights reserved.
Table 5.6 (page 150 in
textbook)
GF(23) Arithmetic Using Generator for the
Polynomial (x3 + x + 1)
(a) Addition
(b) Multiplication
© 2017 Pearson Education, Ltd., All rights reserved.
Summary
• Groups
• Rings
• Abelian group
• Cyclic group
• fields
• Finite fields of the form
GF(p)
• Finite fields of the
• Finite fields of Order p form GF(2n)
• Finding the multiplicative • Motivation
inverse in GF(p) • Modular
polynomial
• Polynomial arithmetic arithmetic
• Ordinary polynomial
• Finding the
arithmetic
multiplicative
• Polynomial arithmetic
inverse
with coefficients in Zp
• Computational
• Finding the greatest
common divisor considerations
© 2017 Pearson Education, Ltd., All rights reserved.
• Using a generator