Transcript Advanced Internet Technologies

"There are those who are destined to be good, but
never to experience it. I believe I am one of them."
--- Evariste Galois (1811-1832)
1
Mathematical Background: A Revision

finite fields (FF)
required for understanding



AES
Elliptic Curve Cryptography
To study FF, we shall revise the concepts of



groups, rings, fields from abstract algebra
Modular arithmetic and Euclidean Algorithm
Finite fields of the form GF(p), where p is a prime
number
2
Group Theory: History




Groups: First used by Evariste Galois
(b.1811- d.1832) in his work, without defining
a Group
Galois, a student of M. Vernier in 1827 and
a contemporary of Cauchy, Poisson, Abel,
Jacobi, Fourier, Gauss and Napolean (ruled
during 1800-1815)
He failed to join Ecole Polytechnique, though
he appeared twice in the entrance tests.
An ardent Republican, he was sent to prison
twice by the King.
3
Quest for Academy Award



1829: Galois (only 18 years old) submitted
two papers to Académie des Sciences for
publication in its ‘Memoirs’; Cauchy was the
referee for the papers.
Galois read a posthumous paper of Abel and
found that there was an overlap between his
and Abel’s work. So he consulted Cauchy.
Cauchy (winner of Grand prix in 1816)
advised him to rewrite it and submit it for
Grand Prix.
Feb 1830: Galois submitted the modified
paper to Fourier for Grand Prix; Fourier died
in April 1830 and the paper was lost; Abel
and Jacobi got the Grand Prix prize.
4
Last Night



1831: Galois again submitted to Académie
des Sciences; Poisson was the Reviewer. He
did not understand the paper and rejected it.
night of 30 May 1832: injured at the duel
with Perscheux d'Herbinville over the prison’s
physician’s daughter named Stephanie-Felice
du Motel: abandoned by both Perscheux as
well as his seconds. A peasant took him to a
hospital, where he died at the age of 21 in
1832.
A story?: an injured Galois wrote notes on the
rejected paper; a night of furious writings by
Galois
5
First definitions





Liouville, Galois’s elder brother, copied his
papers and sent them to Gauss, Jacobi and
others
14 years later”
1846: Liouville got Galois' papers published
1845: Cauchy defined a "conjugate system of
substitutions“, another name of Groups.
During 1845-46, he wrote 25 papers on it.
1854: The first person to try to give (not
completely correct) an abstract definition of a
group: Cayley.
1863: Jordan’s commentary on Galois paper
and his book used the term GROUP
6
Group Theory
the first modern book

Walter Ledermann's book Introduction
to the theory of finite groups, published
by publisher Oliver & Boyd in Edinburgh
1949 (when Ledermann was 38 years
old, assistant lecturer at St Andrews )

was based on Schur's lectures on
group theory.
7
Group Theory and communism


Ledermann wrote it in the British Museum
Library (sitting in the same chair where Karl
Marx wrote Das Capital)
Ledermann came for a lecture on Group
Theory at University of Notre Dame in the
United States; the parcel of books was
stopped by US Customs, who mistook it as a
book of Communist groups, till the Head of
Dept of Notre Dame personally spoke to
Customs.
8
A note on types of numbers


Positive integers and Integers
Rational numbers: “A rational number is any number
that can be written as a ratio of two integers.”
Reference: [1]
http://bing.search.sympatico.ca/?q=difference%20between%20a%20real%20number
%20and%20a%20rational%20number&mkt=en-ca&setLang=en-CA


Examples: Integers, fractions, mixed numbers, and decimals;
together with their negative images.
Examples of irrational numbers: √2, √3, √5, pi (π), e
π = a mathematical constant whose value is the ratio of any circle 's circumference to
its diameter =3.14159265358979323846264338327950288419716939937510
e = base of the natural logarithm; known as Napier's constant; symbol honors Euler
= 2.718281828459045235360287471352662497757………….
= is the unique number with the property that the area of the region bounded by
the hyperbola y = 1/x, the x-axis, and the vertical lines x = 1 and x = e is 1. In
other words
e
1∫ (dx/x) = ln e = 1.
9
A note on types of numbers………………..2

Real numbers:






Any number that can be found on the number
line;
a number required to label any point on the
number line;
a number whose absolute value names the
distance of any point from 0.
both rational and irrational numbers;
Between any two rational numbers on the number
line there is an irrational number. [1]
Between any two irrational numbers there is a
rational number [1]
10
A note on types of numbers………………..3

Complex numbers: Example: x + i y ,
where



x and y: real numbers and
i = √(-1) .
The field of complex numbers includes the
field of real numbers as a subfield.
References: (i) http://www.themathpage.com/aPreCalc/rational-irrationalnumbers.htm
(ii) http://mathworld.wolfram.com/ComplexNumber.html
11
Group
DEFINITION:
 a set of elements or “numbers”
 with some operation whose result is also in the set
(closure)
(The operation is shown through the symbol “.” in the
examples below.)
 obeys:



associative law: (a.b).c = a.(b.c)
has an identity element e so that for all
a Є G, e.a = a.e = a
For each a Є G, there exists an inverse element a-1 Є
G,such that a.a-1 = e
12
Example of a group
Example 1: N = a set of n distinct symbols
= {1,2,…..,n}
S = set of all permutations of the n symbols
S is a Group, under the operation of permutation.
Prove

Closure

Association

Existence of an identity element as a member of the group

