1 of 37

MODULE 3

Basic Concepts of Number Theory and Finite Fields: Groups, Rings and Fields, Finite fields of the form GF(p), Prime Numbers, Fermat’s and Euler’s theorem, discrete logarithm. (Text 1: Chapter 3 and Chapter 7: Section 1, 2, 5)

Text Books:

William Stallings , “Cryptography and Network Security Principles and Practice”, Pearson

Education Inc., 6th Edition, 2014, ISBN: 978-93-325-1877-3

2. Bruce Schneier, “Applied Cryptography Protocols, Algorithms, and Source code in C”, Wiley

Publications, 2nd Edition, ISBN: 9971-51-348-X.

Reference Books:

1. Cryptography and Network Security, Behrouz A. Forouzan, TMH, 2007.

2. Cryptography and Network Security, Atul Kahate, TMH, 2003.

2 of 37

Group

a set S of elements or “numbers”

may be finite or infinite

with some operation ‘.’ so G=(G,.)
Obeys CAIN:

Closure: a,b in S, then a.b in G
Associative law: (a.b).c = a.(b.c)
has Identity e: e.a = a.e = a
has iNverses a^-1: a.a^-1 = e

if commutative a.b = b.a

then forms an abelian group

Groups, rings, and fields are the fundamental elements of a branch of mathematics known as abstract algebra, or modern algebra. In abstract algebra, we are concerned with sets on whose elements we can operate algebraically; that is, we can combine two elements of the set, perhaps in several ways, to obtain a third element of the set. These operations are subject to specific rules, which define the nature of the set. By convention, the notation for the two principal classes of operations on set elements is usually the same as the notation for addition and multiplication on ordinary numbers. However, it is important to note that, in abstract algebra, we are not limited to ordinary arithmetical operations.

A group G, sometimes denoted by {G, • }, is 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: Closure, Associative, Identity element, Inverse element.

Note - we have used . as operator: could be addition +, multiplication x or any other mathematical operator. A group can have a finite (fixed) number of elements, or it may be infinite. Note that integers (+ve, -ve and 0) using addition form an infinite abelian group. So do real numbers using multiplication.

3 of 37

Cyclic Group

define exponentiation as repeated application of operator

example: a³ = a.a.a

and let identity be: e=a⁰
a group is cyclic if every element is a power of some fixed element a

i.e., b = a^k for some a and every b in group

a is said to be a generator of the group

4 of 37

Ring

a set of “numbers”
with two operations (addition and multiplication) which form:
an abelian group with addition operation
and multiplication:

has closure
is associative
distributive over addition: a(b+c) = ab + ac

if multiplication operation is commutative, it forms a commutative ring
if multiplication operation has an identity and no zero divisors, it forms an integral domain

5 of 37

Field

a set of numbers
with two operations which form:

abelian group for addition
abelian group for multiplication (ignoring 0)
ring

have hierarchy with more axioms/laws

group -> ring -> field

6 of 37

Group, Ring, Field

7 of 37

Finite (Galois) Fields

finite fields play a key role in cryptography
can show number of elements in a finite field must be a power of a prime pⁿ
known as Galois fields
denoted GF(pⁿ)
in particular often use the fields:

GF(p)
GF(2ⁿ)

8 of 37

Galois Fields GF(p)

GF(p) is the set of integers {0,1, … , p-1} with arithmetic operations modulo prime p
these form a finite field

since have multiplicative inverses
find inverse with Extended Euclidean algorithm

hence arithmetic is “well-behaved” and can do addition, subtraction, multiplication, and division without leaving the field GF(p)

9 of 37

GF(7) Multiplication Example

×	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

10 of 37

Polynomial Arithmetic

can compute using polynomials

