Hardware Security
Department of Computer Science and Engineering
Topic
Finite Field Architectures-1
Concepts Covered:
❑ Finite Fields or Galois Fields
❑ Characteristic-2 Finite Field Operations
❑ Karatsuba Multipliers
❑ Modulo Operation in GF(2)
Finite Fields
▪ A finite field is a field with a finite number of elements.
▪ The number of elements in the set is called the order of the field.
▪ A field with order m exists if m is a prime power, i.e m=pn for some integer n
and with p a prime integer.
▪ p is called the characteristic of the finite field.
Galois Fields
▪ GF(p): The elements of the fields can be represented by 0, 1, …, p-1
▪ However if p is not prime, then multiplications are not defined.
▪ However for finite fields GF(pn), with n>1, slightly complex representations are
used.
▪ Elements are represented as polynomials over GF(p).
Binary Finite Fields
▪ A finite field defines a finite set S and two
commutative operations ( ∙ , + ) in which
1. Two elements can be added, subtracted, multiplied
2. Any element can be divided by a non-zero element
3. Multiplication distributes over addition
▪ Binary Finite Fields: The set S consists
polynomials with coefficients in {0,1}
▪ Also known as Galois field
▪ Represented as GF(2m), where 2m is the number of
elements in S
▪ AES is constructed using binary finite fields
Polynomials over a field
A polynomial over a field F is an expression
of the form :
b( x) = bn −1 x n −1 + bn − 2 x n − 2 + ... + b0
x being called indeterminate of the polynomial,
and the bi F the coefficients.
The degree of a polynomial equals l if b j = 0, j >l ,
and l is the smallest number with this property.
The set of polynomials over a field F is denoted
by F[x]. The set of polynomials over a field F,
which has a degree less than l , is denoted by F[x]|l
Operations on Polynomials
▪ Addition:
c( x) = a( x) + b( x) ci = ai + bi ,0 i n
Addition is closed
0 (polynomial with all coefficients 0) is the identity element.
The inverse of an element can be found by replacing each
coefficient of the polynomial by its inverse in F.
F [ x]l , + forms an Abelian group
Example
Let F be the field in GF (2). Compute the sum
of the polynomials denoted by 57 and 83.
In binary, 57=01010111, and 83=10000011.
In polynomial notations we have,
(x 6 + x 4 + x 2 + x + 1) ( x 7 + x + 1)
= x 7 + x 6 + x 4 + x 2 + (1 1) x + (1 1)
= x7 + x6 + x4 + x2
The addition can be implemented with the bitwise XOR
instruction.
Multiplication
▪ Associative
▪ Commutative
▪ Distributive wrt. addition of polynomials.
In order to make the multiplication closed over F [ x] |l
we select a polynomial m(x) of degree l , called the
reduction polynomial.
The multiplication is then defined as follows:
c( x) = a( x).b( x) c( x) a( x) b( x) (mod m(x))
Hence, the structure <F [ x] |l , +,. is a commutative ring.
For special choices of the polynomial m(x), the structure
becomes a field.
Irreducible Polynomial
▪ A polynomial d(x) is irreducible over the field GF(p) iff there
exist no two polynomials a(x) and b(x) with coefficients in
GF(p) such that d(x)=a(x)b(x), where a(x) and b(x) are of
degree > 0.
Let F be the field GF(p). With suitable choice for the reduction
polynomial, the structure <F [ x] |n , +,. is a field with p n elements,
usually denoted by GF(p n ).
Example
Degree Irreducible
Polynomial
1 (x+1),x
2 (x2+x+1)
3 (x3+x2+1), (x3+x+1)
4 (x4+x3+x2+x+1),
(x4+x3+1),(x4+x+1)
Example of Multiplication
Compute the product of the elements 57 and 83 in GF(28 )
57=01010111, and 83=10000011.
In polynomial notations we have,
(x 6 + x 4 + x 2 + x + 1) ( x 7 + x + 1)
= ( x13 + x11 + x9 + x8 + x 7 ) ( x 7 + x 5 + x 3 + x 2 + x )
( x 6 + x 4 + x 2 + x + 1)
= x13 + x11 + x9 + x8 + x 6 + x5 + x 4 + x3 + 1
and,
( x13 + x11 + x9 + x8 + x 6 + x 5 + x 4 + x 3 + 1)
x 7 + x 6 + 1 (mod x8 + x 4 + x3 + x + 1)
Finite Field Multiplication
▪ Consider for example the field GF(24) with irreducible polynomial x4 + x + 1
▪ x5 + x + 1 is not in the field GF(24)
▪ So, modular reduction
(x5 + x + 1)mod(x4 + x + 1) = x2 + 1
Multiplication Algorithms
▪ The choice of multiplier is determined by the application.
▪ Montgomery for example is suited for low resource
environments.
▪ If designed properly, the Karatsuba multiplier is the fastest.
Squaring
Finite Field Multiplication
▪ There are several forms of : Karatsuba multiplier. We consider the combinational
type which requires just a single clock cycle.
▪ Two common types of combinational Karatsuba implementations.
▪ Simple Karatsuba Multiplier.
▪ General Karatsuba Multiplier.
Simple Karatsuba Multiplier
Recursive Simple Karatsuba Multiplier
General Karatsuba Multiplier
▪ Instead of splitting into two, splits into more than two.
▪ For example, an n bit multiplier is split into m different
multiplications.
A. Weimerskirch, Generalizations of the Karatsuba Algorithm for Efficient Implementations, Cryptology ePrint
Archive, 2006
Comparing the General and Simple
Hybrid Karatsuba Multiplier
◦ For all recursions less than 29
use the General Karatsuba
Multiplier or school book.
◦ For all recursions greater than
29 use the Simple Karatsuba
multiplier
C. Rebeiro, Power Attack Resistant Efficient FPGA Architecture for Karatsuba Multiplier , VLSID 2008
Conclusion:
Finite Field Theory is central to cryptographic algorithms.
Understanding Finite Fields is crucial to develop efficient
architectures for cryptographic algorithms.
Binary Finite Fields offer efficient designs.