Existence of an inverse for every member of the Group
A Finite Group: if the number of members of the group
is finite.
An Infinite Group
13
Abelian Group
If in addition to the three properties stated in
slide 2, the property of commutation is
satisfied, G is said to be an abelian group.
Commutative: if for all a,b Є G,
a.b = b.a
Examples: 2. Prove that S, as defined in
Example 1, is not an Abelian group.
3. Prove that the set of integers (positive,
negative and zero) is an Abelian group under
addition. Hint: Identity element = 0, Inverse
element of X is –X.
14
Some Definitions and
the definition of a Cyclic Group




Exponentiation: defined as repeated application of an
operator.
 example:
a3 = a.a.a
Identity Element :
e=a0
If a’ be the inverse of a, a-n = (a’)n
A Group is cyclic if every member of the
Group is generated by a single element “a”,
(called the Generator) through
exponentiation. “a” is a member of the
Group.
A cyclic group is Abelian.
15
Cyclic Group
(continued)
Cyclic group:





b = ak
For some integer value of k, b should stand for
every member of the Group
A cyclic Group may be finite or infinite.
Subgroups of a cyclic group are also cyclic.
A cyclic group may have more than one
generator element.
Example 4a: A group of integers, under the
operation of addition, is a cyclic group. Both 1
and –1 are the generators.
16
Cyclic Groups of Finite Group Order

A cyclic group of finite group order n is
denoted as Cn with a generator element a
and an identity element e such that e = an.
The operations of such a group may be
defined mod n.
Example 4b: Zn is a finite cyclic group of
integers 0,1,2……(n-1), under the operation
of “addition mod n”, with a generator
element of 1 and an identity element of 0
17
Generator of a Field

GENERATOR: an element whose
successive powers take on every
element of the field except the zero

For Prime number fields: a = gj modp



Not every element of a field is a generator.
For every 0<j<=(p-1), a different element is obtained.
ORDER of a generator element: the smallest
exponent j (< p), that gets the identity
element.
gj mod p = 1
18
Example of a generator and order
Examples1: Modulo 13:
4 and 5 are NOT generator elements.
a = 2 is a generator element.
Its order is 12.
exponent, b
1 2 3 4 5 6
7
8 9 10 11 12
ab mod13
2 4 8 3 6 12 11 9 5 10 7
1
19
Another Example: a generator and order
Examples 2: Modulo 11: 2, 6, 7 and 8 are examples of
generator elements.
Order of 2, 6, 7 and 8: 10.
20
Ring
Consider a set of “numbers” with two binary operations, called
addition and multiplication.


If the set constitutes an Abelian group with addition operation,
and,
if with multiplication operation, the set:
has closure: For a, b Є G, a.b Є G
 is associative: For a, b, c Є G, (a.b).c =
a.(b.c)
 distributive over addition:
a.(b+c) = a.b + a.c
the set constitutes a Ring.
In a Ring, we can do multiplication,
addition and subtraction without leaving
the Ring.
21

Commutative Ring
Ex 5: The set of all square matrices is a
Ring over addition and multiplication.
For a Ring, if multiplication operation is
commutative, the set forms a commutative ring.
Examples :

Ex 6: The set of matrices of Ex 5 is NOT a commutative
Ring.
Ex 7: The set S2 of even integers ( positive, negative
and 0), under the operations of addition and
multiplication, is a Commutative Ring.
22
Integral Domain

A commutative ring R is said to constitute an Integral Domain if,

multiplication operation has an identity:
a.1 = 1.a for all a Є R,
and if,

for a, b Є R, if a.b = 0, then either
a = 0 or b = 0.
Ex 8: S3, the set of integers (positive, negative and 0)
under the operations of addition and multiplication is
an Integral domain.
23
Field
a Field: a set of elements F, with two binary
operations, called addition and multiplication,
such that
 F is an Integral Domain, and,
 For each a Є F, except 0, there is an element
a-1 in F such that
a. a-1 = a-1.a = 1
(Existence of multiplicative inverse)
24
Field
(continued)
Thus in a Field, we can do addition, subtraction,
multiplication and division without leaving the
set.
Ex 9.The set of all integers S3 is not a Field.
10.The following are Fields:



The set of Rational Numbers
The set of real numbers
The set of complex numbers.
All of the above examples of Fields have infinite
number of elements. We shall see that Fields
can be finite also.
25
Group, Ring and Field
[A1] closure under addition:
[A2] Associativity of addition:
[A3] Additive identity:
Group
Abelian Group
Ring
Commutative Ring
Integral domain
Field
[A4] Additive inverse:
[A5] Commutativity of addition:
[M1] closure under multiplication:
[M2] Associativity of multiplication:
[M3] Distributive laws:
[M4] Commutativity of multiplication
[M5] Multiplicative identity:
[M6] No zero divisors:
[M7] Multiplicative inverse: 26
Mathematical properties 1
A1: If a and b belong to S, then a + b is also in S
A2: a + (b+c) = (a+b) + c for all a,b,c in S
A3: There is an element 0 in R such that
a + 0 = 0 + a = a for all a in S
A4: For each a in S there is an element –a in S
such that a + (-a) = (-a) + a = 0
A5: a + b = b + a for all a,b in A
M1: If a and b belong to S, then ab is also in S
M2: a (bc) = (ab) c for all a, b, c in S
27
Mathematical properties 2
M3: a(b+c) = ab + ac for all a, b, c in S
(a+b)c = ac + bc for all a, b, c in S
M4: ab = ba for all a, b in S
M5: There is an element 1 is S such that
a1 = 1a = a for all a in S
M6: If a , b in S and ab = 0, then either
a = 0 or b = 0
M7: If a belongs to S and a  0, there is an
element a-1 in S such that a. a-1 = a-1. a = 1
28
Agenda
After defining Rings and Fields:
 Modular arithmetic
 Divisors, GCD, Euclid’s theorem
 prime numbers
 Fields of type Zp
 Finite Fields, Extended Euclid’s Theorem for
