Cryptography Reference
In-Depth Information
the other hand, the arithmetic in prime fields is typically more difficult to implement
efficiently, due in part to the propagation of carry bits. Nonetheless, prime fields are
usually preferred due to better hardware support on embedded processors.
Most of the low-end CPUs support multiplication of word-size integers in hardware.
This feature significantly accelerates multiprecision multiplication in F p . Arithmetic
on binary fields is not natively supported in the Instruction Set of typical embedded
processors. None of the CPUs used in sensor networks support multiplication in the
binary field. Therefore, efficient implementation of polynomial multiplication remains
a challenging task. The elements of a finite field F 2 m can be represented by binary
polynomials of degrees less than m , where m is a prime number. For security reasons,
ECC systems are defined over finite fields where m is usually greater than 160 bits. In
software, the coefficients of a binary polynomial may be stored in an array of tW -bit
words. The s = tW-m highest order bits in the last word of the array remain unused
(always set to 0).
The addition of field elements is performed bitwise and is very fast, requiring only
word operations (XORs), which are supported by all computer architectures. Addition
in the binary field is analogous to multiprecision integer addition, without the carries.
Other arithmetic operations (beside multiplication) include inversion, squaring, reduc-
tion, and calculation of square roots.
9.8.2.1 Binary Polynomial Multiplication
The simplest way to perform polynomial multiplication is to use basic schoolbook
multiplication. This method for two polynomials p ( z ) and q ( z ) of degree m- 1 is illus-
trated in Figure 9.7.
The algorithm requires m- 1 left shifts of p ( z ) and a modulo 2 addition of p ( z ) to
the accumulator for every non-zero coefficient of q ( z ). This “shift-and-add” method
Figure 9.7. Binary Polynomial Multiplication Using the Basic Schoolbook Method
Search WWH ::




Custom Search