Chapter: Cryptography and Network Security

Finite Fields

1 Groups, Rings and Field: 2 Modular Arithmetic

FINITE FIELDS

 

1 Groups, Rings and Field:

 

Group: A set of elements that is closed with respect to some operation.

 

Closed-> The result of the operation is also in the set

 

The operation obeys:

Obeys associative law: (a.b).c = a.(b.c)

 

Has identity e: e.a = a.e = a

 

Has inverses a-1: a.a-1 = e

 

Abelian Group: The operation is commutative

 

a.b = b.a

 

Example: Z8, + modular addition, identity =0

Cyclic Group

 

Exponentiation: Repeated application of operator

 

example: a3 = a.a.a

 

Cyclic Group: Every element is a power of some fixed element, i.e., b = ak for some a and every b in group a is said to be a generator of the group

 

Example: {1, 2, 4, 8} with mod 12 multiplication, the generator is 2.

 

20=1, 21=2, 22=4, 23=8, 24=4, 25=8

 

Ring:

 

A group with two operations: addition and multiplication

 

The group is abelian with respect to addition: a+b=b+a

 

Multiplication and additions are both associative:

 

a+(b+c)=(a+b)+c

 

a.(b.c)=(a.b).c

 

Multiplication distributes over addition, a.(b+c)=a.b+a.c

 

Commutative Ring: Multiplication is commutative, i.e., a.b = b.a

 

Integral Domain: Multiplication operation has an identity and no zero divisors

 

Field:

 

An integral domain in which each element has a multiplicative inverse.

 


 

2 Modular Arithmetic

 

modular arithmetic is 'clock arithmetic'

 

a congruence a = b mod n says when divided by n that a and b have the same remainder o 100 = 34 mod 11

 

usually have 0<=b<=n-1

 

-12mod7 = -5mod7 = 2mod7 = 9mod7 o b is called the residue of a mod n

 

can do arithmetic with integers modulo n with all results between 0 and n

 

Addition

 

a+b mod n

 

Subtraction

 

a-b mod n = a+(-b) mod n

 

Multiplication

 

a.b mod n

 

derived from repeated addition

 

can get a.b=0 where neither a,b=0 o eg 2.5 mod 10

 

Division

 

a/b mod n

 

is multiplication by inverse of b: a/b = a.b-1 mod n

 

if n is prime b-1 mod n exists s.t b.b-1 = 1 mod n o eg 2.3=1 mod 5 hence 4/2=4.3=2 mod 5

 

integers modulo n with addition and multiplication form a commutative ring with the laws of

 

Associativity : (a+b)+c = a+(b+c) mod n

 

Commutativity : a+b = b+a mod n

 

Distributivity : (a+b).c = (a.c)+(b.c) mod n

 

 

also can chose whether to do an operation and then reduce modulo n, or reduce then do the operation, since reduction is a homomorphism from the ring of integers to the ring of integers modulo n

 

a+/-b mod n = [a mod n +/- b mod n] mod n o (the above laws also hold for multiplication)

 

if n is constrained to be a prime number p then this forms a Galois Field modulo p

 

denoted GF(p) and all the normal laws associated with integer arithmetic work

 

Greatest Common Divisor

 

the greatest common divisor (a,b) of a and b is the largest number that divides evenly into both a and b

 

Euclid's Algorithm is used to find the Greatest Common Divisor (GCD) of two numbers a and n, a<n

 

use fact if a and b have divisor d so does a-b, a-2b GCD (a,n) is given by:

 

let g0=n g1=a

 

gi+1 = gi-1 mod gi when gi=0 then (a,n) = gi-1

 

eg find (56,98) g0=98 g1=56

 

g2 = 98 mod 56 = 42

 

g3 = 56 mod 42 = 14

 

g4 = 42 mod 14 = 0 hence (56,98)=14

 

Finite Fields or Galois Fields

 

Finite Field: A field with finite number of elements

 

Also known as Galois Field

 

The number of elements is always a power of a prime number. Hence, denoted as GF(pn)

 

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

 

Can do addition, subtraction, multiplication, and division without leaving the field GF(p)

 

GF(2) = Mod 2 arithmetic GF(8) = Mod 8 arithmetic

There is no GF(6) since 6 is not a power of a prime

 

Polynomial Arithmetic

 

f(x) = anxn + an-1xn-1 + …+ a1x + a0 = Σ aixi

 

Ordinary polynomial arithmetic:

 

Add, subtract, multiply, divide polynomials,

 

Find remainders, quotient.

 

Some polynomials have no factors and are prime.

 

Polynomial arithmetic with mod p coefficients

 

Polynomial arithmetic with mod p coefficients and mod m(x) operations

 

Polynomial Arithmetic with Mod 2 Coefficients

 

All coefficients are 0 or 1, e.g.,

 

let f(x) = x3 + x2 and g(x) = x2 + x + 1 f(x) + g(x) = x3 + x + 1

 

f(x) x g(x) = x5 + x2

 

Polynomial Division: f(x) = q(x) g(x) + r(x)

 

can interpret r(x) as being a remainder

 

r(x) = f(x) mod g(x)

 

if 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 finite field

 

Can use Euclid‟s algorithm to find gcd and inverses.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Cryptography and Network Security : Finite Fields |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.