finding multiplicative inverse
Polynomial arithmetic
29
Modular Arithmetic:
Definitions
modulo operator:
a mod n = b
where b is the remainder when a is divided by n;
is called the residue of a mod n.

a = q.n + b
0 <= b < n; q = a/n
where x is the largest integer
less than or equal to x

b
Example 13: a = (b+c)mod 8
In the next slide, b is the element given
in the first column (outside the box).
c is the element given in the top row
(outside the box).
The values of a are given in the box.
30
Modulo 8 Example
31
Congruency mod n
If a mod n = b mod n, a and b
are said to be congruent mod n.
The above statement may be written as,
a=b mod n


reducing k modulo n: The process of
finding the smallest Non-negative
integer, to which k is congruent
32
Modular Arithmetic:
A Revision (continued)

Modular Arithmetic:

a = qn + r.
r
0
1.n
2.n
q.n
a
(q+1).n
r
-q.n
0
a
-(q-1).n
Thus 11 = 1.7 + 4 
-11 = -2.7 + 3 
-3.n
r = 4 = 11 mod 7
r = 3 =-11mod 7
-2.n
-n
33
k mod m
11 mod 7 = 4
 (-11) mod 7 = 3
 In general, If r = k mod m,
( - k) mod m = m - r if r ≠ 0;
But ( - k) mod m = 0 if r = 0.
i.e. k mod m may or may not be equal to
(-k) mod m.
r = k mod m = k mod (-m) = k mod(lml)

34
Reducing k modulo 7:
...
-21 -20 -19 -18 -17 -16 -15
-14 -13 -12 -11 -10 -9 -8
-7 -6 -5 -4 -3 -2 -1
0
1
2
3
4
5
7
14
21
28
...
8
15
22
29
9
16
23
30
10
17
24
31
11
18
25
32
12
19
26
33
6
Example 12
Reduced values
13
20
27
34
All the elements in a column are
congruent mod 7


[O] = {….,-21,-14,-7,0,7,14….}
is called a Residue Class. (Every column constitutes
a Residue Class.)
The Smallest Non-negative integer of the class is
used to represent the class.
35
Modular Arithmetic:
[a mod n + b mod n] mod n =
(a + b)mod n
 [a mod n - b mod n] mod n =
(a - b)mod n
 [a mod n x b mod n] mod n =
(a x b)mod n
Ex 14 of Exponentiation:To evaluate 1211mod 7:
122mod 7 = 4; 128mod 7 = 44mod 7 = 4;
12 x 122 x 128 mod 7= 5 x 4 x 4 mod 7 = 3

36
“Note that the positions of primes constitute just about
the most fundamental, inarguable, nontrivial information
available to our consciousness. This transcends history,
culture, and opinion. It would appear to exist 'outside'
space and time and yet to be accessible to any
consciousness with some sense of repetition, rhythm, or
counting.”
-- Matthew R. Watkins,
School of Mathematical Sciences at Exeter University, UK
http://www.maths.ex.ac.uk/%7Emwatkins/zeta/ss-b.htm, as of
November 3, 2007
37
Modular Arithmetic
Additive and multiplicative inverses
additive inverse: Let c be the inverse of a.
Then a + c = 0 mod n.
Example 15: Additive inverse of 5 mod 8:
5 + c = 0 mod 8. Therefore c = 3
multiplicative inverse: Let c be the
inverse of a.
Then a x c = 1 mod n.
Example 16: Multiplicative inverse of 5 mod 8:
5 x c = 1 mod 8. Therefore c = 5, 13, ….
38
Relatively Prime Numbers



Two integers are said to be relatively prime
if their only common positive integer factor is
1.
In Example 16,
5 and 8 are relatively prime.
Consider the case where ‘a’ and ‘n’ have a
common factor other than 1 (i. e. the case
where ‘a’ and ‘n’ are not relatively prime)
39
Multiplicative Inverse

(continued…)
Example 17: a=6 & n=8

6.c = 1 mod 8
No value of c, that satisfies the above, can
be found .
In general an integer has a multiplicative
inverse in Zn if that integer is relatively
prime to n.
40
Inverses
for modulo 8
a
Additive
Inverse of a
Multiplicative
Inverse of a
0
0
-
1
7
1
2
6
-
3
5
3
4
4
-
5
3
5
6
2
-
7
1
7
41
Multiplicative Inverse:
Table 2
a
6.a mod 8
5.a mod 8
0
0
0
1
6
5
2
4
2
3
2
7
4
0
4
5
6
1
6
4
6
7
2
3
a =5 is the multiplicative inverse of 5
mod 8.
42
Multiplicative Inverse:
Table 2
Continued
a
6.a mod 8
5.a mod 8
8
0
0
9
6
5
10
4
2
11
2
7
12
0
4
13
6
1
14
4
6
15
2
3
a =13 is the multiplicative inverse of 5
mod 8.
43
Multiplicative Inverse
Let c be the Multiplicative Inverse of b mod n.
b.c = 1 mod n = k.n + 1
Therefore
b.(c + n) = (k + b).n + 1
= k1.n + 1
Thus c, c + n, c + 2n……. are all multiplicative
inverses of c. However for a field Zp, with
members as 0,1,2,3…….(p-1), the smallest
positive number would be said to be the
Multiplicative Inverse.

