TWO WEEKS TO AES

— The Advanced Encryption Standard (AES) uses arithmetic in the finite field GF (28),
with the irreducible polynomial m(x) = x8 + x4 + x3 + x + 1
DIVISIBILITY
— We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers
— b divides a if there is no remainder on division
— The notation b | a is commonly used to mean b divides a
— The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24
13 | 182; - 5 | 30; 17 | 289; - 3 | 33; 17 | 0
PROPERTIES OF DIVISIBILITY
— If a | 1, then a = ±1
— If a | b and b | a, then a = ±b
— Any b ≠ 0 divides 0
— If a | b and b | c, then a | c [11 | 66 and 66 | 198 = 11 | 198]
— If b | g and b | h, then b | (mg + nh) for arbitrary integers m and n
MODULAR ARITHMETIC
— The modulus
— if a is an integer and n is a positive integer, we define a mod n to be the remainder
when a is divided by n; the integer n is called the modulus
— thus, for any integer a:
o a = qn + r 0 ≤ r < n; q = [a/ n]
o a = [a/ n] * n + ( a mod n)
o 11 mod 7 = 4; -11 mod 7 = 3
— Congruent modulo n
o Two integers a and b are said to be congruent modulo n if (a mod n) = (b mod
n)
o This is written as a = b(mod n)2 or a≡b(mod n)
o Note that if a = 0(mod n), then n | a
o 73 ≡ 4 (mod 23); 21 ≡ - 9 (mod 10)

PROPERTIES OF CONGRUENCE
— Congruences have the following properties:
1. a = b (mod n) if n|(a – b)
2. a = b (mod n) implies b = a (mod n)
3. a = b (mod n) and b = c (mod n) imply a = c (mod n)
— To demonstrate the first point, if n|(a - b), then (a - b) = kn for some k
o So we can write a = b + kn
o Therefore, (a mod n) = (remainder when b + kn is divided by n) = (remainder
when b is
o divided by n) = (b mod n)

23 = 8 (mod 5) because 23 - 8 = 15 = 5 * 3
- 11 = 5 (mod 8) because - 11 - 5 = - 16 = 8 * (- 2)
81 = 0 (mod 27) because 81 - 0 = 81 = 27 * 3
MODULAR ARITHMETIC
— Modular arithmetic exhibits the following properties:
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) - (b mod n)] mod n = (a - b) mod n
3. [(a mod n) * (b mod n)] mod n = (a * b) mod n
— We demonstrate the first property:
— Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + jn for some integer
j and b = rb + kn for some integer k. Then
o (a + b) mod n = (ra + jn + rb + kn) mod n
o = (ra + rb + (k + j)n) mod n
o = (ra + rb) mod n
o = [(a mod n) + (b mod n)] mod n