f(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀ = ∑ a_ixⁱ

n.b. not interested in any specific value of x
which is known as the indeterminate

several alternatives available

ordinary polynomial arithmetic
poly arithmetic with coefs mod p
poly arithmetic with coefs mod p and polynomials mod m(x)

11 of 37

Ordinary Polynomial Arithmetic

add or subtract corresponding coefficients
multiply all terms by each other
eg

let f(x) = x³ + x² + 2 and g(x) = x² – x + 1

f(x) + g(x) = x³ + 2x² – x + 3

f(x) – g(x) = x³ + x + 1

f(x) x g(x) = x⁵ + 3x² – 2x + 2

12 of 37

Polynomial Arithmetic with Modulo Coefficients

when computing value of each coefficient do calculation modulo some value

forms a polynomial ring

could be modulo any prime
but we are most interested in mod 2

ie all coefficients are 0 or 1
eg. let f(x) = x³ + x² and g(x) = x² + x + 1

f(x) + g(x) = x³ + x + 1

f(x) x g(x) = x⁵ + x²

13 of 37

Polynomial Division

can write any polynomial in the form:

f(x) = q(x) g(x) + r(x)
can interpret r(x) as being a remainder
r(x) = f(x) mod g(x)

if have no remainder say g(x) divides f(x)
if g(x) has no divisors other than itself & 1 say it is irreducible (or prime) polynomial
arithmetic modulo an irreducible polynomial forms a field

14 of 37

Polynomial GCD

can find greatest common divisor for polys

c(x) = GCD(a(x), b(x)) if c(x) is the poly of greatest degree which divides both a(x), b(x)

can adapt Euclid’s Algorithm to find it:

Euclid(a(x), b(x))

if (b(x)=0) then return a(x);

else return

Euclid(b(x), a(x) mod b(x));

all foundation for polynomial fields as see next

We can extend the analogy between polynomial arithmetic over a field and integer arithmetic by defining the greatest common divisor as shown.

We began this section with a discussion of arithmetic with ordinary polynomials. Arithmetic operations are performed on polynomials (addition, subtraction, multiplication, division) using the ordinary rules of algebra. Polynomial division is not allowed unless the coefficients are elements of a field. Next, we discussed polynomial arithmetic in which the coefficients are elements of GF(p). In this case, polynomial addition, subtraction, multiplication, and division are allowed. However, division is not exact; that is, in general division results in a quotient and a remainder. Finally, we showed that the Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements of a field. All of the material in this section provides a foundation for the following section, in which polynomials are used to define finite fields of order pⁿ.

15 of 37

Modular Polynomial Arithmetic

can compute in field GF(2ⁿ)

polynomials with coefficients modulo 2
whose degree is less than n
hence must reduce modulo an irreducible poly of degree n (for multiplication only)

form a finite field
can always find an inverse

can extend Euclid’s Inverse algorithm to find

Consider now the case of polynomial arithmetic with coordinates mod 2 and polynomials mod an irreducible polynomial m(x). That is Modular Polynomial Arithmetic uses the set S of all polynomials of degree n-1 or less over the field Zp. With the appropriate definition of arithmetic operations, each such set S is a finite field. The definition consists of the following elements:

Arithmetic follows the ordinary rules of polynomial arithmetic using the basic rules of algebra, with the following two refinements.
Arithmetic on the coefficients is performed modulo p.
If multiplication results in a polynomial of degree greater than n-1, then the polynomial is reduced modulo some irreducible polynomial m(x) of degree n. That is, we divide by m(x) and keep the remainder.

This forms a finite field. And just as the Euclidean algorithm can be adapted to find the greatest common divisor of two polynomials, the extended Euclidean algorithm can be adapted to find the multiplicative inverse of a polynomial.

16 of 37

Example GF(2³)

17 of 37

Computational Considerations

since coefficients are 0 or 1, can represent any such polynomial as a bit string
addition becomes XOR of these bit strings
multiplication is shift & XOR

cf long-hand multiplication

modulo reduction done by repeatedly substituting highest power with remainder of irreducible poly (also shift & XOR)

18 of 37

Computational Example

in GF(2³) have (x²+1) is 101₂ & (x²+x+1) is 111₂
so addition is

(x²+1) + (x²+x+1) = x
101 XOR 111 = 010₂

and multiplication is

(x+1).(x²+1) = x.(x²+1) + 1.(x²+1)

= x³+x+x²+1 = x³+x²+x+1

011.101 = (101)<<1 XOR (101)<<0 =

1010 XOR 101 = 1111₂

19 of 37

Computational Example (con't)

in GF(2³) have (x²+1) is 101₂ & (x²+x+1) is 111₂
polynomial modulo reduction (get q(x) & r(x)) is

(x³+x²+x+1 ) mod (x³+x+1) = 1.(x³+x+1) + (x²) = x²
1111 mod 1011 = 1111 XOR 1011 = 0100₂

20 of 37

Using a Generator

equivalent definition of a finite field
a generator g is an element whose powers generate all non-zero elements

in F have 0, g⁰, g¹, …, g^q-2

can create generator from root of the irreducible polynomial
then implement multiplication by adding exponents of generator

21 of 37

Prime Numbers

prime numbers only have divisors of 1 and self

they cannot be written as a product of other numbers
note: 1 is prime, but is generally not of interest

eg. 2,3,5,7 are prime, 4,6,8,9,10 are not
prime numbers are central to number theory
list of prime number less than 200 is:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

22 of 37

Prime Factorisation

to factor a number n is to write it as a product of other numbers: n=a x b x c
note that factoring a number is relatively hard compared to multiplying the factors together to generate the number
the prime factorisation of a number n is when its written as a product of primes

eg. 91=7x13 ; 3600=2⁴x3²x5²

23 of 37

Relatively Prime Numbers & GCD

two numbers a, b are relatively prime if have no common divisors apart from 1

eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only common factor

conversely can determine the greatest common divisor by comparing their prime factorizations and using least powers

eg. 300=2¹x3¹x5² 18=2¹x3² hence GCD(18,300)=2¹x3¹x5⁰=6

24 of 37

Fermat's Theorem

a^p-1 = 1 (mod p)

where p is prime and gcd(a,p)=1

also known as Fermat’s Little Theorem
also have: a^p = a (mod p)
useful in public key and primality testing

25 of 37

Euler Totient Function ø(n)

when doing arithmetic modulo n
complete set of residues is: 0..n-1
reduced set of residues is those numbers (residues) which are relatively prime to n

eg for n=10,
complete set of residues is {0,1,2,3,4,5,6,7,8,9}
reduced set of residues is {1,3,7,9}

number of elements in reduced set of residues is called the Euler Totient Function ø(n)

26 of 37

Euler Totient Function ø(n)

to compute ø(n) need to count number of residues to be excluded
in general need prime factorization, but

for p (p prime) ø(p)=p-1
for p.q (p,q prime) ø(p.q)=(p-1)x(q-1)

eg.

ø(37) = 36

ø(21) = (3–1)x(7–1) = 2x6 = 12

27 of 37

Euler's Theorem

a generalisation of Fermat's Theorem
a^ø(n) = 1 (mod n)

for any a,n where gcd(a,n)=1

eg.

a=3;n=10; ø(10)=4;

hence 3⁴= 81 = 1 mod 10

a=2;n=11; ø(11)=10;

hence 2¹⁰= 1024 = 1 mod 11

also have: a^ø(n)+1 = a (mod n)

28 of 37

Primality Testing

often need to find large prime numbers
traditionally sieve using trial division

ie. divide by all numbers (primes) in turn less than the square root of the number
only works for small numbers

alternatively can use statistical primality tests based on properties of primes

for which all primes numbers satisfy property
but some composite numbers, called pseudo-primes, also satisfy the property

can use a slower deterministic primality test

29 of 37

Miller Rabin Algorithm

a test based on prime properties that result from Fermat’s Theorem
algorithm is:

TEST (n) is:

1. Find integers k, q, k > 0, q odd, so that (n–1)=2^kq

2. Select a random integer a, 1<a<n–1

3. if a^q mod n = 1 then return (“inconclusive");

4. for j = 0 to k – 1 do

5. if (a²^jq mod n = n-1)

then return(“inconclusive")

6. return (“composite")

30 of 37

Probabilistic Considerations

if Miller-Rabin returns “composite” the number is definitely not prime
otherwise is a prime or a pseudo-prime
chance it detects a pseudo-prime is < ¹/₄
hence if repeat test with different random a then chance n is prime after t tests is:

Pr(n prime after t tests) = 1-4^-t
eg. for t=10 this probability is > 0.99999

could then use the deterministic AKS test

How can we use the Miller-Rabin algorithm to determine with a high degree of confidence whether or not an integer is prime? If Miller-Rabin returns “composite” the number is definitely not prime, otherwise it is either a prime or a pseudo-prime. The chance it detects a pseudo-prime is < ¹/₄

So if apply test repeatedly with different values of a, the probabiility that the number is a pseudo-prime can be made as small as desired, eg after 10 tests have chance of error < 0.00001

If really need certainty, then would now expend effort to run a deterministic primality proof such as AKS. Prior to 2002, there was no known method of efficiently proving the primality of very large numbers. All of the algorithms in use, including the most popular (Miller-Rabin), produced a probabilistic result. In 2002, Agrawal, Kayal, and Saxena [AGRA02] developed a relatively simple deterministic algorithm that efficiently determines whether a given large number is a prime. The algorithm, known as the AKS algorithm, does not appear to be as efficient as the Miller-Rabin algorithm. Thus far, it has not supplanted this older, probabilistic technique.

31 of 37

Prime Distribution

prime number theorem states that primes occur roughly every (ln n) integers
but can immediately ignore evens
so in practice need only test 0.5 ln(n) numbers of size n to locate a prime

note this is only the “average”
sometimes primes are close together
other times are quite far apart

32 of 37

Chinese Remainder Theorem

used to speed up modulo computations
if working modulo a product of numbers

eg. mod M = m₁m₂..m_k

Chinese Remainder theorem lets us work in each moduli m_iseparately
since computational cost is proportional to size, this is faster than working in the full modulus M

33 of 37

Chinese Remainder Theorem

can implement CRT in several ways
to compute A(mod M)

first compute all a_i = A mod m_i separately
determine constants c_i below, where M_i = M/m_i
then combine results to get answer using:

34 of 37

Primitive Roots

from Euler’s theorem have a^ø(n)mod n=1
consider a^m=1 (mod n), GCD(a,n)=1

must exist for m = ø(n) but may be smaller
once powers reach m, cycle will repeat

if smallest is m = ø(n) then a is called a primitive root
if p is prime, then successive powers of a "generate" the group mod p
these are useful but relatively hard to find

35 of 37

Powers mod 19

36 of 37

Discrete Logarithms

the inverse problem to exponentiation is to find the discrete logarithm of a number modulo p
that is to find i such that b = aⁱ (mod p)
this is written as i = dlog_a b (mod p)
if a is a primitive root then it always exists, otherwise it may not, eg.

x = log₃ 4 mod 13 has no answer

x = log₂ 3 mod 13 = 4 by trying successive powers

whilst exponentiation is relatively easy, finding discrete logarithms is generally a hard problem

Discrete logarithms are fundamental to a number of public-key algorithms, including Diffie-Hellman key exchange and the digital signature algorithm (DSA).

Discrete logs (or indices) share the properties of normal logarithms, and are quite useful. As with ordinary positive real numbers, the logarithm function is the inverse of exponentiation. The logarithm of a number is defined to be the power to which some positive base (except 1) must be raised in order to equal that number. If working with modulo arithmetic, and the base is a primitive root, then an integral discrete logarithm exists for any residue.

However whilst exponentiation is relatively easy, finding discrete logs is not, in fact is as hard as factoring a number. This is an example of a problem that is "easy" one way (raising a number to a power), but "hard" the other (finding what power a number is raised to giving the desired answer). Problems with this type of asymmetry are very rare, but are of critical usefulness in modern cryptography.

37 of 37

Discrete Logarithms mod 19

×	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

×	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

×	1	2	3	4	5	6
0	0	0	0	0	0	0
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1