44
Some properties of modulo operator
some peculiarities



if (a+b)≡(a+c) mod n then b≡c mod n
but if (a.b)≡(a.c) mod n then b≡c mod n
only if a is relatively prime to n
Proof:

Given (a+b) = (a+c) mod n

Add -a (the additive inverse of a) to both
sides.
[-a +a+b] = [-a +a+c] mod n
b = c mod n
45
properties of modulo operator: Proof

Proof:

Given (a x b) = (a x c) mod n

Multiply with a-1 (Multiplicative inverse of a)
on both sides:
a-1 (a x b) = [a-1 (a x c)] mod n
b = c mod n


REVISION: However the multiplicative inverse
of ‘a’ exists only if ‘a’ and ‘n‘ are
relatively prime.
a ≡ b mod n if n|(a-b)
46
Agenda
After studying examples of modular arithmetic:
 Modular arithmetic
 Divisors, GCD, Euclid’s theorem
 prime numbers
 Fields of type Zp
 Finite Fields, Extended Euclid’s Theorem for
finding multiplicative inverse
Polynomial arithmetic
47
Divisors




If for some m, a=mb (a,b,m all
integers),
that is b divides into a with no
remainder ,
denote this as b|a
and say that b is a divisor of a
eg. all of 1,2,3,4,6,8,12,24 are the
divisors of 24.
48
Properties of Divisors
If a|1, then a = 1.
 If a|b and b|a, then a = b.
 Any b  0, divides 0.
 If b|g and b|h,
then b|(mg + nh)
for arbitrary integers m and n

49
Greatest Common Divisor


gcd(a,b) = max [k, such that k|a and k|b]
Properties:
1. gcd is required to be positive.
gcd(a,b) = gcd(a, -b) = gcd(-a,b) = gcd(-a,-b) = gcd(|a|,|b|)
2. gcd(a,0) = |a|
3. If gcd(a,b) = 1, a and b are relatively prime.
50
Properties of gcd function
contd…
Assume that a › b.
4. gcd(a,b) = gcd (b, a mod b)
called a Theorem on the next slide
Proof:
 let d = gcd(a,b)
 Then d|a and d|b ( i. e. a = k1d and b = k2d )
If (a mod b) = r,

a = kb + r
or
r = a – kb
= k1.d – k. k2d
This proves d|r.



Thus (4) can be repetitively used to find d.
51
Greatest Common Divisor:

c = gcd(a,b) is the largest number that
divides evenly into both a and b


2 definitions
eg gcd(60,24) = 12
Positive integer c is gcd of two positive
integers a and b if


c is a divisor of a and b;
Any divisor of a and b is a divisor of c.
Theorem: gcd(a,b) = gcd (b, a mod b)
RHS may be a simpler function if a>b.

52
Euclid’s algorithm




Stated in his book “Elements”, written in 300 BC.
Historians believe that the algorithm was devised
~200 years earlier
an efficient way to find gcd(a,b)
derived from the observation:
If a & b have a common factor d (ie a=m.d & b=n.d),
then d is also a factor in any difference between them,
a-p.b = (m.d)-p.(n.d) = d.(m-p.n).
uses successive instances of the theorem:

gcd(a,b) = gcd(b, a mod b)
Note: This MUST always terminate by giving gcd
since eventually we get a mod b = 0 (no remainder).
53
Euclid's GCD Algorithm
Euclid's Algorithm to compute gcd(a,b):


A  a, B  b
while B>0



R = A mod B
A  B, B  R
return A = gcd(a,b)
The example on the next slide uses Euclid’s algorithm.
Even more useful: Extended Euclid’s Algorithm: Used
for finding out the Multiplicative Inverse
54
Example GCD(1970,1066)
1970 = 1 x 1066 + 904
1066 = 1 x 904 + 162
904 = 5 x 162 + 94
162 = 1 x 94 + 68
94 = 1 x 68 + 26
68 = 2 x 26 + 16
26 = 1 x 16 + 10
16 = 1 x 10 + 6
10 = 1 x 6 + 4
6 = 1 x 4 + 2
4 = 2 x 2 + 0
Hence gcd(1970,1066) = 2
gcd(1066, 904)
gcd(904, 162)
gcd(162, 94)
gcd(94, 68)
gcd(68, 26)
gcd(26, 16)
gcd(16, 10)
gcd(10, 6)
gcd(6, 4)
gcd(4, 2)
gcd(2, 0)
55
Agenda
After the Euclid’s theorem:
 Modular arithmetic
 Divisors, GCD, Euclid’s theorem
 prime numbers
 Fields of type Zp
 Finite Fields, Extended Euclid’s Theorem for
finding multiplicative inverse
Polynomial arithmetic
56
Prime Numbers