11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8) - (15 mod 8)] mod 8 = - 4 mod 8 = 4
(11 - 15) mod 8 = - 4 mod 8 = 4
[(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5
(11 * 15) mod 8 = 165 mod 8 = 5
ADDITION MODULO 8 AND MULTIPLICATION MODULO 8
PROPERTIES OF MODULAR ARITHMETIC FOR INTEGERS IN Zn

GREATEST COMMON DIVISOR (GCD)

— The greatest common divisor of a and b is the largest integer that divides both a and b
— We can use the notation gcd(a,b) to mean the greatest common divisor of a and b
— We also define gcd(0,0) = 0
— Positive integer c is said to be the gcd of a and b if:
o c is a divisor of a and b
o Any divisor of a and b is a divisor of c
— An equivalent definition is:
o gcd(a,b) = max[k, such that k | a and k | b]

GCD
— Because we require that the greatest common divisor be positive, gcd(a,b) = gcd(a,-b) =
gcd(-a,b) = gcd(-a,-b)
— In general, gcd(a,b) = gcd(| a |, | b |)
gcd(60, 24) = gcd(60, - 24) = 12
— Also, because all nonzero integers divide 0, we have gcd(a,0) = | a |
— We stated that two integers a and b are relatively prime if their only common positive
integer factor is 1;
o This is equivalent to saying that a and b are relatively prime if gcd(a,b) = 1

8 and 15 are relatively prime because

the positive divisors of 8 are 1, 2, 4, and 8,
the positive divisors of 15 are 1, 3, 5, and 15.
So 1 is the only integer on both lists.
EUCLIDEAN ALGORITHM
— an efficient way to find the GCD(a,b)
— uses theorem that:
 o d=GCD(a,b) = GCD(b, a mod b)
— Euclidean Algorithm is:
— EUCLID(a,b)
1. A = a; B = b
2. if B = 0 return A = gcd(a, b)
3. R = A mod B
4. A = B
5. B = R
6. goto 2

EXTENDED EUCLIDEAN ALGORITHM EXAMPLE

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:
o (A1) Closure:
 If a and b belong to G, then a Ÿ b is also in G
o (A2) Associative:
 a Ÿ (b Ÿ c) = (a Ÿ b) Ÿ c for all a, b, c in G
o (A3) Identity element:
 There is an element e in G such that a Ÿ e = e Ÿ a = a for all a in G;
e.g., 0 in additive and 1 for the multiplication
o (A4) Inverse element:
 For each a in G, there is an element a’ in G such that aŸa’ = a’ Ÿ a = e
o (commutative group or Abelian Group) Commutative:
 a Ÿ b = b Ÿ a for all a, b in G
CYCLIC GROUP
— 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:
o (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
o (M1) Closure under multiplication: If a and b belong to R , then ab is also in R
o (M2) Associativity of multiplication: a (bc ) = (ab)c for all a , b , c in R
o (M3) Distributive laws: a(b+c) = ab + ac for all a , b , c in R and (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 and multiplication
without leaving the set
— A ring is said to be commutative if it satisfies the following additional condition:
o (M4) Commutativity of multiplication: ab = ba for all a, b in R
— An integral domain is a commutative ring that obeys the following axioms.
 o (M5) Multiplicative identity: There is an element 1 in R such that a 1 = 1a = a
— for all a in R
o (M6) No zero divisors: If a , b in R and ab = 0, then either a = 0 or b = 0

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:
o (A1–M6)
 F is an integral domain; that is, F satisfies axioms A1 through A5 and
M1 through M6
o (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 following rule: a /b
= a (b-1 )

FINITE FIELDS OF THE FORM GF(p)

— Finite fields play a crucial role in many cryptographic algorithms
— The output of encryption algorithms are within the same set of the input.
— It can be shown that the order of a finite field (the number of elements in the field) must
be a power of a prime p, i.e., pn , where n is a positive integer
— The only positive integers that are divisors of p are p and 1
— 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
HOW TO CONSTRUCT A FINITE FIELD OF ORDER A PRIME P
— GF(p) is defined with the following properties:
1. GF(p) consists of p elements
2. The binary operations + and * are defined over the set. The operations of addition,
subtraction, multiplication, and division can be performed without leaving the
set. Each element of the set other than 0 has a multiplicative inverse
— We have shown that the elements of GF(p) are the integers {0, 1, . . . , p – 1} and
— the arithmetic operations are addition and multiplication mod p
What if 2n bits data? 2n is not a prime
POLYNOMIAL ARITHMETIC
— We can distinguish three classes of polynomial arithmetic:
o Ordinary polynomial arithmetic, using the basic rules of algebra
o Polynomial arithmetic in which the arithmetic on the coefficients is performed
modulo p; that is, the coefficients are in GF(p )
o Polynomial arithmetic in which the coefficients are in GF(p ), and the
polynomials are defined modulo a polynomial f (x ) whose highest power is
some integer n
ORDINARY POLYNOMIAL ARITHMETIC EXAMPLE
— As an example:
o let f(x) = x3 + x2 + 2 and g(x) = x2 - x + 1,
— Then:
o f(x) + g(x) = x3 + 2x2 - x + 3
o f(x) - g(x) = x3 + x + 1
o f(x) * g(x) = x5 + 3x2 - 2x + 2
 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
o 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
o Even if the coefficient set is a field, polynomial division is not necessarily exact
o With the understanding that remainders are allowed, we can say that
polynomial
o division is possible if the coefficient set is a field

POLYNOMIAL DIVISION
— We can write any polynomial in the form:
o 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)
o Written as g(x) | f(x)
o We can say that g(x) is a factor of f(x)
o 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)
o An irreducible polynomial is also called a prime polynomial
EXAMPLE OF POLYNOMIAL ARITHMETIC OVER GF(2)

POLYNOMIAL ARITHMETIC MODULO (X3 + X + 1)

ARITHMETIC IN GF(23)
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:
o c(x) divides both a(x) and b(x)
o Any divisor of a(x) and b(x) is a divisor of c(x)
— An equivalent definition is:
o 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
EXTENDED EUCLID [(X8 + X4 + X3 + X + 1), (X7 + X + 1)]
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
— Modulo reduction is done by repeatedly substituting highest power with remainder of
irreducible polynomial (also shift and XOR)
in GF(23) have (x2+1) is 1012 & (x2+x+1) is 1112
so addition is
(x2+1) + (x2+x+1) = x
101 XOR 111 = 0102
and multiplication is
(x+1)·(x2+1) = x·(x2+1) + 1·(x2+1)= x3+x+x2+1 = x3+x2+x+1
011·101 = (101)<<1 XOR (101)<<0 = 1010 XOR 101 = 11112
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
o The elements of F consist of 0, g0, g1, . . . ., gq-2
— Consider a field F defined by a polynomial f(x)
o 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
GENERATOR FOR GF(23) DEFINED ON X3 + X + 1
— Let us consider the finite field GF(23), defined over the irreducible polynomial x3 + x +
1,
— Generator g satisfies
f(g)=g3+g+1=0
— Then we have
g3 = -g-1=g+1
g4 = g(g3)=g(g+1)= g2 +g
g5 = g(g4)=g(g2 +g)= g3 + g2 = g2 +g+1
g6 = g(g5)=g(g2 +g+1)= g3+g2+g= g2 +g+g+1= g2 +1
g7 = g(g6)=g(g2 +1)= g3+g=g+g+1=1=g0
GF(23) ARITHMETIC USING GENERATOR FOR THE POLYNOMIAL (X3 + X + 1)