A prime number p: an integer, whose only
integer factors are itself and 1.
Aug 6, 2002: Manindra Agrawal, Neeraj
Kayal, Nitin Saxena of IIT Kanpur:
Theorem: There is a deterministic polynomialtime algorithm for determining whether a
number is a prime or a composite.
Odd Primes: all prime numbers except 2
The magical prime: 2, used in cryptography
57
Prime Numbers sequence
Reference:http://www.maths.ex.ac.uk/%7Emwatkins/zeta/ss-b.htm
Here the sequence of primes is presented graphically in terms of a
step function or counting function which is traditionally denoted
as (x). (Note: this has nothing to do with the value =3.14159...)
The height of the graph at horizontal position x indicates the
number of primes less than or equal to x. Hence at each prime value
of x, we see a vertical jump of one unit.
58
Prime Numbers sequence
Reference:http://www.maths.ex.ac.uk/%7Emwatkins/zeta/ss-e.htm
Now zooming out by a factor of 2500, we get the above graph. Senior
Max Planck Institute mathematician Don Zagier, in his article "The
first 50 million primes" [Mathematical Intelligencer, 0 (1977) 1-19]
states: "For me, the smoothness with which this curve
climbs is one of the most astonishing facts in
mathematics."
59
Prime Number Factors of a number
 Unique factors of any integer a > 1:

a =  pap where P is the set of prime numbers
p P
and where ap is the degree of p
 c = a.b  cp = (ap+bp) for all p.
Ex:33033 = 3x7x112 X13; 85833 = 3x3x3x11x172
c3 = 3+1 =4, c7 = 1, c11 = 2 +1 = 3, c13 = 1, c17 = 2
gcd(33033, 85833) = 3x11 =33

d|b  dp  bp for all p; Thus if d = 143, 143|33033
Calculating the prime factors of a large number is a
difficult task. So prime number factorization  NOT
used for evaluation of a.b or of the greatest common
divisor (gcd) of a and b.
60
Agenda
After discussing prime numbers:
 Modular arithmetic
 Divisors, GCD, Euclid’s theorem
 prime numbers
 Fields of type Zp
 Finite Fields, Extended Euclid’s Theorem for
finding multiplicative inverse
Polynomial arithmetic

with coefficient obeying modulo n arithmetic

with modulo m(x) and with coefficient obeying
modulo n arithmetic
61
Modular Arithmetic

Consider the set of non – negative
integers:



Zp = { 0, 1, 2, 3………(p-1) }
Each element of Zp represents a residue
class modulo ‘p’ where ‘p’ is a prime
number.
Properties of Modular Arithmetic for
Integers in Zp are given in table 4.2
(Stallings) 4th Ed.
62
Table 4.2
Reference: Page 105 Stallings, 4th Edition
Properties
Expressions
Commutative Laws
(w+x) mod p = (x+w) mod p
(w.x) mod p = (x.w) mod p
Associative laws
[(w+x) + y] mod p = [w+(x+y)] mod p
[(w.x). y] mod p = [w.(x.y)] mod p
Distributive Laws
[w. (x + y)] mod p = [w.x + w.y] mod p
Identities
(0 +w)mod p = w mod p
(1 . w) mod p = w mod p
Additive inverse
(-w)
Multiplicative Inverse
(w-1)
For each w  Zp , there exists a z such that
w+z  0 mod n
For each w  Zp ,there exists a z such that
w .z = 1 mod p
63
Agenda
After discussing Fields of type Zp:
 Modular arithmetic
 Divisors, GCD, Euclid’s theorem
 prime numbers
 Fields of type Zp
 Finite Fields, Extended Euclid’s Theorem for
finding multiplicative inverse
Polynomial arithmetic
64
Order of a Finite Field


Order of a Finite Field: the number of
elements in the field
For

Zp = { 0, 1, 2, 3………(p-1) }
Order = p
65
Galois Fields
Galois Field GF(pn): A finite field of order pn
For p: any prime integer and
n: any integer, greater than or equal to 1, there
is a unique field with pn elements, denoted by
GF(pn).
Unique: Any two fields with the same number
of elements must be essentially the same,
except perhaps for giving the elements of the
field different names.  An interesting fact
66
Galois fields of interest in cryptography:
GF(p)
GF(2n).
Let us first consider GF(p)
GF(p) = {0, 1, 2, …. (p-1)}, with
arithmetic operations modulo p.
67
Galois Fields GF(p):
Some Properties
Every element in GF(p): relatively prime to p
 every element has a multiplicative inverse.
 Hence GF(p) is a Field.
CHARACTERISTIC of a Field: The number of
times a multiplicative identity can be added to
itself before you get to zero.
For GF(p), Characteristic = the number of elements in
the field = p.
A Field of characteristic p: Fp
68
Mutiplicative Inverse Algorithm
finding the multiplicative inverse of b,
such that b.b-1 = 1:
Given that b <m
Extended Euclid (m,b) Algorithm:
To find c such that c.b = 1 mod m
69
Finding Inverses
for m>>b
EXTENDED EUCLID(m, b) ALGORITHM
1.(A1, A2, A3)(1, 0, m);
(B1, B2, B3)(0, 1, b)
2. if B3 = 0,
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
i.e.
B2: multiplicative inverse of b
4. Q = A3/B3
5. (T1, T2, T3)(A1 – Q B1, A2 – Q B2, A3 – Q
B3)
6. (A1, A2, A3)(B1, B2, B3)
7. (B1, B2, B3)(T1, T2, T3)
8. goto 2
70
Example: Inverse of 550 in GF(1759)
Ti = Ai – Bi x Q
Hence 355 is multiplicative inverse of 550 mod 1759.
If B2 be –ve, subtract it from m to get the answer. 71
Finite Field GF(2)
A
B
A+B
A-B
0
0
0
0
0
1
1
1
1
0
1
1
1
1
0
0
Thus in GF(2),
a+b = a-b is an XOR operation.
a.b is an AND operation.
A.B
0
0
0
1
72
Agenda
Polynomial arithmetic
(Ordinary polynomial algebra is of no interest in
cryptography.)
 with coefficients obeying modulo n arithmetic
 Prime polynomials and polynomial gcd
 with modulo m(x) and with coefficient obeying
modulo n arithmetic
73
Polynomial Arithmetic

Consider a polynomial:



A zero-th degree polynomial is a ‘constant
polynomial’.
A nth degree polynomial is called a MONIC
polynomial, if an = 1.
several alternatives available



ordinary polynomial arithmetic: Not used in cryptography
poly arithmetic: with coeff arithmetic as mod
p: called polynomial basis over a finite field
poly arithmetic with coeff mod p and polynomials mod M(x)
74
A Revision: Group, Ring and Field
[A1] closure under addition:
[A2] Associativity of addition:
[A3] Additive identity:
Group
Abelian Group
Ring
Commutative Ring
Integral domain
Field
[A4] Additive inverse:
[A5] Commutativity of addition:
[M1] closure under multiplication:
[M2] Associativity of multiplication:
[M3] Distributive laws:
[M4] Commutativity of multiplication
[M5] Multiplicative identity:
[M6] No zero divisors:
[M7] Multiplicative inverse: 75
Polynomial Arithmetic with
Modulo Coefficients
Poly arithmetic is based on the fact that powers of x are
linearly independent
Let coefficients be elements of a Field GF(p).
 The set of such polynomials forms a polynomial
ring.
Difference between a Field and a Ring: Consider two
elements a and b.



Field: a/b = a.b-1 is also an element of the field.
Ring: (that is not a Field): b-1 may not exist as an element
of the Ring. ( a/b may not result in an exact division.)
Even if the coeff are the elements of a Field, the
division of polynomials may leave a remainder.
76
Polynomials over GF(2)

In cryptography, we are interested in mod 2


all coefficients are 0 or 1
The coeff use modulo 2 arithmetic
EXAMPLE: f(x) = x3 + x2 and g(x) = x2 + x + 1
ADDITION: f(x) + g(x) = x3 + x + 1
Addition of polynomials: requires XOR of coeffs
MULTIPLICATION:
multiplication of g(x) with x3: x5 + x4 + x3
multiplication of g(x) with x2: x4 + x3 + x2
f(x) . g(x) = x5 + x2
77
Polynomials over GF(2)
Multiplication and Addition

f(x): 1100
g(x):0111
Addition: XOR process yields: 1011
Multiplication: Uses shifting and XOR:
multiplication of g(x) with x3: 111000 Lshift by 3
multiplication of g(x) with x2: 011100 Lshift by 2
f(x) . g(x) = 100100
78
Agenda
Polynomial arithmetic
(Ordinary polynomial algebra is of no interest in
cryptography.)
 with coefficients obeying modulo n arithmetic
 Prime polynomials and polynomial gcd
 with modulo m(x) and with coefficient
obeying modulo n arithmetic
79
Modulo m(x): A preliminary view
Multiplication: increases the degree of the
resultant polynomial.
To ensure that the degree remains ‘the same’,
we may consider:
( f(x) . g(x) ) mod m(x).
If a(x) = f(x) . g(x),
a(x) = q(x).m(x) + r(x),
( f(x) . g(x) ) mod m(x) may be said to be equal
to r(x)
The degree of r(x) <= that of m(x).
80
A Prime Polynomial


can write any polynomial in the form:
 a(x) = q(x) m(x) + r(x)
if the remainder is zero, m(x) divides a(x)
If f(x), over a Field F, has no divisors other than itself
& 1, it is called
an irreducible (or prime) polynomial.
 Another definition: f(x), over a Field F, is irreducible,
iff f(x) cannot be expressed as a product of two
polynomials, both of degree lower than that of f(x).

81
Polynomial GCD
Definition: c(x) is the greatest common divisor
of a(x) and b(x) if


c(x) divides both a(x) and b(x).
Any divisor of a(x) and b(x) is a divisor of c(x).
Euclid’s Algorithm to find polynomial gcd:
Based on
gcd[a(x), b(x)] = gcd[b(x), a(x) mod b(x)]
with the assumption that
the degree of a(x) > the degree of b(x).
82
Euclid’s Algorithm to find gcd[a(x), b(x)]
-- similar to Extended Euclid(m, b) Algorithm
gcd[a(x), b(x)];
Assume: the degree of a(x) > the degree of b(x).
1. A(x)  a(x); B(x)  b(x)
2. if B(x) = 0 return A(x) = gcd[a(x), b(x)]
3. R(x) = A(x) mod B(x)
4. A(x)  B(x)
5. B(x)  R(x)
6. goto 2
83
Euclid’s Algorithm to find gcd[a(x), b(x)]
An Example
Given:a(x) = x6+x5+x4+x3+x2+x+1
b(X) = x4 +x2 +x+1
Euclid’s Algorithm
A x6+x5+x4+x3+x2+x1+x+1 x4 +x2 +x+1
B x4 +x2 +x+1
x3 +x2+1
R x3 +x2+1
0
Q x2 +x
x+1
gcd[a(x), b(x)] = A(x) = x3 +x2+1
x3 +x2+1
0
84
Agenda
Polynomial arithmetic
(Ordinary polynomial algebra is of no interest in
cryptography.)
 with coefficients obeying modulo n arithmetic
 Prime polynomials and polynomial gcd
 with modulo m(x) and with coefficient obeying
modulo n arithmetic
85
Polynomials over GF(2)


Polynomial arithmetic modulo an irreducible
polynomial forms a Field.
By analogy with modulo operations studied earlier, if
a and b are relatively prime, the multiplicative inverse
exists.
We shall look at an extended Euclid algorithm to
evaluate the multiplicative inverse of a(x) modulo
b(x), where b(x) is an irreducible polynomial.
On the coefficients, the arithmetic is modulo 2.
86
Extracts from earlier slides





If a mod 7 = b mod 7, a and b are said to be
congruent mod 7.
[O] = {….,-21,-14,-7,0,7,14….}
is called a Residue Class Mod 7.
The Smallest Non-negative integer of the class is
used to represent the class.
To find the smallest Non-negative integer, to which k is
congruent, is called reducing k modulo n
Zp = { 0, 1, 2, 3………(p-1) }

Each element of Zp represents a residue class
modulo ‘p’ where ‘p’ is a prime number.
87
Set of Residues modulo m(x)


m(x): nth degree polynomial
Example: residue class (x+1), modulo m(x)
consists of all such polynomials a(x) such that
a(x) = (x+1)mod m(x)
Or all the polynomials, which satisfy
a(x) mod m(x) = x+1.
For m(X) = x3 +x+1,
one possible value of a(x) is x4 +x2 +1.
88
GF (pn) with an irreducible polynomial b(x)
Set of residues:
n
 consisting of p elements.

Each of these elements represented by one of
the pn polynomials of degree m<n
Example: GF (23)
with an irreducible polynomial b(x) = x3 +x+1
The set of residues are
{0, 1, x, (x+1), x2, (x2 +1), (x2 + x), (x2+x+1)}

Finding Multiplicative inverse of b(x) modulo m(x):
Assume: degree of b(x) < degree of m(x)
gcd[m(x),b(x)] = 1
89
23 elements of
finite polynomial field GF(23)
Decimal number
0
1
2
3
4
5
6
7
Binary number
000
001
010
011
100
101
110
111
Polynomial
0
1
x
x+1
x2
x2+1
x2+x
x2+x+1
Choose m(x)=(x3+x+1) as the irreducible polynomial.
90
Example GF(23)
91
Multiplicative Inverse:
a(x).b(x) mod (x3 +x+1) = 1
a(x)
x
x+1
x2
x2 + 1
x2 + x
x2 + x + 1
1
b(x) = a-1(x)
x2 +1
x2 + x
x2 + x + 1
x
x+1
x2
1
92
Additive and Multiplicative Inverses in GF (23)
w
0
1
2
3
4
5
6
7
Additive Inverse
-w
0
1
2
3
4
5
6
7
Multiplicative Inverse
w-1
1
5
6
7
2
3
4
If mult results in a polynomial a(x) of degree greater
than 2 (ie n-1 for pn or a degree greater than or
equal to n), reduce it to a polynomial, r(x), of degree
less than or equal to 2 by using
r(x) = a(x) mod(x3+x+1).
93
Multiplicative inverse
Extended Euclid[m(x), b(x)] Algorithm
1.
2.
3.
(A1, A2, A3) (1, 0, m);
(B1, B2, B3) (0, 1, b)
If B3 = 0,
return A3 = gcd(m, b); no inverse
If B3 = 1
return B2 as the multiplicative inverse of B
(i.e.
b(x).B2 = 1 mod m(x) )
7.
Q = A3/B3
(T1, T2, T3) (A1 – Q B1, A2 – Q B2, A3 –
QB3)
(A1, A2, A3) (B1, B2, B3)
(B1, B2, B3) (T1, T2, T3)
8.
Go to 2
4.
5.
6.
94
Modular Polynomial Arithmetic

can compute in field GF(2n)





polynomials with coefficients modulo 2
The elements of GF are polynomials, whose
degree is less than n
hence must reduce modulo an irreducible poly of
degree n (for multiplication only)
The polynomials form a finite field. The
number of elements in the field is 2n.
For every element of the field, a multiplicative
inverse can always be found by using
Euclid’s Inverse algorithm.
95
ARITHMETIC OPERATIONS:
GF(28) with m(x) = (x8+x4+x3+x+1)
AES uses GF(28) and an irreducible polynomial
(x8+x4+x3+x+1).
In binary, it is 100011011
In HEX, the polynomial: 0x11B
Justification: The first out of the 30 irreducible polynomials of
degree 8, given in Lidl, R., Niederreiter, H. ‘Introduction to
Finite Fields and Their Applications’, Cambridge University
Press, 1994
96
MULTIPLICATIVE INVERSE: To find c(x) such
that: (x7+x+1).c(x) = 1 mod(x8+x4+x3+x+1)
A1 1
0
1
x3+ x2+1
A2 0
1
x
x4+x3+ x+1
A3 x8+x4+x3+x+1 x7+x+1
x4+x3+ x2+1 x
B1 0
1
x3+ x2+1
x6+x2+ x+1
B2 1
x
x4+x3+ x+1
x7
B3 x7+x+1
x4+x3+ x2+1 x
1
Qx
x3+ x2+1
x3+ x2+x
Answer: The Multiplicative Inverse of
(x7+x+1) mod(x8+x4+x3+x+1) = c(x) = x7
97
"Genius is condemned by a malicious social
organization to an eternal denial of justice in
favor of fawning mediocrity"
-- Evariste Galois
98
Representation
A polynomial with coeff, obeying modulo 2 arithmetic,
can be represented by a binary or a HEX number.
Example : 0x11B = 100011011 represents
x8+x4+x3+x+1.
This is an irreducible polynomial.
A polynomial in GF (28), a(x) = a7x7+a6x6+…+a1x+a0
can be represented as
( a7 a6 a5……….… a1 a0 )
Addition of two polynomials a(x) and b(x): Use
XOR operation on two bit arrays:
( a7 a6 a5…..… a1 a0 )  ( b7 b6 b5… …..b1 b0 )
99
ARITHMETIC OPERATIONS: MULTIPLICATION
for GF(28) with m(x) = (x8+x4+x3+x+1)
Reduction:
Example 1:
x8 mod m (x) = m (x) – x8 = x4 + x3 + x + 1
Note: x4 + x3 + x + 1 can be represented as 0x1B.
In general : xn mod m (x) = m (x) – xn
Multiplication:
Let b(x) = b7x7+ b6x6+…+ b1x+ b0
Example 2: Consider multiplication of b (x) with x :
x . b (x) mod m (x)
if b7 = 0, x b (x) is in the reduced form.
If b7 = 1 using results of Example 1,
(b6x7+…+b1x2+b0x)  (x4 + x3 + x + 1)
100
ARITHMETIC OPERATIONS: MULTIPLICATION:
Generalized Result
This multiplication x . b (x) mod m (x) is done as follows
x . b (x) mod m (x) = b6b5b4b3b2b1b00
if b7 = 0
= (b6b5b4b3b2b1b00)  (00011011) if b7 = 1
Multiplication by a higher power can be achieved by a repeated
application of Step2.
Example 3:
r (x) = b (x) . a (x) mod m (x)
=(x6 + x4 + x2 + x + 1) . (x7 + x + 1) mod (x8+x4 + x3 + x + 1)
101
ARITHMETIC OPERATIONS: MULTIPLICATION:
Example 3
To get r (x),
Step1
(x6+x4 + x2 + x + 1) . x mod m (x)
(0101 0111) . (0000 0010)
Shift left  1010 1110
step2
(x6+x4 + x2 + x + 1) . x2 mod m (x)
(0101 0111) . (0000 0100)
= (1010 1110) . (0000 0010)  ( 0001 1011)
= (0101 1100)  (0001 1011)
= (0100 0111)
102
ARITHMETIC OPERATIONS:
MULTIPLICATION Example (continued)
Step3
(x6 + x4 + x2 + x + 1) . x3 mod m (x)
(0101 0111) . (0000 1000)
= (0100 0111) . (0000 0010)
= 1000 1110
Step4 Multiplication of b (x) by x4 mod m (x)
(0101 0111) . (0001 0000)
= (1000 1110) . (0000 0010)  (0001 1011)
= (0001 1100)  (0001 1011)
= (0000 0111)
103
ARITHMETIC OPERATIONS:
MULTIPLICATION Example (continued)
Step5 Multiplication of b (x) by x5 mod m (x)
(0101 0111) . (0010 0000)
= (0000 0111) . (0000 0010)
= 0000 1110
Step6 Multiplication of b (x) by x6 mod m (x)
Result = 0001 1100
Step7 Multiplication of b (x) by x7 mod m (x)
Result = 0011 1000
104
ARITHMETIC OPERATIONS:
MULTIPLICATION Example (continued)
Step8 b (x) . a (x) mod m (x) where a (x) = x7 + x + 1
(0011 1000)
 (1010 1110)  ( 0101 0111)
= 1100 0001
Hence
b (x) . a (x) mod m (x)
= (x6+x4 + x2 + x + 1) . (x7 + x + 1) mod (x8+x4 + x3 + x + 1)
= x7+x6+ 1
105
Computational Considerations



Since coefficients are 0 or 1, any such
polynomial can be represented as a bit string.
Addition becomes XOR of the bit strings.
Multiplication is shift or “shift & XOR”.



cf long-hand multiplication
See, again, the line in red, five slides back.
Modulo reduction done by repeatedly
applying the rule of that slide.
106
Use of the bit notation for polynomials:
Ex: for GF(28) with m(x) = x8+x4+x3+x+1.
Example: rc1(x) = 1
rcj(x) = x.rcj-1(x) mod m(x) for j = 2 to 10
 Denoted by RC(1) = 1
RC(j) = 2.RC(j-1) for j = 2 to 10
For GF(28), the number of members of the finite group
are 256, starting from 0 to 255.
Thus RC(2) = 2,………………………………RC(8) = 128

rc9(x) = x8 mod m(x) = x4+x3+x+1  RC(9) = 1B
5
4
2
 RC(10) = 0011 0110 = 3616 = x +x +x +x –
obtained by shifting RC(9) to the left
107
Win thousands of dollars!
Solve problems in Number theory, Graph theory
and Combinatorics-- and WIN!
Paul Erdos, the great Hungarian problem solver,
is the purser of all of the problems.
(The purser is the final judge and arbiter of prize-winning solutions.
The award only goes to the person who solves a problem first, and
the purser is the arbiter of that too.)
Volunteer Advisor for solvers: [email protected]
References: 1.“A Tribute to Paul Erdos”, Cambridge University
Press, 1990, pp. 467-477. 2. “Paths, Flows, and VLSI Layout”,
Springer-Verlag, 1980, pp. 35-45. 3. “Erdos on graphs, his legacy
of unsolved problems”, Fan Chung & RonGraham, AK Peters 1998
4. http://www.math.upenn.edu/~chung/
108